this repo has no description
hauleth.dev
1<!--
2 vim:ft=markdown --!>
3 livebook:{"persist_outputs":true}
4-->
5
6<!-- livebook:{"persist_outputs":true} -->
7
8# Advent of Code 2021
9
10## Setup
11
12```elixir
13Mix.install([
14 {:nx, github: "elixir-nx/nx", sparse: "nx"}
15])
16```
17
18```output
19:ok
20```
21
22## Day 1
23
24### Load input
25
26```elixir
27stream =
28 File.stream!("day1.txt")
29 |> Stream.map(&String.to_integer(String.trim(&1)))
30```
31
32```output
33#Stream<[
34 enum: %File.Stream{
35 line_or_bytes: :line,
36 modes: [:raw, :read_ahead, :binary],
37 path: "day1.txt",
38 raw: true
39 },
40 funs: [#Function<47.58486609/1 in Stream.map/2>]
41]>
42```
43
44### Task 1
45
46<!-- livebook:{"break_markdown":true} -->
47
48Compute count of consecutive increases
49
50```elixir
51stream
52|> Stream.chunk_every(2, 1, :discard)
53|> Enum.count(fn [a, b] -> a < b end)
54```
55
56```output
571688
58```
59
60### Task 2
61
62<!-- livebook:{"break_markdown":true} -->
63
64Compute count of consecutive increases of sums of trigrams.
65
66However we can notice, that if we have list like:
67
68$$
69[a, b, c, d]
70$$
71
72Then when we want to compare consecutive trigrams then we compare:
73
74$$
75a + b + c < b + c + d \\
76a < d
77$$
78
79So we can traverse each 4 elements and then just compare first and last one
80instead of summing and then traversing it again.
81
82```elixir
83stream
84|> Stream.chunk_every(4, 1, :discard)
85|> Enum.count(fn [a, _, _, b] -> a < b end)
86```
87
88```output
891728
90```
91
92## Day 2
93
94### Load input
95
96We do parsing there, as it will help us with the latter tasks. Pattern matching
97is the simplest approach there, as input is in form of:
98
99```
100forward 10
101up 20
102down 30
103```
104
105We need to `trim/1` input to make sure that the last newline will not interrupt
106`String.to_integer/1` calls.
107
108```elixir
109stream =
110 File.stream!("day2.txt")
111 |> Stream.map(fn input ->
112 case String.trim(input) do
113 "forward " <> n -> {:forward, String.to_integer(n)}
114 "up " <> n -> {:up, String.to_integer(n)}
115 "down " <> n -> {:down, String.to_integer(n)}
116 end
117 end)
118```
119
120```output
121#Stream<[
122 enum: %File.Stream{
123 line_or_bytes: :line,
124 modes: [:raw, :read_ahead, :binary],
125 path: "day2.txt",
126 raw: true
127 },
128 funs: [#Function<47.58486609/1 in Stream.map/2>]
129]>
130```
131
132### Task 1
133
134```elixir
135{h, d} =
136 stream
137 |> Enum.reduce({0, 0}, fn
138 {:forward, n}, {h, d} -> {h + n, d}
139 {:up, n}, {h, d} -> {h, d - n}
140 {:down, n}, {h, d} -> {h, d + n}
141 end)
142
143h * d
144```
145
146```output
1471499229
148```
149
150### Task 2
151
152```elixir
153{h, d, _} =
154 stream
155 |> Enum.reduce({0, 0, 0}, fn
156 {:forward, n}, {h, d, a} -> {h + n, d + a * n, a}
157 {:up, n}, {h, d, a} -> {h, d, a - n}
158 {:down, n}, {h, d, a} -> {h, d, a + n}
159 end)
160
161h * d
162```
163
164```output
1651340836560
166```
167
168## Day 3
169
170### Input
171
172```elixir
173stream =
174 File.stream!("day3.txt")
175 |> Enum.map(&String.trim/1)
176 |> Enum.map(&String.to_charlist/1)
177
178defmodule Day3 do
179 def count(list) do
180 Enum.reduce(list, List.duplicate(0, 12), fn input, acc ->
181 for {value, counter} <- Enum.zip(input, acc) do
182 case value do
183 ?1 -> counter + 1
184 ?0 -> counter
185 end
186 end
187 end)
188 end
189end
190```
191
192```output
193{:module, Day3, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:count, 1}}
194```
195
196### Task 1
197
198```elixir
199half = div(length(stream), 2)
200
201{a, b} =
202 stream
203 |> Day3.count()
204 |> Enum.reduce({0, 0}, fn elem, {a, b} ->
205 if elem > half do
206 {a * 2 + 1, b * 2}
207 else
208 {a * 2, b * 2 + 1}
209 end
210 end)
211
212a * b
213```
214
215```output
2163847100
217```
218
219### Task 2
220
221```elixir
222defmodule Day3.Task2 do
223 def reduce(list, cb), do: reduce(list, 0, cb)
224
225 defp reduce([elem], _, _), do: elem
226
227 defp reduce(list, at, cb) do
228 counts = Day3.count(list)
229
230 half = div(length(list), 2)
231 count = Enum.at(counts, at)
232
233 bit =
234 cond do
235 count == half and cb.(count + 1, half) -> ?1
236 count != half and cb.(count, half) -> ?1
237 true -> ?0
238 end
239
240 reduce(Enum.filter(list, &(Enum.at(&1, at) == bit)), at + 1, cb)
241 end
242end
243
244co2 = List.to_integer(Day3.Task2.reduce(stream, &</2), 2)
245o2 = List.to_integer(Day3.Task2.reduce(stream, &>/2), 2)
246
247co2 * o2
248```
249
250```output
2514105235
252```
253
254## Day 4
255
256### Input
257
258This time it is a little bit more convoluted, as there are 2 parts of the input.
259Fortunately we can easily disect the parts via pattern matching.
260
261Technically the conversion to the numbers is not needed, but it does no harm
262and provides additional layer of safety against some whitespace characters left there
263and here.
264
265The `Day4.win/2` function is manually unrolled, as it is easier to write than some
266random jumping in the list.
267
268<!-- livebook:{"disable_formatting":true} -->
269
270```elixir
271[numbers | bingos] =
272 File.read!("day4.txt")
273 |> String.split("\n\n", trim: true)
274
275numbers =
276 numbers
277 |> String.trim()
278 |> String.split(",")
279 |> Enum.map(&String.to_integer/1)
280
281bingos =
282 bingos
283 |> Enum.map(fn bingo ->
284 bingo
285 |> String.split(~r/\s+/, trim: true)
286 |> Enum.map(&String.to_integer/1)
287 end)
288
289defmodule Day4 do
290 def win(
291 [
292 a1, a2, a3, a4, a5,
293 b1, b2, b3, b4, b5,
294 c1, c2, c3, c4, c5,
295 d1, d2, d3, d4, d5,
296 e1, e2, e3, e4, e5
297 ],
298 nums
299 ) do
300 # Rows
301 all_in([a1, a2, a3, a4, a5], nums) or
302 all_in([b1, b3, b3, b4, b5], nums) or
303 all_in([c1, c2, c3, c4, c5], nums) or
304 all_in([d1, d2, d3, d4, d5], nums) or
305 all_in([e1, e2, e3, e4, e5], nums) or
306 # Columns
307 all_in([a1, b1, c1, d1, e1], nums) or
308 all_in([a2, b2, c2, d2, e2], nums) or
309 all_in([a3, b3, c3, d3, e3], nums) or
310 all_in([a4, b4, c4, d4, e4], nums) or
311 all_in([a5, b5, c5, d5, e5], nums)
312 end
313
314 def not_matched(bingo, nums) do
315 Enum.reject(bingo, &(&1 in nums))
316 end
317
318 defp all_in(list, nums) do
319 Enum.all?(list, &(&1 in nums))
320 end
321end
322```
323
324```output
325{:module, Day4, <<70, 79, 82, 49, 0, 0, 15, ...>>, {:all_in, 2}}
326```
327
328### Task 1
329
330We simply traverse the `numbers` list aggregating the numbers (order doesn't really matter,
331here we aggregate them in reverse order to speedup the code). When we have enough numbers
332that any of the `bingos` is winning one, then we halt the reduction and return computed
333result.
334
335```elixir
336numbers
337|> Enum.reduce_while([], fn elem, acc ->
338 matches = [elem | acc]
339
340 case Enum.find(bingos, &Day4.win(&1, matches)) do
341 nil -> {:cont, matches}
342 bingo -> {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
343 end
344end)
345```
346
347```output
34834506
349```
350
351### Task 2
352
353```elixir
354numbers
355|> Enum.reduce_while({bingos, []}, fn elem, {bingos, acc} ->
356 matches = [elem | acc]
357
358 case bingos do
359 [bingo] ->
360 if Day4.win(bingo, matches) do
361 {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
362 else
363 {:cont, {bingos, matches}}
364 end
365
366 _ ->
367 {:cont, {Enum.reject(bingos, &Day4.win(&1, matches)), matches}}
368 end
369end)
370```
371
372```output
3737686
374```
375
376## Day 5
377
378```elixir
379defmodule Day5 do
380 defmodule Point do
381 defstruct [:x, :y]
382
383 def parse(input) do
384 [x, y] = String.split(input, ",")
385
386 %__MODULE__{x: String.to_integer(x), y: String.to_integer(y)}
387 end
388 end
389
390 defmodule Line do
391 defstruct [:start, :finish]
392
393 def new(a, b) do
394 {start, finish} =
395 cond do
396 a.x < b.x -> {a, b}
397 a.y < b.y -> {a, b}
398 true -> {b, a}
399 end
400
401 %__MODULE__{start: start, finish: finish}
402 end
403
404 def horizontal?(a), do: a.start.y == a.finish.y
405 def vertical?(a), do: a.start.x == a.finish.x
406
407 def points(a) do
408 case {sign(a.finish.x - a.start.x), sign(a.finish.y - a.start.y)} do
409 {0, dy} -> for y <- a.start.y..a.finish.y//dy, do: {a.start.x, y}
410 {dx, 0} -> for x <- a.start.x..a.finish.x//dx, do: {x, a.start.y}
411 {dx, dy} -> Enum.zip(a.start.x..a.finish.x//dx, a.start.y..a.finish.y//dy)
412 end
413 end
414
415 def orientation(a) do
416 cond do
417 horizontal?(a) -> :horizontal
418 vertical?(a) -> :vertical
419 true -> :diagonal
420 end
421 end
422
423 defp sign(0), do: 0
424 defp sign(x) when x < 0, do: -1
425 defp sign(x) when x > 0, do: 1
426 end
427end
428
429lines =
430 File.stream!("day5.txt")
431 |> Stream.map(&String.trim/1)
432 |> Stream.map(fn input ->
433 [a, b] = String.split(input, " -> ")
434
435 pa = Day5.Point.parse(a)
436 pb = Day5.Point.parse(b)
437
438 Day5.Line.new(pa, pb)
439 end)
440```
441
442```output
443#Stream<[
444 enum: %File.Stream{
445 line_or_bytes: :line,
446 modes: [:raw, :read_ahead, :binary],
447 path: "day5.txt",
448 raw: true
449 },
450 funs: [#Function<47.58486609/1 in Stream.map/2>, #Function<47.58486609/1 in Stream.map/2>]
451]>
452```
453
454### Task 1
455
456```elixir
457lines
458|> Stream.filter(&(Day5.Line.orientation(&1) != :diagonal))
459|> Stream.flat_map(&Day5.Line.points/1)
460|> Enum.frequencies()
461|> Enum.count(fn {_k, v} -> v > 1 end)
462```
463
464```output
4655197
466```
467
468### Task 2
469
470```elixir
471lines
472|> Stream.flat_map(&Day5.Line.points/1)
473|> Enum.frequencies()
474|> Enum.count(fn {_k, v} -> v > 1 end)
475```
476
477```output
47818605
479```
480
481## Day 6
482
483```elixir
484initial = for i <- 0..8, into: %{}, do: {i, 0}
485
486counts =
487 File.read!("day6.txt")
488 |> String.trim()
489 |> String.split(",")
490 |> Enum.map(&String.to_integer/1)
491 |> Enum.frequencies()
492 |> Map.merge(initial, fn _, a, _ -> a end)
493
494defmodule Day6 do
495 def next(%{0 => next} = population) do
496 1..8
497 |> Map.new(&{&1 - 1, population[&1]})
498 |> Map.merge(%{6 => next, 8 => next}, fn _, v1, v2 -> v1 + v2 end)
499 end
500end
501```
502
503```output
504{:module, Day6, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:next, 1}}
505```
506
507### Task 1
508
509```elixir
5101..80
511|> Enum.reduce(counts, fn _, acc -> Day6.next(acc) end)
512|> Map.values()
513|> Enum.sum()
514```
515
516```output
517343441
518```
519
520### Task 2
521
522```elixir
5231..256
524|> Enum.reduce(counts, fn _, acc -> Day6.next(acc) end)
525|> Map.values()
526|> Enum.sum()
527```
528
529```output
5301569108373832
531```
532
533## Day 7
534
535```elixir
536input =
537 File.read!("day7.txt")
538 |> String.trim()
539 |> String.split(",")
540 |> Enum.map(&String.to_integer/1)
541```
542
543```output
544[1101, 1, 29, 67, 1102, 0, 1, 65, 1008, 65, 35, 66, 1005, 66, 28, 1, 67, 65, 20, 4, 0, 1001, 65, 1,
545 65, 1106, 0, 8, 99, 35, 67, 101, 99, 105, 32, 110, 39, 101, 115, 116, 32, 112, 97, 115, 32, 117,
546 110, 101, 32, 105, ...]
547```
548
549### Task 1
550
551```elixir
552mean = Enum.at(Enum.sort(input), div(length(input), 2))
553
554input
555|> Enum.map(&abs(&1 - mean))
556|> Enum.sum()
557```
558
559```output
560336721
561```
562
563### Task 2
564
565```elixir
566arith_sum = fn n -> div(n * n + n, 2) end
567
568max = Enum.max(input)
569
5700..max
571|> Enum.reduce(:infinity, fn n, acc ->
572 sum =
573 input
574 |> Enum.map(&arith_sum.(abs(&1 - n)))
575 |> Enum.sum()
576
577 if sum < acc, do: sum, else: acc
578end)
579```
580
581```output
58291638945
583```
584
585## Day 8
586
587```elixir
588input =
589 File.stream!("day8.txt")
590 |> Stream.map(fn line ->
591 line
592 |> String.split(" | ")
593 |> Enum.map(fn part ->
594 part
595 |> String.trim()
596 |> String.split(" ")
597 |> Enum.map(fn disp ->
598 disp
599 |> String.to_charlist()
600 |> Enum.sort()
601 |> List.to_string()
602 end)
603 end)
604 |> List.to_tuple()
605 end)
606```
607
608```output
609#Stream<[
610 enum: %File.Stream{
611 line_or_bytes: :line,
612 modes: [:raw, :read_ahead, :binary],
613 path: "day8.txt",
614 raw: true
615 },
616 funs: [#Function<47.58486609/1 in Stream.map/2>]
617]>
618```
619
620```elixir
621input
622|> Enum.map(fn {_, output} ->
623 Enum.count(output, &(byte_size(&1) in [2, 3, 4, 7]))
624end)
625|> Enum.sum()
626```
627
628```output
629390
630```
631
632```elixir
633defmodule Day8.Task2 do
634 def a --- b do
635 MapSet.difference(a, b)
636 end
637
638 def a +++ b do
639 MapSet.union(a, b)
640 end
641
642 def a <~> b do
643 MapSet.intersection(a, b)
644 end
645
646 def a <|> b do
647 (a +++ b) --- (a <~> b)
648 end
649
650 # 1. 7. 4. 2|3|5. 2|3|5. 2|3|5. 6|9|0. 6|9|0. 6|9|0. 8.
651 def deduce({cf, acf, bcdf, acdeg, acdfg, abdfg, abdefg, abcdfg, abcefg, abcdefg}) do
652 a = acf --- cf
653 eg = abcdefg --- (acf +++ bcdf)
654 bd = bcdf --- cf
655 abfg = abdefg <|> abcdfg <|> abcefg
656 b = abfg <~> bd
657 f = abfg <~> cf
658 g = abfg --- (a +++ b +++ f)
659 d = bd --- b
660 c = cf --- f
661 e = eg --- g
662
663 {a, b, c, d, e, f, g} =
664 [a, b, c, d, e, f, g]
665 |> Enum.map(&extract/1)
666 |> List.to_tuple()
667
668 [
669 # 0
670 [a, b, c, e, f, g],
671 # 1
672 [c, f],
673 # 2
674 [a, c, d, e, g],
675 # 3
676 [a, c, d, f, g],
677 # 4
678 [b, c, d, f],
679 # 5
680 [a, b, d, f, g],
681 # 6
682 [a, b, d, e, f, g],
683 # 7
684 [a, c, f],
685 # 8
686 [a, b, c, d, e, f, g],
687 # 9
688 [a, b, c, d, f, g]
689 ]
690 |> Enum.map(&List.to_string(Enum.sort(&1)))
691 |> Enum.with_index()
692 |> Map.new()
693 end
694
695 defp extract(a) do
696 [v] = MapSet.to_list(a)
697
698 v
699 end
700
701 def decode(matches, output) do
702 output
703 |> Enum.map(&matches[&1])
704 |> Integer.undigits()
705 end
706end
707
708input
709|> Enum.map(fn {input, output} ->
710 input
711 |> Enum.sort_by(&byte_size/1)
712 |> Enum.map(&MapSet.new(String.to_charlist(&1)))
713 |> List.to_tuple()
714 |> Day8.Task2.deduce()
715 |> Day8.Task2.decode(output)
716end)
717|> Enum.sum()
718```
719
720```output
721warning: variable "abdfg" is unused (if the variable is not meant to be used, prefix it with an underscore)
722 solutions.livemd#cell:19: Day8.Task2.deduce/1
723
724warning: variable "acdeg" is unused (if the variable is not meant to be used, prefix it with an underscore)
725 solutions.livemd#cell:19: Day8.Task2.deduce/1
726
727warning: variable "acdfg" is unused (if the variable is not meant to be used, prefix it with an underscore)
728 solutions.livemd#cell:19: Day8.Task2.deduce/1
729
730```
731
732```output
7331011785
734```