this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 13
4
5```elixir
6Mix.install([:kino_aoc])
7```
8
9## Setup
10
11<!-- livebook:{"attrs":{"assign_to":"puzzle_input","day":"13","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", "13", 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.#...##\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.#.##.#........\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..#.##.#....#\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..##..######..#\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....##.#.##\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.#.#.##.##.##..\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#..#...####\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##........##..#\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..#######\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#...#.##.##..#.##\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.##.#.##..######.\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
26# puzzle_input =
27"""
28#.##..##.
29..#.##.#.
30##......#
31##......#
32..#.##.#.
33..##..##.
34#.#.##.#.
35
36#...##..#
37#....#..#
38..##..###
39#####.##.
40#####.##.
41..##..###
42#....#..#
43"""
44```
45
46<!-- livebook:{"output":true} -->
47
48```
49"#.##..##.\n..#.##.#.\n##......#\n##......#\n..#.##.#.\n..##..##.\n#.#.##.#.\n\n#...##..#\n#....#..#\n..##..###\n#####.##.\n#####.##.\n..##..###\n#....#..#\n"
50```
51
52```elixir
53defmodule Day13 do
54 def find_axes(list) do
55 reversed = Enum.reverse(list)
56
57 len = length(list)
58
59 back = dbg(do_find(list, 0))
60 front = dbg(do_find(reversed, 0))
61
62 [
63 if(back, do: div(len - back, 2) + back),
64 if(front, do: div(len - front, 2))
65 ]
66 |> Enum.filter(& &1)
67 end
68
69 defp do_find([_], _), do: nil
70
71 defp do_find([_ | a], n) when rem(n, 2) == 0, do: do_find(a, n + 1)
72
73 defp do_find(a, n) do
74 if palindrome?(a) do
75 n
76 else
77 do_find(tl(a), n + 1)
78 end
79 end
80
81 def palindrome?(list) do
82 list == Enum.reverse(list)
83 end
84
85 def print_mirror({rows, cols, _, _}) do
86 width = length(cols)
87
88 display =
89 for row <- rows do
90 for digit <- Integer.digits(row, 2) do
91 if digit == 1, do: "#", else: "."
92 end
93 |> List.to_string()
94 |> String.pad_leading(width, ".")
95 end
96
97 IO.puts(Enum.intersperse(display, "\n"))
98 end
99end
100```
101
102<!-- livebook:{"output":true} -->
103
104```
105{:module, Day13, <<70, 79, 82, 49, 0, 0, 20, ...>>, {:print_mirror, 1}}
106```
107
108```elixir
109mirrors =
110 puzzle_input
111 |> String.split("\n\n", trim: true)
112 |> Enum.map(fn grid ->
113 mirror =
114 grid
115 |> String.split("\n", trim: true)
116 |> Enum.map(fn line ->
117 for <<c <- line>>, do: if(c == ?#, do: 1, else: 0)
118 end)
119
120 rows = Enum.map(mirror, &Integer.undigits(&1, 2))
121 cols = Enum.zip_with(mirror, &Integer.undigits(&1, 2))
122
123 row = Day13.find_axes(rows)
124 col = Day13.find_axes(cols)
125
126 {rows, cols, row, col}
127 end)
128```
129
130<!-- livebook:{"output":true} -->
131
132```
133[
134 {[576, 320, 272, 1423, 591, 1391, 1833], [11, 69, 59, 8, 102, 3, 16, 15, 14, 14, 15], [], ~c"\t"},
135 {[727, 486, 2044, 819, 819, 2044, 486, 727, 1325, 503, 193, 292, 196],
136 [1168, 6048, 4058, 7405, 7405, 4058, 6056, 1168, 7419, 7016, 4924], [4], []},
137 {[26, 71, 71, 27, 18, 6, 84, 35, 104, 119, 119, 104, 35],
138 [3166, 63, 4940, 4626, 3276, 8109, 3629], ~c"\n", []},
139 {[87, 27, 15, 97, 97, 15, 27, 87, 95, 6, 34, 95, 67, 77, 77, 75, 95],
140 [78655, 12352, 100129, 52527, 84909, 118771, 130879], [4], []},
141 {[28948, 11524, 7312, 7312, 11520, 28948, 29291],
142 [67, 103, 91, 60, 60, 1, 102, 24, 1, 1, 90, 1, 98, 1, 1], [], [14]},
143 {[416, 418, 83, 97, 289, 332, 332, 289, 97, 83, 418, 416, 330],
144 [6631, 6150, 1753, 6966, 1032, 193, 192, 3085, 1848], [6], []},
145 {[4683, 7, 7, 4683, 7229, 385, 6553, 7228, 387, 2069, 3123, 1441, 7806, 3255, 1634],
146 [19844, 1462, 1183, 18437, 840, 842, 18437, 1183, 1462, 19844, 13478, 30807, 32634], [2], []},
147 {[370, 1952, 364, 197, 1856, 2039, 327, 1910, 1827, 1562, 1931, 448, 916, 1738, 1738],
148 [9971, 9975, 30684, 10783, 24459, 29376, 17060, 4147, 7044, 17395, 2896], [14], []},
149 {[23425, 9523, 6472, 17236, 17278, 32285, 23094, 6647, 6649, 6649, 6647, 23094, 32285, 17278,
150 17172],
151 [20239, 8708, 21500, 21500, 8708, 20239, 31987, 16624, 7410, 9722, 12287, 5734, 3999, 9626,
152 25332], [], [3]},
153 {[264, 15458, 32359, 32359, 408, 15867, 9722],
154 [24, 59, 58, 58, 59, 24, 71, 7, 59, 59, 7, 71, 24, 59, 26], [], [3]},
155 {[131059, 65309, 65301, 91878, 23060, 16956, 82644, 33027, 33027, 82646, 16956],
156 [1170, 1804, 2035, 1920, 1856, 1856, 1920, 2035, 1804, 1170, 1170, 1185, 1907, 545, 1011, 1166,
157 1804], [], [5]},
158 {[186, 107, 407, 407, 107, 186, 1364, 211, 753, 689, 211, 1364, 186, 107, 407],
159 [264, 96, 6409, 23285, 9690, 26214, 23549, 26118, 6409, 32407, 15603], [3], []},
160 {[11602, 63, 29650, 28032, 4705, 11550, 24734, 7756, 24972],
161 [101, 365, 82, 298, 298, 82, 361, 101, 338, 144, 460, 143, 143, 460, 144], [], ~c"\f"},
162 {[1980, 10172, 22140, 25983, 11116, 6500, 30788, 5172, 18740, 8239, 24, 16875, 24967, 735, 9604,
163 16836, 17152],
164 [25907, 46228, 19968, 7424, 123396, 118793, 112951, 98366, 31786, 129952, 123720, 127208, 130974,
165 8376, 8376], [], [14]},
166 {[19591, 18951, 632, 14023, 883, 13066, 12628],
167 [96, 11, 11, 96, 72, 62, 7, 72, 29, 20, 21, 18, 105, 110, 108], [], [2]},
168 {[899, 258, 495, 1418, 1167, 1703, 1703, 1167, 1418, 495, 258, 899, 722, 284, 284, 658, 899],
169 [16128, 68659, 123373, 98227, 16528, 19584, 30, 29580, 24204, 131059, 89761], [6], []},
170 {[115, 15, 37, 88, 68, 68, 88], ~c"OPI)6`p", [5], []},
171 {[4128, 20521, 10128, 10326, 8166, 6048, 7398, 20431, 16118, 18505, 24601, 774, 13488],
172 [2092, 1557, 6609, 888, 1521, 1458, 1442, 1521, 888, 6609, 1557, 2092, 882, 882, 2092], [],
173 ~c"\r"},
174 {~c"\v\bOO\b\v]5.62.5", [1600, 63, 109, 8146, 1659, 5790, 5857], [3], []},
175 {[70, 115, 52, 470, 102, 462, 84, 484, 62, 444, 467, 127, 127, 465, 444, 62, 484],
176 [10957, 10957, 114297, 54199, 58878, 2486, 98231, 113010, 32888], [], [1]},
177 {[198, 306, 463, 310, 204, 315, 219, 27, 217, 216, 216, 217, 27],
178 [3712, 5470, 5470, 2688, 2815, 1535, 5888, 7905, 1267], ~c"\n", []},
179 {[71371, 104223, 104221, 71371, 8422, 31421, 31421, 8422, 71371],
180 [481, 192, 12, 30, 493, 12, 481, 493, 192, 319, 307, 30, 204, 493, 222, 435, 493], [6], []},
181 {[13279, 13278, 13719, 19445, 8600, 26086, 518, 26199, 3242, 2488, 2488],
182 [168, 1896, 1792, 135, 300, 1688, 2019, 2023, 1704, 167, 1995, 1607, 1976, 1852, 1416], ~c"\n",
183 []},
184 {[1237, 2022, 1161, 1161, 2022, 1237, 1177, 1131, 2029, 79, 1946],
185 [2045, 581, 581, 2037, 1646, 588, 1073, 415, 1638, 587, 1470], [3], []},
186 {[111450, 7065, 54910, 54910, 7065, 111450, 127548, 25051, 61861, 61569, 102656, 53858, 127683,
187 87229, 114432],
188 [17175, 23421, 6638, 17381, 32639, 9217, 6147, 32525, 26321, 9446, 23180, 6474, 32642, 32642,
189 6466, 23180, 9446], [3], []},
190 {[20, 22, 436, 394, 359, 359, 394], [31, 25, 6, 22, 112, 9, 118, 47, 6], [5], []},
191 {[100217, 100217, 46111, 64677, 64959, 18555, 64861, 131030, 388, 112431, 66318, 67525, 118470],
192 [6191, 8041, 993, 1896, 1896, 993, 8043, 6191, 6526, 819, 6371, 7048, 7648, 7628, 1919, 1453,
193 8138], [1], []},
194 {[291, 1, 24, 28, 1, 291, 492], [67, 1, 1, 67, 24, 25, 9, 66, 102], [], [2]},
195 {~c"2aa2\n}|\n2", [204, 493, 301, 30, 12, 307, 200], [2], []},
196 {[3115, 4616, 3100, 4656, 4643, 1344, 167], [44, 80, 82, 44, 2, 1, 2, 77, 24, 112, 17, 69, 69],
197 [], ~c"\f"},
198 {[67339, 92194, 8007, 70176, 4382, 5406, 70176, 8007, 92194, 67339, 55372, 10833, 123746, 57569,
199 57569],
200 [26980, 23, 8279, 8271, 8080, 12504, 21152, 22956, 22180, 3, 4255, 10567, 1544, 17968, 5776,
201 30436, 20651], [14], []},
202 {[6424, 26178, 346, 6490, 23485, 15384, 14592, 9703, 26392, 23515, 32280, 32475, 15706, 32358,
203 9471, 23320, 17254],
204 [37355, 36732, 81146, 81146, 35708, 37355, 96147, 4772, 58045, 4621, 96758, 96758, 4621, 58045,
205 4772], [], ~c"\v"},
206 {[75457, 7450, 103542, 100685, 20575, 20575, 117069, 103542, 7450, 75457, 75457, 7450, 103542,
207 117069, 20575],
208 [22966, 6534, 1795, 16432, 14029, 10570, 28924, 16432, 10570, 16432, 24503, 4228, 14029, 12107,
209 8071, ...], ~c"\n", []},
210 {[114654, 1118, 92031, 101299, 101299, 92031, 1118, 114654, 31935, 80545, 20702, 1480, 17953,
211 69836, 60269, ...],
212 [96904, 78341, 18775, 84868, 66504, 78725, 118578, 96919, 96805, 78826, 118382, 31124, 130880,
213 118637, ...], [4], []},
214 {[14474, 14474, 17870, 27951, 39, 7069, 240, 31399, 31655, 240, 7069],
215 [396, 1676, 1581, 1709, 384, 45, 421, 1855, 274, 222, 51, 1953, 493, ...], [1], []},
216 {[36, 36, 84, 53, 75, 28, 32, 126, 125, 125, 126, 36, 28, ...],
217 [5362, 27129, 6901, 1782, 31485, 1170, 3171], [1], []},
218 {[4259, 8068, 7, 8168, 4551, 6595, 1584, 4292, 84],
219 [442, 168, 164, 164, 184, 442, 59, 292, 5, 32, 211, ...], [], ~c"\f"},
220 {[130987, 86, 74905, 93, 126, 56186, 81145, 81094, 23097, 81025, 124915, ...],
221 [20924, 16916, 16980, 20924, 17386, 17386, 20924, 16980, 16916, 20924, ...], [], [5]},
222 {[38804, 125056, 92872, 151, 1196, 129732, 62279], [50, 99, 51, 51, 67, 50, 68, 83, 65, ...], [],
223 [16]},
224 {[54, 11, 393, 54, 127, 127, 54, 393, 11, ...],
225 [1056, 1057, 388, 5069, 5071, 3510, 5066, 7130, ...], [5], []},
226 {[391, 2025, 404, 2039, 188, 1629, 1605, 1894, ...],
227 [44902, 44902, 123750, 127129, 44866, 45628, 31078, ...], [], [1]},
228 {[1658, 1655, 26, 2019, 1637, 1649, 1655, ...], [446, 444, 34, 34, 444, 446, ...], [], [3]},
229 {[365, 1438, 1069, 780, 1216, 1664, ...], [14332, 2892, 27071, 10003, 17863, ...], [14], []},
230 {[7917, 64, 436, 297, 7982, ...], [70857, 70889, 70889, 70857, ...], [], [2]},
231 {[7224, 12736, 21104, 27923, ...], [32323, 42255, 121795, ...], [5], []},
232 {[203, 313, 1753, ...], [5527, 5527, ...], [], [...]},
233 {[41, 73, ...], [685, ...], [], ...},
234 {[116426, ...], [...], ...},
235 {[...], ...},
236 {...},
237 ...
238]
239```
240
241## Part 1
242
243```elixir
244Enum.map(mirrors, fn {_, _, row, col} ->
245 List.first(col, 0) + List.first(row, 0) * 100
246end)
247|> Enum.sum()
248```
249
250<!-- livebook:{"output":true} -->
251
252```
25340006
254```
255
256## Part 2
257
258```elixir
259defmodule Day13.Part2 do
260 import Bitwise
261
262 def alternatives(list, a, n) do
263 l = length(list)
264
265 list =
266 for i <- 0..n,
267 d = bsl(1, i),
268 j <- 0..l,
269 desmudged = List.update_at(list, j, &bxor(&1, d)),
270 v <- Day13.find_axes(desmudged),
271 v not in a,
272 do: v
273
274 Enum.dedup(list)
275 end
276end
277```
278
279<!-- livebook:{"output":true} -->
280
281```
282{:module, Day13.Part2, <<70, 79, 82, 49, 0, 0, 11, ...>>, {:alternatives, 3}}
283```
284
285```elixir
286mirrors
287|> Enum.with_index()
288|> Enum.map(fn {{rows, cols, row, col}, _idx} ->
289 row = List.first(Day13.Part2.alternatives(rows, row, length(cols)), 0)
290 col = List.first(Day13.Part2.alternatives(cols, col, length(rows)), 0)
291
292 row * 100 + col
293end)
294|> Enum.sum()
295```
296
297<!-- livebook:{"output":true} -->
298
299```
30028627
301```
302
303<!-- livebook:{"offset":14833,"stamp":{"token":"XCP.8-i47duAdnzdKS-qi8IVDyDE21kJUyqTX55xsBPltOjjVtrJUuw2vu5-Ufhj9sPB_IGriiYKDwSN8h0k2cz2-dY78-3ZRE77glupVo5cCwEbWm4pbp6TLRefkSB06zCZdQ","version":2}} -->