Aideen's Code for Kahu's 9402

//Author: aideen.org
//Date: 3/23/2015

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;

int N;
typedef vector<char> V;

const int H = 3281533; //668273;

struct hashF {
  size_t operator()(const V& x) const {
    int ret = 0;
    for (int i=0; i<N; i++) ret = (ret * 10 + x[i]);
    return ret % H;
  }
};

struct eqV
{
  bool operator()(const V &v1, const V &v2) const
  {
    return v1 == v2;
  }
};

unordered_map<V, pair<char, V>, hashF, eqV > mhash;

V start, goal;

#define showrow(r) for(int xxx=0;xxx<r.size();xxx++)cerr<<1+r[xxx]<<",";cerr<<endl;

int V2int(V v) {
  int ret = 0;
  for (int i=0; i<N; i++) {
    ret = ret * 10 + v[i];
  }
  return ret;
}

void BFS(const V &start) {
  cerr << "starting..." << endl;
  vector<V> q;
  q.push_back(start);
  mhash[start] = make_pair(1, V(0));

  V b;
  char x;
  for (int ql = 0; ql<q.size(); ql++) {
    V current = q[ql];
    for (char i=0; i<N; i++) {
      for (char j=i+1; j<=N; j++) { // [i, i+1, ..., j) is cut and moved forward to after [k]
    for (char k=j; k<N; k++) {
      b = current;
      for (x=j; x<=k; x++)  b[i + (x - j)] = current[x];
      for (x=i; x<j; x++)   b[i + (k - j + 1) + (x - i)] = current[x];

      if (mhash[b].first != 0) { continue; }
      q.push_back(b);
      mhash[b] = make_pair(mhash[current].first + 1, current);

      if (b == goal) {
        cerr << "yeaaah! after " << q.size() << " nodes " << endl;
        return;
      }
    }
      }
    }
  }
}

int main(int argc, char **argv) {
  N = atoi(argv[1]);

  for (int i=0; i<N; i++) goal.push_back(i), start.push_back(N-1-i);

  BFS(start);

  cout << int(mhash[goal].first-1) << endl;

  for (V cur = goal; cur.size(); cur = mhash[cur].second) {
    showrow(cur);
  }

  return 0;
}