Meetup maze

maze-escaper.ts

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);
}