Day 17: Trick Shot

Day #17 problem description │ Problem input

Holy crap. This problem was hard.

After looking at the subreddit it looks like most people just brute forced it. That’s easy, but where’s the fun in that? Where possible, we want to solve these problems in the most computationally efficient manner possible.

We are asked to find the initial $x$ - and $y$ -velocities that will land a projectile, fired from the origin, in a given rectangular region $R=[x_\mathrm{min}, x_\mathrm{max}]\times[y_\mathrm{min}, y_\mathrm{max}]$ . In the $x$ -direction, the projectile suffers from drag, so its $x$ -velocity decreases by 1 each tick until it hits 0 (at which point it can’t slow down anymore). In the $y$ -direction, the projectile is affected by gravity (but no drag (?)), so its $y$ -velocity decreases by each tick, forever.

All numbers — time, positions, and velocities — must be (not-necessarily-positive) integers. (And, naturally, time must be positive.) This is an important and helpful constraint on the values we can use.

The solution below does not use brute force; it does not, for instance, try all $v_x$ s between 0 and $R$ 's right edge, or all $v_y$ s between $-\mathrm{abs}(v_\mathrm{max})$ and $\mathrm{abs}(v_\mathrm{max})$ . All potential times, positions, and speeds are derived mathematically. It has no problem running on a target area of x=1000000..1001000, y=-1000000..-1001000 (although this particular target area requires being able to take the integer square root of large numbers, which I did not implement myself).

Setup

