Skip to content

Instantly share code, notes, and snippets.

@blackakula
Created October 2, 2019 18:26
Show Gist options
  • Save blackakula/c1e1a03bb6b4a612b6181cc0a095ef18 to your computer and use it in GitHub Desktop.
Save blackakula/c1e1a03bb6b4a612b6181cc0a095ef18 to your computer and use it in GitHub Desktop.
Meetup maze
const Maze = ` ############################
# # # # #
# #### # #### # # #### #
# # # # #
####### ########## ##########
# # # # # # # #
# # # # #### # # #### #
# # # #
# # # #### #### #### ####
# # # # # # # #
# #### # #### # # #### #
# # # # # # # #
#### # ####### ####### # #
# # # # # #
# ####### ####### # # # #
# # # # #
# #### #### #### #### ####
# # # # # # #`;
const startPoint = {x: 7, y: 6};
const mazeArray = Maze.split("\n").map(row => row.split(''));
enum Move {
U = 'Up',
D = 'Down',
L = 'Left',
R = 'Right',
}
const step = (x: number, y: number, move: Move) => move === Move.U
? {x, y: y-1}
: (move === Move.D
? {x, y: y+1}
: (move === Move.L
? {x: x-1, y}
: {x: x+1, y}
)
)
type Path = Move[]
const wall = ({x, y}: {x: number, y: number}) => mazeArray[y][x] === '#';
interface Cell {
x: number,
y: number,
length: number,
path: Path,
}
const isExit = (cell: Cell) => cell.x === 0 || cell.y === 0 || cell.x === mazeArray[0].length - 1 || cell.y === mazeArray.length - 1;
const key = ({x, y}: {x: number, y: number}) => `${x},${y}`;
const startPointKey = key(startPoint);
let lastCells: {[key: string]: Cell} = {
[startPointKey]: {...startPoint, length: 0, path: []}
}
let hash: {[key: string]: Cell} = {...lastCells};
let moves = 0;
let found = isExit(lastCells[startPointKey]);
let exit: Cell = undefined;
while (!found) {
let newLast = {};
Object.keys(lastCells).map(cellKey => {
const lastCell = lastCells[cellKey];
[Move.U, Move.D, Move.L, Move.R].map(move => {
const newCoords = step(lastCell.x, lastCell.y, move);
const keyNewCoords = key(newCoords);
if (!wall(newCoords) && !hash.hasOwnProperty(keyNewCoords)) {
const newCell = {...newCoords, length: lastCell.length + 1, path: [...lastCell.path, move]};
newLast[keyNewCoords] = newCell;
hash[keyNewCoords] = newCell;
}
})
});
console.log(JSON.stringify(newLast))
if (Object.keys(newLast).length === 0) {
break;
}
const check = Object.keys(newLast).reduce((result, cellKey) => result.found ? result : {found: isExit(newLast[cellKey]), cell: newLast[cellKey]}, {found: false, cell: undefined});
found = check.found;
if (found) exit = check.cell;
lastCells = newLast;
}
if (exit === undefined) {
console.log('Path not found');
} else {
console.log(exit.path);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment