Advent of code

◂ 19 décembre 2024 ▸

  Linen Layout : Compter le nombre de façons de découper une chaîne en sous-chaîne autorisées.

gwurrw, guuu, bgguuu, … 

bwwwggur … 

buwwugww … 

wbrbwgub … 

1. code_part1.py
2. code_part2.py
3. code_part2_rapide.py

from functools import cache
from collections import defaultdict

with open("input.txt", 'r', encoding='utf-8') as f:
    lines = [line[:-1] for line in f.readlines()]

patterns = lines[0].split(', ')
lines = lines[2:]

##### Creating a dictionary of patterns to speed up things, like this:
#    Patterns  r, wr, b, g, bwu, rb, gb, br  will create:
#
#    {'exists': True,
#     'subs': {'b': {'exists': True,
#                    'subs': {'r': {'exists': True, 'subs': {}},
#                             'w': {'exists': False,
#                                   'subs': {'u': {'exists': True, 'subs': {}}}}}},
#              'g': {'exists': True, 'subs': {'b': {'exists': True, 'subs': {}}}},
#              'r': {'exists': True, 'subs': {'b': {'exists': True, 'subs': {}}}},
#              'w': {'exists': False, 'subs': {'r': {'exists': True, 'subs': {}}}}}}
#

class Patterns_dict:
    def __init__(self, patterns=None):
        self.exists = False
        self.subs = defaultdict(Patterns_dict)
        if patterns:
            self.add_patterns(patterns)
    
    def add_patterns(self, patterns):
        for pat in patterns:
            self.add_pattern(pat)

    def add_pattern(self, pattern):
        if not pattern:
            self.exists = True
            return
        self.subs[pattern[0]].add_pattern(pattern[1:])

    def find_matches(self, string):
        if len(string) == 0:
            return 1 if self.exists else 0
    
        c = string[0]
        r = 0
        if self.exists:
            r = nb_match(string)
        if pat_d2 := self.subs.get(c, None):
            r += pat_d2.find_matches(string[1:])
        return r

patterns_dict = Patterns_dict(patterns)
    
@cache
def nb_match(line):
    return patterns_dict.find_matches(line)

nb1 = 0
nb2 = 0

for line in lines:
    if n := nb_match(line):
        nb1 += 1
        nb2 += n

print("Réponse partie 1:", nb1)
print("Réponse partie 2:", nb2)