this post was submitted on 19 Dec 2024
7 points (76.9% liked)

Advent Of Code

981 readers
21 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
[email protected]
[email protected]
[email protected]
7
๐Ÿ‘ป - 2024 DAY 19 SOLUTIONS -๐Ÿ‘ป (programming.dev)
submitted 6 days ago by [email protected] to c/[email protected]
31 comments fedilink hide all child comments
 

Day 19 - Linen Layout

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

you are viewing a single comment's thread
view the rest of the comments
[โ€“] [email protected] 4 points 6 days ago* (last edited 6 days ago)

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")))