Module day07 

Bridge Repair

The equations can be validated using a recursive solution that checks all possible combinations of operators. However, the number of states to check grows exponentially as 2ⁿ in part one and 3ⁿ in part two.

A much faster approach works in reverse from the end of the equation to prune as many states as possible by checking which operations are possible. For example:

Test Value: 123456
Equation: 2 617 56
Addition is possible as 123456 >= 56
Multiplication is not possible as 56 is not a factor of 123456
Concatenation is possible as 1234 || 56 = 123456

Following the concatenation branch and applying an inverse concatenation (the full solution would also follow the addition branch):

Test Value: 1234
Equation: 2 617
Addition is possible as 1234 >= 617
Multiplication is possible as 2 * 617 = 1234
Concatenation is not possible as 1234 does not end in 617

Following the multiplication branch:

Test Value: 2
Equation: 2

The test value is equal to the last term which means that the equation is valid.

Inverse concatenation can be implemented without time-consuming conversion to or from strings by dividing the left term by the next power of ten greater than the right term. For example:

• 7 || 9 => 79 => 79 / 10 => 7
• 12 || 34 => 1234 => 1234 / 100 => 12
• 123 || 789 => 123789 => 123789 / 1000 => 123

Functions

next_power_of_ten 🔒

parse

part1

part2

valid 🔒

Type Aliases

Input 🔒