# Daily Challenge #107 - Escape the Mines

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!

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

stackblitz.com/edit/typescript-vmdbzm

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
}
``````

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

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

const height = caveMap.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']
);
``````  