Linen Layout

Advent of Code 2024 Day 19

Part 1

This may be...like...really tricky

The way I see it:

• I'm given a list of substrings
• And a list of long strings that contain many of the substrings, often the same one multiple times
• I have to match every character in a long string to some part or whole of the substrings
• Only when every character matches is the long string valid
• If even one character doesn't match, the long string is invalid

The example's first desired design offers a glimpse at how complicated this process could be:

r, wr, b, g, bwu, rb, gb, br

brwrr

Let's say I catalogued the patterns by their length:

{
    1: [r,b,g],
    2: [wr,rb,gb,br],
    3: [bwu]
}

The max length of a pattern is three, so I should never try to match more than three characters at a time. That's a nice limit.

I'll start small and build up.

Matched: 
Remainder: brwrr

Check for matches:
b       Match
br      Match
brw     No match

For each match, repeat the process with the remaining substring of the original design.

Starting with the first match of b:

Matched: b
Remainder: rwrr

Check for matches:
r       Match
rw      No match
rwr     No match

The only match is r:

Matched: b,r
Remainder: wrr

Check for matches:
w       No match
wr      Match
wrr     No match

The only match is wr:

Matched: b,r,wr
Remainder: r

Check for matches:
r:      Match

Every character in the design matched part a substring, so it is valid.

And I think I understand how the recursive algorithm I just stepped through should work.

There are some important small details I must account for in my algorithm:

• What happens when there are no matches?
• Start with smallest or biggest possible substring?
• What happens when the remainder is smaller than the biggest possible substring?
• How do I escape the function as soon as the pattern is determined possible, and avoid checking for additional winning cases?

Thankfully, I wrote them down and can refer to them later.

Setting everything up

Before entering what is sure to be recursive-atory, I have a few subtasks to complete:

• Parse the input into a list of patterns and a list of designs
• Catalogue the patterns by length

Turning one string into structured data

let input = input.split('\n\n')
let patterns = input[0].split(',')
let designs = input[1].split('\n')

Organizing patterns into groups by length

And computing the longest one.

let groups = patterns.reduce((acc, curr) => {
    let len = curr.length
    if (!(len in acc)) {
        acc[len] = []
    }
    acc[len].push(curr)
    return acc
}, {})
let longest = Math.max(Object.keys(groups).map(Number))

Writing another recursive algorithm. Joy.

First, this is the single line of code that runs my recursive algorithm and outputs the sum of valid designs:

let part1 = designs.map(d => isValid(d)).reduce((a,c) => { a += c ? 1 : 0 }, 0)

Now, onward to write the beast that is...isValid().

function isValid(design) {

}

It's gonna need more than the current design as an argument.

What else will I need to track in each iteration?

• Which portion has been matched
• Or which portion remains
• Has the design been determined possible yet?

Hmm, maybe that's it?

function isValid(remainingPortion) {

}

Now, diving inside.

First, I should check if the design has been decreed possible by the time any iteration is about to run.

I'll track that in a variable inside the map call, as a global variable available to all recursive function calls:

let part1 = designs.map(d => {
    let flag = false
    isValid(d)
    return flag
}).reduce((a,c) => { a += c ? 1 : 0 }, 0)

Then, first thing I'll do in my function is check flag:

function isValid(remainingPortion) {
    if (flag) { return true; }
}

That may need to be a break. I'll tinker later.

Next, I'll go biggest-to-smallest with the pattern matching:

• Try to match the longest pattern first, and smaller ones after that
• But only as big as what's remaining

Say my remaining string is brwrr and the longest pattern is of length 3:

let upper = Math.min(design.length, longest)
let options = []
for (let i = upper; i > 0; i--) {
    options.concat(groups[i].filter(p => p == design.slice(0,i)))
}

That should:

• Iterate through the groups of patterns three characters or less
• Generate an array of patterns matching the substring of characters at the beginning of the design
• Append the list of matched patterns (max of 1 match) to the temporary list of options

