A personal blast from the past¶

https://adventofcode.com/2023/day/12

Today's puzzle is clearly inspired by Nonograms, and this brought back a lot of memories for me!

A long, long time ago I participated in a popular online programming challenge called The Python Challenge, which, to my surprise still exists and appears to be operational today! I loved it, even though many of the challenges didn't really involve much Python coding. I helped moderate the forums for a while, and I created a new challenge for the site that required you to... solve a nonogram, programatically! I have no idea if that challenge still works; the forums are long gone now so I can't easily check without solving all the intervening challenges again. I included a javascript version of the solver to show that even your browser could solve such puzzles.

This was almost 20 years ago now, I no longer have the original code I wrote. I don't think it'll be useful for this challenge anyway, because today's puzzle requirements are slightly different. Most of all, I was still rather green around the software engineering ears back then, and I'm sure I'd cringe if I saw the code today. However, I do still love solving Nonograms to this day, solving them the traditional way, by myself rather than with code. Either on paper, or more typically, via the very excellently coded Conceptis Puzzles Pic-a-Pix mobile app. They publish a set of Christmas Holiday puzzles as a PDF, to print out, every year, try your hand at the 2023 edition, if you have a few Christmas Holiday hours to kill. :)

So, what do we need to do? We need to find the number of ways to fit groups of consecutive 'broken springs' (marked with #) and 'operational springs' (. characters) onto a line, with a number of ? unknown spots. We also are given the consecutive lengths of the # broken springs. The . and # characters are exactly like the white and black squares in a nonogram here, and the ? are just like the unknown squares in a nonogram. The consecutive spring group lengths make the picture complete, that's the very basis of a nonogram. I'm therefor referring to the broken springs as 'filled' cells, the operation springs are 'blank' cells, and the unknown spots can stay 'unknown'.

If there were no given blank and filled cells in the input row (just ? unknown cells), the number of possible placings is really easy to calculate. There will always be a blank cell between two groups of filled cells, so in addition to the total of filled cells (the sum of the group counts, $t$) for the $n$ groups, you will have $n - 1$ fixed blank cells. Given a total line length $l$, that leaves $r = l - t - (n - 1)$ remaining unknown cells to distribute between and around those groups. Essentially, this means there are $n + r$ possible positions to place the $n$ groups, which is a straightforward combinations calculation: the number of ways to pick $n$ out of $n + r$ options, or ${n+r \choose n}$.

With the constraints, there are fewer possibilities. The easiest and most efficient way to calculate the number of options is to apply dynamic programming, breaking down the problem into smaller subproblems. Here, we can look at how many ways can you place any one of the groups, and for each group you have solved carry the count forward to the next. This naturally translates to a table with columns per line cell, and rows per group.

In the table cells, you store a cumulative count for that group, going along the cells and incrementing the count for each position in the line that the group could fit. Per group we only need to search for up to $r + 1$ positions, starting at the earliest position where the previous group could fit plus the blank cell that must separate them, and there are $r$ extra positions you could shift the group to. Store those counts in the space for the required blank cell, so right after the length of the group being fit. To make this easier, always add an extra dummy cell at the end of your table that is set to ., a blank. This makes the table $l + 1$ cells long; the extra blank doesn't change the outcome but makes it easier to retrieve the final total count.

Example time¶

For example, given a single group of length 3, giving us $n = 1, t = 3$. We want to position this on a line with $l = 5$, with all the cells as ? unknowns, giving us $r = 5 - 3 - (1 - 1) = 2$. We can expect there to be ${n+r \choose n} = {3 \choose 1} = 3$ combinations for this problem. We can see that if we use a table with $l + 1 = 6$ columns and a single row, starting out with zeros. I've added an extra row with cell indices plus a row for the solution being tested so far. Cells that haven't been filled with a count are blank, their value doesn't matter as they are not consulted unless a previous step has provided a concrete count:

Starting table

	`?`	`?`	`?`	`?`	`?`	`.`
3
index	$0$	$1$	$2$	$3$	$4$	$5$
solution

We only need to visit $r + 1 = 3$ positions in this table. This being the first group, the group would fit at position $p = 0$, giving us 1 possiblity to fill the row. Store this count after the group length, so at $p + 3 = 3$:

p = 0

	`?`	`?`	`?`	`?`	`?`	`.`
3				[1]
index	$0$	$1$	$2$	$3$	$4$	$5$
solution	`#`	`#`	`#`	`.`

I've marked the new cell value with [...] brackets to make this clearer.

Go to the next position; the group would still fit because it's all ? unknowns, and add 1 to the previous count, again at $p + 3 = 4:

p = 1

	`?`	`?`	`?`	`?`	`?`	`.`
3				1	[2]
index	$0$	$1$	$2$	$3$	$4$	$5$
solution	`.`	`#`	`#`	`#`	`.`

Go to the third position, $p = 2$ and do the same thing again:

p = 2

	`?`	`?`	`?`	`?`	`?`	`.`
3				1	2	[3]
index	$0$	$1$	$2$	$3$	$4$	$5$
solution	`.`	`.`	`#`	`#`	`#`	`.`

The answer to the question how many ways can you fit the groups on the line is stored in the last cell of the table, here that's 3.

Add constraints¶

So how does this change when there are not just unknowns? What if the line has 2 filled cells, like ??#?.. Lets go through the steps.

Starting with the same setup as before but with the line updated:

Starting table

	`?`	`?`	`#`	`?`	`.`	`.`
3
index	$0$	$1$	$2$	$3$	$4$	$5$
solution

The group still fits at positions $p = 0$ and $p = 1$:

p = 0

	`?`	`?`	`#`	`?`	`.`	`.`
3				[1]
index	$0$	$1$	$2$	$3$	$4$	$5$
solution	`#`	`#`	`#`	`.`

p = 1

	`?`	`?`	`#`	`?`	`.`	`.`
3				1	[2]
index	$0$	$1$	$2$	$3$	$4$	$5$
solution	`.`	`#`	`#`	`#`	`.`

We can't create a solution at $p / 2$ however:

p = 2

	`?`	`?`	`#`	`?`	`.`	`.`
3				1	2	[2]
index	$0$	$1$	$2$	$3$	$4$	$5$
solution	`.`	`.`	`#`	`#`	`X`

I've marked the spot where you can't place a filled cell wiwh X. Because the group doesn't fit there, we carry forward the 2 from the previous position. The final count is 2 possible solutions.

Adding another group¶

So how does this then work with more than one group? From row 2 onwards, you can start fitting the corresponding group the cumulative group size plus the current group index, because that's the left-most location where the previous group could have be fitted (in an all-unknowns scenario) and there is still the required blank cell in between the groups. To track the number of possible solutions, for patterns that are valid, you add the number of possible solutions for the groups preceding, plus the number of options for this group at the previous position. Before we incremented by just 1 each time, but that's because is exactly 1 way to fit size 0 group to a size 0 pattern. When the pattern doesn't fit, just continue to carry forward the count accumulated for the current group so far. This will all become clearer below.

I'm using the final pattern from the example here, with the line ?###???????? and 3 groups sized 3, 2 and 1. This gives $l = 12, n = 3, t = 3 + 2 + 1 = 6$ and $r = 12 - 6 - (3 - 1) = 4$. The table will be $l + 1 = 13$ cells wide, and $n = 3$ rows high, and for each group we need to look at $r + 1 = 5$ possible positions.

The starting table can be visualised like this:

Starting table

	`?`	`#`	`#`	`#`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`.`
3
2
1
index	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
solution

Since the three groups have distinct sizes, I'll label them as g3, g2 and g1 in the examples below, and bold their count label in the table display.

The first group, g3, can only fit at $p = 1$, so we can fill out the first row with 1's for the cells at $p = 4, 5$, so after the first round of 5 steps examining the first group, we have:

g3, p = 4

	`?`	`#`	`#`	`#`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`.`
3				0	1	1	1	[1]
2
1
index	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
solution	`.`	`#`	`#`	`#`	`.`

So far, so straightforward. So what happens for the second group? Since there is just one way for g3 to fit the pattern, the second group counts look exactly the same as if this was a first group on a shorter line; the counts start at 1 and increment for every additional position that would fit.

We start at $p = 4$; to correspond to the cumulative size of the groups and required blanks processed so far (the first group comprises 3 filled cells + 1 blank cell to separate the groups):

g2, p = 4

	`?`	`#`	`#`	`#`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`.`
3				(0)	1	1	1	1
2							[0]
1
index	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
solution				`X`	`#`	`#`	`.`

There is no solution at this position because we can't store a required . blank at $p = 3$ to separate g3 from g2. It doesn't matter at this point that there is a 0 in the corresponding $g3, p = 3$ table cell here (marked with (...) for visual reference), the pattern doesn't fit and so we can only carry forward our current accumulated count, which is 0, to be filled into the cell at $g2, p = 6$.

The next 4 positions we try all fit, so we can add the corresponding 1 count from the preceding row to our accumulated sum and so after the remaining steps the table becomes:

g2, p = 8

	`?`	`#`	`#`	`#`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`.`
3				0	1	1	1	(1)
2							0	1	2	3	[4]
1
index	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
solution								`.`	`#`	`#`	`.`

For each step, we can see from the corresponding 'preceding' cell in the row above there is exactly one solution for the pattern up to that point, and so the counts still increment by just 1 here.

Lets carry this forward now to the 3rd and final group, g1. We've processed 3 + 2 + 2 blank cells so far, so we start at $p = 7$ to fit our group at it's 5 possible positions. Here is the first step result:

g1, p = 7

	`?`	`#`	`#`	`#`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`.`
3				0	1	1	1	1
2							(0)	1	2	3	4
1									[0]
index	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
solution							`.`	`#`	`.`

The pattern would allow us to fit the single filled cell at this position, but the count carried over from the $g2, p = 6$ cell in the table is 0. There are no solutions possible at this position because we can't fit both g3 and g2 before this point.

The next step is also a valid solution for just this group, in isolation, but this time there is a count for the preceding groups too:

g1, p = 8

	`?`	`#`	`#`	`#`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`.`
3				0	1	1	1	1
2							0	(1)	2	3	4
1									0	[1]
index	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
solution								`.`	`#`	`.`

Given the groups placed up to this point, according to the table, there is just one possible solution that would allow the final, single filled cell to be placed at $p = 8$, so can add the 1 from $g2, p = 7$ to our 0 count and fill in 1 at $g1, p = 9$.

Now it gets interesting. There are 2 different ways to produce patterns preceding position $p = 9$, according to the table cell at $g2, p = 8$, and so fitting our g1 group at $p = 9$ would result in 3 different possible solutions (2 for the preceding groups, plus one extra variant for this group):

g1, p = 9

	`?`	`#`	`#`	`#`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`.`
3				0	1	1	1	1
2							0	1	(2)	3	4
1									0	1	[3]
index	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
solution									`.`	`#`	`.`

Lets do this again, moving on to the next step:

g1, p = 10

	`?`	`#`	`#`	`#`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`.`
3				0	1	1	1	1
2							0	1	2	(3)	4
1									0	1	3	[6]
index	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
solution										`.`	`#`	`.`

We now have 6 possible solutions to get us to this point! There are 3 different ways to fit the pattern up and including position $p = 9$ with the preceding groups and blanks, and 3 more ways to position the final single group cell in the line up to $p = 11$.

There is just one more step to go for this pattern:

g1, p = 11

	`?`	`#`	`#`	`#`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`?`	`.`
3				0	1	1	1	1
2							0	1	2	3	(4)
1									0	1	3	6	[10]
index	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
solution											`.`	`#`	`.`

The final count is 4 + 6 = 10 possible solutions for the three groups to fit this pattern.

Edge case not in the examples¶

There is actually two edge cases that aren't covered by the examples, but one that will probably bite you in the actual puzzle inputs.

First, a pattern that uses a small number of # characters in the first $r + 1$ section with enough room past these for the first group to fit in more locations. E.g, this simple example is only valid with the first group placed at position 1:

?#???## 1,2

You need to account for this when checking this first group; .#...## is a valid solution, but ...#.## is not, but the above table approach would still count 2 possibilities! The trick is to not actually start with all 1 values as a preceding counts row for the first group, only with 1s as long as there is no # filled cell up to that point, and 0 for the remainder.

Secondly, the sum for the current group needs to be reset whenever you encounter a # filled cell to the immediate right of the current group, because you can't match a single group to two separate sections of filled cells.

Performance and further implementation tricks¶

This algorithm is really efficient; we only have to look at $r + 1$ positions for each of $n$ groups. $r + 1$ depends on the length of the pattern $l$ and the total sum $t$ of the groups, but is considerably lower than $l$, always.

In my implementation, I not only add a blank . to the end of the pattern, but also one to the start, again to avoid having to make boundary checks. I also add a first row to the table with the primed 1s and 0s for the first group.

In [1]:

import typing as t
from dataclasses import dataclass


@dataclass
class SpringsPattern:
    patt: str
    groups: tuple[int, ...]

    @classmethod
    def from_line(cls, line: str) -> t.Self:
        patt, _, rem = line.partition(" ")
        return cls(patt, tuple(map(int, rem.split(","))))

    @property
    def arrangement_count(self) -> int:
        n, plen, tot = len(self.groups), len(self.patt), sum(self.groups)
        r = plen - tot - (n - 1)
        # add a blank cell to the start and end of the pattern for easier checks
        patt = f".{self.patt}."
        # the DP table tracking number of possible arrangements for each group
        table: list[list[int]] = [[0] * (plen + 2) for _ in range(n + 1)]
        # where to start for each group; incremented with group size + 1 after each group
        offset = 1
        # prime the counts for the first group with 1s and 0s, based on the
        # first filled cell position.
        for i in range(patt.index("#") if "#" in patt else plen + 2):
            table[0][i] = 1
        for g, gsize in enumerate(self.groups, 1):
            # total number of possible solutions for this group
            total = 0
            for p in range(offset, offset + r + 1):
                # Check the pattern; the group must not have a filled cell before and
                # after, and not have blanks for the cells of the group itself.
                if patt[p + gsize] == "#":
                    total = 0
                elif patt[p - 1] != "#" and all(c != "." for c in patt[p : p + gsize]):
                    total += table[g - 1][p - 1]
                table[g][p + gsize] = total
            offset += gsize + 1
        return table[-1][-1]


test_patterns = {
    "???.### 1,1,3": 1,
    ".??..??...?##. 1,1,3": 4,
    "?#?#?#?#?#?#?#? 1,3,1,6": 1,
    "????.#...#... 4,1,1": 1,
    "????.######..#####. 1,6,5": 4,
    "?###???????? 3,2,1": 10,
    "?#???## 1,2": 1,
}

for line, expected in test_patterns.items():
    assert SpringsPattern.from_line(line).arrangement_count == expected

In [2]:

import aocd

lines = aocd.get_data(day=12, year=2023).splitlines()
patterns = [SpringsPattern.from_line(line) for line in lines]
print("Part 1:", sum(p.arrangement_count for p in patterns))

Part 1: 7169

Pattern explosion¶

Part 2 is a walk in the park with the DP solution above! The patterns may be 5 times the size, the algorithm has no trouble processing these in a short amount of time anyway. :D

In [3]:

@dataclass
class UnfoldedSpringsPattern(SpringsPattern):
    def __post_init__(self):
        self.patt = "?".join([self.patt] * 5)
        self.groups = self.groups * 5


test_patterns = {
    "???.### 1,1,3": 1,
    ".??..??...?##. 1,1,3": 16384,
    "?#?#?#?#?#?#?#? 1,3,1,6": 1,
    "????.#...#... 4,1,1": 16,
    "????.######..#####. 1,6,5": 2500,
    "?###???????? 3,2,1": 506250,
}

for line, expected in test_patterns.items():
    assert UnfoldedSpringsPattern.from_line(line).arrangement_count == expected

In [4]:

patterns = [UnfoldedSpringsPattern.from_line(line) for line in lines]
print("Part 2:", sum(p.arrangement_count for p in patterns))

Part 2: 1738259948652