Advent of Code 2024, Day 7

Today we’re parsing a bunch of numbers, dealing with buffer overflow due to badly sizing our variables, and generating all variations of things using binary.

Spoilers after the header, links just below. Let’s get into it!

adventofcode2024/day07 at main · javorszky/adventofcode2024

Contribute to javorszky/adventofcode2024 development by creating an account on GitHub.

GitHubjavorszky

Spoilers

Part 1

Honestly the hardest part was figuring out how to generate all possible variations of operators that I could plop into the spaces between the parts on each line. Parsing the lines into a data structure was easy enough. My choice was this:

struct Line {
    target: i64,
    parts: Vec<i64>
}

Could I have chosen u64? Probably. I did in part 2.

As Rust doesn’t have the concept of functions as values, I can’t really easily save a function to a variable, and then pass that variable around like I can in Golang or Elixir. So what’s left is a different way of generating possible variations. This stack overflow post helped me a lot: https://www.reddit.com/r/rust/comments/91h6t8/generating_all_possible_case_variations_of_a/ and the playground that’s linked to from there: https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=8cbf699864db9c3a9af2e71b7da75c44.

The gist of it is you find out how long your things need to be. I have two possible values, an addition or a product, and I have len-1 spaces between the numbers: for a list of [1, 2, 3, 4] I have three spaces, each can take two options for a total of 8 possible variations. I need to use two for loops here: the outer one goes from 0 to 7 (binaries 000 and 111), and the inner loop moves a single 1 over one space at a time at equal length to the binary using (1 << index).

let binary_end = 2u32.pow((len-1) as u32)-1;

for mask in 0..binary_end {
    let mut variation: Vec<Operator> = Vec::new();
    
    for test in 0..l.parts.len()-1 {
        if mask & (1 << test) == 0 {
            variation.push(Operator::Add);
        } else {
            variation.push(Operator::Product);
        }
    }
}

The mask is going to loop through all the binaries up to 2^len-1. You might be thinking:

Gabor, what the f is that 2u32.pow((len-1) as u32)-1 there?!

Excellent question! So.

• 2u32 means take the literal (and thus unknown type) number and treat it as a u32 type
• .pow is the function to raise a u32 number to whatever exponent, see the docs for power
• (len-1) is the exponent we need to raise 2. len of our parts of the example above is 4, we have n-1 gaps, so we need the -1
• as u32, treat the number coming before it as a u32. Because len is a usize, because that one comes from Vec<_>::len, also see the docs for vector len, the resulting number is also going to be usize
• -1 because 8 (2^3) is actually binary 1000, and we need 111, which is 7 decimal

Basically what it’s going to do is for every mask, which has all the possible ways three digits can be either 0 or 1, it will translate that into a list of add or product by comparing the end result to 0.

[]; // starting with an empty list. add = 0, product != 0

110 &
001 =
000 = 0
[add] // result is 0, so first element is an add

110 &
010 =
010 != 0
[add, product] // result is not 0, so second element is a product

110 &
100 =
100 != 0
[add, product, product] // result is not 0, so third element is a product

It does’t keep the order, but that also doesn’t matter because all we really care about is that the list is complete, not that it’s in any specific order.

Once I have a combination, I can use my handy dandy manual operation executor function to actually do the thing. Starter number is the first one in the list, and then I iterate over the rest, pass the operator and the two numbers to the function, and save the result. I occasionally check whether the resulting number is greater than what I need, and if so, short circuit. Once every number has been dealt with for a particular set of operators, I check whether that’s the target number, and if so, return true. The function in question:

fn operate(left_number: i64, operator: &Operators, right_number: i64) -> i64 {
    match operator {
        Operators::Plus => {left_number + right_number}
        Operators::Product => {left_number * right_number}
    }
}

Fascinatingly simple. I also love enums!

Got the correct answer. The only gotcha I ran into is that the example input has small number, whereas occasionally the numbers in the actual input could not fit into an i32, which Rust told me by panicking about it.

Part 2

Reading the problem the hardest part is going to be generating all the possible lists the operators can be. Hold on ...

And yep, that’s what’s ended up being the hardest. The cool thing about having only two options is you can deal with binaries, because that’s base 2 given to you for free.

With the third option though, you need to do things in base 3. Not to worry, some juggling and paper doodling later I figured out how to turn a decimal into a vec of base 3 numbers (essentially remainders when dividing by 3), mapped those to the operators, forced the lenghts of the vec of operators to be the same as the gaps, and again generated all of them.

I also had to change everything to u64 mostly so the numbers fit in memory.

fn variants_to_base3(code: u64, len: usize) -> Vec<P2Operators>{
    let mut variants: Vec<P2Operators> = Vec::new();
    let mut steps = code;

    for _i in 0..len {
        let  remainder = steps.wrapping_rem(3);
        match remainder {
            0 => variants.push(P2Operators::Add),
            1 => variants.push(P2Operators::Multiply),
            2 => variants.push(P2Operators::Concatenate),
            _ => unreachable!()
        }

        steps = steps.checked_div(3).unwrap();
    }

    variants
}

The most useful function is above. I like that on integers I can call .checked_div, as well as all the others, and it gives me the flattened result throwing away the fraction. Then the .wrapping_rem gives me the remainder which I can map to an operator.

Executing part 2 took some time, but it’s still within seconds. Got my ⭐️⭐️!

Spoiler photo by Kevin Bhagat on Unsplash