this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 14
4
5```elixir
6Mix.install([:kino_aoc])
7```
8
9## Section
10
11<!-- livebook:{"attrs":{"assign_to":"puzzle_input","day":"14","session_secret":"ADVENT_OF_CODE_SESSION","year":"2023"},"chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
12
13```elixir
14{:ok, puzzle_input} =
15 KinoAOC.download_puzzle("2023", "14", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
16```
17
18<!-- livebook:{"output":true} -->
19
20```
21{:ok,
22 "####....#..O#O..#.....OO.O#..O.......O.#OO.#...O.O..O..O..OO.##.O#...........#....##O#..O#.O.O......\n....#..#.........O.O#..OO#OO....O.....#O.#.O##..#...OO#OOO.O...#...O..#.O.#....##.....#O............\n...#O..#........#....O...O.......O#.##.O.......O..O#O#.#OO....O..O.......#O.........#O.#.O...#...#..\n#O...O...O.O..O..OO.#...O.O#....##O.##..#.OOO#...OO.#...OOO.#.O.#....#....O..##.....OO....#..O...#O.\n.#.......##.#...#...O............O...#......#..#.OO...O#....O.#..........O..O.OOO#.#O#....OO..#.#O.#\n..#..........#..O.O#.....O.OOO.#.##...##...OO..#..#.O#..OO.O#..#O..#O.O#.O.O#..#.#OOO..#OO.O.##..#..\n#..#....O.#O.O.#...O......O...###O.#...OOO#..#.O..#O.O..O.#OO...O...#..#OOO.....O...O...OO..##....O.\n...##....#..#.O#..#O...#.#......##.OO.O.......O....#O#..OOOO#....O.#OO.#O....#...O#O#..O.#.....O....\n...#O....#.#O........O.O#O....O...#.O....#....#...#O.....O.O.O.#.#.......#.........#O#........O.....\n...O...#.O#....#O#O.....O..O#...#O........O.#.##.....O.#...O..#...##O.#.#O#..O..##......#O.#...O#..#\n#..OO#.#.........O#......#O.##.O#...O..#.#.#.OO........#......#....#..#.......O.#O.##.###.####....O.\nO..O...#O..O..##.O..............#O......OOO#...#.#.#.........OO....OO....O#.#.O#.O.........#.......O\n..O#.#....O..#....#OO..##...#..#...O..##O...##.O..O.OO.#.###...O..#.OO..O#...#......#.....O.#..O..#.\nO..####.O..O.OO##.O...O..O#.#O..O...O..........#O.#..#..O..O#..O##O.O.#O.#..O.OO.O..#...O.#O..O.O.#.\n.......O..........#...OO.O#.#.#OOOO...OO#O..O.#.#......#O.#.#...#.O#......O.O.OO...#.##..#.O.#..O..#\n.#.....#O........#.O...#........O............#O......##.O..O..#.#......O#O..O...O..O.#.O...O.#..OOOO\n.......O#...O...OO#.....#..O.#O..##..#O.#....OO.##.#O#......O#..O....OO..#...#O...O...##O..O###..OOO\n...O...#..O..O..#O.O......#.O...#..O#..#..O.OO...O....O.#O#..###O....O..##OOO.#O.....#...#.....#...O\nO...OO.#...#...O.O..#O.OO..O.#.#.#O#.O.#.O..O#O.....##O..O#.O..O........O...#.......O#.#...#.#..OO..\n..OO..#.#.O#.OOO.....##.O..OOO##O#.O..O.##OOO...O..##.O......#O.##..#O..O....#.##.O###...##..O......\n.......O..OO....##......O..O#O.O.O#....#O.....#....O..O.OO...#.O.#..#....#.O..#O....O......##O.....#\n......O..#...O..O#O.#.O.......#.O#.....O.O#..#.#...O..##......O.O..O#.#.#..#.O.#O.O#.O.#......#.O...\n....O.....O..O.......#.O.OO.....O##....##.#OO..#O..#.#...##..O#O.O...O..OO..##....O#O..O....#...O.#O\n.......O.##O.#O#.........O#.OO....###.OO..O.#..#.....OO.O.O...O......O..O..O....O...#.#....#....#O..\nO..#O......#.O..#O.O.#......O#..#.O##..#.#.O.....#.O...O..OO..####.#...##......#.....#O#......OO.O.#\n...OOO.#O....O#O...O.##OO..#....OO...O.#.....OO.#OOO.#.........#....O....#.#..O.#O#.#...O.O...O.#...\n..O.#.OOO..O.#...#OO.#.O.##OO..O..####.#....#.OO##O..#.O..O#..O#....#..O#..#.O.O..O...O...O.....O.O.\n.#.#O.O..#.O.O##.....O#..#..#..OO##...OOO.#O...#.O#...#O....#OO.OO..#.OO#.OO#O#............O......#.\nO#..#....O...#.#.O....#.OOO.#.OO.....OO###.O..#..#.O..#...#.#....O#.O#....#.#.O.#.....#....O.....O#.\nO..O.#.....#.....OOO..O..OOO.#..#.##.O..O.......#..O.##O#...#.#.......#.#....#.O.O..OO..#.O..#..O#O.\n...O...O#....#O.......#........#.O.O..O.#O#...O...#..O.#..OO#O...#........O...#.....OO.#...#.O...#.#\nO.#.O#...O#....#OO.O.##......O...##..#..O#.#.#O.....OOO..#O....#...O..O#O....#.#....OO.#..#.....OO.#\n...O#..O.#.#..O........O.....#.........#.....O.......O......#..#.#O....#O.O#O.#..##O#....#O...O.O...\n#..O.O...O#..O.O.#O..#...O#....#..#...O..#O...O.....O..OO#OOO#OOO...#.O...#.OO#O.....#O.#.........O.\nO.O...#....O#OO...O.OO..#..OO...#..O..O.O....#...#..O..OOO#.....#..OO.#O....O.#.O.OOO.#OO....##OO..O\n.#O#.#.##...###O..O#...#.O.#.O...O#.O.....O....O..OOO....#...O...OO.....#.#O#O..#O......#.O.....#.#O\nO.#O.OO......##......O..OOO##.OOO.#..O...O.O#..#O.#O.O......#................##..#....#O......#.....\n........#.....##...OO.O......#..#.......#O.....O....O....#O.##..OO...O...O..........#..O.....OO...#.\n#..O.#.......O......O#.O..........#O#.O#.#..#..O..O#.O.O..O.O........O......O..O.O..O.O..#O....O#.#.\n...#...OO#..#..##.O.....O...........O.#O#O...##...O..#..#..O....#..O#O.##..O##......OOO....##..###.#\n.#..#....OOO......O#O...##O..O.OO...O..#.....#.O..##...." <> ...}
23```
24
25```elixir
26puzzle_input =
27 """
28 O....#....
29 O.OO#....#
30 .....##...
31 OO.#O....O
32 .O.....O#.
33 O.#..O.#.#
34 ..O..#O..O
35 .......O..
36 #....###..
37 #OO..#....
38 """
39```
40
41<!-- livebook:{"output":true} -->
42
43```
44"O....#....\nO.OO#....#\n.....##...\nOO.#O....O\n.O.....O#.\nO.#..O.#.#\n..O..#O..O\n.......O..\n#....###..\n#OO..#....\n"
45```
46
47```elixir
48map =
49 puzzle_input
50 |> String.split("\n", trim: true)
51 |> Enum.with_index(0)
52 |> Enum.flat_map(fn {line, y} ->
53 line
54 |> String.to_charlist()
55 |> Enum.with_index()
56 |> Enum.filter(fn {p, _} -> p != ?. end)
57 |> Enum.map(fn
58 {?#, x} -> {{x, y}, :cube}
59 {?O, x} -> {{x, y}, :round}
60 end)
61 end)
62 |> Map.new()
63
64{width, height} = Enum.reduce(map, {0, 0}, fn {{x, y}, _}, {w, h} -> {max(x, w), max(y, h)} end)
65```
66
67<!-- livebook:{"output":true} -->
68
69```
70{9, 9}
71```
72
73## Part 1
74
75```elixir
76defmodule Day14 do
77 def weight(map, width, height) do
78 for(col <- 0..width, do: Day14.column_weight(map, col, height))
79 |> Enum.sum()
80 end
81
82 def column_weight(map, col, height) do
83 do_column_weight(map, col, height, 0, 0, height)
84 end
85
86 defp do_column_weight(_map, _col, -1, stack, sum, height) do
87 sum + sum(height + 1, stack)
88 end
89
90 defp do_column_weight(map, col, row, stack, sum, height) do
91 case Map.fetch(map, {col, row}) do
92 :error ->
93 do_column_weight(map, col, row - 1, stack, sum, height)
94
95 {:ok, :cube} ->
96 do_column_weight(map, col, row - 1, 0, sum + sum(height - row, stack), height)
97
98 {:ok, :round} ->
99 do_column_weight(map, col, row - 1, stack + 1, sum, height)
100 end
101 end
102
103 def sum(_, 0), do: 0
104 def sum(s, n), do: div((2 * s - n + 1) * n, 2)
105
106 def print(map, width, height) do
107 for y <- 0..height do
108 row =
109 for x <- 0..width do
110 case Map.get(map, {x, y}) do
111 nil -> " "
112 :cube -> "#"
113 :round -> "O"
114 end
115 end
116
117 ["#{y}\t", row, "\n"]
118 end
119 |> IO.puts()
120 end
121end
122```
123
124<!-- livebook:{"output":true} -->
125
126```
127{:module, Day14, <<70, 79, 82, 49, 0, 0, 15, ...>>, {:print, 3}}
128```
129
130```elixir
131Day14.print(map, width, height)
132```
133
134<!-- livebook:{"output":true} -->
135
136```
1370 O #
1381 O OO# #
1392 ##
1403 OO #O O
1414 O O#
1425 O # O # #
1436 O #O O
1447 O
1458 # ###
1469 #OO #
147
148```
149
150<!-- livebook:{"output":true} -->
151
152```
153:ok
154```
155
156```elixir
157Day14.weight(map, width, height)
158```
159
160<!-- livebook:{"output":true} -->
161
162```
163136
164```
165
166## Part 2
167
168```elixir
169defmodule Day14.Part2 do
170 def round(map, width, height) do
171 map
172 |> move(width, height)
173 |> rotate(height)
174 |> move(height, width)
175 |> rotate(width)
176 |> move(width, height)
177 |> rotate(height)
178 |> move(height, width)
179 |> rotate(width)
180 end
181
182 def move(map, width, height) do
183 for(x <- 0..width, col = move_column(map, x, height), c <- col, into: %{}, do: c)
184 end
185
186 def move_column(map, col, height) do
187 do_move(map, col, height, 0, [])
188 end
189
190 defp do_move(_map, col, -1, stack, acc) do
191 expand_stack(0, col, stack) ++ acc
192 end
193
194 defp do_move(map, col, row, stack, acc) do
195 case Map.fetch(map, {col, row}) do
196 :error ->
197 do_move(map, col, row - 1, stack, acc)
198
199 {:ok, :cube} ->
200 do_move(
201 map,
202 col,
203 row - 1,
204 0,
205 expand_stack(row + 1, col, stack) ++ [{{col, row}, :cube} | acc]
206 )
207
208 {:ok, :round} ->
209 do_move(map, col, row - 1, stack + 1, acc)
210 end
211 end
212
213 defp expand_stack(start, col, len) do
214 for y <- 0..(len - 1)//1, do: {{col, start + y}, :round}
215 end
216
217 def rotate(map, height) do
218 Map.new(map, fn {{x, y}, v} ->
219 {{height - y, x}, v}
220 end)
221 end
222
223 def rounds_with_memoisation(map, width, height) do
224 Stream.iterate(map, &round(&1, width, height))
225 end
226end
227```
228
229<!-- livebook:{"output":true} -->
230
231```
232{:module, Day14.Part2, <<70, 79, 82, 49, 0, 0, 17, ...>>, {:rounds_with_memoisation, 3}}
233```
234
235```elixir
236{nmap, _, _} =
237 Day14.Part2.rounds_with_memoisation(map, width, height)
238 |> Stream.with_index()
239 |> Enum.reduce_while(%{}, fn {map, idx}, set ->
240 case Map.fetch(set, map) do
241 :error -> {:cont, Map.put(set, map, idx)}
242 {:ok, prev} -> {:halt, {map, idx, prev}}
243 end
244 end)
245```
246
247<!-- livebook:{"output":true} -->
248
249```
250{%{
251 {9, 8} => :round,
252 {4, 6} => :round,
253 {9, 9} => :round,
254 {7, 7} => :round,
255 {9, 7} => :round,
256 {1, 5} => :round,
257 {7, 5} => :cube,
258 {8, 1} => :round,
259 {0, 8} => :cube,
260 {9, 5} => :cube,
261 {4, 1} => :cube,
262 {9, 6} => :round,
263 {5, 9} => :cube,
264 {8, 7} => :round,
265 {6, 4} => :round,
266 {5, 4} => :round,
267 {9, 1} => :cube,
268 {5, 6} => :cube,
269 {5, 2} => :cube,
270 {4, 9} => :round,
271 {2, 5} => :cube,
272 {3, 9} => :round,
273 {0, 9} => :cube,
274 {4, 8} => :round,
275 {6, 2} => :cube,
276 {7, 8} => :cube,
277 {6, 5} => :round,
278 {6, 8} => :cube,
279 {2, 3} => :round,
280 {5, 0} => :cube,
281 {5, 8} => :cube,
282 {7, 4} => :round,
283 {3, 3} => :cube,
284 {8, 4} => :cube,
285 {2, 9} => :round
286 }, 10, 3}
287```
288
289```elixir
290Day14.Part2.rounds_with_memoisation(map, width, height)
291|> Enum.take(11)
292|> Stream.each(&Day14.print(&1, width, height))
293|> Enum.map(&Day14.weight(&1, width, height))
294|> IO.inspect(charlists: :as_lists)
295```
296
297<!-- livebook:{"output":true} -->
298
299```
3000 O #
3011 O OO# #
3022 ##
3033 OO #O O
3044 O O#
3055 O # O # #
3066 O #O O
3077 O
3088 # ###
3099 #OO #
310
3110 #
3121 # O#
3132 OO##
3143 OO#
3154 OOO#
3165 O# O# #
3176 O#
3187 OOOO
3198 # O###
3209 # OO#
321
3220 #
3231 # O#
3242 ##
3253 O#
3264 OOO#
3275 O# O# #
3286 O# O
3297 OOO
3308 # OO###
3319 # OOO# O
332
3330 #
3341 # O#
3352 ##
3363 O#
3374 OOO#
3385 O# O# #
3396 O# O
3407 OOO
3418 # O### O
3429 # OOO# O
343
3440 #
3451 # O#
3462 ##
3473 O#
3484 OOO#
3495 O# O# #
3506 O# O
3517 OOO
3528 # O### O
3539 # OO# OO
354
3550 #
3561 # O#
3572 ##
3583 #
3594 OOO#
3605 O# O# #
3616 O# O
3627 OOOO
3638 # O### O
3649 # OO# OO
365
3660 #
3671 # O#
3682 ##
3693 #
3704 OOO#
3715 O# O# #
3726 O# O
3737 OOOO
3748 # ### O
3759 # OOO# OO
376
3770 #
3781 # O#
3792 ##
3803 O#
3814 OO#
3825 O# O# #
3836 O# O
3847 OOOO
3858 # ### O
3869 # OOO# OO
387
3880 #
3891 # O#
3902 ##
3913 O#
3924 OO#
3935 O# O# #
3946 O#
3957 OOOO
3968 # O### O
3979 # OOO# OO
398
3990 #
4001 # O#
4012 ##
4023 O#
4034 OOO#
4045 O# O# #
4056 O#
4067 OOOO
4078 # O### O
4089 # OOO# O
409
4100 #
4111 # O#
4122 ##
4133 O#
4144 OOO#
4155 O# O# #
4166 O# O
4177 OOO
4188 # O### O
4199 # OOO# O
420
421[136, 129, 114, 110, 110, 105, 103, 106, 111, 114, 110]
422```
423
424<!-- livebook:{"output":true} -->
425
426```
427[136, 129, 114, 110, 110, 105, 103, 106, 111, 114, 110]
428```
429
430<!-- livebook:{"offset":13089,"stamp":{"token":"XCP.6NDtt8fJ01JLOq3nTevL25H4mHLTDc6Od4j4bkK8EzYDIEbnkcC_afNOcboznLxeJd_Vr-eQOTfSeVj0rfhlPWRbNSo_OLjTWZxTnB_TdqgAr5J0iWjRjf2BDccO40DsHw","version":2}} -->