this repo has no description
hauleth.dev
1<!--
2 vim:ft=markdown --!>
3 livebook:{"persist_outputs":true}
4-->
5
6# Advent of Code 2021
7
8## Setup
9
10```elixir
11Mix.install([
12 {:nx, github: "elixir-nx/nx", sparse: "nx"}
13])
14```
15
16## Day 1
17
18### Load input
19
20```elixir
21stream =
22 File.stream!("day1.txt")
23 |> Stream.map(&String.to_integer(String.trim(&1)))
24```
25
26### Task 1
27
28<!-- livebook:{"break_markdown":true} -->
29
30Compute count of consecutive increases
31
32```elixir
33stream
34|> Stream.chunk_every(2, 1, :discard)
35|> Enum.count(fn [a, b] -> a < b end)
36```
37
38### Task 2
39
40<!-- livebook:{"break_markdown":true} -->
41
42Compute count of consecutive increases of sums of trigrams.
43
44However we can notice, that if we have list like:
45
46$$
47[a, b, c, d]
48$$
49
50Then when we want to compare consecutive trigrams then we compare:
51
52$$
53a + b + c < b + c + d \\
54a < d
55$$
56
57So we can traverse each 4 elements and then just compare first and last one
58instead of summing and then traversing it again.
59
60```elixir
61stream
62|> Stream.chunk_every(4, 1, :discard)
63|> Enum.count(fn [a, _, _, b] -> a < b end)
64```
65
66## Day 2
67
68### Load input
69
70We do parsing there, as it will help us with the latter tasks. Pattern matching
71is the simplest approach there, as input is in form of:
72
73```
74forward 10
75up 20
76down 30
77```
78
79We need to `trim/1` input to make sure that the last newline will not interrupt
80`String.to_integer/1` calls.
81
82```elixir
83stream =
84 File.stream!("day2.txt")
85 |> Stream.map(fn input ->
86 case String.trim(input) do
87 "forward " <> n -> {:forward, String.to_integer(n)}
88 "up " <> n -> {:up, String.to_integer(n)}
89 "down " <> n -> {:down, String.to_integer(n)}
90 end
91 end)
92```
93
94### Task 1
95
96```elixir
97{h, d} =
98 stream
99 |> Enum.reduce({0, 0}, fn
100 {:forward, n}, {h, d} -> {h + n, d}
101 {:up, n}, {h, d} -> {h, d - n}
102 {:down, n}, {h, d} -> {h, d + n}
103 end)
104
105h * d
106```
107
108### Task 2
109
110```elixir
111{h, d, _} =
112 stream
113 |> Enum.reduce({0, 0, 0}, fn
114 {:forward, n}, {h, d, a} -> {h + n, d + a * n, a}
115 {:up, n}, {h, d, a} -> {h, d, a - n}
116 {:down, n}, {h, d, a} -> {h, d, a + n}
117 end)
118
119h * d
120```
121
122## Day 3
123
124### Input
125
126```elixir
127stream =
128 File.stream!("day3.txt")
129 |> Enum.map(&String.trim/1)
130 |> Enum.map(&String.to_charlist/1)
131
132defmodule Day3 do
133 def count(list) do
134 Enum.reduce(list, List.duplicate(0, 12), fn input, acc ->
135 for {value, counter} <- Enum.zip(input, acc) do
136 case value do
137 ?1 -> counter + 1
138 ?0 -> counter
139 end
140 end
141 end)
142 end
143end
144```
145
146### Task 1
147
148```elixir
149half = div(length(stream), 2)
150
151{a, b} =
152 stream
153 |> Day3.count()
154 |> Enum.reduce({0, 0}, fn elem, {a, b} ->
155 if elem > half do
156 {a * 2 + 1, b * 2}
157 else
158 {a * 2, b * 2 + 1}
159 end
160 end)
161
162a * b
163```
164
165### Task 2
166
167```elixir
168defmodule Day3.Task2 do
169 def reduce(list, cb), do: reduce(list, 0, cb)
170
171 defp reduce([elem], _, _), do: elem
172
173 defp reduce(list, at, cb) do
174 counts = Day3.count(list)
175
176 half = div(length(list), 2)
177 count = Enum.at(counts, at)
178
179 bit =
180 cond do
181 count == half and cb.(count + 1, half) -> ?1
182 count != half and cb.(count, half) -> ?1
183 true -> ?0
184 end
185
186 reduce(Enum.filter(list, &(Enum.at(&1, at) == bit)), at + 1, cb)
187 end
188end
189
190co2 = List.to_integer(Day3.Task2.reduce(stream, &</2), 2)
191o2 = List.to_integer(Day3.Task2.reduce(stream, &>/2), 2)
192
193co2 * o2
194```
195
196## Day 4
197
198### Input
199
200This time it is a little bit more convoluted, as there are 2 parts of the input.
201Fortunately we can easily disect the parts via pattern matching.
202
203Technically the conversion to the numbers is not needed, but it does no harm
204and provides additional layer of safety against some whitespace characters left there
205and here.
206
207The `Day4.win/2` function is manually unrolled, as it is easier to write than some
208random jumping in the list.
209
210<!-- livebook:{"disable_formatting":true} -->
211
212```elixir
213[numbers | bingos] =
214 File.read!("day4.txt")
215 |> String.split("\n\n", trim: true)
216
217numbers =
218 numbers
219 |> String.trim()
220 |> String.split(",")
221 |> Enum.map(&String.to_integer/1)
222
223bingos =
224 bingos
225 |> Enum.map(fn bingo ->
226 bingo
227 |> String.split(~r/\s+/, trim: true)
228 |> Enum.map(&String.to_integer/1)
229 end)
230
231defmodule Day4 do
232 def win(
233 [
234 a1, a2, a3, a4, a5,
235 b1, b2, b3, b4, b5,
236 c1, c2, c3, c4, c5,
237 d1, d2, d3, d4, d5,
238 e1, e2, e3, e4, e5
239 ],
240 nums
241 ) do
242 # Rows
243 all_in([a1, a2, a3, a4, a5], nums) or
244 all_in([b1, b3, b3, b4, b5], nums) or
245 all_in([c1, c2, c3, c4, c5], nums) or
246 all_in([d1, d2, d3, d4, d5], nums) or
247 all_in([e1, e2, e3, e4, e5], nums) or
248 # Columns
249 all_in([a1, b1, c1, d1, e1], nums) or
250 all_in([a2, b2, c2, d2, e2], nums) or
251 all_in([a3, b3, c3, d3, e3], nums) or
252 all_in([a4, b4, c4, d4, e4], nums) or
253 all_in([a5, b5, c5, d5, e5], nums)
254 end
255
256 def not_matched(bingo, nums) do
257 Enum.reject(bingo, &(&1 in nums))
258 end
259
260 defp all_in(list, nums) do
261 Enum.all?(list, &(&1 in nums))
262 end
263end
264```
265
266### Task 1
267
268We simply traverse the `numbers` list aggregating the numbers (order doesn't really matter,
269here we aggregate them in reverse order to speedup the code). When we have enough numbers
270that any of the `bingos` is winning one, then we halt the reduction and return computed
271result.
272
273```elixir
274numbers
275|> Enum.reduce_while([], fn elem, acc ->
276 matches = [elem | acc]
277
278 case Enum.find(bingos, &Day4.win(&1, matches)) do
279 nil -> {:cont, matches}
280 bingo -> {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
281 end
282end)
283```
284
285### Task 2
286
287```elixir
288numbers
289|> Enum.reduce_while({bingos, []}, fn elem, {bingos, acc} ->
290 matches = [elem | acc]
291
292 case bingos do
293 [bingo] ->
294 if Day4.win(bingo, matches) do
295 {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
296 else
297 {:cont, {bingos, matches}}
298 end
299
300 _ ->
301 {:cont, {Enum.reject(bingos, &Day4.win(&1, matches)), matches}}
302 end
303end)
304```
305
306## Day 5
307
308```elixir
309defmodule Day5 do
310 defmodule Point do
311 defstruct [:x, :y]
312
313 def parse(input) do
314 [x, y] = String.split(input, ",")
315
316 %__MODULE__{x: String.to_integer(x), y: String.to_integer(y)}
317 end
318 end
319
320 defmodule Line do
321 defstruct [:start, :finish]
322
323 def new(a, b) do
324 {start, finish} =
325 cond do
326 a.x < b.x -> {a, b}
327 a.y < b.y -> {a, b}
328 true -> {b, a}
329 end
330
331 %__MODULE__{start: start, finish: finish}
332 end
333
334 def horizontal?(a), do: a.start.y == a.finish.y
335 def vertical?(a), do: a.start.x == a.finish.x
336
337 def intersect?(a, b) do
338 a.start.x in b.start.x..b.finish.y and b.start.y in a.start.y..a.finish.y
339 end
340
341 def overlapping?(a, b) do
342 {a.start.x, a.finish.x} == {b.start.x, b.finish.x} or
343 {a.start.y, a.finish.y} == {b.start.y, b.start.y}
344 end
345
346 def orientation(a) do
347 cond do
348 horizontal?(a) -> :horizontal
349 vertical?(a) -> :vertical
350 true -> :diagonal
351 end
352 end
353 end
354end
355
356lines =
357 File.stream!("day5.txt")
358 |> Stream.map(&String.trim/1)
359 |> Stream.map(fn input ->
360 [a, b] = String.split(input, " -> ")
361
362 pa = Day5.Point.parse(a)
363 pb = Day5.Point.parse(b)
364
365 Day5.Line.new(pa, pb)
366 end)
367
368x_min =
369 lines
370 |> Enum.map(& &1.start.x)
371 |> Enum.min()
372
373x_max =
374 lines
375 |> Enum.map(& &1.finish.x)
376 |> Enum.max()
377
378y_min =
379 lines
380 |> Enum.map(& &1.start.y)
381 |> Enum.min()
382
383y_max =
384 lines
385 |> Enum.map(& &1.finish.y)
386 |> Enum.max()
387
388{x_min, x_max, y_min, y_max}
389
390arr = Nx.iota({1000, 1000})
391
392arr = Nx.subtract(arr, arr)
393
394lines
395|> Enum.flat_map(fn a ->
396 case Day5.Line.orientation(a) do
397 :diagonal -> [(a.start.x - a.finish.x) / (a.start.y - a.finish.y)]
398 _ -> []
399 end
400end)
401```
402
403### Task 1
404
405```elixir
406%{horizontal: horiz, vertical: vert} = Enum.group_by(lines, &Day5.Line.orientation/1)
407
408horiz = Enum.sort_by(horiz, &{&1.start.x, &1.start.y})
409vert = Enum.sort_by(vert, & &1.start.x)
410```
411
412## Day 6
413
414```elixir
415initial = for i <- 0..8, into: %{}, do: {i, 0}
416
417counts =
418 File.read!("day6.txt")
419 |> String.trim()
420 |> String.split(",")
421 |> Enum.map(&String.to_integer/1)
422 |> Enum.frequencies()
423 |> Map.merge(initial, fn _, a, _ -> a end)
424```
425
426### Task 1
427
428```elixir
4291..80
430|> Enum.reduce(counts, fn _, %{0 => next} = acc ->
431 1..8
432 |> Map.new(fn idx -> {idx - 1, acc[idx]} end)
433 |> Map.update!(6, &(&1 + next))
434 |> Map.put(8, next)
435end)
436|> Map.values()
437|> Enum.sum()
438```
439
440### Task 2
441
442```elixir
4431..256
444|> Enum.reduce(counts, fn _, %{0 => next} = acc ->
445 1..8
446 |> Map.new(fn idx -> {idx - 1, acc[idx]} end)
447 |> Map.update!(6, &(&1 + next))
448 |> Map.put(8, next)
449end)
450|> Map.values()
451|> Enum.sum()
452```