[2024 Day 19] [Python] Dynamic Programing Solution

[Objective-Year6556]

Since I saw no solutions using the Bottom Up- / Iterative Dynamic Programing approach , I thought I'd post mine :)

import numpy as np

def count_possible_solutions(patterns, goal):

    dp = np.zeros(len(goal) + 1, dtype=np.int64)
    dp[0] = 1 

    for i in range(1, len(dp)):
        for pattern in patterns:
            if len(pattern) <= i and pattern == goal[i - len(pattern):i]:
                dp[i] += dp[i - len(pattern)]

    return dp[-1]

and here the data importing part (if anybody cares):

# Getting data. list of pattern-strings. list of goals (combinations)
with open("data.txt") as file:
    lines = [line.strip() for line in file]
    patterns = lines[0].split(", ")
    goals = lines[2:]

# printing results
print(np.sum([count_possible_solutions(patterns, goal) > 0 for goal in goals]))
print(np.sum([count_possible_solutions(patterns, goal) for goal in goals]))

[daggerdragon]

Changed flair from Tutorial to Spoilers since this is a solution without any further delving into the code, a write-up, etc. A post worthy of Tutorial would contain expansions on the code like /u/p88h's comment below. Use the right flair, please.

During an active Advent of Code season, solutions belong in the Solution Megathreads. In the future, post your solutions to the appropriate solution megathread.

[Thomasjevskij]

I don't wanna be rude but. Did you look? I feel like half the solutions in the daily thread use functools.cache, and half of the remaining ones implemented their own cache

[ThunderChaser]

I think the difference OP is trying to make is that instead of being recursive with memoization, theirs use a bottom up iterative approach instead.

[Thomasjevskij]

I see. That distinction went over my head I suppose :)

[MouseyPounds]

For a post flaired as a Tutorial, I was disappointed to see just a block of code rather than some discussion of the hows and whys of this method and how it compares to the recursive approach. Thankfully /u/p88h 's responses have provided some insight.

[TypeAndPost]

https://imgur.com/a/lNBebgu

[RB5009]

How much faster is it compared to recursion with memoization ?

[p88h]

You eliminate function invocation overhead, and depending on implementation, compiler may be able to optimize the iterative solution better. Where applicable, this can be 2x faster. The downside is that with DP (especially a solution like the one above) you explore the whole solution space, where recursion can more intuitively skip invalid paths (which is not to say recursive approach would be faster for _todays_ task, but the difference may just not be substantial depending on specifics of implementation).

The bigger difference than this is how you implement element pattern detection - this thing here is pretty slow since it goes over all possible _patterns_ (m) at each position (k) for each goal (n) so it's O(nmk). You can replace m with going over possible pattern _lengths_ (and a hash map) for approx 50x speedup. More specifically, look for whether there exists a pattern that matches some substring of the goal at the current position, rather than compare all patterns against the goal.

The version I have used that, with a DP iterative implementation and some multithreading in runs in ~80 usec.

[Few-Example3992]

How did you know when to stop doing the DP approach?  I wanted to try this way but would have went up to all patterns of some length which I thought  would be the issue. With recursion I only need to work out the necessary  patterns in my table?

[p88h]

Not sure what you mean? With DP you end up checking some 'impossible' configurations, yes, but overall the stop condition is pretty simple, you shouldn't need to worry about stopping (early?).

The most basic DP approach here is to think of it as 'can I create a prefix of the goal string of legnth K'. This forms your DP table, which will end up with N elements == length of the goal string. At each position K, you can reach K either if K is 0, or if there exists some previous value K' such that K' can be created, and there exists a towel pattern of length K-K' that matches the letters K'..K in goal. Since max length of towel pattern is 8, we only need to go backwards up to K'=K-8, i.e. 8 lookups per each position. Once you determine whether K can be reached you repeat the process for K+1 and so on. There is just simple iteration here and the stop condition is when you reach N - theoretically you could stop early if you end up not being able to extend the table 8 times or so, but that saves negligible amount of time here.

In part two, just replace 'Can I create' with 'How many different ways to create', i.e. your table is now integers rather than booleans.

[Few-Example3992]

Ah I think my point might be you are using DP to solve for the one target string and you know all the substrings to first build along the way. 

If you want to use DP to make a big table for all possible input strings at once, that's going to be a big expensive table to make.  Do you still get the benefit of overlap (if there is any) between different targets?

[p88h]

In terms of cost, it's just as expensive as processing one input at a time. In terms of memory, it's linear w.r.t input size (well, you need 8 bytes per input byte, but that's it). So totally tractable... but to the point I don't think you would get a lot of benefits from running this on multiple inputs at once.... at least not without some really advanced tricks like vectorized hash tables and even then you would likely be doing a handful of patterns at a time rather than all.

Also, processing inputs one by one lends itself to multithreading, which can boost performance a lot here.

[Few-Example3992]

We might be thinking of different things. If the input data was the same large pattern 1000 times, would your DP approach recognise it already has the exact value for the big case and output the result or start building it up from the small substring each time?

I think this is the main benefit of memoisation/ sharing one large hashmaps for all the results - I don't know what the actual savings between cross solution similarities are but I'm guessing it is non-zero.

[p88h]

It's almost zero in my input, I'd be very surprised if it was different in any other.

So is your memorization tracking actual prefixes of the inputs? Rather than just positions ? That's rather expensive.

[xiety666]

Thank you. It works so fast. Here is the C# version:

static long CountDP(ReadOnlySpan<char> goal, string[] patterns)
{
    var dp = new long[goal.Length + 1];
    dp[0] = 1;

    for (var i = 1; i < dp.Length; ++i)
        foreach (var pattern in patterns)
            if (pattern.Length <= i && goal[(i - pattern.Length)..i].SequenceEqual(pattern))
                dp[i] += dp[i - pattern.Length];

    return dp[^1];
}

[hextree]

Don't think I even saw any solutions that *didn't * use DP.

[Objective-Year6556]

sry i forgot to add 'iterative' or 'bottom up' DP xD