Advent of Code Day 7 was a classic recursion problem, lets figure it out!

---

The below is a guest post by the amazing Shraddha Agrawal.

---

Part 1

We’re given a list of numbers, where each row is of the format A: B C ... where A, B, C and so on are numbers. We need to figure out if the numbers following the colon (ie, B , C and so on) can be combined with mathematical operators to get the first value in the row (ie A). The following rules are defined for the same:

1. Operators that are allowed: addition and multiplication.
2. Operators are always evaluated left to right, ie, we should not follow the operator precedence rules.

Once we figure out the rows for which the above is valid, the final answer should be the sum of the first number for all those rows.

Solution

Instantly after reading the problem, I knew this was the day to break out recursion. Here, it makes sense because we have variable count of numbers in each row and starting with the first number, calculation with the next number could be any of the allowed operators, ie we will have branching at every new number we encounter.

Before we write the recursive solution for this, lets first write a function to do the calculation between two numbers depending on the supplied operator.

func calculate(a, b int, operation byte) int {
	calculation := 0
	switch operation {
	case '+':
		calculation = a + b
	case '*':
		calculation = a * b
	}
	return calculation
}

We can write our recursive solution now. The recursive function would receive the calculation so far, the target number and a slice of numbers remaining to be evaluated. The idea is that with each call to the recursive function we would apply one of the possible operators to combine the calculated value so far with the next number in the row. The base case would be if all numbers are handled, we have a success if the current calculation is equal to target otherwise a failure. If the current calculation is greater than target value, again, this is a failure case.

Putting it together, we have this nice elegant solution:

func isCalculationAMatch(expectedSum, sum int, input []int) bool {
	if len(input) == 0 {
		return sum == expectedSum
	}

	if sum > expectedSum {
		return false
	}

	if isCalculationAMatch(expectedSum, calculate(sum, input[0], '+'), input[1:]) {
		return true
	}

	return isCalculationAMatch(expectedSum, calculate(sum, input[0], '*'), input[1:])
}

We can iterate over all the rows in the input and use the above function to figure out if the row is valid. If yes, we can add its target value to the final sum, which is the answer for part 1.

Part 2

This time part two was pretty straight forward. The only thing that was added is we now have one more operator, the concatenation operator ||, which combines the digits from its left and right inputs into a single number. eg - 12 || 3 would result in 123. Now we need to evaluate input rows with three operators and find the sum of target value of all valid rows.

In the above example, three more rows become valid with the new operator.

Solution

We need to simply add a couple of lines in each of the function above to solve part 2! First, lets modify the calculation function to handle the new operator.

We need to be careful while concatenating the two numbers is that the second number can be greater than a single digit so we would first need to figure out the power of 10 we need to multiple the first number with before adding the second one to it.

The new version of calculate looks like this:

func calculate(a, b int, operation byte) int {
	calculation := 0
	switch operation {
	case '+':
		calculation = a + b
	case '*':
		calculation = a * b
	case '|':
		mul, q := 10, 10
		for q != 0 {
			q = b / mul
			if q > 0 {
				mul *= 10
			}
		}
		calculation = (a * mul) + b
	}
	return calculation
}

For updating the recursion, we simply need to add one more branch! I added a boolean so we can reuse the same function for both part one and part two.

func isCalculationAMatch(expectedSum, sum int, input []int, isPart2 bool) bool {
	if len(input) == 0 {
		return sum == expectedSum
	}

	if sum > expectedSum {
		return false
	}

	if isCalculationAMatch(expectedSum, calculate(sum, input[0], '+'), input[1:], isPart2) {
		return true
	}

	if isPart2 && isCalculationAMatch(expectedSum, calculate(sum, input[0], '|'), input[1:], isPart2) {
		return true
	}
	return isCalculationAMatch(expectedSum, calculate(sum, input[0], '*'), input[1:], isPart2)
}

And that’s it! The sum this time would give the answer to part two. Final code can be found here.

How was solving day 7 for you? I would love to compare notes and checkout your solution. Reach out to me on Twitter, Bluesky or on e-mail at contact[at]shraddhaag[dot]dev.