Pyro
It's so disappointing. India has a massive tech service industry and could've been a force for good, but the government loves their censorship and authoritarianism too much.
Dude, you forgot the /s
If someone doesn't know, they can check out the EPIC Saga!
Yay, I made it in the screenshot! Thanks everyone, this was my first year and it was a lot of fun!
Python
Approach: Recursive memoized backtracking with a Trie
I get to use one of my favorite data structures here, a Trie! It helps us figure out whether a prefix of the design is a valid pattern in linear time.
I use backtracking to choose potential component patterns (using the Trie), kicking off matching the rest of the design down the stack. We can continue matching longer patterns immediately after the recursion stack unwinds.
In addition, I use global memoization to keep track of the feasibility (part 1) or the number of combinations (part 2) for designs and sub-designs. This way, work done for earlier designs can help speed up later ones too.
I ended up combining part 1 and 2 solutions into a single function because part 1 is a simpler variant of part 2 where we count all designs with the number of possible pattern combinations > 0.
Reading Input
import os
here = os.path.dirname(os.path.abspath(__file__))
# read input
def read_data(filename: str):
global here
filepath = os.path.join(here, filename)
with open(filepath, mode="r", encoding="utf8") as f:
return f.read()
Trie Implementation
class Trie:
class TrieNode:
def __init__(self) -> None:
self.children = {} # connections to other TrieNode
self.end = False # whether this node indicates an end of a pattern
def __init__(self) -> None:
self.root = Trie.TrieNode()
def add(self, pattern: str):
node = self.root
# add the pattern to the trie, one character at a time
for color in pattern:
if color not in node.children:
node.children[color] = Trie.TrieNode()
node = node.children[color]
# mark the node as the end of a pattern
node.end = True
Solution
def soln(filename: str):
data = read_data(filename)
patterns, design_data = data.split("\n\n")
# build the Trie
trie = Trie()
for pattern in patterns.split(", "):
trie.add(pattern)
designs = design_data.splitlines()
# saves the design / sub-design -> number of component pattern combinations
memo = {}
def backtrack(design: str):
nonlocal trie
# if design is empty, we have successfully
# matched the caller design / sub-design
if design == "":
return 1
# use memo if available
if design in memo:
return memo[design]
# start matching a new pattern from here
node = trie.root
# number of pattern combinations for this design
pattern_comb_count = 0
for i in range(len(design)):
# if design[0 : i+1] is not a valid pattern,
# we are done matching characters
if design[i] not in node.children:
break
# move along the pattern
node = node.children[design[i]]
# we reached the end of a pattern
if node.end:
# get the pattern combinations count for the rest of the design / sub-design
# all of them count for this design / sub-design
pattern_comb_count += backtrack(design[i + 1 :])
# save the pattern combinations count for this design / sub-design
memo[design] = pattern_comb_count
return pattern_comb_count
pattern_comb_counts = []
for design in designs:
pattern_comb_counts.append(backtrack(design))
return pattern_comb_counts
assert sum(1 for dc in soln("sample.txt") if dc > 0) == 6
print("Part 1:", sum(1 for dc in soln("input.txt") if dc > 0))
assert sum(soln("sample.txt")) == 16
print("Part 2:", sum(soln("input.txt")))
Those are some really great optimizations, thank you! I understand what you're doing generally, but I'll have to step through the code myself to get completely familiar with it.
It's interesting that string operations win out here over graph algorithms even though this is technically a graph problem. Honestly your write-up and optimizations deserve its own post.
Even though I have the Up button set to Show Parent in settings, it's not showing up for comments.
That's really stretching it. So you can't show a plane heading in the vague direction of a tall structure?