Skip to content

Instantly share code, notes, and snippets.

@Deraen
Last active December 26, 2015 01:49
Show Gist options
  • Save Deraen/7073508 to your computer and use it in GitHub Desktop.
Save Deraen/7073508 to your computer and use it in GitHub Desktop.
Using A* to find how to sort array using given operations with least operations
node_modules
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');
};
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]));
});
});
*/
{
"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"
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment