aoc/year2021/
day17.rs

1//! # Trick Shot
2//!
3//! Although this problem is easy to brute force, we can apply some reasoning and simplify both
4//! parts.
5//!
6//! ## Part One
7//! Part one can be solved analytically. Movement upwards in the positive y direction is
8//! symmetrical. For example, launching a probe at a y-velocity of 5 initially,
9//! would result in a speed and y-position:
10//!
11//! ```text
12//!     Time:       0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12
13//!     Speed:      5,  4,  3,  2,  1,  0, -1, -2, -3, -4, -5, -6, -7
14//!     Y-Position: 0,  5,  9, 12, 14, 15, 15, 14, 12,  9,  5,  0, -6
15//! ```
16//!
17//! The maximum y velocity is reached when we *just* touch the target area on the way down at the
18//! bottom y-coordinate. For the example above, if the bottom y coordinate was -6 then the maximum
19//! initial upwards velocity is one less, our starting velocity of 5.
20//!
21//! The maximum height is `5 + 4 + 3 + 2 + 1`, which is the sum from 1 to n given by the formula for
22//! triangular numbers [`(n * (n + 1) / 2`](https://en.wikipedia.org/wiki/Triangular_number#Formula).
23//!
24//! ## Part Two
25//! A brute force solution would check every possible combination of `x` and `y` for a total
26//! complexity of `O(xy)`. By thinking in terms of time `t` instead and applying a dynamic
27//! programming solution we can instead solve in a complexity of `O(x + y)` by treating `x` and `y`
28//! independently.
29//!
30//! We create 2 `vecs`. The first `new` counts how many x-velocity values enter the target area at
31//! time `t` for the first time, only considering horizontal movement. The second `continuing`
32//! counts how many are still in the target area at time `t`.
33//!
34//! For example, using the sample `target area: x=20..30, y=-10..-5` gives a progression:
35//!
36//! ```text
37//!     X-Velocity : 6
38//!     Time:        0,  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
39//!     New:         0,  0, 0, 0, 0, 1, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
40//!     Continuing:  0,  0, 0, 0, 0, 0, 1, 1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1
41//!
42//!     X-Velocity : 7
43//!     Time:        0,  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
44//!     New:         0,  0, 0, 0, 1, 1, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
45//!     Continuing:  0,  0, 0, 0, 0, 1, 2, 2, 2, 2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2
46//!
47//!     X-Velocity : 8
48//!     Time:        0,  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
49//!     New:         0,  0, 0, 1, 1, 1, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
50//!     Continuing:  0,  0, 0, 0, 1, 2, 2, 2, 2, 2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2
51//!
52//!     ...
53//!
54//!     X-Velocity : 30
55//!     Time:        0,  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
56//!     New:         0, 11, 5, 3, 1, 1, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
57//!     Continuing:  0,  0, 0, 1, 2, 2, 2, 2, 2, 2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2
58//! ```
59//!
60//! Then for each y velocity value we find the time when it enters the target area. The first time
61//! this happens we add *both* `new` and `continuing` to the total. For subsequent times while we're
62//! still in the target area we add only the `new` values, as the `continuing` are trajectories
63//! that we've already considered. For example, for an initial y-velocity of 0:
64//!
65//! ```text
66//!     Time:       0,   1,   2,     3,   4
67//!     Speed:      0,  -1,  -2,    -3,  -4
68//!     Y-Position: 0,  -1,  -3,    -6, -10
69//!     Total:      0,   0,   0, 3 + 1,   5
70//! ```
71//!
72//! Summing this for all y-velocity values gives the desired result.
73use crate::util::iter::*;
74use crate::util::parse::*;
75
76type Input = [i32; 4];
77
78pub fn parse(input: &str) -> Input {
79    input.iter_signed().chunk::<4>().next().unwrap()
80}
81
82pub fn part1(input: &Input) -> i32 {
83    let &[_, _, bottom, _] = input;
84    let n = -(bottom + 1);
85    n * (n + 1) / 2
86}
87
88pub fn part2(input: &Input) -> usize {
89    let &[left, right, bottom, top] = input;
90
91    // Find minimum dx where triangular number reaches left boundary.
92    let min_dx = (1..left).find(|&n| n * (n + 1) / 2 >= left).unwrap();
93    let max_dx = right + 1;
94    let min_dy = bottom;
95    let max_dy = -bottom;
96
97    let max_t = (1 - 2 * bottom) as usize;
98    let mut new = vec![0; max_t];
99    let mut continuing = vec![0; max_t];
100    let mut total = 0;
101
102    for mut dx in min_dx..max_dx {
103        let mut x = 0;
104        let mut first = true;
105
106        for t in 0..max_t {
107            if x > right {
108                break;
109            }
110            if x >= left {
111                if first {
112                    first = false;
113                    new[t] += 1;
114                } else {
115                    continuing[t] += 1;
116                }
117            }
118            x += dx;
119            dx = (dx - 1).max(0);
120        }
121    }
122
123    for mut dy in min_dy..max_dy {
124        let mut y = 0;
125        let mut t = 0;
126        // Skip the positive arc, assuming top is negative.
127        if dy > 0 {
128            t = 2 * dy as usize + 1;
129            dy = -dy - 1;
130        }
131        let mut first = true;
132
133        while y >= bottom {
134            if y <= top {
135                if first {
136                    first = false;
137                    total += continuing[t];
138                }
139                total += new[t];
140            }
141            y += dy;
142            dy -= 1;
143            t += 1;
144        }
145    }
146
147    total
148}
aoc/year2021/day17.rs

aoc/year2021/
day17.rs