type Time = i64;
type Num = i64;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Pos<T> {
	x: T,
	y: T,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Velo<T> {
	vx: T,
	vy: T,
}

#[derive(Debug, Clone, Copy)]
struct Rect<T> {
	x_min: T,
	x_max: T,
	y_min: T,
	y_max: T,
}

#[derive(Debug, Clone, Copy)]
struct Trajectory {
	_t: Time,
	_pos: Pos<Num>,
	velo: Velo<Num>,
}

fn read_input(input: &str) -> Option<Rect<Num>> {
	let re = {
		regex::Regex::new(r"target area:\s*x=([\d-]+)\.\.([\d-]+),\s*y=([\d-]+)\.\.([\d-]+)")
			.ok()?
	};

	let caps = re.captures(input.trim())?;
	let [x1, x2, y1, y2] = // force line break :/
		[1, 2, 3, 4].map(|i| caps.get(i).and_then(|m| m.as_str().parse().ok()));

	let [x1, x2, y1, y2] = [x1?, x2?, y1?, y2?];

	let [x_min, x_max] = if x1 < x2 { [x1, x2] } else { [x2, x1] };
	let [y_min, y_max] = if y1 < y2 { [y1, y2] } else { [y2, y1] };

	Some(Rect {
		x_min,
		x_max,
		y_min,
		y_max,
	})
}

fn sqrt(n: Num) -> Option<Num> {
	let sqrt = Roots::sqrt(&n);
	if sqrt * sqrt == n {
		Some(sqrt)
	} else {
		None
	}
}

The Math

Because $x$ decreases by 1 each tick until it hits 0, and $y$ decreases by 1 each tick forever, we have the following equations for the $x$ - and $y$ -coordinates at time $t$ of a projectile fired with an initial velocity of $(v_x, v_y)$ . (Derivations are left to the reader, but a helpful fact is that $1+2+\ldots+n=\frac{1}{2}n(n+1)$ .)

\begin{align*} x(t, v_x) &= \begin{cases} v_x t - \frac{1}{2}t(t-1)&t \le v_x\\ \frac{1}{2}v_x(v_x+1)&t \ge v_x \end{cases}\\ y(t, v_y)&=v_y t - \frac{1}{2}t(t-1) \end{align*}

Note that even though the two definitions of $x$ overlap at $t=v_x$ , they also coincide there, so it’s not a problem.

Now, we must find the values of $(v_x,v_y)$ that land the projectile in $R$ . To do this, we simply find the values of $(v_x,v_y)$ that will land the projectile precisely at a point $(x,y)$ in $R$ , for each $(x,y)\in R$ . And to do this, we find the $(v_x,v_y)$ that will land the projectile at $(x,y)$ precisely at time $t$ , for each positive $t$ .

To find the velocities that will land the projectile precisely at $(t,x,y)$ , we solve the above equations for $v_x$ and $v_y$ . Finding $v_y$ is simple: $v_y=\frac{2y+t(t-1)}{2t}$ . For $v_x$ , it’s a bit more complicated, as we have two options:

v_x=\begin{cases} \frac{2x+t(t-1)}{2t}&t\le v_x\\ \frac{-1\pm\sqrt{1+8x}}{2}&t\ge v_x \end{cases}

And as we said above, we need everything to be an integer, so we can either have no pairs of velocities that work, one pair, or two pairs.

fn find_velocities(t: Time, position: Pos<Num>) -> [Option<Velo<Num>>; 2] {
	if t == 0 {
		return [Some(Velo { vx: 0, vy: 0 }), None];
	}

	let Pos { x, y } = position;

	let vy_numer = 2 * y + t * (t - 1);
	let vy_denom = 2 * t;
	let vy = if vy_numer % vy_denom == 0 {
		vy_numer / vy_denom
	} else {
		return [None, None];
	};

	let vx1 = {
		let vx_numer = 2 * x + t * (t - 1);
		let vx_denom = 2 * t;
		let vx = vx_numer / vx_denom;
		if vx_numer % vx_denom == 0 && vx >= t {
			Some(vx)
		} else {
			None
		}
	};

	let vx2 = {
		let discriminant = 1 + 8 * x;
		sqrt(discriminant).and_then(|sqrt_disc| {
			let vx_numer = sqrt_disc - 1;
			let vx_denom = 2;
			let vx = vx_numer / vx_denom;
			if vx_numer % vx_denom == 0 && vx <= t {
				Some(vx)
			} else {
				None
			}
		})
	};

	[vx1, vx2].map(|opt_vx| opt_vx.map(|vx| Velo { vx, vy }))
}

Awesome. We have the 0, 1, or 2 velocities that will land the projectile at $(x, y)$ at time $t$ . But how to find the $t$ s for which the projectile can even land at $(x,y)$ ? We cannot enumerate all $t$ s, as there are infinitely many positive integers. Could we perhaps keep firing it with a larger and larger $v_y$ and hope that it would continue to land in $R$ at some point in its trajectory? The answer is no: there are only finitely many values of $v_y$ for which there exists a time $t$ such that the projectile has a vertical position of $y$ at $t$ . Let’s prove it, and let’s find them.

Solving the equation $y=v_y t- \frac{1}{2}t(t-1)$ for $t$ , we find that:

t=\frac{1}{2}\left((2v_y+1)\pm\sqrt{(2v_y+1)^2-8y}\right)

First and foremost, for this to be an integer, $(2v_y+1)^2-8y$ must be a perfect square. Letting $m^2 =(2v_y+1) ^ 2$ and $n^2 = m^2 - 8y$ , we have $m^2 - n^2 = 8y$ , which factors into $(m-n)(m+n)=8y$ . Since everything must be an integer, we can use the factor pairs of $8y$ to find $m$ and $n$ . If $8y=(m-n)(m+n)=k_1k_2$ , then $m=\frac{1}{2}(k_1+k_2)$ . Hence, if $2v_y+1=\frac{1}{2}(k_1+k_2)$ , then $(2v_y+1)^2 - 8y$ will indeed be a perfect square. Of course, we also need $\frac{1}{2}(k_1+k_2)$ to be an odd integer so that $v_y$ will be an integer. Finally, we plug $v_y$ into our equation for $t$ and if we get an integer, we’ve got a match: if the projectile is fired with a $y$ -velocity of $v_y$ , then it will hit the vertical position $y$ precisely at $t$ .

The astute reader will note that there every projectile with $v_y>0$ hits $y=0$ on the way down. Therefore we exclude $y=0$ from consideration altogether; a problem that included $y=0$ in $R$ would have infinitely many answers or be impossible to solve.

fn find_ts_and_vys_for_y(y: Num) -> Vec<(Time, Num)> {
	assert_ne!(y, 0);

	let mut ans = vec![];

	// Need to find all integer (t, vy) that satisfy y = vy * t - t*(t-1)/2 with t > 0
	//
	// Step one: (2*vy + 1)^2 - 8*y = must be square
	//
	// In other words there must exist integral m and n such that m^2 - n^2 = 8y (with
	// 2*vy + 1 = m). m^2 - n^2 = (m-n)*(m+n), and so...
	let eight_y = 8 * y;
	let abs_eight_y = eight_y.abs();
	for k1 in 1..=Roots::sqrt(&abs_eight_y) {
		if abs_eight_y % k1 != 0 {
			continue;
		}

		for sign in [-1, 1] {
			let k1 = sign * k1;
			let k2 = eight_y / k1;
			// k1 and k2 are now two signed integers that multiply to 8y

			let two_m = k1 + k2;
			if two_m % 2 != 0 {
				continue;
			}

			let m = two_m / 2;

			// Now, m was 2*vy + 1, and so...
			if (m - 1) % 2 != 0 {
				continue;
			}
			let vy = (m - 1) / 2;
			let discriminant = m * m - eight_y;
			if discriminant < 0 {
				continue;
			}

			let sqrt_disc = sqrt(discriminant).unwrap();

			for pm in [-1, 1] {
				let t_numer = 2 * vy + 1 + pm * sqrt_disc;
				if t_numer <= 0 || t_numer % 2 != 0 {
					continue;
				}
				let t = t_numer / 2;
				ans.push((t, vy));
			}
		}
	}

	ans
}

We are nearly there! To find whether, and how, the projectile can reach the point $(x,y)$ , we find:

the set of pairs $(t, v_y)$ that give the projectile a vertical position of $y$ at time $t$ , and
for each of these pairs, we check that the projectile can indeed reach $(x,y)$ at time $t$ (we know it can reach $y$ , but can it reach $x$ ?) and find the velocities $(v_x,v_y)$ that will achieve that, if possible.

And we simply do this for every $(x,y)\in R$ .

fn get_x(t: Time, vx: Num) -> Num {
	if t <= vx {
		vx * t - t * (t - 1) / 2
	} else {
		vx * (vx + 1) / 2
	}
}

fn get_trajectories(rect: Rect<Num>) -> Vec<Trajectory> {
	let Rect {
		x_min,
		x_max,
		y_min,
		y_max,
	} = rect;

	let mut trajectories = vec![];

	for y in y_min..=y_max {
		if y == 0 {
			// If any vx works, then there will be infinitely many choices for vy because it
			// retraces its ascent on its descent. And if no vx works, then it's moot
			continue;
		}

		let ts_and_vys = find_ts_and_vys_for_y(y);

		for (t, vy) in ts_and_vys {
			for x in x_min..=x_max {
				let velocities = find_velocities(t, Pos { x, y });

				for velo in velocities {
					let velo = match velo {
						Some(v) => v,
						None => continue,
					};
					if velo.vy == vy && get_x(t, velo.vx) == x {
						trajectories.push(Trajectory {
							_t: t,
							_pos: Pos { x, y },
							velo,
						});
					}
				}
			}
		}
	}

	trajectories
}

Once we get all the trajectories, the actual answers we’re asked for are pretty simple.

Part 1

Part 1 asks us to find the maximum possible height that can be achieved by a projectile that reaches $R$ . As we said above, a projectile with initial $y$ -velocity $v_y$ reaches an apex of $\frac{1}{2}v_y(v_y+1)$ .

fn pt1<T: std::borrow::Borrow<Trajectory>>(trajectories: impl Iterator<Item = T>) -> Option<Num> {
	trajectories
		.map(|traj| {
			let traj = *traj.borrow();
			let vy = traj.velo.vy;
			if vy < 0 {
				return 0;
			}
			vy * (vy + 1) / 2
		})
		.max()
}

Part 2

Part 2 asks us to simply count distinct initial velocities that land the projectile in $R$ .

fn pt2<T: std::borrow::Borrow<Trajectory>>(trajectories: impl Iterator<Item = T>) -> usize {
	trajectories
		.map(|traj| {
			let Trajectory { velo, .. } = *traj.borrow();
			(velo.vx, velo.vy)
		})
		.collect::<Set<_>>()
		.len()
}