• API
• FAQ
• Tools
• Trends
• Archive
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