dev.to staff

Posted on Nov 4, 2019

Daily Challenge #107 - Escape the Mines

#challenge

A poor miner is trapped in a mine and you have to help him to get out! The mine is completely dark so you have to tell him where to go.

Implement a method solve(cave_map, miner, exit) that has to return the path the miner must take to reach the exit as an array of moves: ['up', 'down', 'right', 'left']. Those are the only four possible moves as the miner cannot move diagonally.

cave_map is a 2-dimensional array of Boolean values, representing squares. false for walls, true for open space. It will never be larger than 5 x 5. It is laid out as an array of columns. All columns will always be the same size, though not necessarily the same size as rows (in other words, maps can be rectangular). The map will never contain any loop, so there will always be only one possible path. The map may contain dead-ends though.

miner is the position of the miner at the start, as an object made of two zero-based integer properties, x and y. For example (0,0) would be the top-left corner.

exit is the position of the exit, in the same format as miner.

Note that the miner can't go outside the map, as it is a tunnel.

Let's take a pretty basic example :

cave_map = [[true, false],
    [true, true]];
solve(cave_map, (0,0), (1,1));
// Should return ['right', 'down']

Challenge maps:
A simple map. (2x2)
cave_map = [[true, false], [true, true]]; miner = (0,0) exit = (1,0)

A linear map. (1x4)
cave_map = [[true], [true], [true], [true]]; miner = (0,0) exit = (3,0)

Walk around an obstacle (3x3)
cave_map = [[true, true, true], [false, false, true], [true, true, true]]; miner = (0,0) exit = (2,0)

Change directions several times (5x5)
cave_map = [[true, true, false, false, false], [false, true, true, false, false], [false, false, true, true, false], [false, false, false, true, true], [false, false, false, false, true]]; miner = (0,0) exit = (4,4)

Good luck!

Today's challenge is edited from damned3's kata on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (3)

erezwanderman • Nov 4 '19

const solve = (caveMap: boolean[][], mine: [number, number], exit: [number, number]) => {
  if (mine[0] === exit[0] && mine[1] === exit[1]) {
    return [];
  }
  if (mine[0] > 0 && caveMap[mine[0] - 1][mine[1]]) {
    caveMap[mine[0] - 1][mine[1]] = false;
    const subSolution = solve(caveMap, [mine[0] - 1, mine[1]], exit);
    if (subSolution instanceof Array) return ['left', ...subSolution];
    caveMap[mine[0] - 1][mine[1]] = true;
  }
  if (mine[0] < caveMap.length - 1 && caveMap[mine[0] + 1][mine[1]]) {
    caveMap[mine[0] + 1][mine[1]] = false;
    const subSolution = solve(caveMap, [mine[0] + 1, mine[1]], exit);
    if (subSolution instanceof Array) return ['right', ...subSolution];
    caveMap[mine[0] + 1][mine[1]] = true;
  }
  if (mine[1] > 0 && caveMap[mine[0]][mine[1] - 1]) {
    caveMap[mine[0]][mine[1] - 1] = false;
    const subSolution = solve(caveMap, [mine[0], mine[1] - 1], exit);
    if (subSolution instanceof Array) return ['up', ...subSolution];
    caveMap[mine[0]][mine[1] - 1] = true;
  }
  if (mine[1] < caveMap[0].length - 1 && caveMap[mine[0]][mine[1] + 1]) {
    caveMap[mine[0]][mine[1] + 1] = false;
    const subSolution = solve(caveMap, [mine[0], mine[1] + 1], exit);
    if (subSolution instanceof Array) return ['down', ...subSolution];
    caveMap[mine[0]][mine[1] + 1] = true;
  }

  return 'No solution';
};

const testCases: [boolean[][], [number, number], [number, number]][] = [
  [ [[true, false], [true, true]], [0, 0], [1, 1] ],
  [ [[true], [true], [true], [true]], [0, 0], [3, 0] ],
  [ [[true, true, true], [false, false, true], [true, true, true]], [0, 0], [2, 0] ],
  [ [[true, true, false, false, false], [false, true, true, false, false], [false, false, true, true, false], [false, false, false, true, true], [false, false, false, false, true]], [0, 0], [4, 4] ],
];

for (const testCase of testCases) {
  console.log(testCase, solve(testCase[0], testCase[1], testCase[2]));
}

stackblitz.com/edit/typescript-vmdbzm

Craig McIlwrath • Nov 5 '19

