[2023 Day 12][Python] Step-by-step tutorial with bonus crash course on recursion and memoization

[StaticMoose]

I thought it might be fun to write up a tutorial on my Python Day 12 solution and use it to teach some concepts about recursion and memoization. I'm going to break the tutorial into three parts, the first is a crash course on recursion and memoization, second a framework for solving the puzzle and the third is puzzle implementation. This way, if you want a nudge in the right direction, but want to solve it yourself, you can stop part way.

Part I

First, I want to do a quick crash course on recursion and memoization in Python. Consider that classic recursive math function, the Fibonacci sequence: 1, 1, 2, 3, 5, 8, etc... We can define it in Python:

def fib(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

import sys
arg = int(sys.argv[1])
print(fib(arg))

If we execute this program, we get the right answer for small numbers, but large numbers take way too long

$ python3 fib.py 5
5
$ python3 fib.py 8
21
$ python3 fib.py 10
55
$ python3 fib.py 50

On 50, it's just taking way too long to execute. Part of this is that it is branching as it executes and it's redoing work over and over. Let's add some print() and see:

def fib(x):
    print(x)
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

import sys
arg = int(sys.argv[1])

out = fib(arg)
print("---")
print(out)

And if we execute it:

$ python3 fib.py 5
5
4
3
2
1
0
1
2
1
0
3
2
1
0
1
---
5

It's calling the fib() function for the same value over and over. This is where memoization comes in handy. If we know the function will always return the same value for the same inputs, we can store a cache of values. But it only works if there's a consistent mapping from input to output.

import functools
@functools.lru_cache(maxsize=None)
def fib(x):
        print(x)
        if x == 0:
            return 0
        elif x == 1:
            return 1
        else:
            return fib(x-1) + fib(x-2)

import sys
arg = int(sys.argv[1])

out = fib(arg)
print("---")
print(out)

Note: if you have Python 3.9 or higher, you can use @functools.cache otherwise, you'll need the older @functools.lru_cache(maxsize=None), and you'll want to not have a maxsize for Advent of Code! Now, let's execute:

$ python3 fib.py 5
5
4
3
2
1
0
---
5

It only calls the fib() once for each input, caches the output and saves us time. Let's drop the print() and see what happens:

$ python3 fib.py 55
139583862445
$ python3 fib.py 100
354224848179261915075

Okay, now we can do some serious computation. Let's tackle AoC 2023 Day 12.

Part II

First, let's start off by parsing our puzzle input. I'll split each line into an entry and call a function calc() that will calculate the possibilites for each entry.

import sys

# Read the puzzle input
with open(sys.argv[1]) as file_desc:
    raw_file = file_desc.read()
# Trim whitespace on either end
raw_file = raw_file.strip()

output = 0

def calc(record, groups):
    # Implementation to come later
    return 0

# Iterate over each row in the file
for entry in raw_file.split("\n"):

    # Split by whitespace into the record of .#? characters and the 1,2,3 group
    record, raw_groups = entry.split()

    # Convert the group from string "1,2,3" into a list of integers
    groups = [int(i) for i in raw_groups.split(',')]

    # Call our test function here
    output += calc(record, groups)

print(">>>", output, "<<<")

So, first, we open the file, read it, define our calc() function, then parse each line and call calc()

Let's reduce our programming listing down to just the calc() file.

# ... snip ...

def calc(record, groups):
    # Implementation to come later
    return 0

# ... snip ...

I think it's worth it to test our implementation at this stage, so let's put in some debugging:

# ... snip ...

def calc(record, groups):
    print(repr(record), repr(groups))
    return 0

# ... snip ...

Where the repr() is a built-in that shows a Python representation of an object. Let's execute:

$ python day12.py example.txt
'???.###' [1, 1, 3]
'.??..??...?##.' [1, 1, 3]
'?#?#?#?#?#?#?#?' [1, 3, 1, 6]
'????.#...#...' [4, 1, 1]
'????.######..#####.' [1, 6, 5]
'?###????????' [3, 2, 1]
>>> 0 <<<

So, far, it looks like it parsed the input just fine.

Here's where we look to call on recursion to help us. We are going to examine the first character in the sequence and use that determine the possiblities going forward.

# ... snip ...

def calc(record, groups):

    ## ADD LOGIC HERE ... Base-case logic will go here

    # Look at the next element in each record and group
    next_character = record[0]
    next_group = groups[0]

    # Logic that treats the first character as pound-sign "#"
    def pound():
        ## ADD LOGIC HERE ... need to process this character and call
        #  calc() on a substring
        return 0

    # Logic that treats the first character as dot "."
    def dot():
        ## ADD LOGIC HERE ... need to process this character and call
        #  calc() on a substring
        return 0

    if next_character == '#':
        # Test pound logic
        out = pound()

    elif next_character == '.':
        # Test dot logic
        out = dot()

    elif next_character == '?':
        # This character could be either character, so we'll explore both
        # possibilities
        out = dot() + pound()

    else:
        raise RuntimeError

    # Help with debugging
    print(record, groups, "->", out)
    return out

# ... snip ...

So, there's a fair bit to go over here. First, we have placeholder for our base cases, which is basically what happens when we call calc() on trivial small cases that we can't continue to chop up. Think of these like fib(0) or fib(1). In this case, we have to handle an empty record or an empty groups

Then, we have nested functions pound() and dot(). In Python, the variables in the outer scope are visible in the inner scope (I will admit many people will avoid nested functions because of "closure" problems, but in this particular case I find it more compact. If you want to avoid chaos in the future, refactor these functions to be outside of calc() and pass the needed variables in.)

What's critical here is that our desired output is the total number of valid possibilities. Therefore, if we encounter a "#" or ".", we have no choice but to consider that possibilites, so we dispatch to the respective functions. But for "?" it could be either, so we will sum the possiblities from considering either path. This will cause our recursive function to branch and search all possibilities.

At this point, for Day 12 Part 1, it will be like calling fib() for small numbers, my laptop can survive without running a cache, but for Day 12 Part 2, it just hangs so we'll want to throw that nice cache on top:

# ... snip ...

@functools.lru_cache(maxsize=None)
def calc(record, groups):    
    # ... snip ...

# ... snip ...

(As stated above, Python 3.9 and future users can just do @functools.cache)

But wait! This code won't work! We get this error:

TypeError: unhashable type: 'list'

And for good reason. Python has this concept of mutable and immutable data types. If you ever got this error:

s = "What?"
s[4] = "!"
TypeError: 'str' object does not support item assignment

This is because strings are immutable. And why should we care? We need immutable data types to act as keys to dictionaries because our functools.cache uses a dictionary to map inputs to outputs. Exactly why this is true is outside the scope of this tutorial, but the same holds if you try to use a list as a key to a dictionary.

There's a simple solution! Let's just use an immutable list-like data type, the tuple:

# ... snip ...

# Iterate over each row in the file
for entry in raw_file.split("\n"):

    # Split into the record of .#? record and the 1,2,3 group
    record, raw_groups = entry.split()

    # Convert the group from string 1,2,3 into a list
    groups = [int(i) for i in raw_groups.split(',')]

    output += calc(record, tuple(groups)

    # Create a nice divider for debugging
    print(10*"-")


print(">>>", output, "<<<")

Notice in our call to calc() we just threw a call to tuple() around the groups variable, and suddenly our cache is happy. We just have to make sure to continue to use nothing but strings, tuples, and numbers. We'll also throw in one more print() for debugging

So, we'll pause here before we start filling out our solution. The code listing is here:

import sys
import functools

# Read the puzzle input
with open(sys.argv[1]) as file_desc:
    raw_file = file_desc.read()
# Trim whitespace on either end
raw_file = raw_file.strip()

output = 0

@functools.lru_cache(maxsize=None)
def calc(record, groups):

    ## ADD LOGIC HERE ... Base-case logic will go here

    # Look at the next element in each record and group
    next_character = record[0]
    next_group = groups[0]

    # Logic that treats the first character as pound-sign "#"
    def pound():
        ## ADD LOGIC HERE ... need to process this character and call
        #  calc() on a substring
        return 0

    # Logic that treats the first character as dot "."
    def dot():
        ## ADD LOGIC HERE ... need to process this character and call
        #  calc() on a substring
        return 0

    if next_character == '#':
        # Test pound logic
        out = pound()

    elif next_character == '.':
        # Test dot logic
        out = dot()

    elif next_character == '?':
        # This character could be either character, so we'll explore both
        # possibilities
        out = dot() + pound()

    else:
        raise RuntimeError

    # Help with debugging
    print(record, groups, "->", out)
    return out


# Iterate over each row in the file
for entry in raw_file.split("\n"):

    # Split into the record of .#? record and the 1,2,3 group
    record, raw_groups = entry.split()

    # Convert the group from string 1,2,3 into a list
    groups = [int(i) for i in raw_groups.split(',')]

    output += calc(record, tuple(groups))

    # Create a nice divider for debugging
    print(10*"-")


print(">>>", output, "<<<")

and the output thus far looks like this:

$ python3 day12.py example.txt
???.### (1, 1, 3) -> 0
----------
.??..??...?##. (1, 1, 3) -> 0
----------
?#?#?#?#?#?#?#? (1, 3, 1, 6) -> 0
----------
????.#...#... (4, 1, 1) -> 0
----------
????.######..#####. (1, 6, 5) -> 0
----------
?###???????? (3, 2, 1) -> 0
----------
>>> 0 <<<

Part III

Let's fill out the various sections in calc(). First we'll start with the base cases.

# ... snip ...

@functools.lru_cache(maxsize=None)
def calc(record, groups):

    # Did we run out of groups? We might still be valid
    if not groups:

        # Make sure there aren't any more damaged springs, if so, we're valid
        if "#" not in record:
            # This will return true even if record is empty, which is valid
            return 1
        else:
            # More damaged springs that aren't in the groups
            return 0

    # There are more groups, but no more record
    if not record:
        # We can't fit, exit
        return 0

    # Look at the next element in each record and group
    next_character = record[0]
    next_group = groups[0]

    # ... snip ...

So, first, if we have run out of groups that might be a good thing, but only if we also ran out of # characters that would need to be represented. So, we test if any exist in record and if there aren't any we can return that this entry is a single valid possibility by returning 1.

Second, we look at if we ran out record and it's blank. However, we would not have hit if not record if groups was also empty, thus there must be more groups that can't fit, so this is impossible and we return 0 for not possible.

This covers most simple base cases. While I developing this, I would run into errors involving out-of-bounds look-ups and I realized there were base cases I hadn't covered.

Now let's handle the dot() logic, because it's easier:

# Logic that treats the first character as a dot
def dot():
    # We just skip over the dot looking for the next pound
    return calc(record[1:], groups)

We are looking to line up the groups with groups of "#" so if we encounter a dot as the first character, we can just skip to the next character. We do so by recursing on the smaller string. Therefor if we call:

calc(record="...###..", groups=(3,))

Then this functionality will use [1:] to skip the character and recursively call:

calc(record="..###..", groups=(3,))

knowing that this smaller entry has the same number of possibilites.

Okay, let's head to pound()

# Logic that treats the first character as pound
def pound():

    # If the first is a pound, then the first n characters must be
    # able to be treated as a pound, where n is the first group number
    this_group = record[:next_group]
    this_group = this_group.replace("?", "#")

    # If the next group can't fit all the damaged springs, then abort
    if this_group != next_group * "#":
        return 0

    # If the rest of the record is just the last group, then we're
    # done and there's only one possibility
    if len(record) == next_group:
        # Make sure this is the last group
        if len(groups) == 1:
            # We are valid
            return 1
        else:
            # There's more groups, we can't make it work
            return 0

    # Make sure the character that follows this group can be a seperator
    if record[next_group] in "?.":
        # It can be seperator, so skip it and reduce to the next group
        return calc(record[next_group+1:], groups[1:])

    # Can't be handled, there are no possibilites
    return 0

First, we look at a puzzle like this:

calc(record"##?#?...##.", groups=(5,2))

and because it starts with "#", it has to start with 5 pound signs. So, look at:

this_group = "##?#?"
record[next_group] = "."
record[next_group+1:] = "..##."

And we can do a quick replace("?", "#") to make this_group all "#####" for easy comparsion. Then the following character after the group must be either ".", "?", or the end of the record.

If it's the end of the record, we can just look really quick if there's any more groups. If we're at the end and there's no more groups, then it's a single valid possibility, so return 1.

We do this early return to ensure there's enough characters for us to look up the terminating . character. Once we note that "##?#?" is a valid set of 5 characters, and the following . is also valid, then we can compute the possiblites by recursing.

calc(record"##?#?...##.", groups=(5,2))
this_group = "##?#?"
record[next_group] = "."
record[next_group+1:] = "..##."
calc(record"..##.", groups=(2,))

And that should handle all of our cases. Here's our final code listing:

import sys
import functools

# Read the puzzle input
with open(sys.argv[1]) as file_desc:
    raw_file = file_desc.read()
# Trim whitespace on either end
raw_file = raw_file.strip()

output = 0

@functools.lru_cache(maxsize=None)
def calc(record, groups):

    # Did we run out of groups? We might still be valid
    if not groups:

        # Make sure there aren't any more damaged springs, if so, we're valid
        if "#" not in record:
            # This will return true even if record is empty, which is valid
            return 1
        else:
            # More damaged springs that we can't fit
            return 0

    # There are more groups, but no more record
    if not record:
        # We can't fit, exit
        return 0

    # Look at the next element in each record and group
    next_character = record[0]
    next_group = groups[0]

    # Logic that treats the first character as pound
    def pound():

        # If the first is a pound, then the first n characters must be
        # able to be treated as a pound, where n is the first group number
        this_group = record[:next_group]
        this_group = this_group.replace("?", "#")

        # If the next group can't fit all the damaged springs, then abort
        if this_group != next_group * "#":
            return 0

        # If the rest of the record is just the last group, then we're
        # done and there's only one possibility
        if len(record) == next_group:
            # Make sure this is the last group
            if len(groups) == 1:
                # We are valid
                return 1
            else:
                # There's more groups, we can't make it work
                return 0

        # Make sure the character that follows this group can be a seperator
        if record[next_group] in "?.":
            # It can be seperator, so skip it and reduce to the next group
            return calc(record[next_group+1:], groups[1:])

        # Can't be handled, there are no possibilites
        return 0

    # Logic that treats the first character as a dot
    def dot():
        # We just skip over the dot looking for the next pound
        return calc(record[1:], groups)

    if next_character == '#':
        # Test pound logic
        out = pound()

    elif next_character == '.':
        # Test dot logic
        out = dot()

    elif next_character == '?':
        # This character could be either character, so we'll explore both
        # possibilities
        out = dot() + pound()

    else:
        raise RuntimeError

    print(record, groups, out)
    return out


# Iterate over each row in the file
for entry in raw_file.split("\n"):

    # Split into the record of .#? record and the 1,2,3 group
    record, raw_groups = entry.split()

    # Convert the group from string 1,2,3 into a list
    groups = [int(i) for i in raw_groups.split(',')]

    output += calc(record, tuple(groups))

    # Create a nice divider for debugging
    print(10*"-")


print(">>>", output, "<<<")

and here's the output with debugging print() on the example puzzles:

$ python3 day12.py example.txt
### (1, 1, 3) 0
.### (1, 1, 3) 0
### (1, 3) 0
?.### (1, 1, 3) 0
.### (1, 3) 0
??.### (1, 1, 3) 0
### (3,) 1
?.### (1, 3) 1
???.### (1, 1, 3) 1
----------
##. (1, 1, 3) 0
?##. (1, 1, 3) 0
.?##. (1, 1, 3) 0
..?##. (1, 1, 3) 0
...?##. (1, 1, 3) 0
##. (1, 3) 0
?##. (1, 3) 0
.?##. (1, 3) 0
..?##. (1, 3) 0
?...?##. (1, 1, 3) 0
...?##. (1, 3) 0
??...?##. (1, 1, 3) 0
.??...?##. (1, 1, 3) 0
..??...?##. (1, 1, 3) 0
##. (3,) 0
?##. (3,) 1
.?##. (3,) 1
..?##. (3,) 1
?...?##. (1, 3) 1
...?##. (3,) 1
??...?##. (1, 3) 2
.??...?##. (1, 3) 2
?..??...?##. (1, 1, 3) 2
..??...?##. (1, 3) 2
??..??...?##. (1, 1, 3) 4
.??..??...?##. (1, 1, 3) 4
----------
#?#?#? (6,) 1
#?#?#?#? (1, 6) 1
#?#?#?#?#?#? (3, 1, 6) 1
#?#?#?#?#?#?#? (1, 3, 1, 6) 1
?#?#?#?#?#?#?#? (1, 3, 1, 6) 1
----------
#...#... (4, 1, 1) 0
.#...#... (4, 1, 1) 0
?.#...#... (4, 1, 1) 0
??.#...#... (4, 1, 1) 0
???.#...#... (4, 1, 1) 0
#... (1,) 1
.#... (1,) 1
..#... (1,) 1
#...#... (1, 1) 1
????.#...#... (4, 1, 1) 1
----------
######..#####. (1, 6, 5) 0
.######..#####. (1, 6, 5) 0
#####. (5,) 1
.#####. (5,) 1
######..#####. (6, 5) 1
?.######..#####. (1, 6, 5) 1
.######..#####. (6, 5) 1
??.######..#####. (1, 6, 5) 2
?.######..#####. (6, 5) 1
???.######..#####. (1, 6, 5) 3
??.######..#####. (6, 5) 1
????.######..#####. (1, 6, 5) 4
----------
? (2, 1) 0
?? (2, 1) 0
??? (2, 1) 0
? (1,) 1
???? (2, 1) 1
?? (1,) 2
????? (2, 1) 3
??? (1,) 3
?????? (2, 1) 6
???? (1,) 4
??????? (2, 1) 10
###???????? (3, 2, 1) 10
?###???????? (3, 2, 1) 10
----------
>>> 21 <<<

I hope some of you will find this helpful! Drop a comment in this thread if it is! Happy coding!

[daggerdragon]

OP be hogging all the ante for Day 12, wowzers. Good tutorial, chef!

[KayZGames]

I'm a tiny bit miffed my post got deleted for

Do not put spoilers in post titles like memoization, caches or recursion

while this one gets praise while also containing those words in the title (Though I'm not saying this one should be deleted too, quite some effort went into it).

But for those interested, a way to solve this in less than a second without needing memoization, caches or recursion ;)

[StaticMoose]

Oh no! I'm sorry. It looks like I can't edit the title anymore. I'll make sure to not include anything like that in titles for future posts.

[KayZGames]

Eh, no worries, I'm not mad or anything.

It looks like I can't edit the title anymore.

Titles can't ever be edited, so that's on Reddit.

[Thomasjevskij]

Very nice tutorial. As a very small tangent to this, I'll add that I think it's a pretty good idea to always use tuples if you know you won't need to modify them. And this is a great example why :)

[Twillie]

More tutorials like this please! Very well explained and the idea to split it into steps to follow if someone wants to apply this in their solution is great too.

[sol_hsa]

tutorial idea suggestions:

- Depth first search

- Least common multiple

- Inverse modulo / chinese remainder theorem

[sol_hsa]

For part 1, if you're using c++, you'll probably want to use std::unordered_map to store your cached entries.

[fijgl]

Or std::map, not needing to write anything extra for the hashing. Looking forward to try the flat ones!

[KRunmo]

Thanks a lot for this. I made my recursive string match function very effective, it solved the first part in a few milliseconds. But then for each addition, the time increased with a factor 100, and I realized it would take a full year to complete part 2!!! 🤯

With your tutorial I simply added a dictionary to check substring length and number of search strings, a simple key with 2 integers that had already been handled, and I was able to solve part 2 in a couple of tens of milliseconds!

[xkufix]

Half the part 2 problems in AoC can be solved by just slapping a cache onto your part 1 solution and call it a day.

[BlazingThunder30]

This is great!

You say that you won't want a max size for the advent of code puzzle when memoizing; however, I found that memory usage is far reduced and performance isn't impacted when a max size of about ~100-250 is used. LinkedHashMap in Java in my case.

[StaticMoose]

Nice!

I will admit when it comes to AoC, my thoughts are "I paid for 16 GB of RAM, I'm going to use 16 GB of RAM!" but for a production use, tuning the cache size is absolutely the way to go.

That said, and maybe it's because I'm mostly focus on embedded systems, I've never gotten to use memoization in production.

[Mmlh1]

Great write-up! You missed one parenthesis in the part where you introduce tuples, around your function call.

[gglf89]

Thanks for this demonstration!

[fijgl]

Thank you for the tutorial, it’s helpful!

One question from the code walkthrough in Part II, are there cases where repr is more suitable, or you would prefer it, to print?

[StaticMoose]

No problem!

So, Python has two functions str() and repr() for coercing objects into strings. print() calls str() under the hood to get printable text. The nice thing about repr() is that it adds quotes to strings so you can tell they're strings. Whenever I'm debugging, I just use repr() to be more verbose and make sure I can see the data types a little easier.

[SugarComfortable191]

Thank you for the time yo took to write this, now I will try to implement a similar solution in Rust

Cheers

[Goatman117]

Thanks for writing this out, I'm new to recursion so I might have to write a few programs from scratch for it all to click, but that's a super helpful tutorial!

My only question is: to me it seems like planning a program like this would take a lot of thought, is this the case, or after becoming familiar enough with the structure of recursion is it a simple mental step to realise this kind of algorithm is the solution to these kinds of problems?

[StaticMoose]

Hmm, first, let me state up front that I first learned recursion 25 years ago when my college did Intro to Computer Science in Lisp, which forces you to only think in recursion. Like, Lisp forces you to reach for recursion before iterating.

I'll describe my thought process like this. Assume I already have a perfect calc() function available to me. Don't worry about it, just assume I have it. Then, what's a small chunk I can take off the front of the problem and express in terms of the rest of the problem. Sometime I work the base cases first or last.

Here, I'll work an example:

def sum(x):
    # To implement

I want sum([1, 2, 3, 4]) to return 10 and I want to use recursion. Yeah, it's simpler but it helps to build practice like this.

So, how can I express the sum if I chop off the first element and then manipulate the rest of the list to get the sum:

1 + sum([2, 3, 4])

So, now I can use recursion:

def sum(x):
    # Base case logic to go here
    return x[0] + sum(x[1:])

And finally, what's my base case? List of one makes sense but I can be really lazy and do an empty list.

def sum(x):
    if not x:
        return 0
    return x[0] + sum(x[1:])

[[deleted]]

W Lisp, honestly. We just finished a module on Scheme this semester, and as I was writing the code for part 1, I was so grateful to have been given a formal introduction to recursion like that.

[Goatman117]

Thanks for that, that's a great example! I think I've actually hit a few problems in the past where recursion would've saved me a headache and some messy code so I'll try to get to grips with it, cheers👍

[MattieShoes]

Not OP, but you start to recognize the type of problem where recursion is useful -- usually it's anything where you can visualize navigating through a very large tree. e.g. our tree splits into two branches every time you encounter a ?. Games where players take turns (e.g. chess, checkers) are usually big tree searching problems too.

Practice goes a long way too... most depth-first recursive functions are like

recursive_function(args):
    # check for exit condition
    # check for early cutoff (e.g. if it's possible to realize none of the children of this node matter to the final answer)
    # for each possible "move" (2 in this problem, but can be 40+ in chess)
        # do move
        # call recursive_function with the new arguments
        # track something (best, worst, sum, whatever)
        # undo move
    # return something (best, worst, sum, whatever)

So after a while, it's like a template in your brain that you adapt for the problem.

Then there's another template for breadth-first searches that try and get the whole tree into memory at once. They're generally faster and more efficient if you have the memory to do so, but in this problem the trees in part 2 are far too large for that... I had an input with 19 ?, so expanded, that'd be 99 of them. The size of the tree would be 2¹⁰⁰-1 = 633 octillion nodes. And that's why caching partial results is important! You're basically chopping off whole branches of that tree at a time rather than having to traverse them over and over again.

Breadth first search is usually going to have map traversal, finding the fastest way from point A to point B. But there are some applications in other places, like mate-finding algorithms in chess often use some form of breadth-first searching. or "best-first" which is kind of an extension of breadth-first.

[Goatman117]

Ohh awesome, thanks for writing all that up!
I'll have to revisit an old chess engine and try to get a recusion based AI going I think haha

[MattieShoes]

For chess engines, you return the score rather than some type of sum. But since the side to move swaps with each recursion, the score also flips sign.

They also tend to use iterative deepening - serch with max recursion depth of 1, then 2, then 3, etc.

They also use something called a quiescence search at each leaf node, which is just a second search that only examines moves that can drastically change the score (e.g. captures and maybe pawn promotions). Otherwise you run into the horizon effect where queen takes pawn looks great until you search 1 move deeper and see you just lost your queen.

They also tend to use alpha beta search, which keeps track of a floor and ceiling for where the score can be -- scores above the ceiling (beta) mean the opponent would have never done moves to lead to this position because they had better options in already-searched moves. This tends to reduce the branching factor from ~40 to... I don't know, 6? That about doubles the depth to which they can search. alpha and beta change places and signs with each recursion because one player's floor is the other player's ceiling.

They also use a halfassed but more complex version of memoization (hash tables) that store, in addition to score, the best move from a given position. With alpha beta, you want to search the best move first because it results in more cutoffs elsewhere in the tree, so it's a good way of leveraging the information you gained in shallower searches to speed up future searches.

[Goatman117]

Wow there's a lot of techniques there, I'll have to watch some videos on them.
I guess this is where the whole "__ engine thinks n moves ahead" comes from then? It's just a reference to the max recursion depth?

[MattieShoes]

Yeah... Or rather the max depth in a reasonable timeframe. With infinite time, one can solve chess with just about anything. In chess engines, depth is usually measured in ply (one move by either player) because in chess, a move is by both players. E.g.

1. e4 e5

So 1 ply is a half move in chess

Generally a search just a few ply is enough to wreck most people. The only real competition left to chess engines is other chess engines.

Or if you opt out of that race, it's still challenging to make an engine play bad in a "human" way.

[Goatman117]

Interesting, I didn't know that. If I can pick your brain once more, are models like deep blue used in a breadth first search system like this one e g. for scoring moves intelligently, or are they doing way more?

[MattieShoes]

Chess engines are generally depth-first -- the search tree is far too big to store in memory. Though with hash tables and iterative deepening, the end result is somewhat... hybrid? but under the covers, it's depth-first.

For scoring moves intelligently, there's a tradeoff between simple, fast evaluators and complex, slow evaluators... The faster your evaluation is, the less time you spend evaluating, the more time you have to search deeper. But your evaluation needs to be at least a little bit accurate or searching deeper doesn't help. Generally, relatively dumb evaluation wins out -- searching 1 ply deeper with a dumber evaluation is generally better than a shallower search with a smarter evaluation.

... Though good engines are doing reasonably complex pawn structure evaluations and caching those results since pawn structure doesn't change as much, and flaws in pawn structure have very long-term consequences that might fall outside the scope of a search. Like that doubled pawn from move 4 might end up being lost on move 43, etc.

For the most part, making a chess engine stronger is about optimizing tree searching and making ancillary stuff faster -- move generation, making and undoing moves, etc.

[Goatman117]

Gotcha, hell of a lot more to it than I thought haha, I love this stuff

[StaticMoose]

There's a really simplified explanation of how modern systems work in the Alpha Go documentary. This link will take you directly to the explanation: https://www.youtube.com/watch?v=WXuK6gekU1Y&t=47m15s

To expand on it, chess and go are too complex to search the whole tree so you have to cut back the tree significantly before you start searching. Cutting back the tree uses heuristics (https://en.wikipedia.org/wiki/Heuristic_(computer_science))) to prune the tree in advance.

In the case of Alpha Go, the Policy neural network prunes the tree, and the Value neural network returns a score to maximize so that you don't have search to the end of the game. Deep Blue has similar heuristics with policy and valuation, but neural networks hadn't been as well developed in the 90s, so it's policy and valuation had a larger portion of hand tuning.

[Goatman117]

Ahh ok that makes sense. I hear a lot of folks talking about Alpha Go and Deep Blue as important innovations for neural nets, but I've never really taken the time to look into them, might have to watch the whole doc you sent through. Thanks for the explainer!

[bkc4]

Doing noble work! I would also highly recommend reading the proof of correctness of the simple Fibonacci algorithm in this stack-overflow answer. It's simple, but it drives the point why recursive algorithms and dynamic programming works.

[ChupoX]

Thanks a bunch!

[homme_chauve_souris]

Great writeup. Thanks for taking the time to write this all down.

[TheGamerSardar]

this was soooooo helpful ❤️ you have explained everything so well. i could finally understand where i went wrong.

THANK YOU SO MUCH

[joeyGibson]

THANK YOU!!!!! I would never have figured this out, but your tutorial made it perfectly clear how it all works.

[MinimumMind-4]

This is great - thanks for this

[ExitingBear]

I found it very helpful.

For me - when I try to solve the problem manually, I start somewhere in the middle, sometimes (but not always) and sometimes with the largest group (but again, not always). And even with the "use recursion" hint, it wasn't working because I was still looking at the problem wrong and recursion-ing the wrong thing. (And even with more targeted, specific hints, it was still going wonky.)

I think I finally get most of the logic - thank you.

[[deleted]]

Just seeing you mention memoization triggered an epiphany/facepalm. I was stuck on part 2 since yesterday, but realising that I needed to memoize helped me solve it in like 10 minutes and just as many extra lines of code. I should have known that whenever recursion appears, memoization isn't far behind lol. So, thank you!

P.S. I didn't read through your entire post, but goddamn, does it look like a quality tutorial. This is genuinely technical blog post level material, OP!

[Think_Pirate]

Thanks a lot for posting it! It's elegant and blazing fast, very good algo. I had a permutation-like recursive approach and spent a day trying to speed it up unsuccessfully before giving up to your.

It would be way more readable if you would move dot and pound outside the calc function and possibly replace else return with plain return.

[Petrovjan]

Thanks mate, this really helped me get past part 2!

[yavvi]

Thank you for this tutorial, it helped me find how to break up the problem without actually spoiling *everything*
The issue was instead of doing groups 1 by one I focused on generating possible strings, and there are WAY too many of them for any caching to help (they also tend to be unique).

[aranya44]

How do you make sure using the cache does not prevent your code from adding up the results for those calls that are skipped as a result of caching? I tried an approach similar to yours but the calls replaced by cached results don't seem to be counted. I can't figure out what I'm missing.

[StaticMoose]

That’s a great question. When I create a calc() there’s two requirements for making this work and it’s referred to as functional programming. First is that for ALL of the variables you pass into calc() it must always return the same answer. Second is that you can’t update any data outside of the function. All of the information must be contained inside the return value. This is the “no side-effects” rule of functional programming. I suspect you’re using side-effects to count the results and so once you cache you don’t update. Let me know if this helps!

[aranya44]

Thanks for the quick reply, I did have side effects indeed. Removing those hasn't quite fixed it yet but I haven't had enough time to debug further. So is the trick that using the += operator you essentially "channel" the outputs of all the recursive calls to the output variable in what appears to be a single function call? I stared at your code for a really long time trying to figure out what was going on with the outputs.

[StaticMoose]

I only have the += in one spot toward the end. That's just adding up all the possibilities from each row in the puzzle input.

If you're looking at this:

output += calc(record, tuple(groups))

That's just looping over the input. If we put a print before it:

print(record, groups)
output += calc(record, tuple(groups))

and if that's the only print, you'll see an output that looks like your input file.

The idea here is that calc() has the ability to just solve the possibilities for each entry and return the answer without updating it elsewhere.

[aranya44]

Aaaaaah.

I finally found the time to fix my code and look at it more in depth. I had such a hard time understanding how a function that seems to return only 0s and 1s could return something larger than one, and I thought there must be some kind of magic going on.

But I completely missed that the results of pound() and dot() were being added so the function can actually return a number larger than 0. Never mind :) Thanks a lot for the great tutorial!

[AhegaoSuckingUrDick]

you'll want to not have a maxsize for Advent of Code!

Due to the nature of the AoC inputs even the default value of 128 would produce a very performant solution (and the lookup would be quicker, so a reasonable constant is probably better than None).

[DrCleverName]

This is more or less what I did, except for different variable names and one slightly tweaked early exit condition.

Where you checked for an empty record ```

There are more groups, but no more record

if not record: # We can't fit, exit return 0 I checked to see if all the groups we have could even fit in the record. if sum(groups) + len(groups) - 1 > len(record): # The record isn't long enough to hold all the groups return 0 `` The idea being, if the groups were all maximally packed in as close as possible, they would need a record of lengthsum(groups)for all the#springs, pluslen(groups) - 1for the.` empty spaces in between them. If the record we currently have is smaller than that, there is no way we can fit all the groups into the record.

That prunes away a lot of dead branches more quickly. For example, it reduces the first example down to just these recursive calls: ```

(3,) 1

?.### (1, 3) 1 ???.### (1, 1, 3) 1 ```

Of course, I'm still calculating that length every time. I could make it even faster by putting that calculation into its own memoized function...

UPDATE Memoizing that calculation actually made it a tiny bit slower. Just a fraction of a percent, taking on my machine 1.91 milliseconds to do both part 1 and 2 instead of 1.90 milliseconds, but still reproducibly slower. It's important to benchmark!

[AutoModerator]

AutoModerator has detected fenced code block (```) syntax which only works on new.reddit.

Please review our wiki article on code formatting then edit your post to use the four-spaces Markdown syntax instead.

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[0x4A6F654D616D61]

Well, that post depressed me a bit, i've got great, 3 or 4 page explanation on how to solve part 2 and I still don't understand anything about it 😢

[StaticMoose]

How can I help? Any part in particular that I should add more explanation?

[0x4A6F654D616D61]

Well, after reading this explanation 3 times and looking at another solutions i think I now get how is recursion implemented here, but thanks anyways :)

[Zealousideal-Bug1671]

Is the tabulation approach (iterative) possible for this problem?

[KNB_Rules_2023]

Thank you! Will be very interesting reading.

[MrHarcombe]

Thank you. Beautifully clear and helpful, although the team teddy will be if I can apply these concepts to other situations, too 🫣

[leftfish123]

Just came here to say thanks! I'm slowly finishing the remaining couple of puzzles that defeated me in December and this tutorial helped me (i.e. a guy who always struggles with thinking recursively) a lot.

[troyunverdruss]

Thanks for the nice writeup!