stevensonmt
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
Marked As Solved
lud
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}.
Also Liked
stevensonmt
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.
Werner
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):
and a nice project by Angelika Tyborska:
Popular in Questions
Other popular topics
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #websockets
- #supervisor
- #advent-of-code
- #elixirconf-us
- #distillery
- #processes
- #forms
- #api
- #metaprogramming
- #security
- #performance









