Advent of Code 2023 Day 12

The catch-up grinds on. Every year there’s one moderately hard puzzle I just don’t get, and this year’s was day 12. The puzzle involves validating sequences of characters. Consider this line:

???.### 1,1,3

The numbers on the right mean there must be groups of 1, 1, and 3 # characters, separated by one or more .. Each ? can stand for either a . or a #. The challenge is to count how many arrangements in each line match the group lengths.

I decided to try each possible permutation and validate it with a regex. None of the input lines were much longer than 15 characters, so an O(2^n) solution would be fine. Sure enough, it was.

Part 2 revealed I had swallowed the bait. It asked the same counting question, but quintupled the length of each line.

As ever in Advent of Code, you shouldn’t count each distinct instance of something when you can group similar ones together. I wrote a function to use BFS to explore valid sequences, storing each as just the index and size of the current group being traversed.

```{python}
# .
@cache
def decide_dot(group_index, group_size, n_groups, target_length):
    # Not in group
    if group_size == 0:
        return (group_index, group_size)
    # Exiting group
    elif group_size == target_length:
        return (group_index + 1, 0)


# #
@cache
def decide_hash(group_index, group_size, n_groups, target_length):
    # Starting group
    if group_size == 0 and group_index < n_groups:
        return (group_index, 1)
    # Advance current group
    elif group_size < target_length:
        return (group_index, group_size + 1)


def parse(line):
    parts = line.split(" ")
    parts[1] = list_map(parts[1].split(","), int)
    return parts


def bfs(string, groups):
    # group_index, group_size
    start = (
        0,
        0,
    )
    n_groups = len(groups)
    reference = groups + [0]
    last = {start: 1}
    choices = {".": (decide_dot,), "#": (decide_hash,), "?": (decide_dot, decide_hash)}

    # Dict of states to add to count?
    for char in string:
        next = defaultdict(lambda: 0)
        choosers = choices[char]

        for state in list(last.keys()):
            count = last.pop(state)
            group_index, group_size = state
            target_length = reference[group_index]

            for chooser in choosers:
                result = chooser(group_index, group_size, n_groups, target_length)
                if result is not None:
                    next[result] += count
        last = next
    correct = {(n_groups, 0), (n_groups - 1, reference[-2])}
    return sum(v for k, v in last.items() if k in correct)


# Multiply by recursive call to remaining string
def reparse(data, n=5):
    return [["?".join([l[0]] * n), l[1] * n] for l in data]


raw = split_lines("inputs/day12.txt")
parsed = list_map(raw, parse)
part1 = sum(bfs(line, nums) for line, nums in parsed)
print(part1)

new_parsed = reparse(parsed)
part2 = sum(bfs(line, nums) for line, nums in new_parsed)
print(part2)
```