Skip to content

Instantly share code, notes, and snippets.

@wtfaremyinitials
Created June 5, 2014 00:35
Show Gist options
  • Save wtfaremyinitials/6238b2840244290977ec to your computer and use it in GitHub Desktop.
Save wtfaremyinitials/6238b2840244290977ec to your computer and use it in GitHub Desktop.
Maze solver in NodeJS for /r/dailyprogrammer challenge
// My solution to this /r/dailyprogrammer challenge on reddit (http://redd.it/278ptv)
process.stdin.resume();
process.stdin.setEncoding('utf8');
var width = 0;
var height = 0;
var maze = [];
function getStartPoint() {
for(var x = 0; x < maze.length; x++) {
for(var y = 0; y < maze[x].length; y++) {
if(maze[x][y] == 'S') {
return {x: x, y: y};
}
}
}
}
function getSurrounding(tile) {
return [
{x: tile.x + 1, y: tile.y},
{x: tile.x - 1, y: tile.y},
{x: tile.x, y: tile.y + 1},
{x: tile.x, y: tile.y - 1}
];
}
var tried = [];
function find(tiles) {
var tile = tiles[tiles.length - 1];
if(tried.indexOf(tile.x + ':' + tile.y) != -1)
return false;
tried.push(tile.x + ':' + tile.y);
if(maze[tile.x][tile.y] == 'E')
return tiles;
if(maze[tile.x][tile.y] == '#')
return false;
var surrounding = getSurrounding(tile);
for(var i = 0; i < surrounding.length; i++) {
var newTiles = tiles.slice(0);
newTiles.push(surrounding[i]);
var result = find(newTiles);
if(result)
return result;
}
return false;
}
function solve() {
var steps = find([getStartPoint()]);
for(var i = 1; i < steps.length-1; i++)
maze[steps[i].x][steps[i].y] = '*';
for(var i = 0; i < maze.length; i++) {
var line = maze[i].join('');
line = line.substring(0, line.length - 1);
console.log(line);
}
}
process.stdin.on('data', function (chunk) {
if(!width && !height) {
var dimensions = chunk.split(" ");
width = parseInt(dimensions[0]);
height = parseInt(dimensions[1]);
return;
}
if(maze.length != height) {
maze.push(chunk.split(''));
return;
}
solve();
process.stdin.pause();
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment