Zadanie

Dzisiaj na wejściu otrzymujemy listę stringów które możemy wykorzystać do tworzenia innych większch stringów za pomocą konkatenacji.

Dostajemy też listę długich stringów które będziemy próbować zbudować.

r, wr, b, g, bwu, rb, gb, br

brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb

Naszym zadaniem jest policzyć ile długich ciągów znaków jesteśmy w stanie stworzyć za pomocą fragmentów z pierwszej linijki.

Przykłady:

• brwrr - br + wr + r
• bggr - b + g + g + r
• ubwu - nie da się!

Rozwiązanie

W faktycznym inpucie naszego zadania stringi budulcowe są sporo dłuższe i jest ich więcej, jedną z fajnych struktur do przechowywania takiego typu danych jest trie, pozwala ono bowiem na weryfikowanie w wydajny sposób czy dany prefix występuje w jakim kolwiek ze słow z dużego słownika.

Trie działa w ten sposób że każdy poziom drzewka zawiera odnośniki do kolejnych liter które mogą wystąpić dalej, ewentualnie może też mieć znak specjalny, w moim przypadku znak $, który oznacza koniec słowa.

W funkcji parsującej, dokonałem też tworzenia drzewka trie, jest ono w rzeczywistości po prostu wielopoziomową mapą, w której kluczami są kolejne litery (lub $), a wartościami mapy wyższego poziomu.

def parse(data: str):
    towels, desired = data.split("\n\n")
    towels = towels.split(", ")
    desired = desired.split("\n")

    trie = dict()
    for towel in towels:
        cur = trie
        for c in towel:
            if c not in cur:
                cur[c] = dict()
            cur = cur[c]
        cur[END] = None

    return trie, desired

Funkcja szukająca została zaimplementowana za pomocą rekurencji, żeby zwiększyć nieco przejrzystość kodu:

if __name__ == "__main__":
    trie, tracked, desired = parse(sys.stdin.read().strip())

    def backtracking(cur, string):
        cur = tracked[cur_id]
        if not string:
            if END in cur:
                return True
            return False

        c = string[0]
        res = False

        # jeśli możemy zakończyć słowo, próbujemy znaleźć wzorzec od początku
        if END in cur and c in trie:
            res = backtracking(trie[c], string[1:]) or res

        # ale też jeśli możem próbujemy kontynuować aktualnie zaczęty wzorzec
        if c in cur:
            res = backtracking(cur[c], string[1:]) or res

        return res

    count = 0
    for string in desired:
        res = backtracking(trie, string)
        if res:
            count += 1

    print("Part 1: ", count)

Niestety program freezuje się już na pierwszym stringu, problem jest taki że duplikujemy wielokrotnie naszą pracę, przydałoby się zaimplementować jakąś memoizację poprzednich wyników.

Najprościej byłoby użyć po prostu functools.cache tak samo jak zrobiliśmy to w dniu 11, jednak problem jest taki że ten dekorator umie cachować tylko wartości które są hashowalne, niestety nasze obikty dict, nie są hashowalnie więc musimy zaimplementować własny cache.

Jako funkcję hashującą możemy po prostu użyć id obiektu, ponieważ jest on unikalny, a jako cache możemy użyć zwykłego słownika:

def backtracking(cur, string):
    cache_id = (id(cur), string)
    if cache_id in cache:
        return cache[cache_id]
    ...
    cache[cache_id] = res
    return res

Po tej prostej modyfikacji program działa praktycznie natychmiastowo, a wynik jest poprawny.

Część 2

Żeby zdobyć drugą gwiazdkę nie wystarczy tylko policzyć ile stringów możemy zbudować, ale też na ile różnych sposobów możemy to zrobić. Na szczęście nasz kod jest już dobrze przystosowany do takiego zadania i niewiele trzeba zmienić żeby to osiągnąć.

Jako że obie części zadania są do siebie bardzo podobne, dodaje tutaj kod rozwiązujący je na raz:

import sys

END = "$"


def parse(data: str):
    towels, desired = data.split("\n\n")
    towels = towels.split(", ")
    desired = desired.split("\n")

    trie = dict()
    for towel in towels:
        cur = trie
        for c in towel:
            if c not in cur:
                cur[c] = dict()
            cur = cur[c]
        cur[END] = None

    return trie, desired


if __name__ == "__main__":
    trie, desired = parse(sys.stdin.read().strip())

    cache = dict()

    def backtracking(cur, string):
        cache_id = (id(cur), string)
        if cache_id in cache:
            return cache[cache_id]

        if not string:
            if END in cur:
                return 1
            return 0

        c = string[0]
        res = 0

        if END in cur and c in trie:
            res += backtracking(trie[c], string[1:])

        if c in cur:
            res += backtracking(cur[c], string[1:])

        cache[cache_id] = res
        return res

    part1 = 0
    part2 = 0
    for string in desired:
        res = backtracking(trie, string)
        if res:
            part1 += 1
            part2 += res

    print("Part 1: ", part1)
    print("Part 2: ", part2)

Podsumowanie

Dzisiaj trafiło się kolejne przyjemne zadanie, które było idealnym przykładem na przechowywanie danych w trie, a także na zastosowanie memoizacji. Kod z pierwszego zadania był na tyle dobry że napisanie drugiej części zajeło mi 2 minuty.