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

aoc/year2021/
day17.rs
