Advent of Code 2024 Day 7

Day 7: Bridge Repair

https://adventofcode.com/2024/day/7

Another day, another familiar location.

You are at a bridge that needs repairing. The elves fixing it need to do some final calculations, but they lost their operators, elephants stole them!
Tricksy elephantses

An example input looks like this:

190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20

Each line is information for a calculation.

• The number to the left of the colon is the goal number, the number the calculation should result in.
• The numbers to the right of the colon are the operands, the numbers being operated on.

It is your job to determine if the goal can be reached by applying operators to the operands.

Operators are alway evaluated left to right, elves are not bound by puny things like order of operations when doing math.

The only types of operands that are missing is add: +, and multiply *.

Parsing

Again, keeping things simple because that’s the most surefire way lots of people can translate this code to their language of preference without much effort.

Take in the input, return a list of:

1. The goal number
2. A list of numbers

pub fn parse(input: &str) -> Vec<(u64, Vec<u64>)> {
    let mut equations = Vec::new();
    for line in input.lines() {
        let (goal, nums) = line.split_once(':').unwrap();
        let goal: u64 = goal.parse().unwrap();
        let nums: Vec<u64> = nums
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect();
        equations.push((goal, nums));
    }
    equations
}

Part 1

The question asks for the sum of all goal numbers that are reachable.

Do you like recursion? I like recursion.

The main effort is in the helper function again. In the part_1 code, I loop over each line, determine if it’s reachable, and add the goal number to a sum if it is.

Helper

The helper takes in a goal number and a list of operands. It returns a boolean stating if that goal is reachable given the list of nums.

It does so one number at a time, applying an operation (+ or *), and recursing with the rest of the list.

I did this from left to right at first, but after watching HyperNeutrino’s video for today, I changed it to go from right to left.

This meant flipping the logic for the goal number from + to -, and from * to /. But it allowed me to check if performing an operation would even make sense before recursing, speeding the function up considerably.

fn is_reachable(goal: u64, nums: &[u64]) -> bool {
    if nums.len() == 1 {
        return goal == nums[0];
    }
    let (&last, rest) = nums.split_last().unwrap();
    if goal % last == 0 && is_reachable(goal / last, rest) {
        return true;
    }
    if goal > last && is_reachable(goal - last, rest) {
        return true;
    }
    false
}

Part 1 code

fn part_1(input: &str) -> u64 {
    let equations = parse(input);
    equations
        .into_iter()
        .filter(|(goal, nums)| is_reachable(*goal, nums))
        .map(|(goal, _nums)| goal)
        .sum()
}

Part 2

Turn out the elephants also stole some concatenation operators.

It squooshes two numbers together real tight, it’s like string concatenation, but with numbers.

Helper

The helper function changes slightly. It adds a check to see if concatenating a number makes sense (if the goal number ends in the last number), then it recurses with that last number “un”-concatenated (is that a word? It is now!).

I did this with some math as this is much faster than converting the numbers to strings first.

fn is_reachable_2(goal: u64, nums: &[u64]) -> bool {
    if nums.len() == 1 {
        return goal == nums[0];
    }
    let (&last, rest) = nums.split_last().unwrap();
    if goal % last == 0 && is_reachable_2(goal / last, rest) {
        return true;
    }
    if goal > last && is_reachable_2(goal - last, rest) {
        return true;
    }
    let last_len = last.ilog10() + 1;
    let magnitude = 10u64.pow(last_len);
    let goal_len = goal.ilog10() + 1;
    let ending = goal % magnitude;
    if goal_len > last_len && last == ending && is_reachable_2(goal / magnitude, rest) {
        return true;
    }
    false
}

Part 2 code

Same as part 1, but use the helper for part 2.

fn part_2(input: &str) -> u64 {
    let equations = parse(input);
    equations
        .into_iter()
        .filter(|(goal, nums)| is_reachable_2(*goal, nums))
        .map(|(goal, _nums)| goal)
        .sum()
}

Final code

For the final code I combined both helpers into one, and changed the parsing logic to be able to operate on one line at a time without first parsing the entire input.

1
fn parse(input: &str) -> impl Iterator<Item = (u64, Vec<u64>)> + '_ {
2
    input.lines().map(|line| {
3
        let (goal, nums) = line.split_once(':').unwrap();
4
        (
5
            goal.parse().unwrap(),
6
            nums.split_whitespace()
7
                .map(|s| s.parse().unwrap())
8
                .collect(),
9
        )
10
    })
11
}
12

13
fn is_reachable_all(goal: u64, nums: &[u64], concat: bool) -> bool {
14
    if nums.len() == 1 {
15
        return goal == nums[0];
16
    }
17
    let (&last, rest) = nums.split_last().unwrap();
18
    if goal % last == 0 && is_reachable_all(goal / last, rest, concat) {
19
        return true;
20
    }
21
    if goal > last && is_reachable_all(goal - last, rest, concat) {
22
        return true;
23
    }
24
    if concat {
25
        let last_len = last.ilog10() + 1;
26
        let magnitude = 10u64.pow(last_len);
27
        let goal_len = goal.ilog10() + 1;
28
        let ending = goal % magnitude;
29
        if goal_len > last_len && last == ending && is_reachable_all(goal / magnitude, rest, concat)
30
        {
31
            return true;
32
        }
33
    }
34
    false
35
}
36

37
pub fn part_1(input: &str) -> u64 {
38
    parse(input)
39
        .filter(|(goal, nums)| is_reachable_all(*goal, nums, false))
40
        .map(|(goal, _nums)| goal)
41
        .sum()
42
}
43

44
pub fn part_2(input: &str) -> u64 {
45
    parse(input)
46
        .filter(|(goal, nums)| is_reachable_all(*goal, nums, true))
47
        .map(|(goal, _nums)| goal)
48
        .sum()
49
}