Shortest path through maze with diagonals

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

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.

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

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