epicbob57

helltaker.ts

May 12th, 2021 (edited)
443
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. enum Block {
  3.     Wall = 'w',
  4.     Empty = ' ',
  5.     Door = 'd',
  6.     Key = 'k',
  7.     Rock = 'r'
  8. }
  9.  
  10. interface BoardState {
  11.     x: number;
  12.     y: number;
  13.     hasKey: boolean;
  14.     board: Block[][];
  15.     moves: number;
  16.     history: string;
  17. }
  18.  
  19. const initial: BoardState = {
  20.     x: 1, y: 5, board: [
  21.         'www   www',
  22.         'wwwrdrwww',
  23.         'wrwr  w w',
  24.         'r  rrr  k',
  25.         ' rrr  rr ',
  26.         'w  r  r w'
  27.     ].map(line => line.split('')) as Block[][],
  28.     hasKey: false,
  29.     moves: 33,
  30.     history: ''
  31. };
  32.  
  33. function toString(state: BoardState): string {
  34.     const lines: string[][] = clone(state).board;
  35.     lines[state.y][state.x] = '*';
  36.     return `${lines.map(l => l.join('')).join('\n')}\n${state.hasKey ? 'Key' : ''}`;
  37. }
  38. // function equals(a: BoardState, b: BoardState): boolean {
  39. //  if (a.x !== b.x || a.y !== b.y) return false;
  40. //  if (a.hasKey !== b.hasKey) return false;
  41. //  for (let i = 0; i < a.board.length; i++) {
  42. //      for (let j = 0; j < a.board[i].length; j++) {
  43. //          if (a.board[i][j] !== b.board[i][j]) return false;
  44. //      }
  45. //  }
  46. //  return true;
  47. // }
  48.  
  49. function clone(state: BoardState): BoardState {
  50.     return JSON.parse(JSON.stringify(state));
  51. }
  52.  
  53. function getBlock({ board, x, y }: BoardState, delta: [number, number]): Block {
  54.     let newX = x + delta[0];
  55.     let newY = y + delta[1];
  56.     if (newY < 0 || newY >= board.length) return Block.Wall;
  57.     if (newX < 0 || newX >= board[y].length) return Block.Wall;
  58.     return board[newY][newX];
  59. }
  60. function setBlock({ board, x, y }: BoardState, delta: [number, number], target: Block): void {
  61.     let newX = x + delta[0];
  62.     let newY = y + delta[1];
  63.     if (newY < 0 || newY >= board.length) return;
  64.     if (newX < 0 || newX >= board[y].length) return;
  65.     board[newY][newX] = target;
  66. }
  67.  
  68. const directions: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  69. const dirIds = ['<', '>', '^', 'v'];
  70.  
  71. function getMoves(prevState: BoardState): BoardState[] {
  72.     if (prevState.moves === 0) return [];
  73.     const { x, y, board } = prevState;
  74.  
  75.     const nextStates: BoardState[] = [];
  76.  
  77.     for (let i = 0; i < 4; i++) {
  78.         const dir = directions[i];
  79.         const target = getBlock(prevState, dir);
  80.         if (target === Block.Wall) continue;
  81.         if (target === Block.Door && !prevState.hasKey) continue;
  82.  
  83.         const nextState = clone(prevState);
  84.         nextState.moves--;
  85.  
  86.         if (target === Block.Rock) {
  87.             const otherSide = getBlock(prevState, [dir[0] * 2, dir[1] * 2]);
  88.             if (otherSide !== Block.Empty) continue;
  89.             setBlock(nextState, [dir[0] * 2, dir[1] * 2], Block.Rock);
  90.             setBlock(nextState, dir, Block.Empty);
  91.         } else if (target === Block.Key) {
  92.             setBlock(nextState, dir, Block.Empty);
  93.             nextState.x += dir[0];
  94.             nextState.y += dir[1];
  95.             nextState.hasKey = true;
  96.         } else if (target === Block.Empty || target === Block.Door) {
  97.             nextState.x += dir[0];
  98.             nextState.y += dir[1];
  99.         }
  100.         nextState.history += dirIds[i];
  101.         nextStates.push(nextState);
  102.     }
  103.     return nextStates;
  104. }
  105.  
  106. const discovered = new Set<string>();
  107. const Q: BoardState[] = [];
  108. discovered.add(toString(initial));
  109. Q.push(initial);
  110. console.time("SOLVED");
  111. let minMoves = initial.moves;
  112. while (Q.length > 0) {
  113.     const v = Q.shift();
  114.     if (v.moves < minMoves) {
  115.         minMoves = v.moves;
  116.         console.log(v.moves);
  117.     }
  118.     if (v.x === 4 && v.y === 0) {
  119.         console.log(toString(v));
  120.         console.log(v.history, v.moves);
  121.         console.timeEnd("SOLVED");
  122.         process.exit(0);
  123.     }
  124.     const adj = getMoves(v);
  125.     for (const w of adj) {
  126.         const str = toString(w);
  127.         if (!discovered.has(str)) {
  128.             discovered.add(str);
  129.             Q.push(w);
  130.         }
  131.     }
  132. }
RAW Paste Data