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

  • @[email protected]
    2•6 months ago

    Python3

    Solver uses trie just like the other python solve here, I try to not look at solve threads until after it is solved. yet, I somehow got a solve that only takes ~7 ms. previously I would rebuild the trie every time and made it take ~55 ms.

    Code 
    from collections import deque

def profiler(method):
    from time import perf_counter_ns
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret

    return wrapper_method

def build_aho_corasick(towels):
    # Each node: edges dict, failure link, output (which towels end here)
    trie = [{'fail': 0, 'out': []}]
    
    # Build trie of towels
    for index, word in enumerate(towels):
        node = 0
        for char in word:
            if char not in trie[node]:
                trie[node][char] = len(trie)
                trie.append({'fail': 0, 'out': []})
            node = trie[node][char]
        trie[node]['out'].append(len(word))  # store length of matched towel

    # Build fail links (BFS)
    queue = deque()
    # Initialize depth-1 fail links
    for c in trie[0]:
        if c not in ('fail', 'out'):
            nxt = trie[0][c]
            trie[nxt]['fail'] = 0
            queue.append(nxt)

    # BFS build deeper fail links
    while queue:
        r = queue.popleft()
        for c in trie[r]:
            if c in ('fail', 'out'):
                continue
            nxt = trie[r][c]
            queue.append(nxt)
            f = trie[r]['fail']
            while f and c not in trie[f]:
                f = trie[f]['fail']
            trie[nxt]['fail'] = trie[f][c] if c in trie[f] else 0
            trie[nxt]['out'] += trie[trie[nxt]['fail']]['out']
    return trie

def count_possible_designs_aho(trie, design):
    n = len(design)
    dp = [0] * (n + 1)
    dp[0] = 1

    # State in the trie automaton
    state = 0

    for i, char in enumerate(design, 1):
        # Advance in trie
        while state and char not in trie[state]:
            state = trie[state]['fail']
        if char in trie[state]:
            state = trie[state][char]
        else:
            state = 0
        
        # For every towel match that ends here:
        for length_matched in trie[state]['out']:
            dp[i] += dp[i - length_matched]
    
    return dp[n]

@profiler
def main(input_data):
    towels,desired_patterns = ( sorted(x.split(), key=len, reverse=True) for x in input_data.replace(',', ' ').split('\n\n') )
    part1 = 0
    part2 = 0
    
    # Build Aho-Corasick structure
    trie = build_aho_corasick(towels)
    
    for pattern in desired_patterns:
        count = count_possible_designs_aho(trie, pattern)
        if count:
            part1 += 1
            part2 += count
    
    return part1,part2

if __name__ == "__main__":
    with open('input', 'r') as f:
        input_data = f.read().replace('\r', '').strip()
    result = main(input_data)
    print("Part 1:", result[0], "\nPart 2:", result[1])