this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 11
4
5```elixir
6Mix.install([:kino_aoc])
7```
8
9## Section
10
11<!-- livebook:{"attrs":{"assign_to":"puzzle_input","day":"11","session_secret":"ADVENT_OF_CODE_SESSION","year":"2023"},"chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
12
13```elixir
14{:ok, puzzle_input} =
15 KinoAOC.download_puzzle("2023", "11", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
16```
17
18<!-- livebook:{"output":true} -->
19
20```
21{:ok,
22 ".#...........#.........................................................................#...............#...........#........................\n.......................#....................................................................................................................\n...............................#...........#.................#.............................#.............................................#..\n......#............................................#........................................................................................\n......................................................................#.....#.....................#.........................................\n.................#.......#.......................................#................#.....#.....................#.............................\n.........................................#.................#................................................................................\n................................#.............................................................#..........#..................................\n#.......................................................................#..............................................#.................#..\n..........#....................................#......................................#............................................#........\n................#....................................#........#.............................................................................\n......#........................................................................#............................................................\n......................#..............#..............................................................#..........#.....#......................\n..................................................#.......................#..................................................#..........#...\n............................#...............................................................................................................\n........#...................................................................................................................................\n..................#.......................#................................................................#................................\n.............................................................#........#.....................................................................\n..............................#.......#......................................#.............#........................#.......................\n.#............................................................................................................#...........................#.\n...................................................................................................#....................#...................\n....................#......................#.............#.....#..................................................................#.........\n.................................................................................................................#..........................\n............................................................................................................................................\n....................................................................#.....................#.................................................\n.................................#..............................................#..............#............#.............#.................\n...........................#............................................#...........................................#.......................\n......................#.........................#...........................................................................................\n.......................................#....................................#...................................#...........................\n.....#." <> ...}
23```
24
25```elixir
26lines = String.split(puzzle_input, "\n", trim: true)
27
28galaxies =
29 for {line, y} <- Enum.with_index(lines),
30 {d, x} <- Enum.with_index(String.to_charlist(line)),
31 d == ?#,
32 do: {x, y}
33
34{sx, sy} =
35 Enum.reduce(galaxies, {0, 0}, fn {x, y}, {mx, my} -> {max(x, mx), max(y, my)} end)
36```
37
38<!-- livebook:{"output":true} -->
39
40```
41{139, 139}
42```
43
44```elixir
45[rows, cols] =
46 Enum.reduce(galaxies, [MapSet.new(), MapSet.new()], fn {x, y}, [rows, cols] ->
47 [MapSet.put(rows, y), MapSet.put(cols, x)]
48 end)
49
50empty_rows = MapSet.difference(MapSet.new(0..sy), rows) |> MapSet.to_list() |> Enum.sort()
51empty_cols = MapSet.difference(MapSet.new(0..sx), cols) |> MapSet.to_list() |> Enum.sort()
52
53{empty_rows, empty_cols}
54```
55
56<!-- livebook:{"output":true} -->
57
58```
59{[23, 54, 77, 81, 87, 91, 106, 107], ~c".178SYh"}
60```
61
62```elixir
63defmodule Day11 do
64 def reduce_unique_pairs(xs, init, fun) when is_function(fun, 3) do
65 do_map(hd(xs), tl(xs), fun, init)
66 end
67
68 def do_map(_h, [], _fun, acc), do: acc
69
70 def do_map(a, xs, fun, acc) do
71 new =
72 Enum.reduce(xs, acc, fn b, acc1 -> fun.(a, b, acc1) end)
73
74 do_map(hd(xs), tl(xs), fun, new)
75 end
76
77 def expand({x, y}, empty_rows, empty_cols, m \\ 2) do
78 {x + delta(x, empty_cols) * (m - 1), y + delta(y, empty_rows) * (m - 1)}
79 end
80
81 defp delta(p, empty) do
82 Enum.count(empty, &(p > &1))
83 end
84end
85```
86
87<!-- livebook:{"output":true} -->
88
89```
90{:module, Day11, <<70, 79, 82, 49, 0, 0, 12, ...>>, {:delta, 2}}
91```
92
93## Part 1
94
95```elixir
96galaxies
97|> Enum.map(&Day11.expand(&1, empty_rows, empty_cols))
98|> Day11.reduce_unique_pairs(0, fn {xa, ya}, {xb, yb}, acc ->
99 acc + abs(xb - xa) + abs(yb - ya)
100end)
101```
102
103<!-- livebook:{"output":true} -->
104
105```
1069686930
107```
108
109## Part 2
110
111```elixir
112galaxies
113|> Enum.map(&Day11.expand(&1, empty_rows, empty_cols, 1_000_000))
114|> Day11.reduce_unique_pairs(0, fn {xa, ya}, {xb, yb}, acc ->
115 acc + abs(xb - xa) + abs(yb - ya)
116end)
117```
118
119<!-- livebook:{"output":true} -->
120
121```
122630728425490
123```
124
125<!-- livebook:{"offset":6621,"stamp":{"token":"XCP.eVlqF57ZVWEep_9Yi2Bop2YbV2ltU4T8e1DrVKC83DPGypJtqq5uBZpnlG1ix3mgZ2cTntGIcUv867ImHAf_1T32D0t35IKejAKx886nb4XpUxf8FuS27jeNiQIFpCl4Pg","version":2}} -->