Using A* to find how to sort array using given operations with least operations

.gitignore

node_modules

README.md

Foo

Gruntfile.js

module.exports = function(grunt) {
  require('matchdep').filterDev('grunt-*').forEach(grunt.loadNpmTasks);

  grunt.initConfig({
    watch: {
      test: {
        files: ['index.js'],
        tasks: ['mochaTest'],
        options: {
          atBegin: true,
        }
      },
    },
    mochaTest: {
      options: {
        reporter: 'spec',
      },
      test: {
        src: ['index.js'],
      },
    }
  });

  grunt.registerTask('default', 'watch');
};

index.js

function arraysEqual(a, b) {
  if (a === b) return true;
  if (a === null || b === null) return false;
  if (a.length != b.length) return true;
  for (var c = 0; c < a.length; ++c) {
    if (a[c] != b[c]) return false;
  }
  return true;
}

function emptyObj(obj) {
  for (var k in obj) {
    if (obj.hasOwnProperty(k)) return false;
  }
  return true;
}

function restack(input) {
  var goal = input.slice(0).sort(function(a, b) { return a - b; });
  var cmds = astar(input, goal);

  cmds.forEach(function(cmd) {
    console.log('cmd', cmd.join(' '));
  });

  return cmds;
}

function exec(arr, cmd) {
  var a = cmd[1];
  var b = cmd[2];
  var aI = arr.indexOf(a);

  arr.splice(aI, 1);

  var bI = arr.indexOf(b);

  if (cmd[0] === 'a') {
    // a Above b
    arr.splice(bI, 0, a);
  } else if (cmd[0] === 'b') {
    // a Below b
    arr.splice(bI + 1, 0, a);
  }

  return arr;
}

function score(array) {
  var sum = 0;

  var prev = null;
  var s;
  for (var i = 0; i < array.length; ++i) {
    s = Math.abs(i - array[i]);
    if (array[i] <= prev) {
      s *= 2;
    }
    sum += s;
    prev = array[i];
  }

  return sum;
}

function buildPath(data, state) {
  var cmds = [];

  while(data.hasOwnProperty(state) && data[state].prev) {
    cmds.push(data[state].cmd);
    state = data[state].prev;
  }

  return cmds.reverse();
}

function astar(start, goal) {
  // {'0,1,2': true}
  var closed = {};
  // {'0,1,2': [0,1,2]}
  var open = {};
  open[start] = start;

  var data = {};
  data[start] = {
    dist: 0,
    score: score(start),
    // prev: previous state
    // cmd:
  };

  while (!emptyObj(open)) {
    var best = null;
    for (var key in open) {
      if (best === null || data[key].score < data[best].score) {
        best = key;
      }
    }
    var current = open[best]; // select one with best score

    // console.log('current: ' + current + ', from: ' + (data[current].prev || '-') +
    //             ' (' + (data[current].cmd || '-') + '), dist: ' + data[current].dist +
    //             ', score: ' + data[current].score);

    if (arraysEqual(current, goal)) {
      return buildPath(data, current);
    }
    delete open[current];
    closed[current] = true;

    for (var a = 0; a < current.length; ++a) {
      for (var b = 0; b < current.length; ++b) {
        if (a === b) continue;

        // Above, below
        for (var c = 0; c < 2; ++c) {
          var dist = data[current].dist + 1;

          var cmd = [['a','b'][c], a, b];

          var next = current.slice(0);
          exec(next, cmd);
          if (arraysEqual(current, next)) continue;

          var s = dist + score(next);
          // console.log('adding? neighbor: ' + cmd + ' -> ' + next + ', dist: ' + dist +', score: ' + s);

          if (closed.hasOwnProperty(next) && s >= data[next].score) {
            continue;
          }

          if (!open.hasOwnProperty(next) || s < data[next].score) {
            data[next] = {
              cmd: cmd,
              prev: current,
              dist: dist,
              score: s,
            };
            if (!open.hasOwnProperty(open, next)) {
              open[next] = next;
            }
          }
        }
      }
    }
  }
}

/*
var chai = require('chai');
chai.should();

describe('cmds', function() {
  it('[2,1,0], 1 above 2 -> [1,2,0]', function() {
    exec([2,1,0], ['a', 1, 2]).should.deep.equal([1,2,0]);
  });

  it('[1,2,0], 0 below 1 -> [1,0,2]', function() {
    exec([1,2,0], ['b', 0, 1]).should.deep.equal([1,0,2]);
  });

  it('[2,1,0], 0 above 2 -> [0,2,1]', function() {
    exec([2,1,0], ['a', 0, 2]).should.deep.equal([0,2,1]);
  });

  it('[0,1,2], 0 above 1 (already true)', function() {
    exec([0,1,2], ['a', 0, 1]).should.deep.equal([0,1,2]);
  });

  it('[0,1,2], 1 below 0 (already true)', function() {
    exec([0,1,2], ['b', 1, 0]).should.deep.equal([0,1,2]);
  });
});

describe('restack', function() {
  it('[1,2,0]', function() {
    restack([1,2,0]).length.should.be.at.most(1);
  });

  it('[2,1,0]', function() {
    restack([2,1,0]).length.should.be.at.most(2);
  });

  it('[3,2,1,0]', function() {
    restack([3, 2, 1, 0]).length.should.be.at.most(3);
  });

  it('big', function() {
    var cmds = restack([6, 8, 0, 4, 3, 10, 2, 9, 1, 5, 7]);

    cmds.length.should.be.at.most(7);
  });
});

describe('score', function() {
  it('[0,1,2,3] < [1,0,2,3]', function() {
    score([0,1,2,3]).should.be.below(score([1,0,2,3]));
  });

  it('[2,1,0] > [0,1,2]', function() {
    score([2,1,0]).should.be.above(score([0,1,2]));
  });

  xit('[0,1,3,2] = [1,2,3,0]', function() {
    score([0,1,3,2]).should.be.equal(score([1,2,3,0]));
  });
});
*/

package.json

{
  "name": "aaaaaaaa",
  "version": "0.0.0",
  "main": "index.js",
  "devDependencies": {
    "chai": "~1.8.1",
    "matchdep": "~0.3.0",
    "grunt": "~0.4.1",
    "grunt-contrib-watch": "~0.5.3",
    "grunt-mocha-test": "~0.7.0"
  }
}