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!