nice job! now do it without recursion. something I always attempt to shy away from as I think it is dirty to do, makes me feel like it is the “lazy man’s” loop.

Aho-Corasick is definitely meant for this kind of challenge that requires finding all occurrences of multiple patterns, something worth reading up on! If you are someone who builds up a util library for future AoC or other projects then that would likely come in to use sometimes.

Another algorithm that is specific to finding one pattern is the Boyer-Moore algorithm. something to mull over: https://softwareengineering.stackexchange.com/a/183757

have to remember we are all discovering new interesting ways to solve similar or same challenges. I am still learning lots, hope to see you around here and next year!

haha, there are way too many days where I end up with code that works with the sample but fails the real input. its just not really possible to expect the sample and description to properly prepare you. oh well, it is what it is.

Nice, don’t be shy to revisit these later on, I am definitely doing the same for older AoC years. I am happy you got it down that low. With python, I am really trying my best to make sure I can figure out a way to keep my solve times lower. Gives me challenge to fight a slow language faults with optimized logic haha

I will eventually get down with using python and be moving over to Rust. I will eventually be happy to move to an old functional language like Haskell. I don’t think I will learn those specialized languages like uiua, I don’t think I can get over the magic like symbols lol

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.

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

I liked all of the Maze solving puzzles. this was a good year for the best maze solving skills to be put to the test. at the end, I disliked 14, 15, and 17 for the simple fact that I am not well versed in solving those types of challenges and it is hard to visualize in my head properly. Did they push me? yes, but enjoyment was less than I had with the other puzzles.

I also enjoyed some of the corrupted memory solving puzzles like day 3 because I got to optimize with either .index( ) or straight regex. I really enjoyed it. however, that pales to the pattern recognition puzzle that day 19 had. Day 19 was extremely fun. many people had to hand roll some kind of pattern solver. I eventually found a solution using Aho-Corasick Algorithm which brought my solution for part 1 and 2 to just about ~55 ms. it was extremely fast as I already had a solver that only took ~120 ms. (in python3) however, now that I looked in the solutions thread, it seems I was not the only one to think of trie and my solution was still slower than their solution, sad me. lol nvm I found I was rebuilding the trie everytime, only need to build it once, dropped to solve ot ~7 ms

I am still solving some of the later puzzles due to holidays but I had fun so far, even though some days I was not well equipped to solve efficiently or at all.

So true, I like tech stuff and even on Lemmy where people are more tech literate, there is mostly just porn politics and memes. I do still like putting in some high quality comments. Allows me to forget about the current state of things.

Top is proprietary llms vs bottom self hosted llms. Bothe end with you getting smacked in the face but one looks far cooler or smarter to do, while the other one is streamlined web app that gets you there in one step.

Morning wood?

It’s loss btw

IDK about you but the company I work for can’t live without npm packages doing almost everything. For example: the is-even package.

To give the most simple and likely reason is just so that there are a restricted set of levels. Adding a “freeplay” mode that can generate random maps is not part of the plan because that would make the regular levels look less desirable. There is also many odd quirks available with special rules. It’s not just because they did not think about generating random maps for those who finished the game. It is so that they can keep control over the game in a way that players are kept playing longer without risking burnout. They don’t want to make the game become a chore but rather a daily task/quest. Spending money to read the last level faster by getting more energy and whatnot is just a plus for them. They know that sunk cost feeling will keep those kinds of players coming back. If not, then it was unlikely the infinite freeplay would.

Off topic: Would a hobby be considered an addiction, too? How about other things we do on a daily basis? Do we draw lines? If so, where?

I’m glad we both came to an agreement 🤝

I didn’t say there are no repercussions. I said it is a safe bet on a risk that many individuals are willing to make.

Breaking the agreement does not always mean you will get in trouble for it. This is the one rule that can be risked breaking without facing repercussions.

Likely prohibitively expensive, will take a long af time to reach wider markets and most likely never pass trials

All my predictions

I’ll be very interested to hear more, do you have a blog?

If the highway increases in size, then more off ramps or more lanes in the off ramps are needed, which in turn need more lanes on the main street that connect to the off ramps. It’s basic filtration system dynamics.

Yes but I imagine this mammoth of a TV survived to the 80s for this specific person to make the generalized statement of it being a developed fear in the 80s.

I didn’t have to work on it for just to not click through ui menus, I just had my autoclicker enabled from some reason(likely game) and just randomly thought, “I’ll use the autoclick, lol” and had some interesting stuff happen. It was entertaining and nothing about being practical.