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 {:kino, github: "livebook-dev/kino"}
16])
17```
18
19```output
20* Getting nx (https://github.com/elixir-nx/nx.git)
21remote: Enumerating objects: 10786, done.
22remote: Counting objects: 100% (2841/2841), done.
23remote: Compressing objects: 100% (635/635), done.
24remote: Total 10786 (delta 2376), reused 2515 (delta 2195), pack-reused 7945
25origin/HEAD set to main
26* Getting kino (https://github.com/livebook-dev/kino.git)
27remote: Enumerating objects: 488, done.
28remote: Counting objects: 100% (488/488), done.
29remote: Compressing objects: 100% (351/351), done.
30remote: Total 488 (delta 269), reused 274 (delta 118), pack-reused 0
31origin/HEAD set to main
32==> kino
33Compiling 19 files (.ex)
34Generated kino app
35==> nx
36Compiling 23 files (.ex)
37Generated nx app
38```
39
40```output
41:ok
42```
43
44## Day 1
45
46### Load input
47
48```elixir
49stream =
50 File.stream!("day1.txt")
51 |> Stream.map(&String.to_integer(String.trim(&1)))
52```
53
54```output
55#Stream<[
56 enum: %File.Stream{
57 line_or_bytes: :line,
58 modes: [:raw, :read_ahead, :binary],
59 path: "day1.txt",
60 raw: true
61 },
62 funs: [#Function<47.58486609/1 in Stream.map/2>]
63]>
64```
65
66### Task 1
67
68<!-- livebook:{"break_markdown":true} -->
69
70Compute count of consecutive increases
71
72```elixir
73stream
74|> Stream.chunk_every(2, 1, :discard)
75|> Enum.count(fn [a, b] -> a < b end)
76```
77
78```output
791688
80```
81
82### Task 2
83
84<!-- livebook:{"break_markdown":true} -->
85
86Compute count of consecutive increases of sums of trigrams.
87
88However we can notice, that if we have list like:
89
90$$
91[a, b, c, d]
92$$
93
94Then when we want to compare consecutive trigrams then we compare:
95
96$$
97a + b + c < b + c + d \\
98a < d
99$$
100
101So we can traverse each 4 elements and then just compare first and last one
102instead of summing and then traversing it again.
103
104```elixir
105stream
106|> Stream.chunk_every(4, 1, :discard)
107|> Enum.count(fn [a, _, _, b] -> a < b end)
108```
109
110```output
1111728
112```
113
114## Day 2
115
116### Load input
117
118We do parsing there, as it will help us with the latter tasks. Pattern matching
119is the simplest approach there, as input is in form of:
120
121```
122forward 10
123up 20
124down 30
125```
126
127We need to `trim/1` input to make sure that the last newline will not interrupt
128`String.to_integer/1` calls.
129
130```elixir
131stream =
132 File.stream!("day2.txt")
133 |> Stream.map(fn input ->
134 case String.trim(input) do
135 "forward " <> n -> {:forward, String.to_integer(n)}
136 "up " <> n -> {:up, String.to_integer(n)}
137 "down " <> n -> {:down, String.to_integer(n)}
138 end
139 end)
140```
141
142```output
143#Stream<[
144 enum: %File.Stream{
145 line_or_bytes: :line,
146 modes: [:raw, :read_ahead, :binary],
147 path: "day2.txt",
148 raw: true
149 },
150 funs: [#Function<47.58486609/1 in Stream.map/2>]
151]>
152```
153
154### Task 1
155
156```elixir
157{h, d} =
158 stream
159 |> Enum.reduce({0, 0}, fn
160 {:forward, n}, {h, d} -> {h + n, d}
161 {:up, n}, {h, d} -> {h, d - n}
162 {:down, n}, {h, d} -> {h, d + n}
163 end)
164
165h * d
166```
167
168```output
1691499229
170```
171
172### Task 2
173
174```elixir
175{h, d, _} =
176 stream
177 |> Enum.reduce({0, 0, 0}, fn
178 {:forward, n}, {h, d, a} -> {h + n, d + a * n, a}
179 {:up, n}, {h, d, a} -> {h, d, a - n}
180 {:down, n}, {h, d, a} -> {h, d, a + n}
181 end)
182
183h * d
184```
185
186```output
1871340836560
188```
189
190## Day 3
191
192### Input
193
194```elixir
195stream =
196 File.stream!("day3.txt")
197 |> Enum.map(&String.trim/1)
198 |> Enum.map(&String.to_charlist/1)
199
200defmodule Day3 do
201 def count(list) do
202 Enum.reduce(list, List.duplicate(0, 12), fn input, acc ->
203 for {value, counter} <- Enum.zip(input, acc) do
204 case value do
205 ?1 -> counter + 1
206 ?0 -> counter
207 end
208 end
209 end)
210 end
211end
212```
213
214```output
215{:module, Day3, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:count, 1}}
216```
217
218### Task 1
219
220```elixir
221half = div(length(stream), 2)
222
223{a, b} =
224 stream
225 |> Day3.count()
226 |> Enum.reduce({0, 0}, fn elem, {a, b} ->
227 if elem > half do
228 {a * 2 + 1, b * 2}
229 else
230 {a * 2, b * 2 + 1}
231 end
232 end)
233
234a * b
235```
236
237```output
2383847100
239```
240
241### Task 2
242
243```elixir
244defmodule Day3.Task2 do
245 def reduce(list, cb), do: reduce(list, 0, cb)
246
247 defp reduce([elem], _, _), do: elem
248
249 defp reduce(list, at, cb) do
250 counts = Day3.count(list)
251
252 half = div(length(list), 2)
253 count = Enum.at(counts, at)
254
255 bit =
256 cond do
257 count == half and cb.(count + 1, half) -> ?1
258 count != half and cb.(count, half) -> ?1
259 true -> ?0
260 end
261
262 reduce(Enum.filter(list, &(Enum.at(&1, at) == bit)), at + 1, cb)
263 end
264end
265
266co2 = List.to_integer(Day3.Task2.reduce(stream, &</2), 2)
267o2 = List.to_integer(Day3.Task2.reduce(stream, &>/2), 2)
268
269co2 * o2
270```
271
272```output
2734105235
274```
275
276## Day 4
277
278### Input
279
280This time it is a little bit more convoluted, as there are 2 parts of the input.
281Fortunately we can easily disect the parts via pattern matching.
282
283Technically the conversion to the numbers is not needed, but it does no harm
284and provides additional layer of safety against some whitespace characters left there
285and here.
286
287The `Day4.win/2` function is manually unrolled, as it is easier to write than some
288random jumping in the list.
289
290<!-- livebook:{"disable_formatting":true} -->
291
292```elixir
293[numbers | bingos] =
294 File.read!("day4.txt")
295 |> String.split("\n\n", trim: true)
296
297numbers =
298 numbers
299 |> String.trim()
300 |> String.split(",")
301 |> Enum.map(&String.to_integer/1)
302
303bingos =
304 bingos
305 |> Enum.map(fn bingo ->
306 bingo
307 |> String.split(~r/\s+/, trim: true)
308 |> Enum.map(&String.to_integer/1)
309 end)
310
311defmodule Day4 do
312 def win(
313 [
314 a1, a2, a3, a4, a5,
315 b1, b2, b3, b4, b5,
316 c1, c2, c3, c4, c5,
317 d1, d2, d3, d4, d5,
318 e1, e2, e3, e4, e5
319 ],
320 nums
321 ) do
322 # Rows
323 all_in([a1, a2, a3, a4, a5], nums) or
324 all_in([b1, b3, b3, b4, b5], nums) or
325 all_in([c1, c2, c3, c4, c5], nums) or
326 all_in([d1, d2, d3, d4, d5], nums) or
327 all_in([e1, e2, e3, e4, e5], nums) or
328 # Columns
329 all_in([a1, b1, c1, d1, e1], nums) or
330 all_in([a2, b2, c2, d2, e2], nums) or
331 all_in([a3, b3, c3, d3, e3], nums) or
332 all_in([a4, b4, c4, d4, e4], nums) or
333 all_in([a5, b5, c5, d5, e5], nums)
334 end
335
336 def not_matched(bingo, nums) do
337 Enum.reject(bingo, &(&1 in nums))
338 end
339
340 defp all_in(list, nums) do
341 Enum.all?(list, &(&1 in nums))
342 end
343end
344```
345
346```output
347{:module, Day4, <<70, 79, 82, 49, 0, 0, 15, ...>>, {:all_in, 2}}
348```
349
350### Task 1
351
352We simply traverse the `numbers` list aggregating the numbers (order doesn't really matter,
353here we aggregate them in reverse order to speedup the code). When we have enough numbers
354that any of the `bingos` is winning one, then we halt the reduction and return computed
355result.
356
357```elixir
358numbers
359|> Enum.reduce_while([], fn elem, acc ->
360 matches = [elem | acc]
361
362 case Enum.find(bingos, &Day4.win(&1, matches)) do
363 nil -> {:cont, matches}
364 bingo -> {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
365 end
366end)
367```
368
369```output
37034506
371```
372
373### Task 2
374
375```elixir
376numbers
377|> Enum.reduce_while({bingos, []}, fn elem, {bingos, acc} ->
378 matches = [elem | acc]
379
380 case bingos do
381 [bingo] ->
382 if Day4.win(bingo, matches) do
383 {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
384 else
385 {:cont, {bingos, matches}}
386 end
387
388 _ ->
389 {:cont, {Enum.reject(bingos, &Day4.win(&1, matches)), matches}}
390 end
391end)
392```
393
394```output
3957686
396```
397
398## Day 5
399
400```elixir
401defmodule Day5 do
402 defmodule Point do
403 defstruct [:x, :y]
404
405 def parse(input) do
406 [x, y] = String.split(input, ",")
407
408 %__MODULE__{x: String.to_integer(x), y: String.to_integer(y)}
409 end
410 end
411
412 defmodule Line do
413 defstruct [:start, :finish]
414
415 def new(a, b) do
416 {start, finish} =
417 cond do
418 a.x < b.x -> {a, b}
419 a.y < b.y -> {a, b}
420 true -> {b, a}
421 end
422
423 %__MODULE__{start: start, finish: finish}
424 end
425
426 def horizontal?(a), do: a.start.y == a.finish.y
427 def vertical?(a), do: a.start.x == a.finish.x
428
429 def points(a) do
430 case {sign(a.finish.x - a.start.x), sign(a.finish.y - a.start.y)} do
431 {0, dy} -> for y <- a.start.y..a.finish.y//dy, do: {a.start.x, y}
432 {dx, 0} -> for x <- a.start.x..a.finish.x//dx, do: {x, a.start.y}
433 {dx, dy} -> Enum.zip(a.start.x..a.finish.x//dx, a.start.y..a.finish.y//dy)
434 end
435 end
436
437 def orientation(a) do
438 cond do
439 horizontal?(a) -> :horizontal
440 vertical?(a) -> :vertical
441 true -> :diagonal
442 end
443 end
444
445 defp sign(0), do: 0
446 defp sign(x) when x < 0, do: -1
447 defp sign(x) when x > 0, do: 1
448 end
449end
450
451lines =
452 File.stream!("day5.txt")
453 |> Stream.map(&String.trim/1)
454 |> Stream.map(fn input ->
455 [a, b] = String.split(input, " -> ")
456
457 pa = Day5.Point.parse(a)
458 pb = Day5.Point.parse(b)
459
460 Day5.Line.new(pa, pb)
461 end)
462```
463
464```output
465#Stream<[
466 enum: %File.Stream{
467 line_or_bytes: :line,
468 modes: [:raw, :read_ahead, :binary],
469 path: "day5.txt",
470 raw: true
471 },
472 funs: [#Function<47.58486609/1 in Stream.map/2>, #Function<47.58486609/1 in Stream.map/2>]
473]>
474```
475
476### Task 1
477
478```elixir
479lines
480|> Stream.filter(&(Day5.Line.orientation(&1) != :diagonal))
481|> Stream.flat_map(&Day5.Line.points/1)
482|> Enum.frequencies()
483|> Enum.count(fn {_k, v} -> v > 1 end)
484```
485
486```output
4875197
488```
489
490### Task 2
491
492```elixir
493lines
494|> Stream.flat_map(&Day5.Line.points/1)
495|> Enum.frequencies()
496|> Enum.count(fn {_k, v} -> v > 1 end)
497```
498
499```output
50018605
501```
502
503## Day 6
504
505```elixir
506initial = for i <- 0..8, into: %{}, do: {i, 0}
507
508counts =
509 File.read!("day6.txt")
510 |> String.trim()
511 |> String.split(",")
512 |> Enum.map(&String.to_integer/1)
513 |> Enum.frequencies()
514 |> Map.merge(initial, fn _, a, _ -> a end)
515
516defmodule Day6 do
517 def next(%{0 => next} = population) do
518 1..8
519 |> Map.new(&{&1 - 1, population[&1]})
520 |> Map.merge(%{6 => next, 8 => next}, fn _, v1, v2 -> v1 + v2 end)
521 end
522end
523```
524
525```output
526{:module, Day6, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:next, 1}}
527```
528
529### Task 1
530
531```elixir
5321..80
533|> Enum.reduce(counts, fn _, acc -> Day6.next(acc) end)
534|> Map.values()
535|> Enum.sum()
536```
537
538```output
539343441
540```
541
542### Task 2
543
544```elixir
5451..256
546|> Enum.reduce(counts, fn _, acc -> Day6.next(acc) end)
547|> Map.values()
548|> Enum.sum()
549```
550
551```output
5521569108373832
553```
554
555## Day 7
556
557```elixir
558input =
559 File.read!("day7.txt")
560 |> String.trim()
561 |> String.split(",")
562 |> Enum.map(&String.to_integer/1)
563```
564
565```output
566[1101, 1, 29, 67, 1102, 0, 1, 65, 1008, 65, 35, 66, 1005, 66, 28, 1, 67, 65, 20, 4, 0, 1001, 65, 1,
567 65, 1106, 0, 8, 99, 35, 67, 101, 99, 105, 32, 110, 39, 101, 115, 116, 32, 112, 97, 115, 32, 117,
568 110, 101, 32, 105, ...]
569```
570
571### Task 1
572
573```elixir
574mean = Enum.at(Enum.sort(input), div(length(input), 2))
575
576input
577|> Enum.map(&abs(&1 - mean))
578|> Enum.sum()
579```
580
581```output
582336721
583```
584
585### Task 2
586
587```elixir
588arith_sum = fn n -> div(n * n + n, 2) end
589
590max = Enum.max(input)
591
592mean = Enum.sum(input) / length(input)
593
594[floor(mean), ceil(mean)]
595|> Enum.map(fn n ->
596 input
597 |> Enum.map(&arith_sum.(abs(&1 - n)))
598 |> Enum.sum()
599end)
600|> Enum.min()
601```
602
603```output
60491638945
605```
606
607## Day 8
608
609```elixir
610input =
611 File.stream!("day8.txt")
612 |> Stream.map(fn line ->
613 line
614 |> String.split(" | ")
615 |> Enum.map(fn part ->
616 part
617 |> String.trim()
618 |> String.split(" ")
619 |> Enum.map(fn disp ->
620 # Sort characters in each entry to simplify later work
621 disp
622 |> String.to_charlist()
623 |> Enum.sort()
624 |> List.to_string()
625 end)
626 end)
627 |> List.to_tuple()
628 end)
629```
630
631```output
632#Stream<[
633 enum: %File.Stream{
634 line_or_bytes: :line,
635 modes: [:raw, :read_ahead, :binary],
636 path: "day8.txt",
637 raw: true
638 },
639 funs: [#Function<47.58486609/1 in Stream.map/2>]
640]>
641```
642
643### Task 1
644
645We simply need to count all occurences of the values that have 2, 3, 4, or 7 highlighted
646segments.
647
648```elixir
649input
650|> Enum.map(fn {_, output} ->
651 Enum.count(output, &(byte_size(&1) in [2, 3, 4, 7]))
652end)
653|> Enum.sum()
654```
655
656```output
657390
658```
659
660### Task 2
661
662```elixir
663defmodule Day8.Task2 do
664 defp a --- b, do: MapSet.difference(a, b)
665
666 defp a +++ b, do: MapSet.union(a, b)
667
668 defp a <~> b, do: MapSet.intersection(a, b)
669
670 # 1. 7. 4. 2|3|5. 2|3|5. 2|3|5. 6|9|0. 6|9|0. 6|9|0. 8.
671 def deduce([cf, acf, bcdf, acdeg, acdfg, abdfg, abdefg, abcdfg, abcefg, abcdefg]) do
672 eg = abcdefg --- (acf +++ bcdf)
673 bd = bcdf --- cf
674 adg = acdeg <~> acdfg <~> abdfg
675 abfg = abdefg <~> abcdfg <~> abcefg
676 a = acf --- cf
677 b = abfg <~> bd
678 f = abfg <~> cf
679 g = adg <~> eg
680 d = adg <~> bd
681 c = cf --- f
682 e = eg --- g
683
684 [a, b, c, d, e, f, g] =
685 [a, b, c, d, e, f, g]
686 |> Enum.map(&extract/1)
687
688 [
689 # 0
690 [a, b, c, e, f, g],
691 # 1
692 [c, f],
693 # 2
694 [a, c, d, e, g],
695 # 3
696 [a, c, d, f, g],
697 # 4
698 [b, c, d, f],
699 # 5
700 [a, b, d, f, g],
701 # 6
702 [a, b, d, e, f, g],
703 # 7
704 [a, c, f],
705 # 8
706 [a, b, c, d, e, f, g],
707 # 9
708 [a, b, c, d, f, g]
709 ]
710 |> Enum.map(&List.to_string(Enum.sort(&1)))
711 |> Enum.with_index()
712 |> Map.new()
713 end
714
715 defp extract(a) do
716 # Just additional sanity check
717 [v] = MapSet.to_list(a)
718
719 v
720 end
721
722 def decode(matches, output) do
723 output
724 |> Enum.map(&matches[&1])
725 |> Integer.undigits()
726 end
727end
728
729input
730|> Enum.map(fn {input, output} ->
731 input
732 |> Enum.sort_by(&byte_size/1)
733 |> Enum.map(&MapSet.new(String.to_charlist(&1)))
734 |> Day8.Task2.deduce()
735 |> Day8.Task2.decode(output)
736end)
737|> Enum.sum()
738```
739
740```output
7411011785
742```
743
744## Day 9
745
746```elixir
747input =
748 File.read!("day9.txt")
749 # ~S[110
750 # 101
751 # 110]
752 |> String.split("\n", trim: true)
753 |> Enum.map(&String.to_charlist(String.trim(&1)))
754 |> Nx.tensor(names: [:y, :x])
755 |> Nx.subtract(?0)
756 |> Nx.add(1)
757
758{width, height} = shape = Nx.shape(input)
759```
760
761```output
762{100, 100}
763```
764
765### Task 1
766
767```elixir
768padded = Nx.pad(input, 99, [{0, 0, 0}, {1, 1, 0}])
769
770shifted = Nx.slice_axis(padded, 0, height, :x)
771
772x1 = Nx.less(input, shifted)
773
774shifted = Nx.slice_axis(padded, 2, height, :x)
775
776x2 = Nx.less(input, shifted)
777
778x = Nx.logical_and(x1, x2)
779
780padded = Nx.pad(input, 99, [{1, 1, 0}, {0, 0, 0}])
781
782shifted = Nx.slice_axis(padded, 0, width, :y)
783
784y1 = Nx.less(input, shifted)
785
786shifted = Nx.slice_axis(padded, 2, width, :y)
787
788y2 = Nx.less(input, shifted)
789
790y = Nx.logical_and(y1, y2)
791
792minimas = Nx.logical_and(x, y)
793
794input
795|> Nx.multiply(minimas)
796|> Nx.sum()
797|> Nx.to_number()
798```
799
800```output
801452
802```
803
804### Task 2
805
806```elixir
807input
808|> Nx.equal(10)
809|> Nx.logical_not()
810|> Nx.select(Nx.iota(shape), 9999)
811|> Nx.to_flat_list()
812|> Enum.reject(&(&1 == 9999))
813|> Enum.map(fn point -> {div(point, width), rem(point, width)} end)
814|> Enum.reduce([], fn {y, x} = point, basins ->
815 basin_left = Enum.find_index(basins, &({y, x - 1} in &1))
816 basin_up = Enum.find_index(basins, &({y - 1, x} in &1))
817
818 case {basin_left, basin_up} do
819 {nil, nil} ->
820 [MapSet.new([point]) | basins]
821
822 {idx, nil} ->
823 List.update_at(basins, idx, &MapSet.put(&1, point))
824
825 {nil, idx} ->
826 List.update_at(basins, idx, &MapSet.put(&1, point))
827
828 {idx, idx} ->
829 List.update_at(basins, idx, &MapSet.put(&1, point))
830
831 {idx1, idx2} ->
832 {old, basins} = List.pop_at(basins, max(idx1, idx2))
833
834 List.update_at(basins, min(idx1, idx2), &(&1 |> MapSet.union(old) |> MapSet.put(point)))
835 end
836end)
837|> Enum.map(&MapSet.size/1)
838|> Enum.sort(:desc)
839|> Enum.take(3)
840|> Enum.reduce(&*/2)
841```
842
843```output
8441263735
845```