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