# Shortest path through maze with diagonals

I’m really baffled by this leetcode problem. My algorithm finds a valid path but it is not guaranteed to be the shortest path as it will include corners that could be cut diagonally (though not always). Any help?

``````defmodule Solution do
@neighbors [{1, 1}, {1, 0}, {0, 1}, {-1, 1}, {1, -1}, {0, -1}, {-1, 0}, {-1, -1}] |> MapSet.new()
@empty_q :gb_sets.empty()

@spec shortest_path_binary_matrix(grid :: [[integer]]) :: integer
def shortest_path_binary_matrix(grid) do
n = length(grid) -1
valid_pts =
grid
|> Enum.with_index()
|> Enum.flat_map(fn {row, i} ->
row
|> Enum.with_index()
|> Enum.reject(fn {v, _} -> v == 1 end)
|> Enum.map(fn {_, j} -> {j, i} end)
end)
|> Enum.reduce(Map.new(), fn pt, map -> Map.put(map, pt, -1) end)

if [{0,0}, {n, n}] |> Enum.any?(fn pt -> not Map.has_key?(valid_pts, pt) end) do
-1
else
visited = MapSet.new()
q = :gb_sets.insert({0, 0, 1}, @empty_q)
path_finder(Map.put(valid_pts, {0, 0}, 1), visited, q, n, 1)
end
end

def path_finder(_, _, @empty_q, _, distance), do: -1
def path_finder(pts, visited, queue, target, distance) do
{{x, y, d}, sub_q} = :gb_sets.take_smallest(queue)
cond do
MapSet.member?(visited, {x, y}) ->
path_finder(pts, visited, sub_q, target, distance)
{x, y} == {target, target} ->
IO.inspect(visited, label: "path in the end")
d
true ->
v = MapSet.put(visited, {x, y})
ns = neighbors({x,y}, target) |> Enum.reject(&MapSet.member?(visited, &1))
{pts, queue} =
ns
|> Enum.reduce({pts, sub_q}, fn {a, b} = n, {map, q} ->
case map[n] do
x when x < d + 1 ->
{
Map.put(map, n, d + 1),
:gb_sets.add_element({a, b, d + 1}, q)
}
_ -> { map, q }
end
end)
path_finder(pts, v, queue, target, d + 1)
end
end

def neighbors({x,y}, n) do
@neighbors
|> Enum.map(fn {a, b} -> {a + x, y + b} end)
|> Enum.reject(fn {a, b} -> a > n or b > n end)
|> Enum.reject(fn {a, b} -> a < 0 or b < 0 end)
end
end
``````

I started with A* but we need Dijkstra here so maybe there are remnants left. Anyway this is a quick solution:

``````defmodule Solution do
@spec shortest_path_binary_matrix(grid :: [[integer]]) :: integer
def shortest_path_binary_matrix(input) do
xm = length(hd(input)) - 1
ym = length(input) - 1

grid = build_grid(input)

open = [{_cost = 1, {0, 0}}]

case Map.has_key?(grid, {0, 0}) do
true ->
state = %{grid: grid, mm: {xm, ym}, open: open, closed: %{}}
solve(state)

false ->
-1
end
end

defp solve(%{grid: grid, mm: mm, open: [best | rest], closed: closed} = state) do
case best do
{cost, ^mm} ->
cost

{cost, {x, y}} ->
neighs =
{x, y}
|> neighbours_with_cost(grid, cost + 1)
|> not_closed(closed)

open = Enum.reduce(neighs, rest, &insert/2)
closed = Map.put(closed, {x, y}, cost)

solve(%{state | open: open, closed: closed})
end
end

defp solve(%{open: []}) do
-1
end

defp not_closed(neighs, closed) do
Enum.filter(neighs, fn {_cost, xy} -> not Map.has_key?(closed, xy) end)
end

defp insert({cost, xy}, [{c_cost, xy} = best | rest]) when cost > c_cost do
# new score is not better for same coords
[best | rest]
end

defp insert({cost, xy} = new, [{c_cost, _} | rest]) when cost < c_cost do
# new cost is better than rest of the list
[new | delete(rest, xy)]
end

defp insert(new, [new | rest]) do
[new | rest]
end

defp insert(new, [top | rest]) do
# new cost is better than rest of the list
[top | insert(new, rest)]
end

defp insert(new, []) do
# new cost is better than rest of the list
[new]
end

defp delete([{_, xy} | rest], xy) do
rest
end

defp delete([h | rest], xy) do
[h | delete(rest, xy)]
end

defp delete([], _) do
[]
end

defp neighbours_with_cost(grid, xy, cost) do
ns = neighbours(grid, xy)
Enum.map(ns, fn xyn -> {cost, xyn} end)
end

defp neighbours({x, y}, grid) do
[
{x - 1, y - 1},
{x, y - 1},
{x + 1, y - 1},
{x - 1, y},
{x + 1, y},
{x - 1, y + 1},
{x, y + 1},
{x + 1, y + 1}
]
|> Enum.filter(fn xy -> Map.has_key?(grid, xy) end)
end

def build_grid(rows) do
rows
|> Enum.with_index()
|> Enum.flat_map(fn {cols, y} ->
cols
|> Enum.with_index()
|> Enum.map(fn {val, x} ->
{{x, y}, val}
end)
end)
|> clean_grid()
|> Map.new()
end

def clean_grid(grid) do
grid |> Enum.filter(fn {_, v} -> v == 0 end) |> Map.new()
end
end

``````

If your algorithm fails to prioritize diagonals over corners maybe there is a misuage of :gb_sets ? Because `take_smallest` will return the lowest `{x, y, cost}` tuple, and that means `{0,999,999}` is lower than `{1,1,1}`.

1 Like

Thanks so much for your help. That was intentional but misguided. I was thinking I wanted to prioritize the closest node to the last node, which is not smart. Just changing the structure of the `gb_set` to `{distance, x, y}` fixed my issue. So happy I’ll be able to sleep tonight.

1 Like

BTW if you’re interested in Maze’s in general, there’s also a book by Pragmatic (although I have not read it, but is on my list):

Mazes for programmers

and a nice project by Angelika Tyborska:

https://github.com/angelikatyborska/mazes

1 Like

That book seems fun. I will definitely check it out. Thanks!