index.js (4227B)
1 const fs = require('fs'); 2 const through = require('through2'); 3 const line_for_line = require('../common/line-for-line'); 4 5 String.prototype.startsWith = function(subject) { 6 return this.substr(0, subject.length) === subject; 7 }; 8 9 const grid = []; 10 let dst = [0,0]; 11 let src = [0,0]; 12 const x = 0; 13 const y = 1; 14 15 function h(start, goal) { 16 return Math.abs(start[x] - goal[x]) + Math.abs(start[y] - goal[y]); 17 }; 18 19 function reconstruct_path(map, goal, start) { 20 const charmap = new Array(map.length).fill(0).map(() => new Array(map[0].length).fill('.')); 21 charmap[goal[y]][goal[x]] = 'E'; 22 23 let current = [...goal]; 24 let steps = 0; 25 while(map[current[y]][current[x]]) { 26 const previous = map[current[y]][current[x]]; 27 // update graphic 28 if (previous[x] < current[x]) charmap[previous[y]][previous[x]] = '>'; 29 if (previous[x] > current[x]) charmap[previous[y]][previous[x]] = '<'; 30 if (previous[y] < current[y]) charmap[previous[y]][previous[x]] = 'v'; 31 if (previous[y] > current[y]) charmap[previous[y]][previous[x]] = '^'; 32 33 current = previous; 34 steps++; 35 } 36 37 process.stdout.write( 38 charmap 39 .map(l => l.join('')) 40 .join('\n') 41 + '\n\n' 42 ); 43 44 return steps; 45 } 46 47 function A_star(grid, src, dst) { 48 const openSet = [src]; 49 const cameFrom = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(false)); 50 const fScore = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(Infinity)); 51 const gScore = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(Infinity)); 52 fScore[src[y]][src[x]] = h(src, dst); 53 gScore[src[y]][src[x]] = 0; 54 55 while(openSet.length) { 56 57 // node = the openSet entry with lowest fScore 58 let current = [-1,-1]; 59 let currentScore = Infinity; 60 for(let test of openSet) { 61 if (fScore[test[y]][test[x]] < currentScore) { 62 currentScore = fScore[test[y]][test[x]]; 63 current = test; 64 } 65 } 66 67 // if current = goal -> reconstruct_path 68 if ((current[x] == dst[x]) && (current[y] == dst[y])) { 69 return reconstruct_path(cameFrom, current, src); 70 } 71 72 // openSet.Remove(current) 73 openSet.splice(openSet.indexOf(current), 1); 74 75 const neighbours = [ 76 [current[x] - 1, current[y] ], 77 [current[x] , current[y] - 1], 78 [current[x] + 1, current[y] ], 79 [current[x] , current[y] + 1], 80 ].filter(pos => { 81 // Filter out-of-grid possible neighbours 82 if (pos[x] < 0) return false; 83 if (pos[y] < 0) return false; 84 if (pos[x] >= grid[0].length) return false; 85 if (pos[y] >= grid.length) return false; 86 // Filter obstacles 87 if (grid[pos[y]][pos[x]] - grid[current[y]][current[x]] > 1) { 88 return false; 89 } 90 return true; 91 }); 92 93 for(const neighbour of neighbours) { 94 const tentative_score = gScore[current[y]][current[x]] + 1; 95 if (tentative_score < gScore[neighbour[y]][neighbour[x]]) { 96 // This path to the neighbour is better than the previous one 97 cameFrom[neighbour[y]][neighbour[x]] = current; 98 gScore[neighbour[y]][neighbour[x]] = tentative_score; 99 fScore[neighbour[y]][neighbour[x]] = tentative_score + h(neighbour, dst); 100 openSet.push(neighbour); 101 } 102 } 103 } 104 105 return -1; 106 } 107 108 fs.createReadStream('input') 109 .pipe(line_for_line()) 110 111 // Turn into paragraphs 112 .pipe(through(function(line, enc, cb) { 113 line = line.toString(); 114 115 const elevations = line 116 .split('') 117 .map((char,i) => { 118 if (char == 'S') { 119 src = [i, grid.length]; 120 char = 'a'; 121 } 122 if (char == 'E') { 123 dst = [i, grid.length]; 124 char = 'z'; 125 } 126 return char.charCodeAt(0) - 97; 127 }); 128 grid.push(elevations); 129 cb(); 130 })) 131 132 .on('finish', () => { 133 const phase_1 = A_star(grid, src, dst); 134 135 let phase_2 = Infinity; 136 for(let i=0; i<grid.length; i++) { 137 for(let j=0; j<grid[i].length; j++) { 138 if (grid[i][j]) continue; 139 const steps = A_star(grid, [j,i], dst); 140 if (steps < 0) continue; 141 if (steps < phase_2) phase_2 = steps; 142 } 143 } 144 145 console.log({ phase_1, phase_2 }); 146 147 148 149 });