this repo has no description
hauleth.dev
1<!-- vim:set ft=markdown: -->
2
3<!-- livebook:{"persist_outputs":true} -->
4
5# Day 17
6
7## Setup
8
9```elixir
10input = File.read!("day17.txt")
11# input = "target area: x=117..7310, y=-9546..-89"
12
13IO.puts(input)
14
15%{"a_x" => a_x, "a_y" => a_y, "b_x" => b_x, "b_y" => b_y} =
16 Regex.named_captures(
17 ~r/target area: x=(?<a_x>-?\d+)\.\.(?<b_x>-?\d+), y=(?<a_y>-?\d+)\.\.(?<b_y>-?\d+)/,
18 input
19 )
20
21a = %{x: String.to_integer(a_x), y: String.to_integer(a_y)}
22b = %{x: String.to_integer(b_x), y: String.to_integer(b_y)}
23
24[a: a, b: b]
25```
26
27<!-- livebook:{"output":true} -->
28
29```
30target area: x=288..330, y=-96..-50
31```
32
33<!-- livebook:{"output":true} -->
34
35```
36[a: %{x: 288, y: -96}, b: %{x: 330, y: -50}]
37```
38
39## Task 1
40
41### Lemma 1
42
43The horizontal velocity there can be ignored, as we can always find a horizontal velocity
44that will reach the target area and will reduce the velocity to $$0$$, which mean that all
45further movement will happen only in one dimension. That velocity is:
46
47$$
48v_x = \lceil \frac{-1 + \sqrt{1 + 8b_x}}{2} \rceil
49$$
50
51#### Proof:
52
53Which came from the fact that distance traveled by the projectile is sum of the arithmetic
54sequence with $$r = -1$$, so the distance traveled is:
55
56$$
57s_x = \frac{2v_{x0} - t + 1}{2}t
58$$
59
60Where $$t$$ is travel time. As $$v_x(t) = v_{x0}$$ then $$v_x(t) = 0 \implies t = v_{x0}$$,
61so after substituting $$t$$ we get:
62
63$$
64s_x = \frac{2v_{x0} - v_{x0} + 1}{2}v_{x0} \\
65s_x = \frac{v_{x0} + 1}{2}v_{x0} \\
66s_x = \frac{v_{x0}^2 + v_{x0}}{2}
67$$
68
69As we want to find the nearest column where we want to stop movement in $$OX$$ then
70we are looking at $$s_x = b_x$$:
71
72$$
73b_x = \frac{v_{x0}^2 + v_{x0}}{2} \\
742b_x = v_{x0}^2 + v_{x0} \\
750 = v_{x0}^2 + v_{x0} - 2b_x
76$$
77
78The soultions for these equation are in form of:
79
80$$
81v_{x0} = \frac{-1 \mp \sqrt{1 + 8b_x}}{2}
82$$
83
84As we assume that $$b_x \gt 0$$, then the solutions will always be trivial. Additionally
85we do not care about negative roots, so we can take only:
86
87$$
88v_{x0} = \frac{-1 + \sqrt{1 + 8b_x}}{2}
89$$
90
91As this can be fractional and we want $$v_x0 \in \mathbb{Z}$$ and assume that target is
92big enough to have at least one point that we can land on, then we can simply round velocity
93up:
94
95$$
96v_x = \lceil \frac{-1 + \sqrt{1 + 8b_x}}{2} \rceil\\
97$$
98
99$$\blacksquare$$
100
101### Lemma 2
102
103TODO
104
105As
106
107$$
108v_{y0} = \frac{2a_y - t + t^2}{2t}
109$$
110
111Left to prove that $$v_0$$ will have highest possible value for $$t = -2a_y$$.
112Then above equation reduces like that:
113
114$$
115v_{y0} = \frac{2a_y + 2a_y + 4a_y^2}{4a_y} \\
116v_{y0} = \frac{4a_y + 4a_y^2}{4a_y} \\
117v_{y0} = 1 + a_y
118$$
119
120```elixir
121v_y = -min(a.y, b.y) - 1
122
123{v_y, v_y * (v_y + 1) / 2}
124```
125
126<!-- livebook:{"output":true} -->
127
128```
129{95, 4560.0}
130```
131
132## Task 2
133
134```elixir
135solveq_pos = fn a, b, c ->
136 [
137 (-b - :math.sqrt(b * b - 4 * a * c)) / (2 * a),
138 (-b + :math.sqrt(b * b - 4 * a * c)) / (2 * a)
139 ]
140 |> Enum.filter(&(&1 > 0))
141end
142
143v_xmin_rest = ceil(hd(solveq_pos.(1, 1, -2 * min(a.x, b.x))))
144v_xmax_rest = floor(hd(solveq_pos.(1, 1, -2 * max(a.x, b.x))))
145
146v_ymax = -min(a.y, b.y) - 1
147v_ymin = min(a.y, b.y)
148
149{xmin, xmax} = Enum.min_max([a.x, b.x])
150{ymin, ymax} = Enum.min_max([a.y, b.y])
151
152offset = fn
153 0 -> {1, -1}
154 v_y when v_y > 0 -> {2 * v_y + 1, -v_y - 1}
155 v_y -> {0, v_y}
156end
157
158v_y_pairs =
159 for v_y <- v_ymin..v_ymax,
160 {offset, fv_y} = offset.(v_y),
161 tmin <- solveq_pos.(-1, 2 * fv_y + 1, -2 * ymax),
162 tmax <- solveq_pos.(-1, 2 * fv_y + 1, -2 * ymin),
163 ceil(tmin) <= floor(tmax),
164 t <- ceil(tmin)..floor(tmax),
165 do: {v_y, t + offset}
166
167v_x_pairs =
168 for t <- Enum.uniq(Enum.map(v_y_pairs, &elem(&1, 1))),
169 v_xmin_move = ceil((2 * xmin / t + t - 1) / 2),
170 v_xmax_move = floor((2 * xmax / t + t - 1) / 2),
171 xrange = Enum.filter(v_xmin_move..v_xmax_move, &(&1 >= t)),
172 xrange =
173 if(v_xmin_rest < t,
174 do: Enum.concat(xrange, v_xmin_rest..min(t, v_xmax_rest)),
175 else: xrange
176 ),
177 v_x <- MapSet.new(xrange),
178 do: {t, v_x}
179
180pairs =
181 for {v_y, t} <- v_y_pairs,
182 {^t, v_x} <- v_x_pairs,
183 into: MapSet.new(),
184 do: {v_x, v_y}
185
186MapSet.size(pairs)
187```
188
189<!-- livebook:{"output":true} -->
190
191```
1923344
193```