AoC Day 7 has us trying to figure out a slightly new kind of math. Our input is a multiline list. The list starts with a single integer, followed by a colon (“:”), and then multiple comma separated integers. Our goal is to find the number of lines, where it is possible to reach the answer (the first integer) using only addition or multiplication of the various other numbers. For example, if a line was 190: 10 19, we could reach 190 by multiplying 10 and 19.
The directions point out that we don’t follow normal order of precedence here. We solve the problem one step at a time before we move onto the next number and try to add/multiple it.
I’ll admit, I was a bit stumped at first on how to test down the line against each combination of addition/multiplication. I got a hint from one of the people at work who had already completed this, and saw that they were using recursion. I had figured recursion was the answer, but I couldn’t figure out how to feed have it check but operations. He did it by using an OR statement which as soon as I saw it I was like WTF didn’t I think about that.
So my first part runs with this:
def part1(data):
answer = 0
for line in data:
goal = int(line[0])
current_value = int(line[1][0])
remaining_values = line[1][1:]
if ((calculate(current_value, remaining_values, "+", goal)) or
(calculate(current_value, remaining_values, "*", goal))):
print(goal)
answer += goal
def calculate (current_value, remaining_values, oper, goal:
if current_value > goal:
return False
if not remaining_values and current_value == goal:
return True
elif not remaining_values:
return False
else:
if oper == '*':
current_value = current_value * int(remaining_values[0])
elif oper == '+':
current_value = current_value + int(remaining_values[0])
elif oper == "|":
current_value = int(str(current_value) + str(remaining_values[0]))
return ((calculate(current_value, remaining_values[1:], '*', goal) or
calculate(current_value, remaining_values[1:], '+', goal)))
The describe how this works, lines 5 -7 start the process off by setting the goal for that line, and then assigning the first number as the current value and any remaining values as things to process in the next iteration. When we get into the calculate() function we first check to see if the current value we have already figured out is greater than the value we’re looking for. If so, then there’s no point in going further and we bail out immediately. If there are still numbers to look at, then we recurse those numbers into another iteration of the calculated() function. If there’s no numbers left and we still haven’t reached our goal then we return False. If there’s no numbers left, and we reach our goal, we return True.
The thing to remember, is that because of the various branches that each equation can take, there are a fair bit of recursions happening at any point in time.
Part 2
For part 2, we need to add a new operation, the concatenate operation. If our new line was 1910: 19, 10 we would be able to reach that by combining 19 and 10 into a single integer of 1910.
Really to make this change was really simple. I added the operation into my calculate logic as another condition, and then updated the return statements to add the additional option.
elif oper == "|":
current_value = int(str(current_value) + str(remaining_values[0]))
if concatinate:
return (calculate(current_value, remaining_values[1:], '*', goal, True) or
calculate(current_value, remaining_values[1:], '+', goal, True) or
calculate(current_value, remaining_values[1:], '|', goal, True))
You can find my complete code on Github.