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:ok
21```
22
23## Day 1
24
25### Load input
26
27```elixir
28stream =
29 File.stream!("day1.txt")
30 |> Stream.map(&String.to_integer(String.trim(&1)))
31```
32
33```output
34#Stream<[
35 enum: %File.Stream{
36 line_or_bytes: :line,
37 modes: [:raw, :read_ahead, :binary],
38 path: "day1.txt",
39 raw: true
40 },
41 funs: [#Function<47.58486609/1 in Stream.map/2>]
42]>
43```
44
45### Task 1
46
47<!-- livebook:{"break_markdown":true} -->
48
49Compute count of consecutive increases
50
51```elixir
52stream
53|> Stream.chunk_every(2, 1, :discard)
54|> Enum.count(fn [a, b] -> a < b end)
55```
56
57```output
581688
59```
60
61### Task 2
62
63<!-- livebook:{"break_markdown":true} -->
64
65Compute count of consecutive increases of sums of trigrams.
66
67However we can notice, that if we have list like:
68
69$$
70[a, b, c, d]
71$$
72
73Then when we want to compare consecutive trigrams then we compare:
74
75$$
76a + b + c < b + c + d \\
77a < d
78$$
79
80So we can traverse each 4 elements and then just compare first and last one
81instead of summing and then traversing it again.
82
83```elixir
84stream
85|> Stream.chunk_every(4, 1, :discard)
86|> Enum.count(fn [a, _, _, b] -> a < b end)
87```
88
89```output
901728
91```
92
93## Day 2
94
95### Load input
96
97We do parsing there, as it will help us with the latter tasks. Pattern matching
98is the simplest approach there, as input is in form of:
99
100```
101forward 10
102up 20
103down 30
104```
105
106We need to `trim/1` input to make sure that the last newline will not interrupt
107`String.to_integer/1` calls.
108
109```elixir
110stream =
111 File.stream!("day2.txt")
112 |> Stream.map(fn input ->
113 case String.trim(input) do
114 "forward " <> n -> {:forward, String.to_integer(n)}
115 "up " <> n -> {:up, String.to_integer(n)}
116 "down " <> n -> {:down, String.to_integer(n)}
117 end
118 end)
119```
120
121```output
122#Stream<[
123 enum: %File.Stream{
124 line_or_bytes: :line,
125 modes: [:raw, :read_ahead, :binary],
126 path: "day2.txt",
127 raw: true
128 },
129 funs: [#Function<47.58486609/1 in Stream.map/2>]
130]>
131```
132
133### Task 1
134
135```elixir
136{h, d} =
137 stream
138 |> Enum.reduce({0, 0}, fn
139 {:forward, n}, {h, d} -> {h + n, d}
140 {:up, n}, {h, d} -> {h, d - n}
141 {:down, n}, {h, d} -> {h, d + n}
142 end)
143
144h * d
145```
146
147```output
1481499229
149```
150
151### Task 2
152
153```elixir
154{h, d, _} =
155 stream
156 |> Enum.reduce({0, 0, 0}, fn
157 {:forward, n}, {h, d, a} -> {h + n, d + a * n, a}
158 {:up, n}, {h, d, a} -> {h, d, a - n}
159 {:down, n}, {h, d, a} -> {h, d, a + n}
160 end)
161
162h * d
163```
164
165```output
1661340836560
167```
168
169## Day 3
170
171### Input
172
173```elixir
174stream =
175 File.stream!("day3.txt")
176 |> Enum.map(&String.trim/1)
177 |> Enum.map(&String.to_charlist/1)
178
179defmodule Day3 do
180 def count(list) do
181 Enum.reduce(list, List.duplicate(0, 12), fn input, acc ->
182 for {value, counter} <- Enum.zip(input, acc) do
183 case value do
184 ?1 -> counter + 1
185 ?0 -> counter
186 end
187 end
188 end)
189 end
190end
191```
192
193```output
194{:module, Day3, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:count, 1}}
195```
196
197### Task 1
198
199```elixir
200half = div(length(stream), 2)
201
202{a, b} =
203 stream
204 |> Day3.count()
205 |> Enum.reduce({0, 0}, fn elem, {a, b} ->
206 if elem > half do
207 {a * 2 + 1, b * 2}
208 else
209 {a * 2, b * 2 + 1}
210 end
211 end)
212
213a * b
214```
215
216```output
2173847100
218```
219
220### Task 2
221
222```elixir
223defmodule Day3.Task2 do
224 def reduce(list, cb), do: reduce(list, 0, cb)
225
226 defp reduce([elem], _, _), do: elem
227
228 defp reduce(list, at, cb) do
229 counts = Day3.count(list)
230
231 half = div(length(list), 2)
232 count = Enum.at(counts, at)
233
234 bit =
235 cond do
236 count == half and cb.(count + 1, half) -> ?1
237 count != half and cb.(count, half) -> ?1
238 true -> ?0
239 end
240
241 reduce(Enum.filter(list, &(Enum.at(&1, at) == bit)), at + 1, cb)
242 end
243end
244
245co2 = List.to_integer(Day3.Task2.reduce(stream, &</2), 2)
246o2 = List.to_integer(Day3.Task2.reduce(stream, &>/2), 2)
247
248co2 * o2
249```
250
251```output
2524105235
253```
254
255## Day 4
256
257### Input
258
259This time it is a little bit more convoluted, as there are 2 parts of the input.
260Fortunately we can easily disect the parts via pattern matching.
261
262Technically the conversion to the numbers is not needed, but it does no harm
263and provides additional layer of safety against some whitespace characters left there
264and here.
265
266The `Day4.win/2` function is manually unrolled, as it is easier to write than some
267random jumping in the list.
268
269<!-- livebook:{"disable_formatting":true} -->
270
271```elixir
272[numbers | bingos] =
273 File.read!("day4.txt")
274 |> String.split("\n\n", trim: true)
275
276numbers =
277 numbers
278 |> String.trim()
279 |> String.split(",")
280 |> Enum.map(&String.to_integer/1)
281
282bingos =
283 bingos
284 |> Enum.map(fn bingo ->
285 bingo
286 |> String.split(~r/\s+/, trim: true)
287 |> Enum.map(&String.to_integer/1)
288 end)
289
290defmodule Day4 do
291 def win(
292 [
293 a1, a2, a3, a4, a5,
294 b1, b2, b3, b4, b5,
295 c1, c2, c3, c4, c5,
296 d1, d2, d3, d4, d5,
297 e1, e2, e3, e4, e5
298 ],
299 nums
300 ) do
301 # Rows
302 all_in([a1, a2, a3, a4, a5], nums) or
303 all_in([b1, b3, b3, b4, b5], nums) or
304 all_in([c1, c2, c3, c4, c5], nums) or
305 all_in([d1, d2, d3, d4, d5], nums) or
306 all_in([e1, e2, e3, e4, e5], nums) or
307 # Columns
308 all_in([a1, b1, c1, d1, e1], nums) or
309 all_in([a2, b2, c2, d2, e2], nums) or
310 all_in([a3, b3, c3, d3, e3], nums) or
311 all_in([a4, b4, c4, d4, e4], nums) or
312 all_in([a5, b5, c5, d5, e5], nums)
313 end
314
315 def not_matched(bingo, nums) do
316 Enum.reject(bingo, &(&1 in nums))
317 end
318
319 defp all_in(list, nums) do
320 Enum.all?(list, &(&1 in nums))
321 end
322end
323```
324
325```output
326{:module, Day4, <<70, 79, 82, 49, 0, 0, 15, ...>>, {:all_in, 2}}
327```
328
329### Task 1
330
331We simply traverse the `numbers` list aggregating the numbers (order doesn't really matter,
332here we aggregate them in reverse order to speedup the code). When we have enough numbers
333that any of the `bingos` is winning one, then we halt the reduction and return computed
334result.
335
336```elixir
337numbers
338|> Enum.reduce_while([], fn elem, acc ->
339 matches = [elem | acc]
340
341 case Enum.find(bingos, &Day4.win(&1, matches)) do
342 nil -> {:cont, matches}
343 bingo -> {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
344 end
345end)
346```
347
348```output
34934506
350```
351
352### Task 2
353
354```elixir
355numbers
356|> Enum.reduce_while({bingos, []}, fn elem, {bingos, acc} ->
357 matches = [elem | acc]
358
359 case bingos do
360 [bingo] ->
361 if Day4.win(bingo, matches) do
362 {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
363 else
364 {:cont, {bingos, matches}}
365 end
366
367 _ ->
368 {:cont, {Enum.reject(bingos, &Day4.win(&1, matches)), matches}}
369 end
370end)
371```
372
373```output
3747686
375```
376
377## Day 5
378
379```elixir
380defmodule Day5 do
381 defmodule Point do
382 defstruct [:x, :y]
383
384 def parse(input) do
385 [x, y] = String.split(input, ",")
386
387 %__MODULE__{x: String.to_integer(x), y: String.to_integer(y)}
388 end
389 end
390
391 defmodule Line do
392 defstruct [:start, :finish]
393
394 def new(a, b) do
395 {start, finish} =
396 cond do
397 a.x < b.x -> {a, b}
398 a.y < b.y -> {a, b}
399 true -> {b, a}
400 end
401
402 %__MODULE__{start: start, finish: finish}
403 end
404
405 def horizontal?(a), do: a.start.y == a.finish.y
406 def vertical?(a), do: a.start.x == a.finish.x
407
408 def points(a) do
409 case {sign(a.finish.x - a.start.x), sign(a.finish.y - a.start.y)} do
410 {0, dy} -> for y <- a.start.y..a.finish.y//dy, do: {a.start.x, y}
411 {dx, 0} -> for x <- a.start.x..a.finish.x//dx, do: {x, a.start.y}
412 {dx, dy} -> Enum.zip(a.start.x..a.finish.x//dx, a.start.y..a.finish.y//dy)
413 end
414 end
415
416 def orientation(a) do
417 cond do
418 horizontal?(a) -> :horizontal
419 vertical?(a) -> :vertical
420 true -> :diagonal
421 end
422 end
423
424 defp sign(0), do: 0
425 defp sign(x) when x < 0, do: -1
426 defp sign(x) when x > 0, do: 1
427 end
428end
429
430lines =
431 File.stream!("day5.txt")
432 |> Stream.map(&String.trim/1)
433 |> Stream.map(fn input ->
434 [a, b] = String.split(input, " -> ")
435
436 pa = Day5.Point.parse(a)
437 pb = Day5.Point.parse(b)
438
439 Day5.Line.new(pa, pb)
440 end)
441```
442
443```output
444#Stream<[
445 enum: %File.Stream{
446 line_or_bytes: :line,
447 modes: [:raw, :read_ahead, :binary],
448 path: "day5.txt",
449 raw: true
450 },
451 funs: [#Function<47.58486609/1 in Stream.map/2>, #Function<47.58486609/1 in Stream.map/2>]
452]>
453```
454
455### Task 1
456
457```elixir
458lines
459|> Stream.filter(&(Day5.Line.orientation(&1) != :diagonal))
460|> Stream.flat_map(&Day5.Line.points/1)
461|> Enum.frequencies()
462|> Enum.count(fn {_k, v} -> v > 1 end)
463```
464
465```output
4665197
467```
468
469### Task 2
470
471```elixir
472lines
473|> Stream.flat_map(&Day5.Line.points/1)
474|> Enum.frequencies()
475|> Enum.count(fn {_k, v} -> v > 1 end)
476```
477
478```output
47918605
480```
481
482## Day 6
483
484```elixir
485initial = for i <- 0..8, into: %{}, do: {i, 0}
486
487counts =
488 File.read!("day6.txt")
489 |> String.trim()
490 |> String.split(",")
491 |> Enum.map(&String.to_integer/1)
492 |> Enum.frequencies()
493 |> Map.merge(initial, fn _, a, _ -> a end)
494
495defmodule Day6 do
496 def next(%{0 => next} = population) do
497 1..8
498 |> Map.new(&{&1 - 1, population[&1]})
499 |> Map.merge(%{6 => next, 8 => next}, fn _, v1, v2 -> v1 + v2 end)
500 end
501end
502```
503
504```output
505{:module, Day6, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:next, 1}}
506```
507
508### Task 1
509
510```elixir
5111..80
512|> Enum.reduce(counts, fn _, acc -> Day6.next(acc) end)
513|> Map.values()
514|> Enum.sum()
515```
516
517```output
518343441
519```
520
521### Task 2
522
523```elixir
5241..256
525|> Enum.reduce(counts, fn _, acc -> Day6.next(acc) end)
526|> Map.values()
527|> Enum.sum()
528```
529
530```output
5311569108373832
532```
533
534## Day 7
535
536```elixir
537input =
538 File.read!("day7.txt")
539 |> String.trim()
540 |> String.split(",")
541 |> Enum.map(&String.to_integer/1)
542```
543
544```output
545[1101, 1, 29, 67, 1102, 0, 1, 65, 1008, 65, 35, 66, 1005, 66, 28, 1, 67, 65, 20, 4, 0, 1001, 65, 1,
546 65, 1106, 0, 8, 99, 35, 67, 101, 99, 105, 32, 110, 39, 101, 115, 116, 32, 112, 97, 115, 32, 117,
547 110, 101, 32, 105, ...]
548```
549
550### Task 1
551
552```elixir
553median = Enum.at(Enum.sort(input), div(length(input), 2))
554
555input
556|> Enum.map(&abs(&1 - median))
557|> Enum.sum()
558```
559
560```output
561336721
562```
563
564### Task 2
565
566```elixir
567arith_sum = fn n -> div(n * n + n, 2) end
568
569max = Enum.max(input)
570
571mean = Enum.sum(input) / length(input)
572
573[floor(mean), ceil(mean)]
574|> Enum.map(fn n ->
575 input
576 |> Enum.map(&arith_sum.(abs(&1 - n)))
577 |> Enum.sum()
578end)
579|> Enum.min()
580```
581
582```output
58391638945
584```
585
586## Day 8
587
588```elixir
589input =
590 File.stream!("day8.txt")
591 |> Stream.map(fn line ->
592 line
593 |> String.split(" | ")
594 |> Enum.map(fn part ->
595 part
596 |> String.trim()
597 |> String.split(" ")
598 |> Enum.map(fn disp ->
599 # Sort characters in each entry to simplify later work
600 disp
601 |> String.to_charlist()
602 |> Enum.sort()
603 |> List.to_string()
604 end)
605 end)
606 |> List.to_tuple()
607 end)
608```
609
610```output
611#Stream<[
612 enum: %File.Stream{
613 line_or_bytes: :line,
614 modes: [:raw, :read_ahead, :binary],
615 path: "day8.txt",
616 raw: true
617 },
618 funs: [#Function<47.58486609/1 in Stream.map/2>]
619]>
620```
621
622### Task 1
623
624We simply need to count all occurences of the values that have 2, 3, 4, or 7 highlighted
625segments.
626
627```elixir
628input
629|> Enum.map(fn {_, output} ->
630 Enum.count(output, &(byte_size(&1) in [2, 3, 4, 7]))
631end)
632|> Enum.sum()
633```
634
635```output
636390
637```
638
639### Task 2
640
641```elixir
642defmodule Day8.Task2 do
643 defp a --- b, do: MapSet.difference(a, b)
644
645 defp a +++ b, do: MapSet.union(a, b)
646
647 defp a <~> b, do: MapSet.intersection(a, b)
648
649 # 1. 7. 4. 2|3|5. 2|3|5. 2|3|5. 6|9|0. 6|9|0. 6|9|0. 8.
650 def deduce([cf, acf, bcdf, acdeg, acdfg, abdfg, abdefg, abcdfg, abcefg, abcdefg]) do
651 eg = abcdefg --- (acf +++ bcdf)
652 bd = bcdf --- cf
653 adg = acdeg <~> acdfg <~> abdfg
654 abfg = abdefg <~> abcdfg <~> abcefg
655 a = acf --- cf
656 b = abfg <~> bd
657 f = abfg <~> cf
658 g = adg <~> eg
659 d = adg <~> bd
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
667 [
668 # 0
669 [a, b, c, e, f, g],
670 # 1
671 [c, f],
672 # 2
673 [a, c, d, e, g],
674 # 3
675 [a, c, d, f, g],
676 # 4
677 [b, c, d, f],
678 # 5
679 [a, b, d, f, g],
680 # 6
681 [a, b, d, e, f, g],
682 # 7
683 [a, c, f],
684 # 8
685 [a, b, c, d, e, f, g],
686 # 9
687 [a, b, c, d, f, g]
688 ]
689 |> Enum.map(&List.to_string(Enum.sort(&1)))
690 |> Enum.with_index()
691 |> Map.new()
692 end
693
694 defp extract(a) do
695 # Just additional sanity check
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 |> Day8.Task2.deduce()
714 |> Day8.Task2.decode(output)
715end)
716|> Enum.sum()
717```
718
719```output
7201011785
721```
722
723## Day 9
724
725```elixir
726input =
727 File.read!("day9.txt")
728 |> String.split("\n", trim: true)
729 |> Enum.map(&String.to_charlist(String.trim(&1)))
730 |> Nx.tensor(names: [:y, :x])
731 |> Nx.subtract(?0)
732 |> Nx.add(1)
733
734{width, height} = shape = Nx.shape(input)
735```
736
737```output
738{100, 100}
739```
740
741### Task 1
742
743```elixir
744minima = fn padded, size, axis ->
745 shifted = Nx.slice_axis(padded, 0, size, axis)
746 x1 = Nx.less(input, shifted)
747
748 shifted = Nx.slice_axis(padded, 2, size, axis)
749 x2 = Nx.less(input, shifted)
750
751 Nx.logical_and(x1, x2)
752end
753
754padded = Nx.pad(input, 99, [{0, 0, 0}, {1, 1, 0}])
755
756x = minima.(padded, width, :x)
757
758padded = Nx.pad(input, 99, [{1, 1, 0}, {0, 0, 0}])
759
760y = minima.(padded, height, :y)
761
762minimas = Nx.logical_and(x, y)
763
764input
765|> Nx.multiply(minimas)
766|> Nx.sum()
767|> Nx.to_number()
768```
769
770```output
771452
772```
773
774### Task 2
775
776```elixir
777input
778|> Nx.equal(10)
779|> Nx.logical_not()
780|> Nx.select(Nx.iota(shape), 9999)
781|> Nx.to_flat_list()
782|> Enum.reject(&(&1 == 9999))
783|> Enum.map(fn point -> {div(point, width), rem(point, width)} end)
784|> Enum.reduce([], fn {y, x} = point, basins ->
785 basin_left = Enum.find_index(basins, &({y, x - 1} in &1))
786 basin_up = Enum.find_index(basins, &({y - 1, x} in &1))
787
788 case {basin_left, basin_up} do
789 {nil, nil} ->
790 [MapSet.new([point]) | basins]
791
792 {idx, nil} ->
793 List.update_at(basins, idx, &MapSet.put(&1, point))
794
795 {nil, idx} ->
796 List.update_at(basins, idx, &MapSet.put(&1, point))
797
798 {idx, idx} ->
799 List.update_at(basins, idx, &MapSet.put(&1, point))
800
801 {idx1, idx2} ->
802 {old, basins} = List.pop_at(basins, max(idx1, idx2))
803
804 List.update_at(basins, min(idx1, idx2), &(&1 |> MapSet.union(old) |> MapSet.put(point)))
805 end
806end)
807|> Enum.map(&MapSet.size/1)
808|> Enum.sort(:desc)
809|> Enum.take(3)
810|> Enum.reduce(&*/2)
811```
812
813```output
8141263735
815```
816
817## Day 10
818
819```elixir
820input =
821 File.stream!("day10.txt")
822 |> Stream.map(&String.trim/1)
823
824defmodule Day10 do
825 @parens %{?( => ?), ?[ => ?], ?< => ?>, ?{ => ?}}
826
827 def parse(input), do: parse(input, [])
828
829 defp parse(<<c>> <> rest, stack) when c in '([{<', do: parse(rest, [@parens[c] | stack])
830 defp parse(<<c>> <> rest, [c | stack]), do: parse(rest, stack)
831 defp parse(<<>>, []), do: :ok
832 defp parse(<<>>, rest), do: {:incomplete, rest}
833 defp parse(<<c>> <> _, _), do: {:unexpected, [c]}
834end
835```
836
837```output
838{:module, Day10, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:parse, 2}}
839```
840
841```elixir
842points = %{
843 ?) => 3,
844 ?] => 57,
845 ?} => 1197,
846 ?> => 25137
847}
848
849input
850|> Enum.map(&Day10.parse/1)
851|> Enum.map(fn
852 {:unexpected, [c]} -> points[c]
853 _ -> 0
854end)
855|> Enum.sum()
856```
857
858```output
859288291
860```
861
862```elixir
863points = %{
864 ?) => 1,
865 ?] => 2,
866 ?} => 3,
867 ?> => 4
868}
869
870median = fn list ->
871 sorted = Enum.sort(list)
872 middle = div(length(list), 2)
873
874 Enum.at(sorted, middle)
875end
876
877input
878|> Enum.map(&Day10.parse/1)
879|> Enum.flat_map(fn
880 {:incomplete, rest} ->
881 [
882 Enum.reduce(rest, 0, fn c, acc ->
883 acc * 5 + points[c]
884 end)
885 ]
886
887 _ ->
888 []
889end)
890|> median.()
891```
892
893```output
894820045242
895```
896
897## Day 11
898
899```elixir
900input =
901 File.read!("day11.txt")
902 |> String.split("\n")
903 |> Enum.map(&String.trim/1)
904 |> Enum.map(fn line ->
905 for <<c <- line>>, do: c - ?0
906 end)
907 |> Enum.with_index()
908 |> Enum.flat_map(fn {row, y} ->
909 for {v, x} <- Enum.with_index(row), do: {{x, y}, v}
910 end)
911 |> Map.new()
912
913defmodule Day11 do
914 def step(map) do
915 updated = Map.new(map, fn {k, v} -> {k, v + 1} end)
916
917 lightup(updated, 0)
918 end
919
920 @diffs for dx <- -1..1, dy <- -1..1, dx != 0 or dy != 0, do: {dx, dy}
921
922 IO.inspect(@diffs)
923
924 def lightup(map, n) do
925 map
926 |> Enum.reduce({map, 0}, fn
927 {_, v}, acc when v < 10 ->
928 acc
929
930 {{x, y} = k, _}, {map, count} ->
931 new_map =
932 @diffs
933 |> Enum.reduce(map, fn {dx, dy}, acc ->
934 point = {x + dx, y + dy}
935
936 case Map.fetch(acc, point) do
937 {:ok, value} when value != 0 -> %{acc | point => value + 1}
938 _ -> acc
939 end
940 end)
941 |> Map.put(k, 0)
942
943 {new_map, count + 1}
944 end)
945 |> case do
946 {map, 0} -> {map, n}
947 {map, m} -> lightup(map, n + m)
948 end
949 end
950end
951```
952
953```output
954[{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}]
955```
956
957```output
958{:module, Day11, <<70, 79, 82, 49, 0, 0, 11, ...>>, {:lightup, 2}}
959```
960
961```elixir
962draw = fn map ->
963 for x <- 0..9 do
964 IO.puts(for y <- 0..9, do: ?0 + map[{x, y}])
965 end
966
967 IO.puts("")
968end
969
9701..100
971|> Enum.reduce({input, 0}, fn _, {map, n} ->
972 {new_map, m} = Day11.step(map)
973 {new_map, n + m}
974end)
975|> elem(1)
976```
977
978```output
9791688
980```
981
982```elixir
983Stream.unfold(1, &{&1, &1 + 1})
984|> Enum.reduce_while(input, fn idx, map ->
985 case Day11.step(map) do
986 {_, 100} -> {:halt, idx}
987 {next, _} -> {:cont, next}
988 end
989end)
990```
991
992```output
993403
994```
995
996## Day 12
997
998```elixir
999input =
1000 File.read!("day12.txt")
1001 |> String.split("\n")
1002 |> Enum.map(&String.split(&1, "-"))
1003
1004graph =
1005 Enum.reduce(input, %{}, fn [a, b], acc ->
1006 acc
1007 |> Map.update(a, [b], &[b | &1])
1008 |> Map.update(b, [a], &[a | &1])
1009 end)
1010
1011defmodule Day12 do
1012 def dfs(graph, start, finish), do: dfs(graph, start, finish, [start])
1013
1014 defp dfs(_graph, vertex, vertex, _visited), do: 1
1015
1016 defp dfs(graph, vertex, finish, visited) do
1017 (graph[vertex] -- visited)
1018 |> Enum.reduce(0, fn vertex, acc ->
1019 visited = if small?(vertex), do: [vertex | visited], else: visited
1020
1021 acc + dfs(graph, vertex, finish, visited)
1022 end)
1023 end
1024
1025 def dfs2(graph, start, finish), do: dfs2(graph, start, finish, %{start => :inf})
1026
1027 defp dfs2(_graph, vertex, vertex, _visited), do: 1
1028
1029 defp dfs2(graph, vertex, finish, visited) do
1030 (graph[vertex] -- keys(visited))
1031 |> Enum.reduce(0, fn vertex, acc ->
1032 visited = if small?(vertex), do: Map.update(visited, vertex, 1, &(&1 + 1)), else: visited
1033
1034 acc + dfs2(graph, vertex, finish, visited)
1035 end)
1036 end
1037
1038 defp keys(map) do
1039 if Enum.any?(map, fn {_, v} -> v == 2 end) do
1040 # there is already some vertex visited twice
1041 Map.keys(map)
1042 else
1043 for {k, v} <- map, v > 1, do: k
1044 end
1045 end
1046
1047 defp small?(<<c>> <> _), do: c in ?a..?z
1048end
1049```
1050
1051```output
1052{:module, Day12, <<70, 79, 82, 49, 0, 0, 15, ...>>, {:small?, 1}}
1053```
1054
1055```elixir
1056Day12.dfs(graph, "start", "end")
1057```
1058
1059```output
10604167
1061```
1062
1063```elixir
1064Day12.dfs2(graph, "start", "end")
1065```
1066
1067```output
106898441
1069```
1070
1071## Day 13
1072
1073```elixir
1074[input, folds] =
1075 File.read!("day13.txt")
1076 |> String.trim()
1077 |> String.split("\n\n")
1078
1079input =
1080 input
1081 |> String.split("\n")
1082 |> Enum.map(fn line ->
1083 [x, y] = String.split(line, ",")
1084
1085 {String.to_integer(x), String.to_integer(y)}
1086 end)
1087 |> MapSet.new()
1088
1089folds =
1090 folds
1091 |> String.split("\n")
1092 |> Enum.map(fn
1093 "fold along " <> <<c>> <> "=" <> rest ->
1094 {String.to_atom(<<c>>), String.to_integer(rest)}
1095 end)
1096
1097defmodule Day13 do
1098 def fold({orientation, pos}, set) do
1099 Enum.reduce(set, MapSet.new(), fn point, acc ->
1100 new_point = folded_coords(orientation, pos, point)
1101
1102 MapSet.put(acc, new_point)
1103 end)
1104 end
1105
1106 defp folded_coords(:x, col, {x, y}) when x > col, do: {abs(2 * col - x), y}
1107 defp folded_coords(:y, row, {x, y}) when y > row, do: {x, abs(2 * row - y)}
1108 defp folded_coords(_, _, point), do: point
1109
1110 def draw(set) do
1111 set
1112 |> Enum.group_by(&elem(&1, 1))
1113 |> Enum.sort()
1114 |> Enum.map(fn {_, points} ->
1115 points
1116 |> Enum.map(&elem(&1, 0))
1117 |> Enum.sort()
1118 |> Enum.chunk_every(2, 1)
1119 |> Enum.map(fn
1120 [a, b] -> b - a
1121 _ -> 0
1122 end)
1123 |> Enum.map(&String.pad_trailing("█", &1, " "))
1124 end)
1125 |> Enum.join("\n")
1126 end
1127end
1128```
1129
1130```output
1131{:module, Day13, <<70, 79, 82, 49, 0, 0, 13, ...>>, {:draw, 1}}
1132```
1133
1134```elixir
1135Day13.fold(hd(folds), input) |> MapSet.size()
1136```
1137
1138```output
1139802
1140```
1141
1142```elixir
1143Enum.reduce(folds, input, &Day13.fold/2)
1144|> Day13.draw()
1145|> IO.puts()
1146```
1147
1148```output
1149███ █ █ █ █ ████ ████ ██ █ █ ███
1150█ █ █ █ █ █ █ █ █ █ █ █ █ █
1151█ █ ██ ████ ███ █ █ █ █ ███
1152███ █ █ █ █ █ █ █ ██ █ █ █ █
1153█ █ █ █ █ █ █ █ █ █ █ █ █ █
1154█ █ █ █ █ █ █ ████ ███ ██ ███
1155```
1156
1157```output
1158:ok
1159```
1160
1161## Day 14