helltaker.ts

enum Block {
    Wall = 'w',
    Empty = ' ',
    Door = 'd',
    Key = 'k',
    Rock = 'r'
}

interface BoardState {
    x: number;
    y: number;
    hasKey: boolean;
    board: Block[][];
    moves: number;
    history: string;
}

const initial: BoardState = {
    x: 1, y: 5, board: [
        'www   www',
        'wwwrdrwww',
        'wrwr  w w',
        'r  rrr  k',
        ' rrr  rr ',
        'w  r  r w'
    ].map(line => line.split('')) as Block[][],
    hasKey: false,
    moves: 33,
    history: ''
};

function toString(state: BoardState): string {
    const lines: string[][] = clone(state).board;
    lines[state.y][state.x] = '*';
    return `${lines.map(l => l.join('')).join('\n')}\n${state.hasKey ? 'Key' : ''}`;
}
// function equals(a: BoardState, b: BoardState): boolean {
//  if (a.x !== b.x || a.y !== b.y) return false;
//  if (a.hasKey !== b.hasKey) return false;
//  for (let i = 0; i < a.board.length; i++) {
//      for (let j = 0; j < a.board[i].length; j++) {
//          if (a.board[i][j] !== b.board[i][j]) return false;
//      }
//  }
//  return true;
// }

function clone(state: BoardState): BoardState {
    return JSON.parse(JSON.stringify(state));
}

function getBlock({ board, x, y }: BoardState, delta: [number, number]): Block {
    let newX = x + delta[0];
    let newY = y + delta[1];
    if (newY < 0 || newY >= board.length) return Block.Wall;
    if (newX < 0 || newX >= board[y].length) return Block.Wall;
    return board[newY][newX];
}
function setBlock({ board, x, y }: BoardState, delta: [number, number], target: Block): void {
    let newX = x + delta[0];
    let newY = y + delta[1];
    if (newY < 0 || newY >= board.length) return;
    if (newX < 0 || newX >= board[y].length) return;
    board[newY][newX] = target;
}

const directions: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const dirIds = ['<', '>', '^', 'v'];

function getMoves(prevState: BoardState): BoardState[] {
    if (prevState.moves === 0) return [];
    const { x, y, board } = prevState;

    const nextStates: BoardState[] = [];

    for (let i = 0; i < 4; i++) {
        const dir = directions[i];
        const target = getBlock(prevState, dir);
        if (target === Block.Wall) continue;
        if (target === Block.Door && !prevState.hasKey) continue;

        const nextState = clone(prevState);
        nextState.moves--;

        if (target === Block.Rock) {
            const otherSide = getBlock(prevState, [dir[0] * 2, dir[1] * 2]);
            if (otherSide !== Block.Empty) continue;
            setBlock(nextState, [dir[0] * 2, dir[1] * 2], Block.Rock);
            setBlock(nextState, dir, Block.Empty);
        } else if (target === Block.Key) {
            setBlock(nextState, dir, Block.Empty);
            nextState.x += dir[0];
            nextState.y += dir[1];
            nextState.hasKey = true;
        } else if (target === Block.Empty || target === Block.Door) {
            nextState.x += dir[0];
            nextState.y += dir[1];
        }
        nextState.history += dirIds[i];
        nextStates.push(nextState);
    }
    return nextStates;
}

const discovered = new Set<string>();
const Q: BoardState[] = [];
discovered.add(toString(initial));
Q.push(initial);
console.time("SOLVED");
let minMoves = initial.moves;
while (Q.length > 0) {
    const v = Q.shift();
    if (v.moves < minMoves) {
        minMoves = v.moves;
        console.log(v.moves);
    }
    if (v.x === 4 && v.y === 0) {
        console.log(toString(v));
        console.log(v.history, v.moves);
        console.timeEnd("SOLVED");
        process.exit(0);
    }
    const adj = getMoves(v);
    for (const w of adj) {
        const str = toString(w);
        if (!discovered.has(str)) {
            discovered.add(str);
            Q.push(w);
        }
    }
}