For each one, I must then recurse with the correct length of substing lobbed off the beginning of the remaining design:

options.forEach(el => {
    isValid(design.slice(0, el.length))
})

I'll know the string is valid if the remaining string has no length:

if (design.length == 0) {
    flag = true;
    break;
}

Again, not sure whether that should be break or return.

Putting the pieces together

Here is a combined first draft of my program:

let input = input.split('\n\n')
let patterns = input[0].split(',')
let designs = input[1].split('\n')
let groups = patterns.reduce((acc, curr) => {
    let len = curr.length
    if (!(len in acc)) {
        acc[len] = []
    }
    acc[len].push(curr)
    return acc
}, {})
let longest = Math.max(Object.keys(groups).map(Number))

let part1 = designs.map(d => {
    let flag = false
    isValid(d)
    return flag
}).reduce((a,c) => { a += c ? 1 : 0 }, 0)

function isValid(design) {
    if (flag) { break; }
    if (design.length == 0) {
        flag = true;
        break;
    } else {
        let upper = Math.min(design.length, longest)
        let options = []
        for (let i = upper; i > 0; i--) {
            options.concat(groups[i].filter(p => p == design.slice(0,i)))
        }
        options.forEach(el => isValid(design.slice(0, el.length)))
    }
}

Does it work? Or does it bug out?

I'll try it on the first example design:

r, wr, b, g, bwu, rb, gb, br

brwrr

Hoping to see an output of the options for each remaining substring of brwrr.

Time to run it!

As expected, lots of errors.

Time for lots of debugging!

...

I messed up a lot:

• I forgot to swap the recursive function call parameters, so it kept iterating on the same input string
• My use of a boolean flag didn't quite serve its function
• I ended up using a global array as a way to store the winning designs
• You can't break from a condition
• I forgot to spread out my list of number keys from the object mapping patterns to their length
• My function didn't seem to return true ever, so instead of relying on its return value, I just checked my new global array
• Probably more, but I already forgot

My updated, seemingly working - at least on the example input - algorithm looks like this:

let longest = Math.max(...Object.keys(groups).map(Number))
let winners = []
let part1 = designs.map(d => {
    isValid(d, d)
    return winners.includes(d)
}).reduce((a,c) => a += c ? 1 : 0, 0)

function isValid(remainder, original) {
    if (winners.includes(original)) { 
        return; 
    } else if (remainder.length == 0) {
        winners.push(original)
    } else {
        let upper = Math.min(remainder.length, longest)
        let options = []
        for (let i = upper; i > 0; i--) {
            options = options.concat(groups[i].filter(p => p == remainder.slice(0,i)))
        }
        options.forEach(el => isValid(remainder.slice(el.length), original))
    }
}

It correctly returns 6 for the example input.

Does my fixed program work on my puzzle input?

Only one way to find out...

Running...

After a minute and no answer, I stopped and added a line to print each design as it ran.

Running...

It's been several minutes, and still the first design hasn't printed.

Yikes. I really stink at writing performant recursive functions.

Any other measures to boost performance?

I printed the remaining string at the beginning of the function call.

As you might guess, there are a ton of repeats, especially long ones.

That means the program is continually walking all the way down a path it has visited N times, where N could be in the millions.

How might I help it avoid walking down so many repeat dead ends?

An idea:

• If the length of the remainder is greater than 0
• And it's substring options for available patterns is 0, mark it as a dead-end
• And if it's substring options for available patterns are all dead-ends, mark it as a dead-end

That way, it feels like I'll accumulate a list of bigger and bigger substrings that are dead-ends, eventually marking invalid designs quickly.

Version 3 of my algorithm, now with dead-end finder

let deadEnds = []
function isValid(remainder, original) {
    if (deadEnds.includes(remainder)) {
        return;
    }
    if (winners.includes(original)) { 
        return; 
    } else if (remainder.length == 0) {
        winners.push(original)
    } else {
        let upper = Math.min(remainder.length, longest)
        let options = []
        for (let i = upper; i > 0; i--) {
            options = options.concat(groups[i].filter(p => p == remainder.slice(0,i)))
        }
        if (options.length == 0 || options.length == options.map(el => deadEnds.includes(el)).length) {
            deadEnds.push(remainder)
        }
        options.forEach(el => isValid(remainder.slice(el.length), original))
    }
}

