rugyoga
Advent of Code 2023 - Day 17
Fairly straightforward Dijkstra’s algorithm
import AOC
aoc 2023, 17 do
def compute(input, candidates) do
{{max_row, max_col}, items} = Grid.parse(input)
heat_map =
items
|> Enum.map(fn {coord, number} -> {coord, String.to_integer(number)} end)
|> Map.new
Heap.new()
|> Heap.push({0, [{{0,0}, :east}]})
|> Heap.push({0, [{{0,0}, :south}]})
|> search({max_row-1, max_col-1}, heat_map, MapSet.new, candidates)
end
def p1(input), do: compute(input, &candidates_simple/1)
def p2(input), do: compute(input, &candidates_ultra/1)
def search(heap, {row_t, col_t} = target, heat_map, seen, candidates) do
{{cost, last_3}, heap} = Heap.pop(heap)
row_col = last_3 |> hd |> elem(0)
cond do
row_col == target -> cost
MapSet.member?(seen, last_3) -> search(heap, target, heat_map, seen, candidates)
true ->
seen = MapSet.put(seen, last_3)
last_3
|> then(candidates)
|> Enum.filter(fn [{{row, col}, _} | _] -> 0 <= row and row <= row_t and 0 <= col and col <= col_t end)
|> Enum.reduce(heap, fn last_3, heap -> Heap.push(heap, {cost+heat_map[last_3 |> hd |> elem(0)], last_3}) end)
|> search(target, heat_map, seen, candidates)
end
end
def candidates_simple([x, _, _]), do: [[go(:left, x)], [go(:right, x)]]
def candidates_simple([x | rest]), do: [[go(:straight, x), x | rest], [go(:left, x)], [go(:right, x)]]
def candidates_ultra(moves) do
cond do
length(moves) < 4 -> [[go(:straight, hd(moves)) | moves]]
length(moves) == 10 -> [[go(:left, hd(moves))], [go(:right, hd(moves))]]
true -> [[go(:straight, hd(moves)) | moves], [go(:left, hd(moves))], [go(:right, hd(moves))]]
end
end
@spec go(any(), {{any(), any()}, any()}) :: {{any(), any()}, :east | :north | :south | :west}
def go(which_way, {row_col, dir}), do: next(row_col, dirs()[dir][which_way])
def dirs() do
%{west: %{left: :south, straight: :west, right: :north},
north: %{left: :west, straight: :north, right: :east},
east: %{left: :south, straight: :east, right: :north},
south: %{left: :east, straight: :south, right: :west}}
end
def next({row, col}, :west), do: {{row, col-1}, :west}
def next({row, col}, :east), do: {{row, col+1}, :east}
def next({row, col}, :north), do: {{row-1, col}, :north}
def next({row, col}, :south), do: {{row+1, col}, :south}
end
Most Liked
bjorng
Erlang Core Team
Dijkstra’s algorithm using gb_sets as priority queue. It solves both parts in 2.7 seconds on my computer.
https://github.com/bjorng/advent-of-code-2023/blob/main/day17/lib/day17.ex
EDIT:
I realized that all elements inserted into the gb_sets are guaranteed to be unique, which means that it is safe to use gb_sets:insert/2 instead of gb_sets:add/2. That reduces the time for my solution from 2.7 seconds to 2.2 seconds.
3
exists
Also used Dijkstra, but through libgraph. It turns out that creating graphs this big in it incurs a massive overhead, 50 seconds for part one and 130 seconds for part two (num_vertices: 39763, num_edges 529036). Well, TIL. The Dijkstra itself is then fast.
For me the interesting part was to realise that I can enforce the direction changes by having “two layers” of the grid, with top-to-bottom ony vertical direction arrows, and bottom-to-top only horizontal direction arrows.
code
Mix.install([{:libgraph, "~> 0.16.0"}])
defmodule Main do
def run() do
get_input()
|> Enum.map(&String.to_charlist/1)
# |> solve(1,3) # part1
|> solve(4,10) # part2
end
def get_input() do
# "testinput17"
"input17"
|> File.read!()
|> String.trim()
|> String.split("\n")
end
def mkgrid(ls) do
for {row, r} <- Enum.with_index(ls),
{val, c} <- Enum.with_index(row),
into: %{},
do: {{r,c}, val-?0}
end
def calc_weight_straight({fr,fc},{tr,tc},grid) do
(for r <- fr..tr, c <- fc..tc, do: grid[{r,c}])
|> Enum.sum() |> Kernel.-(grid[{fr,fc}])
end
def cond_add_edge(g,{fr,fc,fl},{tr,tc,tl},grid) do
if {tr,tc} in Map.keys(grid) do
wt = calc_weight_straight({fr,fc},{tr,tc},grid)
Graph.add_edge(g, {fr,fc,fl}, {tr,tc,tl}, weight: wt)
else g end
end
@st {-1,-1,:t}
@ed {200,200,:t}
def mkgraph(grid,mn,mx) do
rmax = Map.keys(grid) |> Enum.map(&elem(&1,0)) |> Enum.max()
cmax = Map.keys(grid) |> Enum.map(&elem(&1,1)) |> Enum.max()
for {r,c} <- Map.keys(grid), reduce: Graph.new(type: :directed) do
g ->
mn..mx |> Enum.reduce(g, fn d, gacc ->
gacc |> cond_add_edge({r,c,:t}, {r+d,c,:b}, grid)
|> cond_add_edge({r,c,:t}, {r-d,c,:b}, grid)
|> cond_add_edge({r,c,:b}, {r,c+d,:t}, grid)
|> cond_add_edge({r,c,:b}, {r,c-d,:t}, grid)
end)
end
|> Graph.add_edge(@st,{0,0,:t},weight: 1)
|> Graph.add_edge(@st,{0,0,:b},weight: 1)
|> Graph.add_edge({rmax,cmax,:t},@ed,weight: 1)
|> Graph.add_edge({rmax,cmax,:b},@ed,weight: 1)
end
def path_length([a,b|rest],g,sum) do
wt = g |> Graph.edge(a,b) |> Map.get(:weight,0)
path_length([b|rest], g, sum+wt)
end
def path_length([_vtx],_g,sum), do: sum
def solve(ls,mn,mx) do
grid = ls |> mkgrid()
gr = grid |> mkgraph(mn,mx)
Graph.get_shortest_path(gr,@st,@ed)
|> path_length(gr,0)
|> Kernel.-(2)
end
end
:timer.tc(&Main.run/0)
|> IO.inspect(charlists: :as_lists)
I should probably try to rewrite this with just digraph to see how it compares, although digraph does not do edge weights directly.
(sorry, hit the wrong “reply” button…)
2
midouest
Took me a while to implement Dijkstra’s Algorithm and then I got stuck because I was hung up on using x-y coordinates for the distance/previous keys. I rewrote it as a depth-first search and ran it on my desktop computer with 16GB of RAM to find the answer to part 1 in about 10 minutes! I tried the same approach for part 2, but the program consumed all of my RAM + lots of paging to disk. I restarted it a few times with the best result from the previous iteration, but it never found the answer. I eventually went back to my original implementation and finally figured out the trick. This was a nice dive into the Erlang docs to learn about :gb_sets.
Part 1
defmodule Part1 do
def parse(input) do
for line <- String.split(input, "\n", trim: true) do
for char <- String.graphemes(line) do
String.to_integer(char)
end
end
end
def print(map, path) do
for {line, y1} <- Enum.with_index(map) do
for {loss, x1} <- Enum.with_index(line) do
index = Enum.find_index(path, fn pos -> pos == {y1, x1} end)
char =
if index != nil and index > 0 do
{y0, x0} = Enum.at(path, index - 1)
dy = y1 - y0
dx = x1 - x0
case {dy, dx} do
{1, 0} -> "v"
{0, 1} -> ">"
{-1, 0} -> "^"
{0, -1} -> "<"
end
else
Integer.to_string(loss)
end
IO.write(char)
end
IO.puts("")
end
end
def total_loss(map, path) do
path
|> Enum.drop(1)
|> Enum.map(fn {y, x} -> map |> Enum.at(y) |> Enum.at(x) end)
|> Enum.sum()
end
def reconstruct(prev, state), do: reconstruct(prev, state, [])
def reconstruct(_, nil, path), do: path
def reconstruct(prev, {pos, _, _} = state, path),
do: reconstruct(prev, prev[state], [pos | path])
@deltas [{1, 0}, {0, 1}, {-1, 0}, {0, -1}]
def search(map) do
goal = length(map) - 1
start = {0, 0}
dist = %{{start, nil, 0} => 0}
prev = %{}
state = {0, 0, start, nil}
queue = :gb_sets.empty()
queue = :gb_sets.insert(state, queue)
search(map, goal, dist, prev, queue)
end
def search(map, goal, dist, prev, queue) do
{curr_loss, curr_rep, {curr_y, curr_x} = curr_pos, curr_delta} =
curr_state = :gb_sets.smallest(queue)
queue = :gb_sets.delete(curr_state, queue)
if curr_y == goal and curr_x == goal do
reconstruct(prev, {curr_pos, curr_delta, curr_rep})
else
{dist, prev, queue} =
@deltas
|> Stream.map(fn {next_dy, next_dx} = next_delta ->
next_pos = {curr_y + next_dy, curr_x + next_dx}
next_rep = if next_delta == curr_delta, do: curr_rep + 1, else: 1
{next_pos, next_delta, next_rep}
end)
|> Stream.reject(fn {{next_y, next_x}, {next_dy, next_dx}, next_rep} ->
next_y < 0 or next_x < 0 or next_y > goal or next_x > goal or next_rep > 3 or
(curr_delta != nil and
{next_dy, next_dx} == {elem(curr_delta, 0) * -1, elem(curr_delta, 1) * -1})
end)
|> Enum.reduce(
{dist, prev, queue},
fn {{next_y, next_x} = next_pos, next_delta, next_rep}, {dist, prev, queue} ->
next_loss = curr_loss + (map |> Enum.at(next_y) |> Enum.at(next_x))
if next_loss >= dist[{next_pos, next_delta, next_rep}] do
{dist, prev, queue}
else
dist = Map.put(dist, {next_pos, next_delta, next_rep}, next_loss)
prev =
Map.put(prev, {next_pos, next_delta, next_rep}, {curr_pos, curr_delta, curr_rep})
next_state = {next_loss, next_rep, next_pos, next_delta}
queue = :gb_sets.insert(next_state, queue)
{dist, prev, queue}
end
end
)
search(map, goal, dist, prev, queue)
end
end
end
map = Part1.parse(input)
path = Part1.search(map)
Part1.print(map, path)
Part1.total_loss(map, path)
Part 2
defmodule Part2 do
@deltas [{1, 0}, {0, 1}, {-1, 0}, {0, -1}]
def search(map) do
goal = {length(map) - 1, length(hd(map)) - 1}
start = {0, 0}
dist = %{{start, nil, 0} => 0}
prev = %{}
state = {0, 0, start, nil}
queue = :gb_sets.empty()
queue = :gb_sets.insert(state, queue)
search(map, goal, dist, prev, queue)
end
def search(map, {goal_y, goal_x} = goal, dist, prev, queue) do
{curr_loss, curr_rep, {curr_y, curr_x} = curr_pos, curr_delta} =
curr_state = :gb_sets.smallest(queue)
queue = :gb_sets.delete(curr_state, queue)
if curr_y == goal_y and curr_x == goal_x do
if curr_rep < 4 do
search(map, goal, dist, prev, queue)
else
Part1.reconstruct(prev, {curr_pos, curr_delta, curr_rep})
end
else
{dist, prev, queue} =
@deltas
|> Stream.map(fn {next_dy, next_dx} = next_delta ->
next_pos = {curr_y + next_dy, curr_x + next_dx}
next_rep = if next_delta == curr_delta, do: curr_rep + 1, else: 1
{next_pos, next_delta, next_rep}
end)
|> Stream.reject(fn {{next_y, next_x}, {next_dy, next_dx} = next_delta, next_rep} ->
case curr_delta do
nil ->
false
{curr_dy, curr_dx} ->
next_y < 0 or next_x < 0 or next_y > goal_y or next_x > goal_x or
(next_delta != curr_delta and curr_rep < 4) or
(next_delta == curr_delta and next_rep > 10) or
(next_dy == curr_dy * -1 and next_dx == curr_dx * -1)
end
end)
|> Enum.reduce(
{dist, prev, queue},
fn {{next_y, next_x} = next_pos, next_delta, next_rep}, {dist, prev, queue} ->
next_loss = curr_loss + (map |> Enum.at(next_y) |> Enum.at(next_x))
if next_loss >= dist[{next_pos, next_delta, next_rep}] do
{dist, prev, queue}
else
dist = Map.put(dist, {next_pos, next_delta, next_rep}, next_loss)
prev =
Map.put(prev, {next_pos, next_delta, next_rep}, {curr_pos, curr_delta, curr_rep})
next_state = {next_loss, next_rep, next_pos, next_delta}
queue = :gb_sets.insert(next_state, queue)
{dist, prev, queue}
end
end
)
search(map, goal, dist, prev, queue)
end
end
end
map = Part1.parse(input)
path = Part2.search(map)
Part1.print(map, path)
Part1.total_loss(map, path)
2
Popular in Challenges
I said I was on a break, but I took a sneak peak and it looked fun so…
Part 1 completes in half a millisecond with a single pass of the ...
New
This topic is about Day 3 of the Advent of Code 2020 .
Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/le...
New
Reasonably pleased with my solution. The bitstring packet problems are so well suited to Erlang/Elixir it’s almost not fair.
defmodule D...
New
I have 2 arrays: a1 can be any combination of value or nil like that
a1 = [1,nil,3]
and array 2 the same
a2 = [4,2, nil]
How do I com...
New
My solution finishes both parts in 5 seconds on my computer. That time should be possible to reduce by optimizing my rather naive tilt/2 ...
New
Nobody’s doing Advent of Code this year? :grinning_face_with_smiling_eyes:
I might do the first week or so.
For Day 1, first I solved i...
New
Note: This topic is to talk about Day 6 of the Advent of Code 2019.
There is a private leaderboard for elixirforum members. You can join...
New
Gosh this one took me sooo much time.
At first I was trying to iterate each digit independently on the input A number to make digits cha...
New
Today is a brute-force day: advent-of-code-2024/lib/advent_of_code2024/day6.ex at main · ibarakaiev/advent-of-code-2024 · GitHub
Takes a...
New
Note: This topic is to talk about Day 2 of the Advent of Code 2019 .
There is a private leaderboard for elixirforum members. You can joi...
New
Other popular topics
I have an umbrella app.
Some of the apps inside depend on other apps in the umbrella, unsurprisingly.
I’m writing a test for one of the...
New
We have an ECS cluster with 4 services, where each task joins a single cluster, via discovery ECS discovery service.
Currently when I de...
New
This post is an instruction guide to help you setup your Neovim for Elixir development from scratch. It includes general information on h...
New
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
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
Forgive me if this is obvious, but how does one delete a database record WITHOUT selecting it first? Ecto.Repo — Ecto v3.14.0 has exampl...
New
Hello guys,
I have finally made it. I created an admin interface for a framework. It’s been on my todo list for years and with the curre...
New
I have a relationship of love and hate with Elixir. Lots of things are just absolutely right, but there are some things that are kind of ...
New
I have VueJS GUIs with the project generated using Webpack.
I have Elixir modules that will need to be used by the VueJS GUIs.
I forese...
New
I asked this very same question on twitter and got some interesting feedback, but I thought it would be a good question to ask here as we...
New
Latest on Elixir Forum
Sponsor Spotlight
Real-time error tracking, performance insights, and observability for devs.
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
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Real-time error tracking, performance insights, and observability for devs.
Producing high quality Elixir screencasts since 2017.
Enabling companies to succeed by building software people love.
The deployment platform built for Elixir: PaaS ease, VPS control.
Courses that'll move you from confusion to "Aha, now I get it!"