aoc::year2024

Module day07

Source
Expand description

§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.

As 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 concentation (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 concenation 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§

Type Aliases§