Day 7 - Part 1

Oh this is interesting, we have operands and operators, we must work out which operators might work

There's going to be a lot of combinations here, but given only 2 operators, it's roughly n-squared for the number of operands, so it's not the worst performance.

I think a brute force search here is probably easiest.

We also can easily fold the answers as we calculate from left to rihgt, rather than any form of precedence rules.

So we need to read in something like 123: 1 23 and turn that into a total, and a vector of arguments.

We can then conduct a solve by trying combinations of operands for a given set of arguments...

That's a lot easier to write than code...

If we have operands MUL, and ADD, we need to work out how to handle MUL(ADD(1,2),3). We could take something like [1 2 3], and emit two options, [3 3] and [2 3], which is defined as [op(h1, h2), t] Or we could define some intermediate standard, like [1, MUL 2, ADD 3], where each operand takes the previous result and the next value.

I suspect for part 2, we might want to do the latter, but for now, I think we can try the first option. so for [2 4 8], we have ADD(2,4) -> [6 8], and MUL(2,4) -> [8 8], and then ADD(6,8) -> [8] and MUL(8,8) -> [64] We can end whenever we have a single answer, and of course, we then want to know how many of the answers were valid.

I strongly suspect that part 2 will require us to handle precedence, but we'll handle that when we get there.

Playing with AI

Ok, so while out on a walk, I pulled out my phone and asked Claude.ai for some tips on how to solve this, and it suggested a recursive algorithm with backtracking, which is of course, exactly how to easily solve this. I don't know why I didn't think of it before.

A recursive algorithm with backtracking is a great way to solve a problem involving combinations. The classic example of a recursive algorithm is working out the given sum of a fibonacci sequence. A given fibonacci number starts with the sequence 1, 1 and then is otherwise determined to be the sum of the previous 2 numbers, so 1+1 = 2, 1+2 = 3, 2+3 = 5 and so on.

You can work this out iteratively, but it's often much clearer and easier to work this out recursively, by defining a function that works out for fib(n) what fib(n-1)+fib(n-2) is. Of course, in order to work out what fib(n-1) is, it will also have to work out what fib(n-2) is. For simple cases, like the fibonacci sequence, this may not be an issue (and likely isn't in our case), but for anything complex or with really long inputs, we may want to cache results we've already worked out, through something called memoisation. But I think we'll come back to that on another day.

Let's start with the recursive function, and then come to backtracking later.

pub fn total(running_total:u32, args: &Vec<u32>, index: usize) -> u32 {
    // Our base case, make sure it returns when we run out of numbers
    if index == args.len() {
        return running_total;
    }
    // Handle addition, which is running_total + args[index] and repeat for next index
    total(running_total+args[index], args, index+1)
}

This function just does addition, and it works out that the sum of a given series is the running total of the rest of the series plus the current number.

We can also work out multiplication the same way, but this doesn't help us with identifying whether multiplication or addition is the right answer for a given total... for that we're going to need a goal and that's where backtracking comes in.

In the current case, we simply end when we've got to the end of the arguments, but in our new backtracking model, we're also going to take a target number we want to reach.

Instead of simply returning the sum when we run out of numbers, we're now going to compare whether we have hit the target or not.

if running_total == target
  { 1 }
else
  { 0 }

See, we only want to count the number of successful ways that the operations could be applied, we don't need to know how they worked or not.

We'll then say that the total ways to solve [1,2,3] for target 6, with total 0 is the sum of trying all the ways to solve [2,3] for target 6 with total 1, which is solving [3] for target 6 with total 1+2 and for solving [3] for target 6 with total 1*2, which is the same as... and so it goes. At the end, those that end up with 6 return 1, those that don't end up with 0, and we wind all the way back with a total of 2.

Handling recursive bugs

I had a bug in my first implementation, and it took me a while to find it, because recursion makes everything more complex. I had afeeling I knew where it was, but I ended up needing to add this line:

    println!("total({target}, {running_total}, {args:?}, {index})");

into my total function and look at the output in the tests to confirm what it was.

In this case, I've made a simple but basic error with my starting conditions. I've started the entire thing at 0, but with the new code, this creates a very subtle bug. Luckily I caught it with my test, but I couldn't work out why

        // 1+2+3=6, 1+2*3=9, 1*2+3=5, 1*2*3=6
        assert_eq!(2, total(6, &vec![1, 2, 3])); // Correctly says 2 
        assert_eq!(1, total(5, &vec![1, 2, 3])); // Incorrectly says 2
        assert_eq!(1, total(9, &vec![1, 2, 3])); // Doesn't get here

Once I added the printing, I realised that for this example with 3 numbers, I expected a total of 4 combinations, but I actually got 7 out.

The reason is that it was starting the calculations with two options, 0+ and 0*, which meant I was calculating all the combinations twice.

This wouldn't necessarily cause an issue, because 0* anything is 0, so you might expect it to be inert and only count the 0+, but in fact, for this example, 0*1+2+3 is 5, whereas 0+1+2+3 is 6. This creates an extra 5.

