Zelda Ice Puzzle

README.md

Zelda Ice Puzzle

view on jsgist

index.css

/*bug-in-github-api-content-can-not-be-empty*/

index.html

/*bug-in-github-api-content-can-not-be-empty*/

index.js

const level = [
  '          ', // 0
  '          ', // 1
  '          ', // 2
  '         o', // 3
  '          ', // 4
  '          ', // 5
  '          ', // 6
  '          ', // 7
  '    o     ', // 8
  '        o ', // 9
];
const target = [5, 8]
const block = [1, 3]

const directions = {
  r: [1, 0],
  l: [-1, 0],
  u: [0, -1],
  d: [0, 1],
};

const isBlocked = (level, position) => {
  const [x, y] = position;
  return x < 0 || y < 0 || x >= level.length || y >= level.length || level[y][x] === 'o';
};

const canPush = (level, position, offset) => {
  return !isBlocked(level, [position[0] - offset[0], position[1] - offset[1]]);
};

const pushInDirection = (level, position, offset) => {
  let [x, y] = position;
  let [dx, dy] = offset;
  for (;;) {
    let newX = x + dx;
    let newY = y + dy;
    if (isBlocked(level, [newX, newY])) {
      return [x, y];
    }
    x = newX;
    y = newY;
  }
};

const isSamePosition = (a, b) => a[0] === b[0] && a[1] === b[1];

function findSolution(level, block, target) {
  const queue = [{position: block, path: []}];
  const visited = new Set();

  while (queue.length > 0) {
    const { position, path } = queue.shift();

    // try each direction
    for (const [direction, offset] of Object.entries(directions)) {
      if (canPush(level, position, offset)) {
        const newPath = path.concat(direction);
        const newPosition = pushInDirection(level, position, offset);
        if (isSamePosition(newPosition, target)) {
          return newPath;
        }
        const key = `${newPosition[0]},${newPosition[1]}`;
        if (!isSamePosition(newPosition, position) && !visited.has(key)) {
          visited.add(key);
          queue.push({ position: newPosition, path: newPath });
        }
      }
    }
  }
  return undefined;
}

console.log('solution:', findSolution(level, block, target))

jsGist.json

{"name":"Zelda Ice Puzzle ","settings":{},"filenames":["index.html","index.css","index.js"]}