Module aoc::year2023::day12

source ·
Expand description

§Hot Springs

A dynamic programming approach calculates the possible arrangements for each entry in O(n * w) complexity where:

  • n Number of springs
  • w “Wiggle” is the amount of extra free space the springs can slide around in the pattern.

We build a table for each entry with a row for each spring and a column for every character in the pattern. Adding a trailing . character makes bounds checking easier without changing the number of arrangements. The result will be the bottom right value.

Using the sample ?###???????? 3,2,1:

    n = 3
    w = 13 - (3 + 2 + 1) - 3 + 1 = 5

         ?  #  #  #  ?  ?  ?  ?  ?  ?  ?  ?  .
      ┌----------------------------------------
    3 |  0  0  0 [0  1  1  1  1] 0  0  0  0  0
    2 |  0  0  0  0  0  0 [0  1  2  3  4] 0  0
    1 |  0  0  0  0  0  0  0  0 [0  1  3  6 10]

Each pattern updates the total at the index one after its end, if it can fit at that location For example the first spring can only match at indices [1, 2, 3] so it updates the total at index 4 to 1.

The key insight is that the number of arrangements is then propagated as a prefix sum from left to right for each row as long as the character at the index is not a # or until wiggle characters are reached, whichever comes sooner.

To calculate the next row, each matching pattern adds the value from the row above at the index one before its start. The first row is a special case where this value is always 1.

As a nice side effect this approach always overwrites values so we can re-use the memory buffer for different entries without having to zero out values.

§Alternate approach

Another way to look at the problem is to search to the left from each matching position until a # character is found. The previous pattern can’t leave any trailing # characters otherwise it wouldn’t be the previous pattern.

Using the same example ?###???????? 3,2,1 and adding a trailing .:

  • ### can only match at one location giving:

         . # # # . . . . . . . . .
    [0 0 0 0 1 0 0 0 0 0 0 0 0]

  • The next ## can match at 4 possible locations:

        . # # # . # # . . . . . .
   [0 0 0 0 1 0 0 0 0 0 0 0 0]
            <<
   [0 0 0 0 0 0 0 1 0 0 0 0 0]

  • 2nd location:

        . # # # . . # # . . . . .
   [0 0 0 0 1 0 0 0 0 0 0 0 0]
            <<<<
   [0 0 0 0 0 0 0 1 1 0 0 0 0]

  • 3rd location:

        . # # # . . . # # . . . .
   [0 0 0 0 1 0 0 0 0 0 0 0 0]
            <<<<<<
   [0 0 0 0 0 0 0 1 1 1 0 0 0]

  • 4th location:

        . # # # . . . . # # . . .
   [0 0 0 0 1 0 0 0 0 0 0 0 0]
            <<<<<<<<
   [0 0 0 0 0 0 0 1 1 1 1 0 0]

  • The final # can also match at 4 possible locations (for brevity only showing the 2nd pattern in a single position):

        . # # # . # # . # . . . .
   [0 0 0 0 1 0 0 0 0 0 0 0 0]
   [0 0 0 0 0 0 0 1 1 1 1 0 0]
                  <<
   [0 0 0 0 0 0 0 0 1 0 0 0 0]

  • 2nd location:

        . # # # . # # . . # . . .
   [0 0 0 0 1 0 0 0 0 0 0 0 0]
   [0 0 0 0 0 0 0 1 1 1 1 0 0]
                  <<<<
   [0 0 0 0 0 0 0 0 1 2 0 0 0]

  • 3rd location:

        . # # # . # # . . . # . .
   [0 0 0 0 1 0 0 0 0 0 0 0 0]
   [0 0 0 0 0 0 0 1 1 1 1 0 0]
                  <<<<<<
   [0 0 0 0 0 0 0 0 1 2 3 0 0]

  • 4th location:

        . # # # . # # . . . . # .
   [0 0 0 0 1 0 0 0 0 0 0 0 0]
   [0 0 0 0 0 0 0 1 1 1 1 0 0]
                  <<<<<<<<
   [0 0 0 0 0 0 0 0 1 2 3 4 0]

The final result is then the sum of the bottom row with the nuance that any numbers before the last # don’t count as they represent an invalid pattern.

This is equivalent to the prefix sum approach described above but a little clearer to understand however slower to calculate.

Functions§

Type Aliases§