Yesterday evening I was talking about Advent of Code with a friend who is solving the puzzles for the first time. We talked about how a big part of having an easier time with these puzzles is pattern recognition. There are many stable puzzle types that repeat over the years – like the path finding puzzles we’ve already had a few this year.
Reading through today’s adventures in the onsen, I realised there are no matches in my brain-abase for this kind of a puzzle. Since I have nothing else today, I’m excited to jump into today’s puzzle.
Read input
Our input today comes in two parts: first a list of available patterns and then all the designs The Official Onsen Branding Expert has created and wants to implement.
r, wr, b, g, bwu, rb, gb, br
brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwbTo read them in, we need two mapper functions:
def map_patterns(section: str) -> List[str]:
return section.split(", ")
def map_designs(section: str) -> List[str]:
return section.split("\n")First one splits the patterns into a list from commas and the second splits the designs by new lines. No further processing required today and since there’s only one piece of data per item, I didn’t feel a benefit from modelling them with namedtuples or classes.
Part 1
In the first part, our job is to figure out if a given design (like bwurrg) can be created by combining the available patterns in any way. We can reuse any patterns as many times as we need.
My initial idea was to check if we can find the longest pattern that starts a design and then see if the rest can be created and if not, come back and try shorter ones. As I was implementing it, I realised I don’t actually have to start from the longest one: as long as I can find a pattern that starts a design and then recursively implement that for the rest of the design, we’ll find out if it works.
As an example, let’s say we have a design like bwurrg. By looking at it as a human, we can see that bwu is one of the patterns. If we split the known pattern and the unknown rest of it (in parenthesis), we can go step by step:
bwu | (rrg)
bwu | r | (rg)
bwu | r | r | (g)
bwu | r | r | g -> is validLet’s see how we would implement that in Python. Since we are running the same check again but with a smaller word, recursion sounds like a solid approach.
Recursion
There are two key things when designing a recursive function:
- We need a base case that finishes the recursion and starts returning values
- We need to always pass arguments in subsequent calls that reduce them towards the base case
In this case, our base case is an empty design: we can implement any empty design by not using any patterns:
def is_valid_design(design: str, patterns: List[str]) -> bool:
if len(design) == 0:
return TrueNext, we want to go through every pattern and see if our design starts with that pattern:
for pattern in patterns:
if design.startswith(pattern):If the design doesn’t start with any of the patterns, it’s quite clear we won’t be able to implement that design.
If there is a pattern that matches, we then take the rest of the design and check for that:
rest = design[len(pattern) :]
if is_valid_design(rest, patterns):
return TrueLet’s take another look at the bwurrg example to see how this algorithm finds the result:
patterns: r, wr, b, g, bwu, rb, gb, br
does bwurrg start with 'r'? no -> next one
does bwurrg start with 'wr'? no -> next one
does bwurrg start with 'b'? yes
-> does wurrg start with 'r'? no -> next one
does wurrg start with 'wr'? no -> next one
does wurrg start with 'b'? no -> next one
does wurrg start with 'g'? no -> next one
does wurrg start with 'bwu'? no -> next one
does wurrg start with 'rb'? no -> next one
does wurrg start with 'gb'? no -> next one
does wurrg start with 'br'? no -> next one
we ran out of patterns, return False
does bwurrg start with 'g'? no -> next one
does bwurrg start with 'bwu'? yes
-> does rrg start with 'r'? yes
-> does rg start with 'r'? yes
-> does g start with 'r'? no -> next one
does g start with 'wr'? no -> next one
does g start with 'b'? no -> next one
does g start with 'g'? yes
-> is '' empty? yes, return TrueEventually, we either find a path that leads to True or we fall through and return False.
The entire function then looks like:
def is_valid_design(design: str, patterns: List[str]) -> bool:
# Empty design is always valid
if len(design) == 0:
return True
for pattern in patterns:
# If a design starts with a pattern, check if the rest
# can be constructed from available pieces
if design.startswith(pattern):
rest = design[len(pattern) :]
if is_valid_design(rest, patterns):
return True
# No matching pattern combination found, cannot be done
return FalseAnd to calculate how many are valid:
def part_1():
patterns, designs = read_multisection_input(19, [map_patterns, map_designs])
valid_designs = 0
for design in designs:
if is_valid_design(design, patterns):
valid_designs += 1
print(f"Part 1: {valid_designs}")
Part 2
In the second part, the staff would like to know all the possible ways we can implement every design and we need to tell them how many there are in total.
Our solutions is very similar to the first part but this time instead of stopping when we find the first combination that works, we keep going and sum up all the valid ones.
def count_valid_designs(design: str, patterns: List[str]) -> int:
if len(design) == 0:
return 1
count = 0
for pattern in patterns:
if design.startswith(pattern):
count += count_valid_designs(design[len(pattern) :], patterns)
return countWe changed the return value of the base case from True to 1 since we’re summing up values anyway. We also added a count variable and instead of returning inside the for loop, we add to the count and finally return the count.
There are so many combinations to check that this function would run for a very very long time. In Day 11 , we had a similar problem where counting all the splitting rocks was too much.
Whenever calculating something over and over again takes a long time, it’s a good idea to look into caching as we did in day 11. My approach is to always first put in a cache and see if it helps. If it does, yay. If it doesn’t, then we look for alternative optimisations.
Python’s standard library has a good option in functools.cache that we can add with two steps:
from functools import cache
@cache
def count_valid_designs(design: str, patterns: List[str]) -> int:
if len(design) == 0:
return 1
count = 0
for pattern in patterns:
if design.startswith(pattern):
count += count_valid_designs(design[len(pattern) :], patterns)
return countWe import the cache from functools and use it as a decorator to the function we want to cache.
If we now try to run this function, we get an error:
TypeError: unhashable type: 'list'It can be a bit cryptic because nowhere in the stack trace nor the error message does it say anything about caching.
The reason this TypeError occurs is because cache cannot work with unhashable types like lists or dicts or sets that can be modified. To solve the issue, we can convert our list of patterns into an immutable tuple of patterns:
def part_2():
patterns, designs = read_multisection_input(19, [map_patterns, map_designs])
patterns = tuple(patterns)
valid_designs = 0
for design in designs:
valid_designs += count_valid_designs(design, patterns)
print(f"Part 2: {valid_designs}")Now, our caching kicks in and we get the result in no time!