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