this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 18
4
5```elixir
6Mix.install([:kino_aoc, :image])
7```
8
9## Section
10
11<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiIxOCIsInNlc3Npb25fc2VjcmV0IjoiQURWRU5UX09GX0NPREVfU0VTU0lPTiIsInllYXIiOiIyMDI0In0","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
12
13```elixir
14{:ok, puzzle_input} =
15 KinoAOC.download_puzzle("2024", "18", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
16```
17
18<!-- livebook:{"output":true} -->
19
20```
21{:ok,
22 "21,9\n69,53\n31,24\n2,9\n50,53\n2,5\n3,44\n69,49\n25,26\n50,31\n68,41\n54,67\n19,8\n11,9\n9,29\n1,31\n13,12\n28,5\n69,41\n51,66\n53,43\n65,35\n40,67\n43,13\n21,34\n49,3\n65,61\n25,9\n39,21\n59,37\n11,24\n9,30\n63,62\n41,69\n6,29\n68,47\n45,1\n9,1\n11,14\n59,19\n67,54\n12,5\n41,44\n59,45\n3,28\n57,42\n7,25\n43,11\n31,19\n9,6\n53,60\n29,8\n53,67\n17,1\n11,17\n31,3\n55,35\n2,21\n67,61\n37,5\n6,1\n51,24\n39,1\n31,1\n69,58\n61,19\n49,63\n40,21\n28,25\n59,59\n66,69\n30,1\n7,5\n53,49\n4,17\n39,23\n23,20\n62,67\n51,36\n55,39\n41,3\n57,30\n18,7\n6,37\n29,25\n55,48\n37,16\n65,69\n21,5\n43,48\n3,11\n3,9\n63,39\n23,23\n43,67\n47,3\n69,47\n67,53\n65,24\n67,52\n35,20\n46,45\n57,26\n15,32\n35,68\n15,16\n41,1\n63,29\n15,3\n15,18\n51,50\n60,43\n50,1\n35,12\n41,10\n58,39\n27,18\n50,69\n55,40\n2,3\n51,47\n1,11\n16,9\n23,9\n19,7\n29,12\n37,3\n1,15\n11,1\n25,11\n65,56\n37,70\n60,41\n48,69\n62,29\n53,38\n12,35\n67,42\n49,67\n31,5\n39,7\n65,43\n5,25\n23,24\n43,68\n11,11\n9,32\n62,39\n69,39\n51,46\n38,21\n67,37\n5,26\n62,19\n27,21\n48,51\n55,62\n11,33\n25,4\n13,20\n61,58\n62,55\n41,66\n11,40\n16,7\n9,17\n67,65\n1,1\n9,33\n7,35\n1,3\n11,4\n29,21\n47,47\n61,67\n41,70\n42,65\n55,47\n54,49\n36,13\n61,36\n18,23\n26,23\n45,5\n9,18\n61,27\n36,21\n59,32\n4,9\n6,35\n51,23\n1,17\n12,11\n65,67\n41,65\n37,65\n1,24\n21,8\n59,28\n17,14\n63,68\n20,19\n17,10\n63,69\n57,44\n55,56\n45,64\n25,27\n27,4\n22,23\n5,13\n19,14\n47,46\n49,4\n21,15\n63,58\n60,31\n25,28\n6,3\n61,38\n33,5\n58,37\n11,32\n21,7\n44,61\n55,45\n55,37\n35,22\n10,15\n36,5\n19,11\n59,31\n33,19\n30,5\n69,69\n69,63\n57,69\n5,33\n60,27\n29,7\n57,43\n61,61\n3,26\n13,33\n57,59\n66,39\n63,27\n33,11\n51,1\n52,67\n5,29\n35,3\n17,2\n9,31\n37,24\n61,23\n9,5\n68,35\n21,28\n2,25\n51,48\n68,49\n4,19\n43,66\n7,34\n13,15\n36,1\n42,63\n13,0\n23,7\n48,47\n56,31\n55,43\n47,45\n18,15\n56,45\n61,64\n48,45\n69,65\n40,11\n51,68\n51,51\n53,46\n3,30\n49,62\n4,13\n17,27\n38,69\n41,0\n5,23\n65,32\n9,35\n55,21\n65,55\n51,39\n67,51\n5,9\n39,5\n58,49\n21,17\n63,41\n21,18\n57,65\n53,51\n2,13\n53,0\n53,6\n27,17\n55,59\n61,42\n27,7\n25,25\n39,13\n62,53\n51,44\n2,27\n19,17\n58,65\n8,1\n30,23\n14,5\n33,3\n43,65\n18,27\n35,7\n11,35\n12,29\n57,68\n59,63\n44,19\n36,25\n68,37\n15,19\n53,39\n62,69\n35,4\n61,55\n59,43\n23,17\n69,45\n18,5\n50,59\n39,6\n69,32\n17,5\n11,8\n21,2\n39,4\n64,65\n33,2\n17,22\n33,50\n25,24\n44,51\n31,7\n11,38\n11,25\n63,59\n25,21\n42,7\n8,11\n33,9\n45,63\n62,63\n33,4\n66,59\n61,29\n5,27\n59,27\n55,20\n38,9\n8,7\n51,3\n23,1\n53,65\n69,55\n1,34\n70,49\n61,57\n22,9\n17,26\n17,12\n61,69\n49,43\n9,28\n33,26\n15,35\n13,34\n55,27\n68,45\n45,61\n59,47\n13,29\n59,33\n65,53\n10,1\n35,21\n13,27\n28,1\n23,10\n61,37\n69,57\n23,21\n5,28\n57,48\n41,21\n11,13\n20,11\n1,21\n61,66\n66,47\n63,26\n5,15\n3,20\n17,4\n43,5\n16,29\n63,44\n63,55\n55,69\n5,22\n37,11\n50,39\n59,39\n25,16\n48,1\n43,60\n13,6\n49,37\n3,32\n57,23\n46,69\n2,35\n37,1\n53,27\n31,22\n63,36\n46,43\n68,57\n45,67\n32,9\n48,65\n15,15\n8,29\n13,1\n55,41\n65,65\n13,31\n49,69\n19,6\n29,19\n32,23\n49,41\n15,24\n65,22\n15,33\n6,21\n7,9\n69,64\n63,23\n5,21\n15,1\n44,1\n11,27\n63,34\n15,13\n39,9\n63,20\n58,29\n28,21\n7,37\n39,65\n41,16\n21,6\n49,47\n47,61\n50,63\n23,15\n68,67\n64,57\n19,13\n69,61\n1,22\n27,3\n28,13\n19,31\n23,2\n3,31\n25,6\n61,47\n51,63\n59,64\n27,2\n7,33\n63,63\n65,42\n5,12\n12,15\n27,9\n15,7\n6,17\n17,17\n15,2\n59,61\n63,47\n57,33\n13,17\n47,67\n11,26\n20,3\n13,7\n17,33\n10,5\n57,32\n58,53\n7,18\n66,65\n6,5\n11,5\n41,9\n21,21\n69,43\n11,20\n41,14\n38,3\n67,69\n15,17\n45,58\n51,61\n54,23\n49,39\n59,29\n53,63\n45,69\n16,1\n55,51\n21,13\n56,47\n63,40\n63,37\n37,19\n43,3\n7,17\n27,5\n14,25\n17,3\n44,69\n31,8\n14,9\n14,7\n63,45\n4,1\n49,34\n19,44\n46,53\n38,17\n33,0\n50,55\n27,25\n63,21\n19,12\n35,10\n54,3\n65,50\n47,62\n38,65\n61,39\n33,1\n65,52\n5,5\n0,3\n63,33\n30,27\n29,27\n29,1\n48,67\n33,23\n46,5\n60,35\n39,14\n59,46\n51,49\n64,21\n69,60\n3,3\n59,58\n9,36\n9,37\n48,41\n23,5\n7,3\n61,65\n61,22\n3,15\n4,37\n43,20\n66,45\n69,66\n43,12\n54,43\n52,49\n15,23\n33,21\n36,67\n61,24\n5,7\n37,7\n60,55\n53,70\n52,1\n21,33\n53,69\n67,43\n61,34\n6,31\n55,55\n59,40\n16,17\n65,25\n24,29\n59,21\n66,63\n61,41\n17,24\n0,15\n17,19\n1,13\n23,3\n49,45\n39,2\n59,49\n31,25\n65,40\n7,7\n70,43\n57,63\n65,54\n18,1\n41,15\n25,19\n33,18\n5,24\n13,3\n64,37\n43,7\n31,9\n30,11\n56,63\n65,34\n67,39\n17,18\n65,37\n49,56\n59,25\n7,11\n65,38\n37,18\n5,3\n21,22\n47,69\n19,9\n70,39\n15,14\n40,3\n5,31\n19,21\n55,34\n67,49\n45,11\n17,23\n41,5\n33,6\n37,10\n55,2\n17,9\n57,39\n5,1\n9,10\n17,7\n60,23\n55,68\n5,11\n63,67\n59,65\n7,19\n51,56\n26,1\n30,3\n15,20\n19,15\n3,21\n59,51\n11,7\n61,26\n19,23\n22,11\n25,8\n18,17\n27,26\n17,29\n7,13\n65,33\n44,5\n22,13\n56,65\n24,19\n25,17\n55,66\n65,39\n32,19\n3,19\n9,15\n54,63\n55,23\n61,59\n21,11\n46,39\n57,40\n65,19\n65,59\n65,48\n64,47\n32,21\n1,5\n15,11\n65,23\n4,2" <> ...}
23```
24
25```elixir
26bytes =
27 puzzle_input
28 |> String.split("\n", trim: true)
29 |> Enum.map(fn row ->
30 [x, y] = String.split(row, ",")
31
32 {String.to_integer(x), String.to_integer(y)}
33 end)
34```
35
36<!-- livebook:{"output":true} -->
37
38```
39[
40 {21, 9},
41 {69, 53},
42 {31, 24},
43 {2, 9},
44 {50, 53},
45 {2, 5},
46 {3, 44},
47 {69, 49},
48 {25, 26},
49 {50, 31},
50 {68, 41},
51 {54, 67},
52 {19, 8},
53 {11, 9},
54 {9, 29},
55 {1, 31},
56 {13, 12},
57 {28, 5},
58 {69, 41},
59 {51, 66},
60 {53, 43},
61 {65, 35},
62 {40, 67},
63 {43, 13},
64 {21, 34},
65 {49, 3},
66 {65, 61},
67 {25, 9},
68 {39, 21},
69 {59, 37},
70 {11, 24},
71 {9, 30},
72 {63, 62},
73 {41, 69},
74 {6, 29},
75 {68, 47},
76 {45, 1},
77 {9, 1},
78 {11, 14},
79 {59, 19},
80 {67, 54},
81 {12, 5},
82 {41, 44},
83 {59, 45},
84 {3, 28},
85 {57, 42},
86 {7, 25},
87 {43, 11},
88 {31, ...},
89 {...},
90 ...
91]
92```
93
94```elixir
95Image.new!(71, 71, color: :forestgreen)
96|> Image.mutate(fn img ->
97 for x <- 0..70, y <- 0..70, {x, y} in Enum.take(bytes, 1024) do
98 Image.Draw.point(img, x, y, color: :firebrick)
99 end
100
101 img
102end)
103|> elem(1)
104|> Image.resize!(4, interpolate: :nearest)
105```
106
107```elixir
108defmodule Memory do
109 @d [{-1, 0}, {1, 0}, {0, -1}, {0, 1}]
110 def find_path(from, to, bytes), do: do_find([{0, from}], to, MapSet.new(bytes), %{})
111
112 def do_find([], _, _, _), do: :none
113
114 def do_find([{dist, to} | _], to, _, _visited), do: dist
115
116 def do_find([{dist, {x, y} = p} | rest], {w, h} = to, bytes, visited)
117 when not is_map_key(visited, p)
118 when dist < :erlang.map_get(p, visited)
119 do
120 visited = Map.put(visited, p, dist)
121
122 next =
123 for {dx, dy} <- @d,
124 (x + dx) in 0..w,
125 (y + dy) in 0..h,
126 p = {x + dx, y + dy},
127 p not in bytes,
128 not is_map_key(visited, p),
129 do: {dist + 1, p}
130
131 next
132 |> Enum.concat(rest)
133 |> Enum.sort()
134 |> do_find(to, bytes, visited)
135 end
136
137 def do_find([_ | rest], to, bytes, visited), do: do_find(rest, to, bytes, visited)
138end
139```
140
141<!-- livebook:{"output":true} -->
142
143```
144{:module, Memory, <<70, 79, 82, 49, 0, 0, 13, ...>>, {:do_find, 4}}
145```
146
147## Part 1
148
149## Part 1
150
151```elixir
152Memory.find_path({0, 0}, {70, 70}, Enum.take(bytes, 1024))
153```
154
155<!-- livebook:{"output":true} -->
156
157```
158250
159```
160
161## Part 2
162
163```elixir
164{x, y} =
165 bytes
166 |> Enum.reverse()
167 |> Stream.unfold(fn
168 [] -> nil
169 [_ | rest] = curr -> {curr, rest}
170 end)
171 |> Enum.find_value(fn [pos | fallen] ->
172 path = Memory.find_path({0, 0}, {70, 70}, fallen)
173
174 if path != :none do
175 pos
176 end
177 end)
178
179IO.puts("#{x},#{y}")
180```
181
182<!-- livebook:{"output":true} -->
183
184```
18556,8
186```
187
188<!-- livebook:{"output":true} -->
189
190```
191:ok
192```
193
194<!-- livebook:{"offset":7984,"stamp":{"token":"XCP.CPT4l_BNbZGxGbR_fK_dYfzmCSPzRQfyiJPfaGWsNChhlNQI36bgn8XXEOmsc56qlDi2H-j-H4aYpxwTYXzlirEAyckZaTUuHdujjNaTLq1pQEjB3uTTMbVmMkdf1KvN3g0","version":2}} -->