stevensonmt

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

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

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

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):

Mazes for programmers

and a nice project by Angelika Tyborska:

https://github.com/angelikatyborska/mazes

Where Next?

Popular in Questions Top

gshaw
What is the idiomatic way of matching for not nil in Elixir? E.g., First way: defp halt_if_not_signed_in(conn, signed_in_account) when...
New
aadeshere1
I have a another noob question about loop. Since elixir is immutable, while loop is not directly possible. total = 10 while total != 0 ...
New
rms.mrcs
Hi, I need to transform a list of numbers into a map where the keys are the indexes and the values are the original values of the list....
New
alice
Hey, Just curious what are the main benefits of Elixir compared to Clojure? When is Elixir more useful than Clojure and vice versa? Th...
New
LegitStack
I’m trying to make a websocket server in Phoenix or raw Elixir. I heard about gun, I think I could use cowboy, but since I’m not that sma...
New
hpopp
To simplify some tasks at work, I wrote and published this package yesterday. It’s a simple macro that enables Access behaviour on struct...
New
Codball
Mix format works fine if run from the cmd. I’ve followed this to facilitate the implementation into VSC which involves downloading an ext...
New
Mooodi
Given a string, how can I get access to its character by index? Enum.at("my_string", 2) doesn't work. Or rather, not char, but a substr...
New
wernerlaude
In AR this is so simple @articles = current_user.articles How to do in Ecto? def index(conn, _params) do current_user = conn.assig...
New
skosch
To my knowledge, put_in, Map.update etc. all have the one limitation of not automatically creating intermediate keys when needed (for exa...
New

Other popular topics Top

Qqwy
Update: How to use the Blogs &amp; Podcasts section You can post links to your blog posts or podcasts either in one of the Official Blog...
3268 119930 1237
New
vonH
In asking this question I am more interested about the expressiveness of the language itself and less concerned about the availability of...
New
aalberti333
As the title describes, I’m trying to run Enum.map() over a list of key/value pairs, where the value is a map. My data looks like this: ...
New
polypush135
As many of you may have realized by now (sorry for all the posts here) I’ve been working on a db problem where I’m trying to aggregate a ...
New
danschultzer
None of the current solutions worked well for me, so I went ahead and built a user management system from scratch. This project took far...
548 27727 240
New
ashish173
I am using Ecto timestamps with postgres, I can see the timestamps() use the :naive_dateime but for my use case I wanted to store the ti...
New
alice
Hey, Just curious what are the main benefits of Elixir compared to Clojure? When is Elixir more useful than Clojure and vice versa? Th...
New
Patoshizzle
After calling mix ecto.create I get this error: 17:00:32.162 [error] GenServer #PID&lt;0.412.0&gt; terminating ** (Postgrex.Error) FATAL...
New
AstonJ
We’ve put together this wiki for Phoenix LiveView - please feel free to add any info you feel is worth including. What is Phoenix LiveV...
New
vrod
I am using the Starship cross-shell prompt – it seems pretty nice, but I get some errors: [WARN] - (starship::utils): Executing command ...
New

We're in Beta

About us Mission Statement