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

chokchit
** (DBConnection.ConnectionError) connection not available and request was dropped from queue after 2733ms. You can configure how long re...
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
Darmani72
If I have a post route which an argument: post /my_post_route/:my_param1, MyController.my_post_handler How would get the post params ...
New
JeremM34
Hello, how can I check the Phoenix version ? Thanks !
New
electic
Hi, I am new to Elixir. I am trying to use the DateTime component to insert a date into MySQL however the there seems to be no way to fo...
New
dokuzbir
I want to highlight html closing tags when i click a html tag. That works in .html files but doesnt work for html.eex templates. How can...
New
freewebwithme
Using vs code and installed ElixirLS: support and debugger. And I got an error popped up on start up says Failed to run ‘elixir’ comma...
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
romenigld
I am trying to run a deploy with docker and I successfully runned with this command: docker build -t romenigld/blog-prod . but when I t...
New
PeterCarter
There are pre-rolled solutions for other frameworks that do work. However, Phoenix does not seem to have these. Have people had good expe...
New

Other popular topics Top

chrismccord
As promised, the first release candidate of Phoenix 1.3.0 is out! This release focuses on code generators with improved project structure...
New
ovidiubadita
Hey all, I discovered Elixir and I love it. I always wanted to learn a functional programming and I intended to go for Haskell, but afte...
New
Fl4m3Ph03n1x
About me? ( if you have nothing better to do than reading about some random guy in the internet :stuck_out_tongue: ) Hello all, this is ...
New
josevalim
Hi everyone, One of the features added to Elixir early on to help integration with Erlang code was the idea of overridable function defi...
New
baxterw3b
Hi guys, i’m new in the Elixir world, and i have to say, that i love it! i’m having some problem to understand anonymous functions with ...
New
fayddelight
I tried installing elixir 1.11.2 erlang 23.3.4 via asdf in my zsh shell. Enabled the versions locally and globally. When I list them ...
New
nobody
Hi! In PHP: $_SERVER[‘SERVER_ADDR’] - in Elixir? Searched the docs for ip address and the web, no good results. Thanks!
New
hariharasudhan94
Lets say I have map like this fetching from my database %{"_id" =&gt; #BSON.ObjectId&lt;58eb1a7a9ad169198c3dXXXX&gt;, "email" =&gt; ...
New
jononomo
For some reason my phoenix channels are working for me in my local dev environment, but as soon as I deploy via Docker, I get a 403 error...
New
sergio
Kind of like when jquery came out, it was super necessary. Existing drag and drop libraries have a bunch of baggage to support old browse...
New

Latest on Elixir Forum

We're in Beta

About us Mission Statement