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## Section
10
11<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiIxMyIsInNlc3Npb25fc2VjcmV0IjoiQURWRU5UX09GX0NPREVfU0VTU0lPTiIsInllYXIiOiIyMDI0In0","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
12
13```elixir
14{:ok, puzzle_input} =
15 KinoAOC.download_puzzle("2024", "13", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
16```
17
18<!-- livebook:{"output":true} -->
19
20```
21{:ok,
22 "Button A: X+22, Y+88\nButton B: X+90, Y+28\nPrize: X=6496, Y=3076\n\nButton A: X+54, Y+14\nButton B: X+14, Y+44\nPrize: X=8084, Y=1284\n\nButton A: X+96, Y+15\nButton B: X+55, Y+63\nPrize: X=5535, Y=3966\n\nButton A: X+17, Y+42\nButton B: X+40, Y+25\nPrize: X=12176, Y=3136\n\nButton A: X+87, Y+31\nButton B: X+15, Y+36\nPrize: X=6672, Y=2500\n\nButton A: X+59, Y+27\nButton B: X+21, Y+56\nPrize: X=1475, Y=15098\n\nButton A: X+39, Y+51\nButton B: X+98, Y+14\nPrize: X=7890, Y=3126\n\nButton A: X+23, Y+37\nButton B: X+35, Y+14\nPrize: X=16537, Y=6184\n\nButton A: X+21, Y+89\nButton B: X+74, Y+23\nPrize: X=2407, Y=8748\n\nButton A: X+47, Y+17\nButton B: X+35, Y+59\nPrize: X=17994, Y=16242\n\nButton A: X+14, Y+45\nButton B: X+52, Y+16\nPrize: X=18768, Y=3912\n\nButton A: X+29, Y+45\nButton B: X+85, Y+11\nPrize: X=3149, Y=4161\n\nButton A: X+81, Y+95\nButton B: X+67, Y+12\nPrize: X=5489, Y=2110\n\nButton A: X+48, Y+58\nButton B: X+86, Y+22\nPrize: X=4802, Y=2280\n\nButton A: X+27, Y+59\nButton B: X+47, Y+15\nPrize: X=2602, Y=2090\n\nButton A: X+39, Y+87\nButton B: X+94, Y+38\nPrize: X=8830, Y=6134\n\nButton A: X+23, Y+61\nButton B: X+82, Y+16\nPrize: X=8405, Y=3957\n\nButton A: X+54, Y+14\nButton B: X+24, Y+63\nPrize: X=894, Y=1708\n\nButton A: X+26, Y+14\nButton B: X+18, Y+35\nPrize: X=5510, Y=12541\n\nButton A: X+65, Y+55\nButton B: X+21, Y+69\nPrize: X=430, Y=620\n\nButton A: X+11, Y+62\nButton B: X+50, Y+11\nPrize: X=11414, Y=3683\n\nButton A: X+21, Y+54\nButton B: X+93, Y+22\nPrize: X=7683, Y=5642\n\nButton A: X+20, Y+95\nButton B: X+52, Y+29\nPrize: X=5580, Y=10155\n\nButton A: X+37, Y+13\nButton B: X+11, Y+66\nPrize: X=18250, Y=14983\n\nButton A: X+54, Y+28\nButton B: X+37, Y+58\nPrize: X=17939, Y=14902\n\nButton A: X+87, Y+65\nButton B: X+11, Y+79\nPrize: X=3765, Y=4087\n\nButton A: X+74, Y+30\nButton B: X+16, Y+59\nPrize: X=9858, Y=8342\n\nButton A: X+74, Y+31\nButton B: X+17, Y+59\nPrize: X=14764, Y=6598\n\nButton A: X+12, Y+95\nButton B: X+27, Y+33\nPrize: X=945, Y=3324\n\nButton A: X+21, Y+36\nButton B: X+34, Y+14\nPrize: X=7247, Y=5012\n\nButton A: X+48, Y+62\nButton B: X+90, Y+29\nPrize: X=9150, Y=5973\n\nButton A: X+93, Y+43\nButton B: X+49, Y+91\nPrize: X=7090, Y=6422\n\nButton A: X+28, Y+70\nButton B: X+68, Y+21\nPrize: X=17176, Y=3693\n\nButton A: X+33, Y+16\nButton B: X+27, Y+51\nPrize: X=1884, Y=2771\n\nButton A: X+11, Y+43\nButton B: X+51, Y+19\nPrize: X=4114, Y=10066\n\nButton A: X+26, Y+70\nButton B: X+87, Y+46\nPrize: X=3532, Y=6874\n\nButton A: X+22, Y+35\nButton B: X+38, Y+13\nPrize: X=7508, Y=16592\n\nButton A: X+33, Y+16\nButton B: X+48, Y+72\nPrize: X=12065, Y=15896\n\nButton A: X+67, Y+25\nButton B: X+14, Y+55\nPrize: X=4093, Y=10275\n\nButton A: X+36, Y+17\nButton B: X+43, Y+77\nPrize: X=3253, Y=1933\n\nButton A: X+84, Y+24\nButton B: X+42, Y+69\nPrize: X=8862, Y=4869\n\nButton A: X+70, Y+16\nButton B: X+17, Y+68\nPrize: X=5690, Y=3224\n\nButton A: X+58, Y+27\nButton B: X+44, Y+92\nPrize: X=1890, Y=1595\n\nButton A: X+64, Y+30\nButton B: X+29, Y+57\nPrize: X=15004, Y=15224\n\nButton A: X+13, Y+90\nButton B: X+64, Y+33\nPrize: X=6560, Y=6048\n\nButton A: X+37, Y+91\nButton B: X+64, Y+49\nPrize: X=5214, Y=8379\n\nButton A: X+12, Y+80\nButton B: X+75, Y+25\nPrize: X=6684, Y=8460\n\nButton A: X+27, Y+53\nButton B: X+53, Y+30\nPrize: X=4897, Y=14148\n\nButton A: X+41, Y+11\nButton B: X+39, Y+72\nPrize: X=2818, Y=493\n\nButton A: X+74, Y+45\nButton B: X+14, Y+35\nPrize: X=8996, Y=13510\n\nButton A: X+11, Y+36\nButton B: X+86, Y+58\nPrize: X=18273, Y=14722\n\nButton A: X+99, Y+72\nButton B: X+11, Y+39\nPrize: X=2530, Y=3390\n\nButton A: X+55, Y+17\nButton B: X+22, Y+80\nPrize: X=3652, Y=6326\n\nButton A: X+11, Y+17\nButton B: X+76, Y+16\nPrize: X=5480, Y=1976\n\nButton A: X+18, Y+73\nButton B: X+28, Y+22\nPrize: X=3222, Y=4827\n\nButton A: X+14, Y+46\nButton B: X+33, Y+29\nPrize: X=2212, Y=3932\n\nButton A: X+11, Y+14\nButton B: X+80, Y+28\nPrize: X=4187, Y=2450\n\nButton A: X+28, Y+70\nButton B: X+78, Y+25\nPrize: X=2220, Y=1810\n\nButton A: X+53, Y+19\nButton B: X+73, Y+91\nPrize: X=4514, Y=2850\n\nButton A: X+21, Y+54\nButton B: X+54, Y+25\nPrize: X=5609, Y=7594\n\nButton A: X+79, Y+15\nButton B: X+16, Y+80\nPrize: X=14993, Y=17105\n\nButton A: X+20, Y+59\nButton B: X+35, Y+17\nPrize: X=10820, Y=1709\n\nButton A: X+96, Y+22\nButton B: X+24, Y+43\n" <> ...}
23```
24
25```elixir
26#puzzle_input =
27 """
28Button A: X+94, Y+34
29Button B: X+22, Y+67
30Prize: X=8400, Y=5400
31
32Button A: X+26, Y+66
33Button B: X+67, Y+21
34Prize: X=12748, Y=12176
35
36Button A: X+17, Y+86
37Button B: X+84, Y+37
38Prize: X=7870, Y=6450
39
40Button A: X+69, Y+23
41Button B: X+27, Y+71
42Prize: X=18641, Y=10279
43 """
44```
45
46<!-- livebook:{"output":true} -->
47
48```
49warning: outdented heredoc line. The contents inside the heredoc should be indented at the same level as the closing """. The following is forbidden:
50
51 def text do
52 """
53 contents
54 """
55 end
56
57Instead make sure the contents are indented as much as the heredoc closing:
58
59 def text do
60 """
61 contents
62 """
63 end
64
65The current heredoc line is indented too little
66└─ Workspace/hauleth/advent-of-code/2024/day13.livemd#cell:b6uoz4dag7jywljr:3:3
67
68```
69
70<!-- livebook:{"output":true} -->
71
72```
73"Button A: X+94, Y+34\nButton B: X+22, Y+67\nPrize: X=8400, Y=5400\n\nButton A: X+26, Y+66\nButton B: X+67, Y+21\nPrize: X=12748, Y=12176\n\nButton A: X+17, Y+86\nButton B: X+84, Y+37\nPrize: X=7870, Y=6450\n\nButton A: X+69, Y+23\nButton B: X+27, Y+71\nPrize: X=18641, Y=10279\n"
74```
75
76```elixir
77games =
78 puzzle_input
79 |> String.split("\n\n", trim: true)
80 |> Enum.map(fn game ->
81 [
82 "Button A: X+" <> <<ax::2-binary>> <> ", Y+" <> <<ay::2-binary>>,
83 "Button B: X+" <> <<bx::2-binary>> <> ", Y+" <> <<by::2-binary>>,
84 "Prize: " <> prize_pos
85 ] = String.split(game, "\n", trim: true)
86
87 ["X=" <> px, "Y=" <> py] = String.split(prize_pos, ", ")
88
89 %{
90 btn_a: {String.to_integer(ax), String.to_integer(ay)},
91 btn_b: {String.to_integer(bx), String.to_integer(by)},
92 prize: {String.to_integer(px), String.to_integer(py)}
93 }
94 end)
95```
96
97<!-- livebook:{"output":true} -->
98
99```
100[
101 %{btn_a: {22, 88}, btn_b: {90, 28}, prize: {6496, 3076}},
102 %{btn_a: {54, 14}, btn_b: {14, 44}, prize: {8084, 1284}},
103 %{btn_a: {96, 15}, btn_b: {55, 63}, prize: {5535, 3966}},
104 %{btn_a: {17, 42}, btn_b: {40, 25}, prize: {12176, 3136}},
105 %{btn_a: {87, 31}, btn_b: {15, 36}, prize: {6672, 2500}},
106 %{btn_a: {59, 27}, btn_b: {21, 56}, prize: {1475, 15098}},
107 %{btn_a: {39, 51}, btn_b: {98, 14}, prize: {7890, 3126}},
108 %{btn_a: {23, 37}, btn_b: {35, 14}, prize: {16537, 6184}},
109 %{btn_a: {21, 89}, btn_b: {74, 23}, prize: {2407, 8748}},
110 %{btn_a: {47, 17}, btn_b: {35, 59}, prize: {17994, 16242}},
111 %{btn_a: {14, 45}, btn_b: {52, 16}, prize: {18768, 3912}},
112 %{btn_a: {29, 45}, btn_b: {85, 11}, prize: {3149, 4161}},
113 %{btn_a: {81, 95}, btn_b: {67, 12}, prize: {5489, 2110}},
114 %{btn_a: {48, 58}, btn_b: {86, 22}, prize: {4802, 2280}},
115 %{btn_a: {27, 59}, btn_b: {47, 15}, prize: {2602, 2090}},
116 %{btn_a: {39, 87}, btn_b: {94, 38}, prize: {8830, 6134}},
117 %{btn_a: {23, 61}, btn_b: {82, 16}, prize: {8405, 3957}},
118 %{btn_a: {54, 14}, btn_b: {24, 63}, prize: {894, 1708}},
119 %{btn_a: {26, 14}, btn_b: {18, 35}, prize: {5510, 12541}},
120 %{btn_a: {65, 55}, btn_b: {21, 69}, prize: {430, 620}},
121 %{btn_a: {11, 62}, btn_b: {50, 11}, prize: {11414, 3683}},
122 %{btn_a: {21, 54}, btn_b: {93, 22}, prize: {7683, 5642}},
123 %{btn_a: {20, 95}, btn_b: {52, 29}, prize: {5580, 10155}},
124 %{btn_a: {37, 13}, btn_b: {11, 66}, prize: {18250, 14983}},
125 %{btn_a: {54, 28}, btn_b: {37, 58}, prize: {17939, 14902}},
126 %{btn_a: {87, 65}, btn_b: {11, 79}, prize: {3765, 4087}},
127 %{btn_a: {74, 30}, btn_b: {16, 59}, prize: {9858, 8342}},
128 %{btn_a: {74, 31}, btn_b: {17, 59}, prize: {14764, 6598}},
129 %{btn_a: {12, 95}, btn_b: {27, 33}, prize: {945, 3324}},
130 %{btn_a: {21, 36}, btn_b: {34, 14}, prize: {7247, 5012}},
131 %{btn_a: {48, 62}, btn_b: {90, 29}, prize: {9150, 5973}},
132 %{btn_a: {93, 43}, btn_b: {49, 91}, prize: {7090, 6422}},
133 %{btn_a: {28, 70}, btn_b: {68, 21}, prize: {17176, 3693}},
134 %{btn_a: {33, 16}, btn_b: {27, 51}, prize: {1884, 2771}},
135 %{btn_a: {11, 43}, btn_b: {51, 19}, prize: {4114, 10066}},
136 %{btn_a: {26, 70}, btn_b: {87, 46}, prize: {3532, 6874}},
137 %{btn_a: {22, 35}, btn_b: {38, 13}, prize: {7508, 16592}},
138 %{btn_a: {33, 16}, btn_b: {48, 72}, prize: {12065, 15896}},
139 %{btn_a: {67, 25}, btn_b: {14, 55}, prize: {4093, 10275}},
140 %{btn_a: {36, 17}, btn_b: {43, 77}, prize: {3253, 1933}},
141 %{btn_a: {84, 24}, btn_b: {42, 69}, prize: {8862, 4869}},
142 %{btn_a: {70, 16}, btn_b: {17, 68}, prize: {5690, 3224}},
143 %{btn_a: {58, 27}, btn_b: {44, 92}, prize: {1890, 1595}},
144 %{btn_a: {64, 30}, btn_b: {29, 57}, prize: {15004, 15224}},
145 %{btn_a: {13, 90}, btn_b: {64, 33}, prize: {6560, 6048}},
146 %{btn_a: {37, 91}, btn_b: {64, 49}, prize: {5214, ...}},
147 %{btn_a: {12, 80}, btn_b: {75, ...}, prize: {...}},
148 %{btn_a: {27, ...}, btn_b: {...}, ...},
149 %{btn_a: {...}, ...},
150 %{...},
151 ...
152]
153```
154
155Yay, matrices again. We need to solve linear equations in form of:
156
157$$
158\begin{cases}
159a_x x & + & b_x y & = & p_x \\
160a_y x & + & b_x y & = & p_y
161\end{cases}
162$$
163
164So we need to solve:
165
166$$
167\begin{bmatrix}
168a_x & b_x \\
169a_y & b_y
170\end{bmatrix}
171\begin{bmatrix}
172x \\
173y
174\end{bmatrix}
175= \begin{bmatrix}
176p_x \\
177p_y
178\end{bmatrix}
179$$
180
181For each game. So we can use [Cramer's Rule](https://en.wikipedia.org/wiki/Cramer%27s_rule).
182
183$$
184\begin{gather*}
185x = \frac{\text{det}(A_x)}{\text{det}(A)} \\
186y = \frac{\text{det}(A_y)}{\text{det}(A)}
187\end{gather*}
188$$
189
190Assuming that $\text{det}(A) \ne 0$ (otherwise there will be no solution). In case of $2\times2$ matrices determinant is simple to compute:
191
192$$
193\text{det}
194\begin{vmatrix}
195a & b \\
196c & d
197\end{vmatrix}
198= ad - bc
199$$
200
201So in the end we need to compute:
202
203$$
204\begin{gather*}
205x = \frac{p_x b_y - b_x p_y}{a_x b_y - b_x a_y} \\
206y = \frac{a_x p_y - p_x a_y}{a_x b_y - b_x a_y}
207\end{gather*}
208$$
209
210And reject cases where $x$ or $y$ is non-integer value.
211
212```elixir
213defmodule Game do
214 def solve(%{btn_a: {ax, ay}, btn_b: {bx, by}, prize: {px, py}}) do
215 det_a = ax * by - bx * ay
216 det_x = px * by - bx * py
217 det_y = ax * py - px * ay
218
219 if rem(det_x, det_a) == 0 do
220 {div(det_x, det_a), div(det_y, det_a)}
221 end
222 end
223end
224```
225
226<!-- livebook:{"output":true} -->
227
228```
229{:module, Game, <<70, 79, 82, 49, 0, 0, 8, ...>>, {:solve, 1}}
230```
231
232## Part 1
233
234```elixir
235games
236|> Enum.map(&Game.solve/1)
237|> Enum.map(fn
238 nil -> 0
239 {a, b} -> a * 3 + b * 1
240end)
241|> Enum.sum()
242```
243
244<!-- livebook:{"output":true} -->
245
246```
24731897
248```
249
250## Part 2
251
252```elixir
253games
254|> Enum.map(fn %{prize: {px, py}} = game ->
255 add = 10_000_000_000_000
256 %{game | prize: {px + add, py + add}}
257end)
258|> Enum.map(&Game.solve/1)
259|> Enum.map(fn
260 nil -> 0
261 {a, b} -> a * 3 + b * 1
262end)
263|> Enum.sum()
264```
265
266<!-- livebook:{"output":true} -->
267
268```
26987596249540359
270```
271
272<!-- livebook:{"offset":11449,"stamp":{"token":"XCP.AhVykQ8wyKxhTI29dXZZ0BnWEqWCuVGz8E2TRFpScgbUfqJJtY47yrvU9g9OzcejZVc8LbU3ak4YrgSGy5A5XeARPC3qt5fGPV4K9PYS3YabI7-q8rCKi8R6ZpGBpmZeDNQ","version":2}} -->