commit 36b32528b80b0f6f4016e6b5b68880006b27dc10
parent 2703ebecc972deca76a4737ebadd1554100ff296
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 14 Apr 2023 01:39:33 -0400
Add day 17 solution
Diffstat:
6 files changed, 276 insertions(+), 0 deletions(-)
diff --git a/src/17/Cargo.toml b/src/17/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "day17"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
diff --git a/src/17/input b/src/17/input
@@ -0,0 +1,2 @@
+target area: x=25..67, y=-260..-200
+
diff --git a/src/17/part1 b/src/17/part1
@@ -0,0 +1,136 @@
+--- Day 17: Trick Shot ---
+
+You finally decode the Elves' message. HI, the message says. You continue searching for the sleigh
+keys.
+
+Ahead of you is what appears to be a large ocean trench. Could the keys have fallen into it? You'd
+better send a probe to investigate.
+
+The probe launcher on your submarine can fire the probe with any integer velocity in the x (forward)
+and y (upward, or downward if negative) directions. For example, an initial x,y velocity like 0,10
+would fire the probe straight up, while an initial velocity like 10,-1 would fire the probe forward
+at a slight downward angle.
+
+The probe's x,y position starts at 0,0. Then, it will follow some trajectory by moving in
+[1m[97msteps[0m. On each step, these changes occur in the following order:
+
+
+ - The probe's x position increases by its x velocity.
+
+ - The probe's y position increases by its y velocity.
+
+ - Due to drag, the probe's x velocity changes by 1 toward the value 0; that is, it decreases by 1
+if it is greater than 0, increases by 1 if it is less than 0, or does not change if it is already 0.
+
+ - Due to gravity, the probe's y velocity decreases by 1.
+
+
+For the probe to successfully make it into the trench, the probe must be on some trajectory that
+causes it to be within a [1m[97mtarget area[0m after any step. The submarine computer has already calculated
+this target area (your puzzle input). For example:
+
+target area: x=20..30, y=-10..-5
+This target area means that you need to find initial x,y velocity values such that after any step,
+the probe's x position is at least 20 and at most 30, [1m[97mand[0m the probe's y position is at least -10 and
+at most -5.
+
+Given this target area, one initial velocity that causes the probe to be within the target area
+after any step is 7,2:
+
+.............#....#............
+.......#..............#........
+...............................
+S........................#.....
+...............................
+...............................
+...........................#...
+...............................
+....................TTTTTTTTTTT
+....................TTTTTTTTTTT
+....................TTTTTTTT#TT
+....................TTTTTTTTTTT
+....................TTTTTTTTTTT
+....................TTTTTTTTTTT
+
+In this diagram, S is the probe's initial position, 0,0. The x coordinate increases to the right,
+and the y coordinate increases upward. In the bottom right, positions that are within the target
+area are shown as T. After each step (until the target area is reached), the position of the probe
+is marked with #. (The bottom-right # is both a position the probe reaches and a position in the
+target area.)
+
+Another initial velocity that causes the probe to be within the target area after any step is 6,3:
+
+...............#..#............
+...........#........#..........
+...............................
+......#..............#.........
+...............................
+...............................
+S....................#.........
+...............................
+...............................
+...............................
+.....................#.........
+....................TTTTTTTTTTT
+....................TTTTTTTTTTT
+....................TTTTTTTTTTT
+....................TTTTTTTTTTT
+....................T#TTTTTTTTT
+....................TTTTTTTTTTT
+
+Another one is 9,0:
+
+S........#.....................
+.................#.............
+...............................
+........................#......
+...............................
+....................TTTTTTTTTTT
+....................TTTTTTTTTT#
+....................TTTTTTTTTTT
+....................TTTTTTTTTTT
+....................TTTTTTTTTTT
+....................TTTTTTTTTTT
+
+One initial velocity that [1m[97mdoesn't[0m cause the probe to be within the target area after any step is
+17,-4:
+
+S..............................................................
+...............................................................
+...............................................................
+...............................................................
+.................#.............................................
+....................TTTTTTTTTTT................................
+....................TTTTTTTTTTT................................
+....................TTTTTTTTTTT................................
+....................TTTTTTTTTTT................................
+....................TTTTTTTTTTT..#.............................
+....................TTTTTTTTTTT................................
+...............................................................
+...............................................................
+...............................................................
+...............................................................
+................................................#..............
+...............................................................
+...............................................................
+...............................................................
+...............................................................
+...............................................................
+...............................................................
+..............................................................#
+
+The probe appears to pass through the target area, but is never within it after any step. Instead,
+it continues down and to the right - only the first few steps are shown.
+
+If you're going to fire a highly scientific probe out of a super cool probe launcher, you might as
+well do it with [1m[97mstyle[0m. How high can you make the probe go while still reaching the target area?
+
+In the above example, using an initial velocity of 6,9 is the best you can do, causing the probe to
+reach a maximum y position of [1m[97m45[0m. (Any higher initial y velocity causes the probe to overshoot the
+target area entirely.)
+
+Find the initial velocity that causes the probe to reach the highest y position and still eventually
+be within the target area after any step. [1m[97mWhat is the highest y position it reaches on this
+trajectory?[0m
+
+
diff --git a/src/17/part2 b/src/17/part2
@@ -0,0 +1,28 @@
+--- Part Two ---
+
+Maybe a fancy trick shot isn't the best idea; after all, you only have one probe, so you had better
+not miss.
+
+To get the best idea of what your options are for launching the probe, you need to find
+[1m[97mevery initial velocity[0m that causes the probe to eventually be within the target area after any step.
+
+In the above example, there are [1m[97m112[0m different initial velocity values that meet these criteria:
+
+23,-10 25,-9 27,-5 29,-6 22,-6 21,-7 9,0 27,-7 24,-5
+25,-7 26,-6 25,-5 6,8 11,-2 20,-5 29,-10 6,3 28,-7
+8,0 30,-6 29,-8 20,-10 6,7 6,4 6,1 14,-4 21,-6
+26,-10 7,-1 7,7 8,-1 21,-9 6,2 20,-7 30,-10 14,-3
+20,-8 13,-2 7,3 28,-8 29,-9 15,-3 22,-5 26,-8 25,-8
+25,-6 15,-4 9,-2 15,-2 12,-2 28,-9 12,-3 24,-6 23,-7
+25,-10 7,8 11,-3 26,-7 7,1 23,-9 6,0 22,-10 27,-6
+8,1 22,-8 13,-4 7,6 28,-6 11,-4 12,-4 26,-9 7,4
+24,-10 23,-8 30,-8 7,0 9,-1 10,-1 26,-5 22,-9 6,5
+7,5 23,-6 28,-10 10,-2 11,-1 20,-9 14,-2 29,-7 13,-3
+23,-5 24,-8 27,-9 30,-7 28,-5 21,-10 7,9 6,6 21,-5
+27,-10 7,2 30,-9 21,-8 22,-7 24,-9 20,-6 6,9 29,-5
+8,-2 27,-8 30,-5 24,-7
+
+[1m[97mHow many distinct initial velocity values cause the probe to be within the target area after any
+step?[0m
+
+
diff --git a/src/17/src/main.rs b/src/17/src/main.rs
@@ -0,0 +1,102 @@
+/* vx: starting velocity, tx: target
+ *
+ * tx = vx * s - s * (s - 1) / 2
+ * 0 = -s^2 + s + 2 * vx * s - 2 * tx
+ * 0 = s^2 - (1 + 2 * vx) * s + 2 * tx
+ * s = (1 + 2 * vx) / 2 +- sqrt((1 + 2 * vx)^2 / 4 - 2 * tx)
+ *
+ * ty = vy * s - s * (s - 1) / 2
+ * vy = ty / s + (s - 1) / 2
+ *
+ * tx' = vx - s + 1/2
+ * max height reached at s = vx, ty = vy * vx - vx * (vx - 1) / 2
+ *
+ * 0 = s^2 - s (vx + vy + 1) + tx + ty
+ *
+ * for vx != vy: s = (tx - ty) / (vx - vy)
+ * for vx == vy: s = (vx + vy + 1) / 2 +- sqrt((vx + vy + 1)^2/4 - tx - ty)
+ *
+ * vx is bounded by the distance tx and minimum value that still reaches tx:
+ * s = vx, tx = vx * vx - vx * (vx - 1) / 2
+ * 2 tx = 2 vx^2 - vx^2 + vx
+ * 0 = vx^2 + vx - 2 tx
+ * => vx_min = -1/2 +- sqrt(1/4 + 2 tx), vx_max = tx
+ * ^ can also derive via term in sqrt(..) when solve vx eq for s
+ *
+ * - itere over target position x values
+ * - iterate over possible vx
+ * - determine step count s in one dimension:
+ * s = (1 + 2 * vx) / 2 - sqrt((1 + 2 * vx)^2 / 4 - 2 * tx)
+ * - if s = vx.. there are infinitely many s > vx that fulfill the conditions
+ * => use ty * 2 as a bounds, since vy = ty / s + (s - 1) / 2
+ * - itere over target position y values
+ * - compute whole-numbered velocity that will hit target, else skip
+ * - compute max height of arch:
+ * maxy = y(vy)
+ */
+
+#[derive(PartialEq,Eq,PartialOrd,Ord)]
+struct Trajectory {
+ vx: isize,
+ vy: isize,
+}
+
+fn parse_input(input: &str) -> (isize, isize, isize, isize) {
+ let (line, _) = input.split_once("\n").unwrap();
+ let (_, rest) = line.split_once("target area: ").unwrap();
+ let lambda = |r: &str| r.split_once("=").unwrap().1
+ .split("..").map(|v| v.parse::<isize>().unwrap()).collect();
+ let ranges: Vec<Vec<isize>> = rest.split(", ").map(lambda).collect();
+ return (ranges[0][0], ranges[0][1], ranges[1][0], ranges[1][1])
+}
+
+fn gen_trajectories(minx: isize, maxx: isize, miny: isize, maxy: isize) -> Vec<Trajectory> {
+ let mut trajectories: Vec<Trajectory> = Vec::new();
+ for tx in minx..maxx+1 {
+ let minvx = f32::ceil(-0.5 + f32::sqrt(0.25 + 2.0 * (tx as f32))) as isize;
+ for vx in isize::max(1, minvx)..tx+1 {
+ let t = (1.0 + 2.0 * (vx as f32)) / 2.0;
+ let u = f32::sqrt(t * t - 2.0 * (tx as f32));
+ let s = if t > u { t - u } else { t + u };
+ assert!(s > 0.0);
+ if s != s.round() { continue; }
+ let si = s as isize;
+ for ty in miny..maxy+1 {
+ for sn in if si == vx { si..isize::abs(ty)*2+1 } else { si..si+1 } {
+ let vy = (ty as f32) / (sn as f32) + ((sn as f32) - 1.0) / 2.0;
+ aoc::debugln!("{} {} ({}) {} {}", tx, ty, sn, vx, vy);
+ if vy != vy.round() { continue; }
+ let t = Trajectory { vx, vy: vy as isize };
+ let _ = t.vx; /* silence warn about unused var */
+ trajectories.push(t);
+ }
+ }
+ }
+ }
+ return trajectories;
+}
+
+fn part1(aoc: &mut aoc::Info) {
+ let (minx, maxx, miny, maxy) = parse_input(&aoc.input);
+ let trajectories = gen_trajectories(minx, maxx, miny, maxy);
+ let maxy_f = |vy| f32::floor((vy as f32) * (vy as f32)
+ - (vy as f32) * ((vy as f32) - 1.0) / 2.0) as isize;
+ let answer = trajectories.iter().map(|t| maxy_f(t.vy)).max().unwrap();
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("33670");
+}
+
+fn part2(aoc: &mut aoc::Info) {
+ let (minx, maxx, miny, maxy) = parse_input(&aoc.input);
+ let mut trajectories = gen_trajectories(minx, maxx, miny, maxy);
+ trajectories.sort();
+ trajectories.dedup();
+ let answer = trajectories.len();
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("4903");
+}
+
+fn main() {
+ aoc::run(part1, part2);
+}
+
diff --git a/src/17/test1 b/src/17/test1
@@ -0,0 +1 @@
+target area: x=20..30, y=-10..-5