That first and last ifs are the real important parts.

Running again...

...and it finished almost immediately!

And the number isn't 0!

And it is less than half the number of the total designs!

This could be the right answer.

Time to submit!

Too low. Hmmm.

Tons of troubleshooting. Then, a breakthrough!

My question about my own recursive function:

• Are the dead ends being correctly identified and added?

It was time to test one or two at a time.

For the design, bbrgwb, I expected to see these dead ends:

[ 'wb', 'gwb', 'rgwb', 'brgwb', 'bbrgwb' ]

Resulting from:

• Recursing down to gwb as a remainder
• Having g as an option
• Then down to wb
• Where there are no options
• It is added to the dead ends
• Since wb was the only option for gwb, it is added
• And so on back up the recursive calls all the way to the original

The conditions for adding a remainder substring to my list of dead ends are as follows:
(ONE) If there are no options: no patterns match any possible substrings

(TWO) or if these two lists have the same number of items:

• The normal list of options
• A list where, for each item, the first N characters are removed - where N is the number of characters in the item - and the remaining substring is in the list of dead ends

(THREE) and the remainder is not in the list of patterns.

An example of this working is gwb:

• It is false for (ONE): an option is g
• It is true for (TWO): wb is in dead ends, so the normal list has one item, and the computed list checks if gwb minus g - so wb - is a dead end; it is; so that list has one item
• It is true for (THREE): gwb is not in the list of patterns

It took a long time, but this portion of my recursive function now looks like this:

if (   options.length == 0 
    || options.length == options.filter(
         el => deadEnds.includes(remainder.slice(el.length))
       ).length
   ) {
    if (!patterns.includes(remainder)) {
        deadEnds.push(remainder)
    }
}

Running...and winning!

It generates the correct answer for the example input.

And it does two other amazing things:

• It runs in a second on my puzzle input!!!
• It generates a new, higher number!!!
• It's the right answer!!!!!

Holy smokes, Batman!

I did it!!!

What an incredible feeling.

That is one hard-earned gold star.

Ok. Deep breath.

What could Part 2 throw at me?

Part 2

Enter: Multi-branch search trees

In Part 1 I just needed to find one winner.

Now I have to find every winner.

But not literally; meaning I don't want to re-tread any known winning path.

I want to write down each winning sub-path so I don't have to re-tread it each time my algorithm encounters it.

As I understand it, that's memoization at it's simplest.

For example, with gbbr and the patterns g, b, r, gb, and br, this is a crude tree structure:

        gbbr
     g       gb
   b       br  r
br    b
        r

Even with something this small, there are ways to optimize.

The instructions list all possible paths:

• g, b, b, r
• g, b, br
• gb, b, r
• gb, br

Assuming my algorithm explores each path in that order, here is what I want to "write down":

{
    'r': 1,
    'br': 2,
    'bbr': 2,
    'gbbr': 4
}

It will gather those tallies on its journey:

        gbbr
     g       gb
   b       br   b
br    b           r
        r


        4
     2   +   2
   2       1  + 1
 1  + 1           1
        1

If done correctly, then the br b path only needs to be walked once. The second time it is encountered, the total can be looked up.

Writing a second algorithm that processes all/only winning strings

I tried writing one.

I spent two hours writing, running, and troubleshooting.

Each time I paused to consider where my logic was failing, I thought of some new use case to account for.

I underestimated my inability to account for:

• patterns containing smaller patterns
• looking ahead to know if a substring should be memoized
• rethinking everything and starting from another perspective

My head hurts.

Part 2, you win.

I'm a bit bummed, but I also know that earning this second star was a long-shot.

I'm glad I tried!

On to the next day.