this repo has no description
hauleth.dev
1<!-- vim:set ft=markdown: -->
2
3<!-- livebook:{"persist_outputs":true} -->
4
5# Day 15
6
7```elixir
8input =
9 File.read!("day15.txt")
10 |> String.trim()
11 |> String.split("\n")
12 |> Enum.map(&String.to_charlist/1)
13 |> Enum.with_index()
14 |> Enum.flat_map(fn {row, y} ->
15 row
16 |> Enum.with_index()
17 |> Enum.map(fn {v, x} -> {{x, y}, v - ?0} end)
18 end)
19 |> Map.new()
20
21{width, height} = Enum.max(Map.keys(input))
22```
23
24```output
25{99, 99}
26```
27
28## Task 1
29
30```elixir
31shortest_paths =
32 for y <- height..0//-1,
33 x <- width..0//-1,
34 reduce: %{} do
35 acc ->
36 right = acc[{x + 1, y}]
37 bottom = acc[{x, y + 1}]
38
39 value =
40 case {right, bottom} do
41 {nil, nil} -> input[{x, y}]
42 _ -> input[{x, y}] + min(right, bottom)
43 end
44
45 Map.put(acc, {x, y}, value)
46 end
47
48shortest_paths[{0, 0}] - input[{0, 0}]
49```
50
51```output
52429
53```
54
55## Task 2
56
57```elixir
58defmodule Day15.Task2 do
59 def expand_grid(board) do
60 {width, height} = Enum.max(Map.keys(board))
61
62 board
63 |> Enum.flat_map(fn {{x, y}, v} ->
64 for rx <- 0..4, ry <- 0..4 do
65 {{x + (width + 1) * rx, y + (height + 1) * ry}, rem(v - 1 + rx + ry, 9) + 1}
66 end
67 end)
68 |> Map.new()
69 end
70
71 def find_path(board, start, finish) do
72 dists = :gb_sets.singleton({0, start})
73
74 find_path(board, finish, dists, MapSet.new())
75 end
76
77 @surround for dx <- -1..1, dy <- -1..1, abs(dx) != abs(dy), do: {dx, dy}
78
79 def find_path(board, finish, dists, visited) do
80 {{dist, {x, y} = curr}, dists} = :gb_sets.take_smallest(dists)
81
82 if curr == finish do
83 dist
84 else
85 visited = MapSet.put(visited, curr)
86
87 dists =
88 for {dx, dy} <- @surround,
89 next = {x + dx, y + dy},
90 next not in visited,
91 is_map_key(board, next),
92 alt = dist + board[next],
93 reduce: dists do
94 acc ->
95 :gb_sets.add_element({alt, next}, acc)
96 end
97
98 find_path(board, finish, dists, visited)
99 end
100 end
101end
102```
103
104```output
105{:module, Day15.Task2, <<70, 79, 82, 49, 0, 0, 16, ...>>, {:find_path, 4}}
106```
107
108```elixir
109input
110|> Day15.Task2.expand_grid()
111|> Day15.Task2.find_path({0, 0}, {499, 499})
112```
113
114```output
1152844
116```