The answer here is to handle the first initial case more carefully. But this also gave me an idea to wrap the recursive function in a non-recursive function, which can correctly set the initial number right. I think I can put this inside the total function, so something like

pub fn total(target: u32,  args: &Vec<u32>) -> u32 {
    pub fn total_rec(target: u32, running_total:u32, args: &Vec<u32>, index: usize) -> u32 {
        // recursive function here
    }
    total_rec(target, args[0], args, 1)
}

I'm slightly nervous about whether this makes testing the internal function harder, but I think my current test cases should exercise that effectively.

Part 1 final bit

So, now we know which equations can be solved, the actual question wants us to ignore how many ways it can be solved, but to simply add up the totals if the equation can be solved at least 1 or more ways.

This is fairly simple, if ugly now that we're throwing away the total number of ways this could be solved.

input.iter().map(|equation| {
    if total(equation.total, &equation.args) > 0 { equation.total} else {0}
}).sum::<u32>() as usize

Our input in this case is a vector of Equation objects, each representing one line of input, with a total, and a vector of arguments.

So lets run it...

Oh oh, PosOverflow

Huh, I got an error in my parsing function, a PosOverflow. For the first time I looked at the actual data and saw numbers like 5137095277203. At 513 billion, I think we might be outside of 32 bit numbers. Luckily Rust has natural built in support for bigger numbers, so a quick find/replace of u32 for u64 and everything compiles and I got the right answer.

Part 2 - Adding an extra operator

Ok, this is much easier than I thought it might be. I thought we might have to consider operator precedence which would require a significant rewrite of the recursive function into a more complete stack system. Adding a new operator is simply another branch in our backtracking, so all we need to do is implement the new operator.

Concatonating numbers isn't very easy to do as numbers. We could work out the size of the right hand operator, and then multiply the left operator by 10 raised to teh power the size of the right hand operator.

But actually, this is much easier if the numbers are strings and only turned into numbers when we add or multiply them.

So instead of turning them into numbers at parse time, I'm going to convert to a number in the total function on when needed.

Optimising

Ok, so I hate it, I hate how it looks, and even worse, I now have horrid to_string's all over my test code.

       // 1+2 and 1*2 but not 12
        assert_eq!(1, total(2, &vec!["1".to_string(), "2".to_string()], true));

        // 1+2+3=6, 1+2*3=9, 1*2+3=5, 1*2*3=6, 1||2+3=15, 1||2*3=36, 1||2||3=123, 1+2||3=33, 1*2||3=23
        let args = vec![1.to_string(), 2.to_string(), 3.to_string()];
        assert_eq!(2, total(6, &args, true));
        assert_eq!(1, total(5, &args, true));

But, looking at the to_string on a number made me realise that converting back to a number is trivial and cheap, so why don't I do that instead?

One of the reasons I hate it is that in my previous run, part 1 took 1.5 milliseconds on my laptop. But now I'm using strings everywhere and constnatly reconverting them, it's taking 6 milliseconds. That is 4 times slower.

I think converting once and then only converting back when there's a concat operation should make the whole thing faster.

I'm also unhappy with the duplication in my if else, so I wonder if I can pull that out to a local variable... so from this:

    pub fn total_rec(
        target: u64,
        running_total: u64,
        args: &Vec<u64>,
        index: usize,
        concat: bool,
    ) -> u32 {
        // Our base case, make sure it returns when we run out of numbers
        if index == args.len() {
            return if running_total == target { 1 } else { 0 };
        }
        if concat == true {
            total_rec(
                target,
                (running_total.to_string() + &args[index].to_string())
                    .parse::<u64>()
                    .expect("args must be a number"),
                args,
                index + 1,
                concat,
            ) + total_rec(target, running_total + args[index], args, index + 1, concat)
                + total_rec(target, running_total * args[index], args, index + 1, concat)
        } else {
            total_rec(target, running_total + args[index], args, index + 1, concat)
                + total_rec(target, running_total * args[index], args, index + 1, concat)
        }
    }

to this

    pub fn total_rec(
        target: u64,
        running_total: u64,
        args: &Vec<u64>,
        index: usize,
        concat: bool,
    ) -> u32 {
        // Our base case, make sure it returns when we run out of numbers
        if index == args.len() {
            return if running_total == target { 1 } else { 0 };
        }
        let tot = if concat {
            total_rec(
                target,
                (running_total.to_string() + &args[index].to_string())
                    .parse::<u64>()
                    .expect("args must be a number"),
                args,
                index + 1,
                concat,
            )
        } else {
            0
        };
        tot + total_rec(target, running_total + args[index], args, index + 1, concat)
            + total_rec(target, running_total * args[index], args, index + 1, concat)
    }

Not miles better, but more readable I think.

Interedstingly for those interested, this made part 1 significnatly faster, dropping from 6ms down to just 2ms, but it actually made my part 2 slower, raising from around 500ms to around 750ms. I'm not 100% sure I understand why, but just goes to show that optimising based on gut feel is wrong. At least my tests look better though!