daily pastebin goal
72%
SHARE
TWEET

http://aichallenges.appspot.com/fifteen solution

vbuterin Jan 9th, 2012 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. var sym = "0123456789abcdefghijklmnopqrstuvwxyz";
  2. var heuristic = function(state) {
  3.   var h = 0;
  4.   var size = Math.sqrt(state.str.length);
  5.   for (var x = 0; x < size; x++) {
  6.     for (var y = 0; y < size; y++) {
  7.       var val = sym.indexOf(state.str.charAt(x + y * size));
  8.       var fx = val % size;
  9.       var fy = Math.floor(val / size);
  10.       if (val > 0) h += Math.abs(fx-x) + Math.abs(fy-y);
  11.     }
  12.   }
  13.   return h;
  14. }
  15. var move = function(state,dir) {
  16.     var input = state.str;
  17.     var moves = state.moves.concat(dir);
  18.     var place = input.indexOf('0');
  19.     var size = Math.sqrt(input.length);
  20.     var px = place % size;
  21.     var py = Math.floor(place / size);
  22.     var newx = px + [0,1,0,-1][dir];
  23.     var newy = py + [-1,0,1,0][dir];
  24.     if (newx < 0 || newy < 0 || newx >= size || newy >= size) return {'str':input,'moves':moves};
  25.     var newplace = newy * size + newx;
  26.     var output = input.replace('0',input[newplace])
  27.     output = output.substr(0,newplace) + '0' + output.substr(newplace + 1);
  28.     return {'str':output,'moves':moves};
  29. }
  30. var snapshot = function(list) {
  31.   var s = "";
  32.   for (var i = 0; i < list.length; i++) {
  33.     s += list[i].str + " (" + heuristic(list[i]) + "); ";
  34.   }
  35.   return s;
  36. }
  37. var frontier = [];
  38. var explored = [];
  39. var binsearch = function(val) {
  40.     var min = 0;
  41.     var max = frontier.length - 1;
  42.     while (max - min > 1) {
  43.       var ave = Math.floor((max + min) * 0.5);
  44.       if (heuristic(frontier[ave]) > val) min = ave;
  45.       else max = ave;
  46.     }
  47.     if (frontier.length == 0) return 0;
  48.     else if (val > heuristic(frontier[min])) return min;
  49.     else if (val > heuristic(frontier[max])) return max;
  50.     else return max + 1;
  51. }
  52. var unexplored = function(state) {
  53.   for (var i = 0; i < explored.length; i++) {
  54.     if (state.str == explored[i].str) return false;
  55.   }
  56.   return true;
  57. }
  58. this.run = function(map) {
  59.   var count = 0;
  60.   explored = [];
  61.   frontier = [{'str':map,'moves':[]}];
  62.   //var least = 99999;
  63.   while (frontier.length > 0) {
  64.     last = frontier.pop();
  65.     if (unexplored(last)) {
  66.       explored.push(last);
  67.       if (last.str == sym.substring(0,last.str.length))
  68.         return last.moves;
  69.       for (var dir = 0; dir < 4; dir++) {
  70.         var newstate = move(last,dir);
  71.         var heur = heuristic(newstate);
  72.         var place = binsearch(heur);
  73.         //Pruning
  74.         for (var p = frontier.length - 1; p >= 0; p--) {
  75.           if (newstate.str == frontier[p].str) {
  76.             frontier = frontier.slice(0,p).concat(
  77.               frontier.slice(p+1));
  78.             break;
  79.           }
  80.         }
  81.         frontier = frontier.slice(0,place).concat(newstate,
  82.           frontier.slice(place));
  83.       }
  84.     }
  85.   }
  86. }
RAW Paste Data
Top