Advent of Code 2021 - Day 17

Today, I made a poor start, as I woke up 20 minutes late, but I finished fairly well with a very fast validation for the second part.

Problem description

The problem goal is to fire a probe, and to choose the correct initial velocity, in order to abide to a condition given in the input data, with the format target area: x=119..176, y=-141..-84.

Let’s define the sequences $(x_n)$, $(y_n)$, $(x'_n)$ and $(y'_n)$, as :

and

The sequences $x_n$ and $y_n$ represent the position of the probe. $x'_n$ and $y'_n$ represent its velocity. The objective is to look the $X$ and $Y$ values that satisfiy the following conditions :

Before continuing, let’s study briefly these sequences.

It appears that the $(x_n)$ sequence is “eventually constant”, and its non-constant part is increasing.

If $Y \le 0$, the sequence is monotone and decreasing. However, if $Y \gt 0$, the sequence increases, then it decreases.

Part 1

This is a constrained optimisation problem.

The objective is to find the highest reachable y position, while still satisfying the condition given above. This was the most difficult part so far this year, for me.

First, we define a structure to represent the condition given above :

pub struct TargetArea {
    x: RangeInclusive<i64>,
    y: RangeInclusive<i64>
}

Then, a we write a parsing function, that returns a TargetArea from the input data. For the first time this year, I chose to use regular expressions.

pub fn parse_target_area(input: &String) -> TargetArea {
    let re = Regex::new(r"^target area: x=(?P<xmin>-?\d+)\.\.(?P<xmax>-?\d+), y=(?P<ymin>-?\d+)\.\.(?P<ymax>-?\d+)$").unwrap();
    let caps = re.captures(input).unwrap();

    let xmin = caps.name("xmin").unwrap().as_str().parse().expect("xmin must be an integer");
    let xmax = caps.name("xmax").unwrap().as_str().parse().expect("xmax must be an integer");
    let ymin = caps.name("ymin").unwrap().as_str().parse().expect("ymin must be an integer");
    let ymax = caps.name("ymax").unwrap().as_str().parse().expect("ymax must be an integer");

    TargetArea { x: xmin..=xmax, y: ymin..=ymax }
}

The interesting part starts here. We have now to compute the probe trajectory. A good idea is to compute $(x_n)$ and (y_n) in distinct functions, as these two squences are entirely independant from each other.

The function x_sequence returns the non-constant part of $(x_n)$.

pub fn x_sequence(vx0: i64) -> Vec<i64> {
    let mut x = 0;
    let mut seq = vec![x];
    let mut vx = vx0;

    while vx != 0 {
        x += vx;
        if vx > 0 {
            vx = 0.max(vx - 1);
        }
        else {
            vx = 0.min(vx + 1);
        }
        seq.push(x);
    }

    seq
}

The function y_sequence computes $(y_n)$ until $y_n \lt y_min$.

pub fn y_sequence(vy0: i64, ymin: i64) -> Vec<i64> {
    let mut y = 0;
    let mut seq = vec![y];
    let mut vy = vy0;

    while y >= ymin {
        y += vy;
        vy -= 1;
        seq.push(y);
    }

    seq
}

Now, the most difficult part is to determine which values of $X$ and $Y$ will be tested to find the maximum height.

$x_min$ and $x_max$ are both positive, so $X$ must be positive too, and as the $(x_n)$ sequence is increasing, at least one term of this sequence must be inferior to $x_max$. So we have $0 \le X \le x_max$

In the same way, at least one term of $(y_n)$ must be superior to $y_min$, so $y \gt y_min$. But for the first part of the puzzle, we only test positive values of $Y$, as the sequence $(y_n)$ is negative if $Y \le 0$.

The upper bound of $Y$ was the greatest difficulty for me, until I noticed that for $n = 2y + 1, y_n = y_0 = 0$, and $y'_n = -y$. So I decided to test values of $Y$ inferior to $-y_min$.

The function in_target() tests, for a given $Y$, the number of values of $X$ that make the probe reach the target. If this function returns a strictly positive value, this means that the tested value of $Y$ allows the probe to reach the target. We just have to compute the corresponding max height value, a triangular number.

pub fn in_target(vy0: i64, target_area: &TargetArea, x_seqs: &Vec<Vec<i64>>) -> usize {
    let mut yin = Vec::new();
    let mut xin_count = 0;

    let yseq = y_sequence(vy0, *target_area.y.start());
    for i in 0..yseq.len() {
        if target_area.y.contains(&yseq[i]) {
            yin.push(i);       
        }
    }

    for vx0 in 0..=*target_area.x.end() {
        for i in &yin {
            let xi = match x_seqs[vx0 as usize].get(*i) {
                Some(v) => *v, 
                None => *x_seqs[vx0 as usize].last().unwrap()
            };

            if target_area.x.contains(&xi) {
                xin_count += 1;
                break;
            }
        }
    }
    xin_count
}

pub fn solve_part1(input: &Vec<String>) -> i64 {
    let target_area = parse_target_area(input.get(0).unwrap());
    let mut ymax = vec![0];

    let mut x_seqs = Vec::new();
    for vx0 in 0..=*target_area.x.end() {
        x_seqs.push(x_sequence(vx0));
    }

    for vy0 in 0..-target_area.y.start() {
        if in_target(vy0, &target_area, &x_seqs) > 0 { 
            ymax.push(vy0 * (vy0 + 1) / 2);
        }
    }

    *ymax.iter().max().unwrap()
}

Part 2

This part is much simpler, and I spent only 12 minutes to complete it.

The goal to count the number of distinct $(X, Y)$ values that allow the probe to reach the target.

The function in_target() is directly reusable.

pub fn solve_part2(input: &Vec<String>) -> usize {
    let target_area = parse_target_area(input.get(0).unwrap());
    let mut count = 0;

    let mut x_seqs = Vec::new();
    for vx0 in 0..=*target_area.x.end() {
        x_seqs.push(x_sequence(vx0));
    }

    let mut vy0 = *target_area.y.start();
    while vy0 <= -target_area.y.start() {
        count += in_target(vy0, &target_area, &x_seqs);
        vy0 += 1;
    }

    count
}

A note on other contestants solutions.

When I reviewed some other solutions to this puzzle, I noticed that many people used totally arbitrary domains for $X$ and $Y$ variables. I think this is a bad idea, for two reasons :

• Performance : this leads to many useless calculations.
• Safety : If the arbitrary domain is badly guessed (i.e if there is a valid $(X, Y)$ outside of it), the given answers will probably be wrong.