Here's my solution, in Haskell. It uses the A* path-finding algorithm using Manhattan/taxi-cab distance as the heuristic.

I don't think using a list is the best data-structure for holding the open and closed sets. It isn't great for searching for a minimum and removing elements from the middle. I might revisit this and look for a better solution, but for this challenge, it's fast enough.

There are also some things in my solution that I'm not entirely happy about. For one, getRequiredMove isn't a complete function but I didn't like my other ideas on how to put get the Move in the Tile, so I stuck with this.

import Data.List (delete, findIndex)
import Data.Maybe (isJust, fromJust, listToMaybe)

data Move = U | D | L | R deriving (Eq)

instance Show Move where
  show U = "up"
  show D = "down"
  show L = "left"
  show R = "right"

data Tile = Tile { getPos :: Pos, getF :: Int, getG :: Int, getH :: Int, getFrom :: Tile, getMove :: Move } deriving (Show)

instance Eq Tile where
  a == b = getPos a == getPos b

type Map = [[Bool]]
type Pos = (Int, Int)

getRequiredMove :: Pos -> Pos -> Move
getRequiredMove (x1, y1) (x2, y2)
  | x1 == x2     && y1 - 1 == y2 = U
  | x1 == x2     && y1 + 1 == y2 = D
  | x1 - 1 == x2 && y1 == y2     = L
  | x1 + 1 == x2 && y1 == y2     = R
  | otherwise                    = error "invalid move"

tile :: (Pos -> Int) -> Tile -> Pos -> Tile
tile h from pos = Tile { getPos = pos
                       , getG = g'
                       , getH = h'
                       , getF = g' + h'
                       , getFrom = from
                       , getMove = move
                       }
  where g' = getG from + 1
        h' = h pos
        move = getRequiredMove (getPos from) pos

executeMove :: Move -> Tile -> Pos
executeMove U (Tile (x, y) _ _ _ _ _) = (x    , y - 1)
executeMove D (Tile (x, y) _ _ _ _ _) = (x    , y + 1)
executeMove L (Tile (x, y) _ _ _ _ _) = (x - 1, y    )
executeMove R (Tile (x, y) _ _ _ _ _) = (x + 1, y    )

isInMap :: Map -> Pos -> Bool
isInMap m (x, y) = let r = length m
                       c = length $ head m
                   in  all id [ x >= 0, y >= 0, x < c, y < r ]

isNotBlocked :: Map -> Pos -> Bool
isNotBlocked m (x, y) = m !! y !! x

isValidPos :: Map -> Pos -> Bool
isValidPos m p = isInMap m p && isNotBlocked m p

getNeighbors :: Map -> (Pos -> Int) -> Tile -> [Tile]
getNeighbors m h t = map (tile h t) $
                     filter (isValidPos m) $
                     map (flip executeMove t) $
                     [U, D, L, R]

manhattanHueristic :: Pos -> Pos -> Int
manhattanHueristic (a, b) (c, d) = abs $ (a - c) + (b - d)

minimumBy :: (Ord b) => (a -> b) -> [a] -> a
minimumBy f = foldl1 (\m x -> if f x < f m then x else m)

inAny :: (Eq a) => [[a]] -> a -> Bool
inAny ass b = any id $ map (b`elem`) ass

findSmallest :: [Tile] -> Tile
findSmallest = minimumBy getF

backtrace :: Tile -> [Move]
backtrace t@(Tile _ _ _ _ f move) = if f == t then []
                                    else backtrace f ++ [move]

astar :: Map -> Pos -> (Pos -> Pos -> Int) -> [Tile] -> [Tile] -> Maybe [Move]
astar _ _ _ [] _ = Nothing
astar map end h open closed = let pivot = findSmallest open
                                  neighbors = filter (not . inAny [open, closed]) $ getNeighbors map (h end) pivot
                                  open' = neighbors ++ delete pivot open
                                  closed' = pivot : closed
                              in  if (getPos pivot) == end
                                    then Just $ backtrace pivot
                                    else astar map end h open' closed'

solve :: Map -> Pos -> Pos -> Maybe [Move]
solve map start end = astar map end manhattanHueristic [startTile] []
  where startTile = Tile { getPos = start
                         , getF = manhattanHueristic end start
                         , getG = 0
                         , getH = manhattanHueristic end start
                         , getFrom = startTile
                         , getMove = U
                         }

Julian Garamendy • Nov 5 '19 • Edited

Here's a solution in TypeScript.

You can see it in the Playground

Some tests at the end.

// Solution based on: https://www.redblobgames.com/pathfinding/a-star/introduction.html
// by @redblobgames

type Coords = readonly [number, number];

function solve(caveMap: readonly boolean[][], miner: Coords, exit: Coords) {
  const prevCoordsMap = calculatePrevCoordsMap(caveMap, miner);
  const path = getPath(miner, exit, prevCoordsMap);
  return getInstructionsFromPath(path);
}

function compare(c0: Coords, [x1, y1]: Coords) {
  const [x0, y0] = c0;
  return x0 === x1 && y0 === y1;
}

function getInstructionsFromPath(path: readonly Coords[]) {
  return path.reduce<string[]>((acc, cur, index, arr) => {
    if (index < arr.length - 1) {
      acc.push(getDirection(cur, arr[index + 1]));
    }
    return acc;
  }, []);
}

function calculatePrevCoordsMap(caveMap: readonly boolean[][], miner: Coords) {
  const getNeighbours = createGetNeighbours(caveMap);

  const frontier: Coords[] = [miner];
  const comeFrom: { [index: string]: Coords | null } = {
    [miner.toString()]: null,
  };

  const isInComeFrom = (coords: Coords) => comeFrom.hasOwnProperty(coords.toString());

  while (frontier.length > 0) {
    let current = frontier.shift();
    getNeighbours(current!).forEach(next => {
      if (!isInComeFrom(next)) {
        frontier.unshift(next);
        comeFrom[next.toString()] = current!;
      }
    });
  }
  return comeFrom;
}

function createGetNeighbours(caveMap: readonly boolean[][]) {
  const height = caveMap[0].length;
  const width = caveMap.length;
  const isWalkable = ([x, y]: Coords) => caveMap[x] && caveMap[x][y];
  return ([x, y]: Coords) => {
    const n: Coords | null = y > 0 ? [x, y - 1] : null;
    const s: Coords | null = y < height ? [x, y + 1] : null;
    const w: Coords | null = x > 0 ? [x - 1, y] : null;
    const e: Coords | null = x < width ? [x + 1, y] : null;
    return ([n, s, w, e].filter(c => c !== null) as readonly Coords[]).filter(
      c => isWalkable(c)
    );
  };
}

function getPath(
  start: Coords,
  goal: Coords,
  prevCoordsMap: {[index: string]: Coords | null}
) {

  const path: Coords[] = [];
  let current: Coords = goal;
  let count = 0;
  while (compare(current, start) === false) {
    if (++count > 100) break;
    path.push(current);
    const prev = prevCoordsMap[current.toString()];
    if (prev) current = prev;
  }
  path.push(start);
  return path.reverse();
}

function getDirection([x0, y0]: Coords, [x1, y1]: Coords): string {
  if (x1 > x0) return 'right';
  if (x1 < x0) return 'left';
  if (y1 > y0) return 'down';
  if (y1 < y0) return 'up';
  return '';
}

//////////////////////////////
// TESTS
//////////////////////////////

function assertEquals(name: string, a: string[], b: string[]) {
  if (a.length === b.length && a.every((step, i) => b[i] === step)) {
    console.log(`OK: ${name}`);
  } else {
    console.error(`KO: '${name}'\n${a} !== ${b}`);
  }
}

assertEquals(
  'A simple map. (2x2)',
  solve([[true, false], [true, true]], [0, 0], [1, 0]),
  ['right']
);

assertEquals(
  'A linear map. (1x4)',
  solve([[true], [true], [true], [true]], [0, 0], [3, 0]),
  ['right', 'right', 'right']
);

assertEquals(
  'Walk around an obstacle (3x3)',
  solve(
    [[true, true, true], [false, false, true], [true, true, true]],
    [0, 0],
    [2, 0]
  ),
  ['down', 'down', 'right', 'right', 'up', 'up']
);

assertEquals(
  'Change directions several times (5x5)',
  solve(
    [
      [true, true, false, false, false],
      [false, true, true, false, false],
      [false, false, true, true, false],
      [false, false, false, true, true],
      [false, false, false, false, true],
    ],
    [0, 0],
    [4, 4]
  ),
  ['down', 'right', 'down', 'right', 'down', 'right', 'down', 'right']
);

DEV Community

Daily Challenge #107 - Escape the Mines

Top comments (3)

Read next

What exactly is the Rome Protocol

Python Virtual Environments

Observability - 1

A discussion platform for developers