Forem: Robert Mion

Printing Department

Robert Mion — Sat, 28 Mar 2026 02:52:32 +0000

Advent of Code 2025 Day 4

The ease of Part 1 concerns me

I've solved this puzzle at least a dozen times throughout Advent of Code.

There is almost certainly going to be a unique twist in Part 2.

For now, it's time to solve this yet again.

Writing another adjacent grid cell inspector

First, I want to 'pad' the grid with a border of .s so I can safely check each original cell without having to account for out-of-bounds errors.

I usually do this after converting the string into a 2-dimensional array.

But this time, I will opt to create a new string by adding characters from a stringified array and replacing newline characters with dot-padded newline characters.

Here's the single, long concatenation statement:

let lineLength = input.indexOf('\n')
input = new Array(lineLength + 2).fill('.').join('') 
    + '\n.' 
    + input.replaceAll('\n', '.\n.') 
    + '.\n' 
    + new Array(lineLength + 2).fill('.').join('')

It turns this:

..@@.@@@@.
@@@.@.@.@@
@@@@@.@.@@
@.@@@@..@.
@@.@@@@.@@
.@@@@@@@.@
.@.@.@.@@@
@.@@@.@@@@
.@@@@@@@@.
@.@.@@@.@.

Into this:

............
...@@.@@@@..
.@@@.@.@.@@.
.@@@@@.@.@@.
.@.@@@@..@..
.@@.@@@@.@@.
..@@@@@@@.@.
..@.@.@.@@@.
.@.@@@.@@@@.
..@@@@@@@@..
.@.@.@@@.@..
............

And it works like a charm for any grid.

Next, my usual dictionary of relative coordinates for each adjacent cell:

let adjacents = [
    [-1,-1], [-1,0], [-1,1],
    [0,-1], [0,1],
    [1,-1], [1,0], [1,1]
]

Next, creating the grid, initializing the counter, and shell of the nested for loop:

let answer = 0
let grid = input.split('\n').map(el => el.split(''))
for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < input[0].length; col++) {

    }
}

Lastly, checking each adjacent cell and tallying up the rolls:

answer += grid[row][col] == '@' 
    && adjacents
        .map(
            cell => grid[cell[0] + row][cell[1] + col] == '.' ? false : true
        )
        .filter(el => el == true).length < 4 ? 1 : 0

It is one statement that does the following:

Increment answer by 1...
As long as the current cell contains a @...
And the number of adjacent cells containing a @ is less than 4
Otherwise increment by 0

Testing it on the example input produces the correct answer, 13.

What about on my puzzle input?

...

I got the correct answer!

Nice!

And now...for Part 2's likely diabolical twist.

Part 2

What a delightful twist

It is essentally Part 1 repeated until no change in state is produced.

Even as large as my grid is, I feel like brute-forcing this will still generate an answer fairly quickly.

I could be wrong, but that doesn't change my approach to solve this part.

Building on Part 1

For Part 1, I processed a single iteration.

I now need a while loop to process as many iterations as it takes until no new rolls can be removed.

And I need to keep track of both the amount and location of rolls to be removed (a.k.a. turned into empty cells).

let changers = []
do {
    for (let row = 1; row < grid.length - 1; row++) {
        for (let col = 1; col < grid[0].length - 1; col++) {
            changers.push( grid[row][col] == '@' && adjacents.map(cell => grid[cell[0] + row][cell[1] + col] == '.' ? false : true).filter(el => el == true).length < 4 ? [row,col] : null)
        }
    }
    changers = changers.filter(el => el !== null)
    console.log(changers)
} while (changers.length > 0)

The code above successfully catalogs all cell locations of rolls that should be removed.

At least...after 1 iteration.

Since it never mutates the grid or clears the array, it repeatedly adds the same set of cell locations to the same array.

Time to fix that.

let changers = []
let answer = 0
do {
    answer += changers.length
    changers.forEach(cell => {
        grid[cell[0]][cell[1]] = '.'
    })
    changers = []
    for (let row = 1; row < grid.length - 1; row++) {
        for (let col = 1; col < grid[0].length - 1; col++) {
            changers.push( grid[row][col] == '@' && adjacents.map(cell => grid[cell[0] + row][cell[1] + col] == '.' ? false : true).filter(el => el == true).length < 4 ? [row,col] : null)
        }
    }
    changers = changers.filter(el => el !== null)
} while (changers.length > 0)

It was a simple addition of the forEach() loop early in the do-while loop.

I also added the answer variable to track the sum of removed rolls.

Running it on the example input generates the correct answer.

As always, fingers crossed it runs on my puzzle input...and generates the correct answer.

...

It worked!

Finished immediately and generated the correct answer!

Woohoo!!

That was a lot easer than I expected Part 2 to be.

It makes me worried for a much tougher Day 5.

Can't wait to find out!

Lobby

Robert Mion — Tue, 24 Mar 2026 00:48:12 +0000

Advent of Code 2025 Day 3

Part 1

Considering my options, from worst to best

Each line is an ordered list of positive digits.

I must identify the largest 2-digit number made from any two digits appearing in order.

I can think of a few ways to do this, from brute-force to better.

Brute force

Compare every possible combination of digits:

Set an initial value, max, to 0
For each digit except the last
  For each subsequent digit
    If the ordered concatenation of digits is greater than 'max'
      Update max to reflect this 2-digit number

Measuring performance:

Given line length, L
This will run L + L-1 + L-2 + L-3 + ... times
Example: L = 10 - runs 10 times for first number, 9 times for second number, etc. - 55 times

Not great. But still should complete quickly even for line lengths less than 100. My puzzle input lines are roughly 40 digits long.

Brute force but optimized

Compare digit pairings for increasing 10s-place digits

Set an initial value, max, to 0
Set an initial value, lower, to 0
Set an index tracker to 0
While index is less than line length
  If current digit is less than or equal to lower
    Increment index
  Else
    For each subsequent digit
        If the ordered concatenation of digits is greater than 'max'
        Update max to reflect this 2-digit number
  Increment index

Measuring performance:

Ideally, this algorithm will skip several digits
So, still L + L-1 + L-2... but with several L-N skipped
It could be as fast as only comparing digits for the first digit
Or as slow as the one above if all digits appear in increasing order, 123456789

Getting creative: find the two biggest numbers

I'm ultimately trying to identify a pair of digits as close to 99 as possible.

Sounds like a great use case for finding the two biggest digits in a line.

Here are a few scenarios:

A line has two instances of a high number
A line has one instance of a high number, and it is not the last digit in the line
A line has one instance of a high number, but it is the last digit in the line

Scenario 1 is ideal because the answer there is the two numbers combined in order.

Scenario 2 is easy because the answer is that high number paired with the next highest number appearing anywhere after it.

Scenario 3 is harder because it is essentially a red herring, and I will have to check for the next highest number.

Still, this feels way more performant than the two options above.

So, I'm going to proceed with thinking through and coding this algorithm.

Building the creative algorithm

I'll wrap it all in a reduce() since I must eventually calculate a sum.

First step, though, is the find the biggest digit in a line.

input.split('\n').reduce((sum, line) => {
    let digits = line.split('').map(Number)
    let biggest = Math.max(...digits)
    return sum
}, 0)

Next, see if there are two of that biggest number:

let biggest = Math.max(...digits)
let firstBiggest = digits.indexOf(biggest)
let lastBiggest = digits.lastIndexOf(biggest)

If both of those index-based values are equal, there's only one of the biggest number, and my search continues.

But if they are different, then the biggest number is that number twice!

if (firstBiggest !== lastBiggest) {
    sum += +(biggest.toString() + biggest.toString())
}

Next, preparing the other two possible outcomes:

if (firstBiggest !== lastBiggest) {
    sum += +(biggest.toString() + biggest.toString())
} else if (lastBiggest < digits.length - 1) {
    // Biggest digit is not the last digit
    // Find the subsequent biggest digit
} else {
    // Biggest digit is the last digit
    // Find the next biggest digit and proceed
}

For the second condition, I just need to find the highest number in the substring of digits after the highest number, and pair it with the highest number:

if (firstBiggest !== lastBiggest) {
    sum += +(biggest.toString() + biggest.toString())
} else if (lastBiggest < digits.length - 1) {
    sum += +(biggest.toString() + Math.max(...digits.slice(lastBiggest + 1)).toString())
} else {
    // Biggest digit is the last digit
    // Find the next biggest digit and proceed
}

The last condition is actually the same, but opposite.

By that I mean I need the substring of characters including all but he last one.

if (firstBiggest !== lastBiggest) {
    sum += +(biggest.toString() + biggest.toString())
} else if (lastBiggest < digits.length - 1) {
    sum += +(biggest.toString() + Math.max(...digits.slice(lastBiggest + 1)).toString())
} else {
    sum += +(Math.max(...digits.slice(0, lastBiggest)).toString() + biggest.toString())
}

Here is my full algorithm:

let part1 = input.split('\n').reduce((sum, line) => {
    let digits = line.split('').map(Number)
    let biggest = Math.max(...digits)
    let firstBiggest = digits.indexOf(biggest)
    let lastBiggest = digits.lastIndexOf(biggest)
    if (firstBiggest !== lastBiggest) {
        sum += +(biggest.toString() + biggest.toString())
    } else if (lastBiggest < digits.length - 1) {
        sum += +(biggest.toString() + Math.max(...digits.slice(lastBiggest + 1)).toString())
    } else {
        sum += +(Math.max(...digits.slice(0, lastBiggest)).toString() + biggest.toString())
    }
    console.log(sum)
    return sum
}, 0)

Thankfully, it generates the correct sum for the example input!

I now wonder if my conditions account for all of the possible scenarios that could example in my puzzle input.

...

They did!

My answer was correct!!!

Rock on.

Onward to Part 2.

Part 2

More digits, more problems

Now the challenges are:

Which 12 digits do I pick?
What order are they in?

That last challenge is important.

To see why, take this 6-digit line:

Say I had to pick 5 numbers to keep.

Depending on which 1 I keep, I would get two different numbers. And I want the bigger number.

98891
98189

But wait, there's more!

The example lines are poor examples of the real challenge here.

My input lines are over 40 digits long.

The 12 digits that comprise the largest 12-digit number of possibly non-contiguous digits may appear anywhere in that string.

For example, this comes from my input:

1341524443834221222553325236443534253327533543493534348242333119334424249244524325448544522322512344

There are three 9s well before the end of the string

1341524443834221222553325236443534253327533543493534348242333119334424249244524325448544522322512344
                                               *               *        *

I will want to include all three 9s in the joltage number to maximize it's amount.

From there, I will want to include the next largest number, and so on, as long as there are enough digits that follow to amass 12 digits.

So, I could start it with 999855.

In fact, it could contain the last 5 and the remaining digits: 999855512344.

How could I programmatically - and performantly - deduce the same largest 12-digit number from that string?!

Maybe my Part 1 algorithm was on to something

One way to solve this is using recursion:

Explore all continually reducing substrings
Removing one number at a time
Until arriving at a 12-digit string
Update a global 12-digit number only when the new string is greater

But that is ridiculousness.

There's gotta be a better way, right?

After much thought, it turns out my logic from Part 1 may be highly applicable here, too!

Allow me to step through it and attempt to explain.

I'll stick with the same example from above:

1341524443834221222553325236443534253327533543493534348242333119334424249244524325448544522322512344

Recall that the answer I arrived at was:

999855512344

First, I look for the highest number. It's 9.

There are a few.

I target the earliest 9.

It has at least 11 digits after it, so it's a safe choice as the first of 12 digits.

I move to the next 9.

Same situation: 10 digits after it, so a safe choice.

Same for the last 9.

The next highest number is 8.

It, too, is a safe choice because there are at least 8 digits after it.

This continues with the 5s, of which there are 3.

Now for the tricky part.

The next highest number is a 4. There are 2.

But there are not enough digits that come after them to eventually create a 12-digit number.

The next highest number is a 3. There's 1.

Same problem.

Next is a 2.

Same problem.

Next is a 1.

There are enough digits after it to make it a safe choice.

In fact, there are exactly enough digts to make 12.

So I can select each subsequent digit and end this journey.

In summary, the algorithm:

Knows how many digits are remaining to select
Finds the earliest instance of the next highest digit
Confirms whether there are enough digits to fill all remaining slots
If so, it selects the current digit and it proceeds with the next iteration of the current number
If not, it decrements the highest digit and continues the search
And if there are exactly enough digits, it fills all remaining slots then and there

This has a real chance of working!

Time to try codifying it into a working program.

Writing my algorithm...very gradually

Setting the stage:

input.split('\n').reduce((sum, line) => {
    let picks = new Array(12).fill(null)
    let digits = line.split('').map(Number)
    let marker = 0
    return sum
}, 0)

I need

An array with 12 slots to fill with the appropriate digits
An array of digits made from the string
And a way to track the remaining substring

Next, a while loop that will fill the array.

while (!picks.includes(null)) {
    // Continue filling each subsequent slot
}

How many slots are left?

let slotsLeft = picks.length - picks.indexOf(null)

Find the location of the next highest number:

while (!picks.includes(null)) {
    let slotsLeft = picks.length - picks.indexOf(null)

    let digitsLeft = digits.slice(marker)
    let biggest = Math.max(...digitsLeft)
    let firstOf = digitsLeft.indexOf(biggest)
}

If there are enough digits after the biggest digit to fill the rest of the array, slot it into the array and update the location from which to generate the next substring:

if (digitsLeft.length - firstOf >= slotsLeft) {
    picks[picks.indexOf(null)] = biggest
    marker += firstOf
}

That feels right. But is it?

I need to test it on an example.

...

I'm not seeing any evidence of the while loop running.

What's wrong?

Ooohhhhhhh...wow.

Look at that condition:

while (!picks.includes(null)) {}

It only runs when there are no null values in the final array!

That's my stopping condition, not my continue condition!

Exclamation point: removed!

Now I see it running.

Wow wow wow.

Now I see 12 9s when using the first example string.

That's obviously not right.

What's wrong?

Oh, I didn't account for the first digit in the substring being the next correct one.

When that's the case, it's index is 0 and marker doesn't increment.

To fix it, I'll use a ternary operation:

marker += firstOf > 0 ? firstOf : 1

Now I see the correct 12-digit number for the first example string!

But I don't see it move on to the next string.

Why not?

Ohhhh, because the next string has a 9 at the end, and I haven't written the condition for that yet.

This will require more tracking:

Determine the highest number in the substring
See if there are enough remaining digits if it is selected
If not, remove that number as a possibility

I may need to avoid using Math.max(), since that will always find the highest number.

Instead, I may need to count down from 9 repeatedly until finding the next best number.

I don't like it, but it should work.

...

Well, after a lot of head-scratching about how to hone in on the best number, I wrote this:

let current = 9
while (true) {
    if (digitsLeft.includes(current)) {
        if (digitsLeft.length - digitsLeft.indexOf(current) < slotsLeft) {
            current--
        } else {
            break;
        }
    } else {
        current--
    }
}

A manually-breaking while loop
First checks for the current number in the string
Then checks for sufficient remaining digits
If either condition is false, decrement the number
Otherwise, exit the loop because it found the right number

Then, proceed as normal:

picks[picks.indexOf(null)] = current
marker += digitsLeft.indexOf(current) > 0 ? digitsLeft.indexOf(current) : 1

I don't like the redundant code, but I can't save it into a variable outside the while loop.

Alas, my program generates correct numbers from each of the four example strings!

Will it do the same for some randomly selected strings in my puzzle input?

No. No it won't.

Why not?

Well, it appears to be duplicating some digits.

It looks to me like there's a problem with marker placement: it's not moving forward appropriately each iteration through the while loop.

After a lot of trial and error, I figured out where a + 1 was needed:

marker += digitsLeft.indexOf(current) > 0 ? digitsLeft.indexOf(current) + 1 : 1

And with that, it appears to be generating the correct 12-digit numbers from each string!

It may be time to try it on my puzzle input.

Running on my puzzle input

Running.

An answer appeared immediately!

And it is the correct answer!!

Woohoo!!!

That felt awesome.

What a fun challenge!

It took a ton of ruminating to arrive at a working algorithm.

And I'm so glad it paid off with the second gold star for the day.

Feels good to go into Day 4 with 6 gold stars.

Gift Shop

Robert Mion — Sun, 15 Feb 2026 21:03:28 +0000

Advent of Code 2025 Day 2

Part 1

Optimizing a brute force algorithm

I don't yet recognize a pattern in the numbers to write a program that doesn't check every number.

But I do see a way to skip certain ranges, depending on a few characteristics:

Skip any numbers containing an odd amount of digits. Those numbers can't have repeated sets of digits, since two of any number makes an even number
Skip any numbers where the amount of changing digits is less than the amount of

How might I optimize a brute force algorithm?

I don't yet recognize a pattern in the numbers to write a program that doesn't check every number.

But I do see a way to skip certain ranges, depending on a few characteristics:

Skip any numbers containing an odd amount of digits. Those numbers can't have repeated sets of digits, since two of any number makes an even number
Skip any numbers where, when split in half, the second digit could never become a duplicate of the first

I originally understood invalid IDs to be digits where any digit could repeat once and the digit had to comprise only repeat digits.

I now see that an invalid ID must be made of two identical digits.

That should make this much simpler to solve.

Stepping through a few examples to plot out my algorithm

First up, 11-22.

This reveals the first challenge of checking every number in the range, including the bookends.

Step 1, confirm this could have an invalid ID:

11
- Length: 2 (even)

22
- Length: 2 (even)
- Largest unit that changes is in the 10s place: both digits can change

Are both numbers an odd length?
    If Yes, no possible invalid IDs
    If No
        Determine the largest unit that differs between the digits
            Consider doing something depending on whether it's less than or greater to half the length
                Compare the initial digits of each half of the larger digit
                    If any digits in the second half that are before the largest differing unit
                        No possible invalid IDs
                    If all digits that won't change are repeats
                        Proceed with checking each possible ID, skipping large ranges where possible

Putting that algorithm to the test:

11-22
Neither number is odd length
Largest unit is 10s place - maximum place
Safe to proceed with checking

Again:

95-115
One is an odd length
    Consider handling this with a range reducer that lowers or raises the odd length digit to match the even length digit
After doing that
95-99
Neither number is odd length
Largest unit is 1s place - not maximum place
Comparing 10s place: 9 to 9 (identical!)
Safe to proceed with checking

Again:

998-1012
One is an odd length
Increase odd to even length
1000-1012
Neither number is odd length
Largest unit that differs: 10s place
Comparing 1000s place: 1 to 1
Comparing 100s place: 0 to 0
Safe to proceed with checking

Again, with a number from my input:

86274-120443
One is an odd length
Increase odd to even length
100000-120443
Neither number is odd length
Largest unit that differs: 10000s place
Comparing 100000s place: 1 to 1
Safe to proceed with checking

As for the checking part of my algorithm...

Split apart and increment, am I right?

Invalid IDs are numbers where both halves are the same.

It should prove true that I could increment the lower half and compare to the other half for equality.

Doing this properly could save thousands of unnecessary checks.

I'll illustrate:

100000-120443

100 != 000
       +
100 == 100
  +      +

101 == 101

...

119 == 119

120120 > 120443

That was 20 invalid IDs among over 20k possible values.

That feels like optimization to me!

I feel confident I could codify this, too!

Summarizing the tasks in order

Compare lengths of each bounding number
Skip double-odd bounding number ranges
Adjust odd-even bounding number ranges to be even-even
Identify the largest unit/place that can change
Loop: spilt the number in half and increment each until out of range

That feels smart and doable.

Time to finally start coding!

Writing an algorithm

It all goes in a reduce()r:

input.split(',').reduce((counter, range) => {
    // All the important work
    return counter
}, 0)

Extracting the bounding numbers:

let [min, max] = range.split('-').map(Number)

Checking for varying lengths and correcting:

// Same length
if (min.length == max.length) {
    // Both odd length
    if (min.length % 2 == 1) {
        // Skip entire range
    } else {
        // Both even, proceed
        IDchecker(min, max)
    }
} else {
    // Different length
    // Adjust appropriate number to make both even
    if (min.length % 2 == 1) {
        // Increment min until its an even amount of digits
        // Achieved by changing it to the lowest number with a higher unit: NN -> 100
        min = +("1" + new Array(min.length).fill("0").join(""))
    } else {
        // Decrement max until its an even amount of digits
        // Achieved by changing it to the highest number with a lower unit: NNN -> 99
        max = +("1" + new Array(min.length - 1).fill("0").join("")) - 1
    }
    // Both even, proceed
    IDchecker(min, max)
}

As usual, I overlooked a few glaring errors.

Here's the ammended code snippet:

// Same length
if (min.toString().length == max.toString().length) {
    // Both odd length
    if (min.toString().length % 2 == 1) {
        // Skip entire range
    } else {
        // Both even, proceed
        counter += IDchecker(min, max)
    }
} else {
    // Different length
    // Adjust appropriate number to make both even
    if (min.toString().length % 2 == 1) {
        // Increment min until its an even amount of digits
        min = +("1" + new Array(min.toString().length).fill("0").join(""))
    } else {
        // Decrement max until its an even amount of digits
        max = +("1" + new Array(max.toString().length - 1).fill("0").join("")) - 1
    }
    // Both even, proceed
    counter += IDchecker(min, max)
}

What I did wrong:

In JavaScript, I have to convert a number to a string to check its length
I mistakenly referenced min when setting max
I forgot I'll need to adjust counter with the result of calling my IDchecker() function

I'm now seeing exactly what I want in my logging of min and max that will be passed as arguments to my IDchecker() function call.

Examples:

Instead of:
95-115

I pass:
95-99

Instead of:
998-1012

I pass:
1000-1012

It may not seem like much of an optimization.

But it was fun to work through and build.

And I bet it will shave off some time.

Maybe it will even come in handy for Part 2!

Next up, checking for invalid IDs.

Writing `IDchecker()`

function IDchecker(min, max) {
    let tally = 0
    while (min <= max) {
        // Break min in half
        let str = min.toString()
        let len = str.length
        let left = str.slice(0,len / 2)
        let right = str.slice(len / 2)
        // Are they equal? Invalid!
        if (left == right) {
            tally++
            min = +((+(left) + 1).toString() + (+(left) + 1).toString())
        } else if (+right < +left) {
            // If right half is less, make both left
            // Example: 2120 -> 21 20 -> Next invalid is 2121
            min = +(left + left)
        } else if (+left < +right) {
            // If left half is less, make both one greater than left
            // Example: 2034 -> 20 34 -> Next invalid is 2121
            min = +((+(left) + 1).toString() + (+(left) + 1).toString())
        }
    }
    return tally
}

There's some kind of gross code to convert strings to numbers and vice versa.

But overall this feels optimized to skip large ranges of numbers, straight to the next invalid ID.

Correcting for one last major oversight

Per the instructions:

Adding up all the invalid IDs in this example produces 1227775554

My algorithm currently just counts how many invalid IDs there are.

Oops!

Thankfully, it's a simple fix.

From this:

if (left == right) {
    tally++
    min = +((+(left) + 1).toString() + (+(left) + 1).toString())
}

To this:

if (left == right) {
    tally += min
    min = +((+(left) + 1).toString() + (+(left) + 1).toString())
}

Instead of incrementing tally by 1, I increment it by the amount of the invalid ID.

Testing on both inputs

When I run my program on the example input, I see the expected outputs:

Each invalid ID
No valid IDs
The correct sum

Now to run it on my input:

All sorts of invalid IDs
Seemingly no valid IDs
A sum in hundred-billions

Everything feels good enough to submit this answer.

...

It's the correct answer!

Woohoo!!!

I'm so happy all this work to optimize an otherwise brute-force number-checking algorithm paid off!

What twist might Part 2 present?!

Part 2

Feels like this just got exponentially harder

Wow. Looking back now, Part 1 feels easy:

If even digits, cut in half, adjust one half to match or exceed the other by one

But this? I feel like I'll have to employ several case-specific tactics to skip number ranges.

The best way to start is by diving in on an example.

Working through examples from my puzzle input by hand

The number range:

28750-44009

Using manual labor, it looks like invalid IDs are:

How did I deduce that?

The number's length is odd, can't split in half
The number's length is prime, so it can only be split into equal parts of single digits
The next number with equal digits is 33333
The next number exceeds the higher bounday number

That was some specific logic - odd, prime - but fairly straightforward.

The next range:

407363-480868

Using manual labor, it looks like invalid IDs are:

407407
408408
......
444444
445445
......
454454
......
454545
......
455455
......
464464
464646
......
465465
......

How did I deduce that?

Even number
Length: 6
Divisible by 6, 3 and 2
Can change up to the 10,000's place
Consider each next possible invalid id: 6 - 444444, 3 - 414141, 2 - 407407
Proceed with lowest option until surpassing next lowest option: 413413 -> X - 414414
Jump to the next lowest option: 414141
Consider each next possible invalid id: 6 - 444444, 3 - 424242, 2 - 414414
Proceed with lowest option until surpassing next lowest option: 423423 -> X - 424424
Jump to the next lowest option: 424242
Consider each next possible invalid id: 6 - 444444, 3 - 434343, 2 - 425425
Repeat last three steps until surpassing the maximum boundary

Wow, look at that: I missed a ton of invalid IDs!

Is optimization worth the headache?

Though this algorithm seems like it will skip a lot of numbers, it also seems like a nightmare to write.

The numbers in my input are of lengths 1-10.

I would need a dictionary to map length to divisibility.

Something like this that I could run on each number:

{
    // length of number: length of equal parts
    1: [1],
    2: [1],
    3: [1],
    4: [1, 2],
    5: [1],
    6: [1, 2, 3],
    7: [1],
    8: [1, 2, 4],
    9: [1, 3],
    10: [1, 2, 5]
}

That could be simpler if I remove prime number lengths:

{
    4: [1, 2],
    6: [1, 2, 3],
    8: [1, 2, 4],
    9: [1, 3],
    10: [1, 2, 5]
}

What else will I likely have to account for?

Determining whether and where to increment a portion of a number

That feels like a monumental, condition-based nightmare of a task.

All of this begs the question:

Why don't I just brute force this challenge?

In other words, just check every possible number.

That just feels so wasteful, especially when I see ranges like these:

2424167145-2424278200

That includes only one invalid ID:

2424242424

An optimized algorithm could help avoid processing 100k numbers!

There are a few similar ranges like this!

Or this:

9945560-9993116

That doesn't appear to include any invalid IDs on account of:

Seven digits
Can only split at single digit numbers
Only possible digit is 9
9999999 is out of range

Why include that if it doesn't contain an invalid ID for parts 1 or 2? Seems like I may be missing something.

Ugh, what a dilemna!

How many numbers will a brute force algorithm have to check?

I want to gauge performance.

input.split(',').reduce((sum, range) => {
    let [min, max] = range.split('-').map(Number)
    let checked = 0
    let curr = min
    while (curr <= max) {
        checked++
        curr++
    }
    return sum += checked
}, 0)

The answers I get:

Example input: 106
My puzzle input: ~1.7M

That's not bad at all.

I feel less afraid of building an every-number-checking algorithm now.

I just need to start coding

I think accounting for prime number lengths will be the easiest task to code for.

That's because I just have too split the stringified number and check whether every value matches the first.

Here's that code:

let part2 = input.split(',').reduce((sum, range) => {
    let [min, max] = range.split('-').map(Number)
    while (min <= max) {
        let str = min.toString()
        let len = str.length
        if (!(len in divisors)) {
            // prime number length
            if (str.split('').every(el => el == str[0])) {
                sum += min
            }
        } else {
            divisors[len].map(size => {
                // More complicated
            })
        }
        min++
    }
    return sum
}, 0)

Thankfully - and as expected - I see the correct numbers logged when I run my program.

Now for the more complex part: dividing into multiple portions.

I dove in head-first, then troubleshooted, and eventually arrived at this algorithm:

let part2 = Array.from(input.split(',').reduce((uniques, range) => {
    let [min, max] = range.split('-').map(Number)
    while (min <= max) {
        let str = min.toString()
        let len = str.length
        if (!(len in divisors) && len > 1) {
            // prime number length
            if (str.split('').every(el => el == str[0])) {
                console.log(min)
                uniques.add(min)
            }
        } else if (len in divisors && len > 1) {
            divisors[len].forEach(size => {
                // Build a nested array with groups of length 'size'
                let arr = []
                for (let i = 0; i < len; i += size) {
                    arr.push(str.slice(i, i + size))
                }
                // Check whether every item in a group is equal
                if (arr.every(el => el == arr[0])) {
                    console.log(min, arr)
                    uniques.add(min)
                }
            })
        }
        min++
    }
    return uniques
}, new Set())).reduce((a,b) => a + b)

Noteworthy snippets:

The reduce() returns a Set() of unique numbers
Since I need to further reduce() that Set(), I use Array.from() to spread the set's values out
The while loop has two branches: first process prime-number lengths, then process lengths with divisors greater than 1
Both branches require avoidance of single digit numbers
In the second branch, I turn the array of divisors mapped to the number's length into arrays of equal length strings, then compare each string for equality to the first string. Only if all strings match do I attempt to add the number to the unique set of invalid IDs
I need a Set() because for a number like 333333 I don't want to add it three times, once each for [3,3,3,3,3,3], [33,33,33] and [333,333]

Testing and celebrating

I ran it on my puzzle input twice.

The first time my answer was too high.

That's because I overlooked adding single-digit numbers.

The second time my answer was about 50 less.

And it was the correct answer!

Woohoo!!!

What a trip this challenge was.

I'm so glad I didn't attempt to optimize it.

That probably would have taken a ton more time and introduced loads of headaches.

What matters is I gave both parts my full brainpower, and came away with two gold stars!

This may have been my toughest Day 2 challenge yet out of all 10 years of AoC!

Can't wait to see what Day 3 has in store.

Please no shortest path nonsense. Not yet, at least.

Secret Entrance

Robert Mion — Fri, 16 Jan 2026 19:09:28 +0000

Advent of Code 2025 Day 1

Part 1

Round and round we go!

Let's dive straight in to this one.

The challenge models a number line from 0 to 99 - 100 numbers.

Moving past 0 - to the left - should be equivalent to looping back to 99 and counting down.

The example given is:
L5 from 0 lands you on 95

How might I accomplish that with computer code?

Well:

0 - 5 is -5
If the number is negative...
Calculate 100 minus the absolute value of that number
So, 100 - (+5) or 100 - 5 or 95

Another example is:
R5 from 99 lands you on 4

How might I accomplish that with computer code?

Well:

99 + 5 is 104
If the number is greater than 100...
Calculate the number modulo 100 - dividing the number by 100 and keeping the remainder
So, 104 % 100 is 4

An example of a large rotation from my input is:
L888 from, say, 42, lands you on 54

How might I accomplish that with computer code?

Well:

A combination of both techniques above
First performing the modulo on 888 to get: 88 - each additional 100 rotations will result in the same landing spot
Calculating 42 - 88 as -46
Calculating 100 - (+46) as 54

I can use the modulo technique any time the rotation is greater than 99.

I'm ready to turn all this logic into working computer code.

Writing my algorithm

Setting up variables:

input = input.split('\n')
let cursor = 50
let password = 0

Parsing each instruction:

input.forEach(rotation => {
    let dir = rotation[0]
    let amt = +rotation.slice(1) % 100
})

Writing the conditional logic:

input.forEach(rotation => {
    let dir = rotation[0]
    let amt = +rotation.slice(1) % 100
    switch (dir) {
        case "R":
            cursor = (cursor + amt) % 100
            break;
        case "L":
            cursor = (cursor - amt < 0) ? 100 - Math.abs(cursor - amt) : cursor - amt
            break;
    }
    if (cursor == 0) {
        password++
    }
})

I forgot about the use case of a L instruction that doesn't result in a negative number.

That took a few minutes of debugging, and resulted in the ternary operation shown above.

After testing on the example input, it works as expected.

Will it work correctly on my puzzle input, though?

Testing on my puzzle input

Running...

Submitting...

Correct!

Woohoo!!!

Part 2

Of course, now number of rotations is critical

I now am forced to care about the numbers I was modulo-ing away in Part 1.

Use cases I have to identify:

An R instruction that passes 99
An L instruction that passes 0
Any instructions greater than 99
Instructions perfectly divisible by 100 when the cursor is 0

Updating my algorithm

I went straight to it.

Here's what I wrote:

input.forEach(rotation => {
    let dir = rotation[0]
    let amt = +rotation.slice(1)

    if (amt.toString().length > 2) {
        let temp = amt.toString()
        password += +temp.slice(0, amt.length - 2)
        amt = amt % 100
    }
    let next
    switch (dir) {
        case "R":
            next = (cursor + amt) % 100
            if (next < cursor) {
                password++
            }
            cursor = next
            break;
        case "L":
            next = (cursor - amt < 0) ? 100 - Math.abs(cursor - amt) : cursor - amt
            if (next > cursor) {
                password++
            }
            cursor = next
            break;
    }
})

First, I handle rotation amounts over 99
Then, in each case, I determine where the cursor will end up, and update the password if it has crossed 0

Testing my algorithm

It generates the correct answer for the example puzzle input.

It generates an answer that is twice what I Part 1 answer was. That seems low.

Still, it could be right.

Submitting...

Wrong answer. Too low.

Am I overthinking things?

Upon inspecting my input:

Nearly 800 instructions rotate the cursor more than 100 notches, meaning at least pass across 0
No rotations of 0 notches, which could have been an edge case I didn't account for
No rotations that are perfectly divisible by 100, which I think my code still accounts for

So, I have two sets of instructions:

A number less than 100 resulting in 0-1 passes across 0
A number greater than 100 resulting in 1+ passes across 0

Time to re-think and step through my algorithm.

Fixing my mistakes one by one

Wrong condition logic
Wrong variable used
Missing part of condition

Man, I really overlooked some critical details.

Thankfully, the example input helped me see my final glaring error.

Alas, this is the algorithm that allowed me to generate the correct answer:

input.forEach(rotation => {
    let dir = rotation[0]
    let amt = +rotation.slice(1)

    if (amt.toString().length > 2) {
        let temp = amt.toString()
        password += +temp.slice(0, amt.toString().length - 2)
        amt = amt % 100
    }
    let next
    switch (dir) {
        case "R":
            next = cursor + amt
            if (next >= 100) {
                password++
            }
            cursor = (next >= 100) ? next - 100 : next
            break;
        case "L":
            next = cursor - amt
            if (cursor > 0 && next <= 0) {
                password++
            }
            cursor = (next < 0) ? 100 - Math.abs(cursor - amt) : next
            break;
    }
})

I correctly increment the password for each hundred in large instructions
For L rotations, I correctly only increment password when the cursor is at a position higher than 0
For L rotations, I correctly update the cursor's value when it crosses 0

This was the most I've had to troubleshoot a Day 1 Part 2 algorithm.

I have only myself to blame. I simply overlooked a lot of important subtleties.

Thankfully, I come away with two gold stars!

The year is off to a great start!

Code Chronicle

Robert Mion — Sun, 21 Dec 2025 17:51:40 +0000

Advent of Code 2024 Day 25

Part 1

A cool way to end the year

This seems like a fun challenge. And one I am excited to attempt.

The first thing I notice is:

The example input separates locks and keys
My puzzle input does not

So, my algorithm will need to be extra attentive when classifying them.

As per the explanation, I intend to store each lock and key as an array of numbers representing each column height.

Maybe from there I can write an algorithm that does this:

For each lock
  For each column
    Further filter the list of keys to those with 5 - N height
    in this column, where N is the lock column's height
  Any remaining keys are winners

That seems like it could work.

I'm excited to try coding it!

Writing my lock-key matching algorithm

Processing the input into two lists that each contain 5-digit lists:

input = input.split('\n\n').reduce((group, item) => {
    item = item.split('\n').map(line => line.split(''))
    if (item[0].every(el => el == '#')) {
        // Lock
        let digits = []
        for (let i = 0; i < 5; i++) {
            let tally = 0
            while (item[tally + 1][i] == "#") {
                tally++
            }
            digits.push(tally)
        }
        group[0].push(digits)
    } else if (item[0].every(el => el == '.')) {
        // Key
        let digits = []
        for (let i = 0; i < 5; i++) {
            let tally = 0
            while (item[5 - tally][i] == "#") {
                tally++
            }
            digits.push(tally)
        }
        group[1].push(digits)
    }
    return group
}, [[],[]])

I'm proud of both for and nested while loops that walk down and up each column to determine the height.

As expected, my reduce generates two lists, each one containing 5-digit arrays:

[ [ 0, 5, 3, 4, 3 ], [ 1, 2, 0, 5, 3 ] ] 
[ [ 5, 0, 2, 1, 3 ], [ 4, 3, 4, 0, 2 ], [ 3, 0, 2, 0, 1 ] ]

Now for the fun part: matching keys with locks.

Comparing most keys to every lock

I have a list of locks and a list of keys.

What I intend to do:

For each lock
  Further filter the list of keys
  Based on the number in each column
  Until only keys that fit the lock remain
  Increment a running tally of valid keys

That should get me the correct answer for Part 1.

It would certainly work to get the correct answer for the example input.

Now, to write the algorithm as code:

let tally = 0
locks.forEach(lock => {
    tally += lock.reduce((keysRemaining, digit, index) => {
        return keysRemaining.filter(item => item[index] <= 5 - digit)
    }, keys.map(el => el.slice())).length
})

Could it really be that simple?

Here's what I'm doing:

Initialize a value to count all valid keys
Iterate through each lock
Increment the tally based on how long the final list of keys is after filtering it five times - once for each digit

When running it on the example input, I get 3, the correct answer.

I'm tempted to just run it on my puzzle input.

Worst case, I get a wrong submission and only have 3 more attempts to point me in the right direction.

I'm gonna do it!

Running on my puzzle input

What will it output?

...

A number in the low thousands.

Seems...right?

Time to submit.

...

It was correct!

Woohoo!!!

Year in review

I matched my lowest score in a year: 34.

Given that this year seemed like the hardest one, I'm very proud I didn't set a new lowest score.

As for all time scores:

382/500 is 76.4% or a strong C.

That's been my average this entire journey thus far.

This was another real fun year with interesting new puzzles.

Up next, 2025!

Thanks again for reading.

Crossed Wires

Robert Mion — Sat, 20 Dec 2025 01:53:10 +0000

Advent of Code 2024 Day 24

Part 1

Hurry up and wait...and see

This feels like a queue-themed challenge:

Establish values
Generate an inventory of processable steps
Execute steps
Repeat until inventory is complete

I'm concerned there's something in the rules that I may miss or not fully understand.

Hopefully stepping through the first example will be enough to gain confidence to write an algorithm.

Understanding how to architect the example input

Here it is again:

x00: 1
x01: 1
x02: 1
y00: 0
y01: 1
y02: 0

x00 AND y00 -> z00
x01 XOR y01 -> z01
x02 OR y02 -> z02

I can imagine a dictionary to store the initial values:

{
  x00: 1,
  x01: 1,
  x02: 1,
  y00: 0,
  y01: 1,
  y02: 0
}

Then each gate needs some id other than its type, but needs to store it's type, inputs and output.

Hmmm...

[
  {
    'type': 'AND',
    'inputs': ['x00', 'y00'],
    'output': 'z00',
    'done': false
  },
  {
    'type': 'XOR',
    'inputs': ['x01', 'y01'],
    'output': 'z01',
    'done': false
  },
  {
    'type': 'OR',
    'inputs': ['x02', 'y02'],
    'output': 'z02',
    'done': false
  }
]

That might work. It at least seems to have all pertinent information about a gate, and the index serves as a unique id.

Oh, and I will need to store and know the values of all output gates that didn't get initial values:

{
  x00: 1,
  x01: 1,
  x02: 1,
  y00: 0,
  y01: 1,
  y02: 0,
  z00: null,
  z01: null,
  z02: null
}

Understanding how to process the example input's gates

If I think of this task as repeatedly checking the entire list of gates for only the ones whose inputs have values:

For each gate
  If both inputs have values
    Add to the list

Out of the three, all gates' inputs have values.

So, the list will have all gates:

[0, 1, 2]

I can iterate through each, process the inputs, save the value in the output, and mark them as done.

z00 gets 0 because 1 AND 0 is 0
z01 gets 0 because 1 XOR 1 is 0
z02 gets 1 because 1 OR 0 is 1

I think I understand.

I hope I understand.

I'm ready to code.

Turning puzzle input into a state machine

I plan to generate a dictionary and an array of dictionaries.

First, the dictionary of given initial values:

let [values, gates] = input.split('\n\n')
values = values.split('\n').reduce((obj, item) => {
    let [name, value] = item.split(': ')
    obj[name] = +value
    return obj
}, {})

As expected, I see this as output:

{ x00: 1, x01: 1, x02: 1, y00: 0, y01: 1, y02: 0 }

Next, the list of dictionaries filled with each gate's parameters:

gates = gates.split('\n').reduce((list, gate) => {
    let [input1, bool, input2, , output] = gate.split(' ')
    if (!(output in values)) {
        values[output] = null
    }
    list.push({
        'type': bool,
        'inputs': [input1, input2],
        'output': output,
        'done': false
    })
    return list
}, [])

This creates the list of objects and updates the list of values to include the uninitialized values - most or all starting with z.

And I see the expected output:

[
  { type: 'AND', inputs: [ 'x00', 'y00' ], output: 'z00', done: false },
  { type: 'XOR', inputs: [ 'x01', 'y01' ], output: 'z01', done: false },
  { type: 'OR', inputs: [ 'x02', 'y02' ], output: 'z02', done: false }
]

Next, I need to make functions for each of the three booleans:

function AND (a, b) {
    if (a == 1 && b == 1) {
        return 1
    } else if (a == 0 || b == 0) {
        return 0
    }
}
function OR (a, b) {
    if (a == 1 || b == 1) {
        return 1
    } else if (a == 0 && b == 0) {
        return 0
    }
}
function XOR (a, b) {
    if (a !== b) {
        return 1
    } else if (a == b) {
        return 0
    }
}

Pretty straightforward, though maybe not concise. Still, very readable!

Time to start putting this all together with a loop and a queue.

The harder part: processing each set of ready gates

A gate only processes its inputs when both have a value.

The way it seems, only a few gates will have values at first. Then, as more outputs get values, more gates will become ready to process.

I need to write an algorithm that filters the full list for:

gates that are not done as per my object's property
gates whose inputs both have a non-null value

Then processes each gate's boolean and sets the output's value.

Seems straightforward.

Here I go!

let gatesRemaining = gates.length
while (gatesRemaining > 0) {
    gates.forEach(
      gate => {
        if (!gate.done) {
            if (
                 typeof values[gate.inputs[0]] == 'number' && 
                 typeof values[gate.inputs[1]] == 'number') 
            {
                values[gate.output] = eval(
                   `${gate.type}(values['${gate.inputs[0]}'],
                                 values['${gate.inputs[1]}'])`
                )
                gate.done = true
                gatesRemaining--
            }
        }
      }
    )
}

The eval is a bit gross, but it does the job of calling the correct boolean function with the two inputs.

After a bit of debugging my sloppy array accessor syntax, I see the expected result:

values being added correctly
a counter decrementing correctly
a program ending thanks to a counter reaching 0

Time to check on the larger example input.

It works!

Piecing together the decimal

At least for the examples, I have the right keys with the right values.

Now I need to extract just the z-starting keys, put them in order with the values, and join the values to get the decimal.

This may be the toughest part!

Well, not toughest, but definitely a long statement:

let decimal = parseInt(
  Object.keys(values).filter(
    el => el[0].indexOf('z') == 0
  ).sort().reverse().map(el => values[el]).join(''), 
  2
)

Make a list of the key names in my dictionary of values
Keep only the ones starting with z
Sort them alphabetically
Reverse their order
Replace each one with that key's associated value
Join them all into a string of 1s and 0s
Convert that binary string into a decimal

It works!

I see 2024 in my output!

Now, do I think it will work on my puzzle input?

Fingers are tightly crossed.

Although I'm fully expecting it to never terminate or generate an error for something I overlooked.

Time to find out...

Running my algorithm on my puzzle input

...

Wow! It ran and finished instantly!

And it output a big 'ol number!

And it was the correct answer!

Woohoo!!!

I'm so proud of myself for earning these gold stars on days above 20.

Ok, time to see what Part 2 demands.

Part 2

Confusion and intimidation

There's a lot more explanation here.

A lot about binary numbers.

And swapping.

And...more.

I'm confused.

And knowing how large my puzzle input is, I'm fully intimidated to even attempt understanding and coding anything.

So, I sadly bid today farewell without attempting Part 2.

It's a bummer, but my head hurts just reading each short paragraph in this additional explanation.

One gold star earned. Good riddance, Day 24.

LAN Party

Robert Mion — Fri, 19 Dec 2025 00:29:52 +0000

Advent of Code 2024 Day 23

Part 1

An exercise in triangle classification

It seems the challenge is to find every instance where three computers are connected via two shared edges each:

 A
 |\
 | \
 |  \
 B---C

So, a triangle! In this case, the edges are:

A-B
B-C
C-A

For something that simple, how could I write an algorthm that knows those three edges comprise a triangle?

Walking through a possible algorithm

First line:

A-B

A connects to B, and vice versa:

{
    'A': ['B'],
    'B': ['A']
}

Second line:

B-C

B connects to C, and vice versa:

{
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B']
}

Third line:

C-A

C connects to A, and vice versa:

{
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['B', 'A']
}

How would an algorithm know it has a triangle?

Three keys where each key contains both of the other two

Although, I know that with A: B I have B: A.

I just need to determine whether C has C: B and C: A.

Well, really just C: B.

Wow, this may be real simple:

A has B and C
That's two edges
I just need to confirm the remaining edge
Does C have B?
If so, triangle!

Maybe this is my algorithm:

For each key, A
  For each connected key, B
    For each remaining key, Y
      If the remaining key connects to B
        Triangle!

It's a ton of loops, which isn't great.

But at least I only perform one look-up.

And for this first part, I only have to run these loops on the nodes with a t in them.

So, hopefully, this runs fairly quickly, even on an input with a list of a few thousand connections.

Time to write the actual algorithm.

Writing actual code

I wrote the dictionary-building portion all at once instead of in pieces.

Here's the full statement:

let nodes = input.split('\n').reduce((obj, node) => {
    let PCs = node.split('-')
    PCs.forEach((pc, i) => {
        if (!(pc in obj)) {
            obj[pc] = []
        }
        obj[pc].push(PCs[1 - i])
    })
    return obj
}, {})

The code explained:

Use reduce to build an object
Iterate through each line of input
Split each line at the - character to get both computers
Create a key if it doesn't already exist
Add the other computer to the list of connections

Thankfully, when run on the example input, I see my expected output:

{
  kh: [ 'tc', 'qp', 'ub', 'ta' ],
  tc: [ 'kh', 'wh', 'td', 'co' ],
  qp: [ 'kh', 'ub', 'td', 'wh' ],
  de: [ 'cg', 'co', 'ta', 'ka' ],
  cg: [ 'de', 'tb', 'yn', 'aq' ],
  ka: [ 'co', 'tb', 'ta', 'de' ],
  co: [ 'ka', 'ta', 'de', 'tc' ],
  yn: [ 'aq', 'cg', 'wh', 'td' ],
  aq: [ 'yn', 'vc', 'cg', 'wq' ],
  ub: [ 'qp', 'kh', 'wq', 'vc' ],
  tb: [ 'cg', 'ka', 'wq', 'vc' ],
  vc: [ 'aq', 'ub', 'wq', 'tb' ],
  wh: [ 'tc', 'td', 'yn', 'qp' ],
  ta: [ 'co', 'ka', 'de', 'kh' ],
  td: [ 'tc', 'wh', 'qp', 'yn' ],
  wq: [ 'tb', 'ub', 'aq', 'vc' ]
}

Next, I only want to search for triangles among the t-containing computer names:

let tNames = Object.keys(nodes).filter(el => el.indexOf('t') !== -1)

Thankfully, that correctly flags the example input's four target computers:

[ 'tc', 'tb', 'ta', 'td' ]

Next, I want to iterate through each of these target computers' connection lists to find triangles:

let triangles = tNames.reduce((sets, pc) => {
    for (let a = 0; a < nodes[pc].length - 1; a++) {
        for (let b = 1; b < nodes[pc].length; b++) {
            if (nodes[nodes[pc][b]].includes(nodes[pc][a])) {
                sets.push([pc, nodes[pc][a], nodes[pc][b]])
            }
        }
    }
    return sets
}, [])

This took a bit of debugging on account of me messing up all the array accessor syntax.

But I eventually got it working as expected, and generated this output list:

[
  [ 'tc', 'wh', 'td' ],
  [ 'tc', 'td', 'wh' ],
  [ 'tb', 'wq', 'vc' ],
  [ 'ta', 'co', 'ka' ],
  [ 'ta', 'co', 'de' ],
  [ 'ta', 'ka', 'de' ],
  [ 'ta', 'de', 'ka' ],
  [ 'td', 'tc', 'wh' ],
  [ 'td', 'wh', 'qp' ],
  [ 'td', 'wh', 'yn' ],
  [ 'td', 'qp', 'wh' ]
]

Can you spot the issue with this list?

Spoiler: it contains duplicates.

How can I resolve that?

I can sort the list alphabetically
And use a Set() instead of an array
That way it only adds unique values

Let's try!

if (nodes[nodes[pc][b]].includes(nodes[pc][a])) {
    set.add([pc, nodes[pc][a], nodes[pc][b]].sort().join(','))
}

That did the trick! Now my output is the correct items and length:

{
  'tc,td,wh',
  'tb,vc,wq',
  'co,ka,ta',
  'co,de,ta',
  'de,ka,ta',
  'qp,td,wh',
  'td,wh,yn'
}

Is my algorthm ready to take on my puzzle input?

Only one way to find out.

Running my algorithm on my puzzle input

Fingers crossed this works!

...

Oops, one small but major mistake:

My algorithm targets computers with a t anywhere in their name
But I need to target computers that start with a t

Small fix:

let tNames = Object.keys(nodes).filter(el => el.indexOf('t') == 0)

Running again...

...

The results in my output look more promising.

And my count is just under half of the input list.

This could be a winning number.

It's worth a failed submission attempt to see if it's the correct answer.

...

It is the correct answer!

Woohoo!!!

I'm so glad I was able to solve this part with a simple and performant algorithm.

Now, what wrench could Part 2 throw my way?

Part 2

Surprse, surprise

Find the largest interconnect network of computers.

Not a huge twist.

But certainly a huge task.

For me, at least.

I don't know how I would attempt to solve this besides brute force.

And that makes me feel the urge to just skip it.

Take my one well-earned gold star and move along.

That's what I'm gonna do.

Fun Part 1, though!

Monkey Market

Robert Mion — Sun, 07 Dec 2025 18:09:18 +0000

Advent of Code 2024 Day 22

Part 1

Another math gauntlet

I get to program a bunch of math operations.

Some will be part of several conditionals.

I've done it before. I'm confident I can do it again.

One step - and sentence - at a time.

A slow burn of programming

My input is a list of integers, like this example:

I know I'll have to extract each one from my input string:

let buyers = input.split('\n').map(Number)

Then, for each buyer, I'll have to process the next 2000 secret numbers, and calculate the sum of them all:

let answer = buyers.reduce((sum, buyer) => {
  // determine the next 2000 secret numbers
  // sum += 2000th secret number
  return sum
}, 0)

Mixing and Pruning functions

First, Mixing:

Calculate the bitwise XOR or two numbers and use the result

In javascript the XOR operator is a ^:

42 ^ 15 // 37

My function should expect two arguments and return the result:

function mix (secret, value) { return secret ^ value }

Next, Pruning:

Calculate the value of the secret number modulo 16777216 and use the result

In javascript the modulo operator is a %:

8 % 3 // 2 (3 goes into 8 two times, leaving a remainder of 2)

My function should expect one argument and return the result:

function prune (secret) { return secret % 16777216 }

The sequence of three calculations

Calculate the result of multiplying the secret number by 64. Then, mix this result into the secret number. Finally, prune the secret number.

buyer = prune(mix(buyer, buyer * 64))

Calculate the result of dividing the secret number by 32. Round the result down to the nearest integer. Then, mix this result into the secret number. Finally, prune the secret number.

buyer = prune(mix(buyer, Math.floor(buyer / 32)))

Calculate the result of multiplying the secret number by 2048. Then, mix this result into the secret number. Finally, prune the secret number.

buyer = prune(mix(buyer, buyer * 2048))

Do it 2000 times

for (let i = 0; i < 2000; i++ {
  // all three statements above
}

Altogether

Here's my untested algorithm:

let buyers = input.split('\n').map(Number)
function mix (secret, value) { return secret ^ value }
function prune (secret) { return secret % 16777216 }
let answer = buyers.reduce((sum, buyer) => {
  for (let i = 0; i < 2000; i++) {
    buyer = prune(mix(buyer, buyer * 64))
    buyer = prune(mix(buyer, Math.floor(buyer / 32)))
    buyer = prune(mix(buyer, buyer * 2048))
  }
  sum += buyer
  return sum
}, 0)

First test

I added logging statements to show the first and what I assume is the 2000th secret number.

Pressing run...

...and I'm getting some negative 2000th secret numbers.

I messed something up

Debugging

First, I made a function to store my three calculations:

function regen(buyer) {
    buyer = prune(mix(buyer, buyer * 64))
    buyer = prune(mix(buyer, Math.floor(buyer / 32)))
    buyer = prune(mix(buyer, buyer * 2048))
    return buyer
}

Then, I made a single test case and a shorter loop:

let sample = 123
for (let i = 0; i < 10; i++) {
    console.log(sample)
    sample = regen(sample)
}

I need to be sure I'm seeing the same 10 next secret numbers as per the example:

Hmm. The four negative values are incorrect, but everything else is correct.

What's going wrong? What's going right?

Why am I even seeing negative numbers?

Walking through the first three generated secret numbers

123
123 * 64 -> 7872
123 ^ 7872 -> 7867
7867 % 16777216 -> 7867
Math.floor(7867 / 32) -> 245
7867 ^ 245 -> 7758
7758 % 16777216 -> 7758
7758 * 2048 -> 15888384
7758 ^ 15888384 -> 15887950
15887950 % 16777216 -> 15887950

15887950
15887950 * 64 -> 1016828800
15887950 ^ 1016828800 -> 1013579214
1013579214 % 16777216 -> 6946254
Math.floor(6946254 / 32) -> 217070
6946254 ^ 217070 -> 6992416
6992416 % 16777216 -> 6992416
6992416 * 2048 -> 14320467968
6992416 ^ 14320467968 -> 1442558496
1442558496 % 16777216 -> 16495136

16495136
16495136 * 64 -> 1055688704
16495136 ^ 1055688704 -> 1041709600
1041709600 % 16777216 -> 1522208
Math.floor(1522208 / 32) -> 47569
1522208 ^ 47569 -> 1541105
1541105 % 16777216 -> 1541105
1541105 * 2048 -> 3156183040
1541105 ^ 3156183040 -> -1140323343
-1140323343 % 16777216 -> -16249871

-16249871 WRONG

I see where it's becoming a negative number.

But I'm still not sure how to get the correct next secret number.

Studying integers and bitwise operations

bitwise operations in JavaScript work on 32-bit signed integers
The largest integer is 2,147,483,647
The integer I am attempting to operate on is 3,156,183,040
That's a much larger number
To operate on it with bitwise operators in JavaScript, I have to use the BigInt data type instead of the Number data type

When I try to execute this code:

let big = BigInt("1541105")
let big2 = BigInt("3156183040")
let result = big ^ big2

I get this integer instead of the negative integer:
3154643953

And when I calculate:

3154643953 % 16777216

I get the correct next secret number:
527345

Wow, what a fun adventure to discover the error in my code!

Now, how can I fix my program to work with BigInts?

Until the errors stop...eventually?

Wrap each integer with BigInt().

That should work, right?

Yes, but there's still the use of Math.floor().

That's a Number data type function. Can't use it on BigInts.

Turns out that's not even necessary. BigInts will only ever be integers.

Cool!

My latest program

let buyers = input.split('\n').map(BigInt)
function mix (secret, value) { return BigInt(secret ^ value) }
function prune (secret) { return BigInt(secret % BigInt(16777216)) }
function regen(buyer) {
    buyer = prune(mix(buyer, BigInt(buyer * BigInt(64))))
    buyer = prune(mix(buyer, BigInt(buyer / BigInt(32))))
    buyer = prune(mix(buyer, BigInt(buyer * BigInt(2048))))
    return buyer
}
let answer = buyers.reduce((sum, buyer) => {
  for (let i = 0; i < 2000; i++) {
    buyer = regen(buyer)
  }
  sum += buyer
  return sum
}, BigInt(0))

Anything and everything are BigInts.

But guess what...

...it works!

I generate the correct next 10 secret numbers for 123
I generate the correct 2000th secret number for all four other example secret numbers

I think my algorithm is finally working as intended.

Testing on my puzzle input

I hope it generates the correct answer.

If not, I am out of ideas to debug my program.

Here goes nothing...

...

I got the correct answer!

Woohoo!!!

I'm almost certain Part 2 will up the target secret number to something in the billions or trillions.

That will require the puzzler to determine a pattern that is inherit to the calculations.

If so, I may be throwing the towel in quickly.

Time to find out...

Part 2

Not at all what I expected

Instead, it's a much more interesting twist:

Find the four-integer sequence of numbers -9 thru 9
That optimizes for the amount of bananas sold by all monkey buyers in my input

If I were to brute-force this, I would write an algorithm that:

For each combination of four integers
  For each monkey buyer's secret number
    Process as many secret numbers, up to 2000
      Stop if the combination occurs
        Add the price to a running total

How many operations would that generate in a worst-case scenario?

Possible 4-digit combinations: 
(-9 thru 9, four times)
19 * 19 * 19 * 19
----
130k

Monkey buyers:
2002 in my puzzle input
130k * 2002
----
261M

2000 secret numbers for each buyer:
261M * 2000
----
522B

Yikes! That's a lot of processing.

There's most certainly a smarter way to arrive at the correct answer.

But I don't know what it could be.

And I'm satisfied with my single gold star.

So, it's off to the next day's challenge for me.

Keypad Conundrum

Robert Mion — Mon, 01 Dec 2025 21:09:42 +0000

For a few puzzles in this series, I opted to attempt solving them manually. That means I used some means other than writing a program to discover the correct answer. It's obviously not the intended way. But I loved the puzzle - and lacked the necessary computer science skills - so much that I felt joy nonetheless.

This feels like another one of those puzzles, because:

I can explain how to come upon the solution
Doing the work by hand doesn't feel too daunting
Especially since the sandbox is two arrangements of 10 and 5 symbol groups

This one, unlike yesterday's puzzle, is worth attempting.

Confirming my understanding of how to solve

The instructions play out this example keycode: 029A

First, I must figure out the fewest moves to make the robot press those buttons:
<A^A>^^AvvvA

That's 12 commands. Four activate button presses.

Next, I must figure out the fewest moves to make the next robot execute each of those commands:
v<<A>>^A<A>AvA<^AA>A<vAAA>^A

That's 28 commands. 12 activate button presses.

Lastly, I must figure out the fewest moves to make the third robot execute each of those commands:
<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A

That's over twice as many commands. 28 activate button presses.

The trick is in locating the correct shortest path:

There will be multiple for each robot
But for the more distant robot, one of the closer robot's paths will prove faster to traverse on the directional keypad based on the arrangement of moves

So, while >^> is equally as short as ^>> and >>^, having the next distant robot give instructions to execute each of those will result in varying length paths - the ones with repeat directions require fewer movement commands.

First full walkthrough attempt

I'll use the second example, 980A, and try to manually arrive at the shortest path:
<v<A>>^AAAvA^A<vA<AA>>^AvAA<^A>A<v<A>A>^AAAvA<^A>A<vA>^A<A>A

For the first robot, it's a counter-clockwise rectangle:
^^^A<AvvvA>A

That's 12 commands. I can't think of a shorter path.

Next, the robot that must command the first one to execute each of those 12 commands:
<AAA>Av<<A>>^Av<AAA^>AvA^A

That's 26 commands. 12 activate button presses.

I used the path with the most repeat commands.

Finally, the robot that must command the second one to execute each of those 26 commands:
v<<A>>^AAAvA^Av<A<AA>>^AvAA<^A>Av<A<A>>^AAA<Av>A^Av<A>^A<A>A

That 60 commands. 26 activate button presses.

Below, I'll copy-paste the path from the example, then mine again:
<v<A>>^AAAvA^A<vA<AA>>^AvAA<^A>A<v<A>A>^AAAvA<^A>A<vA>^A<A>A
v<<A>>^AAAvA^Av<A<AA>>^AvAA<^A>Av<A<A>>^AAA<Av>A^Av<A>^A<A>A

Well, they are both the same length. And largely similar.

Second full walkthrough attempt

Now for the code 179A.

First robot's instructions:
^<<A^^A>>AvvvA

14 commands.

Second robot's instructions:
<Av<AA>>^A<AA>AvAA^Av<AAA>^A

14 activation button presses. 29 commands.

Third robot's instructions:
v<<A>>^Av<A<AA>>^AAvAA^<A>Av<<A>>^AAvA^AV<A>^AA<A>AV<A<A>>^AAAvA<^A>A

Comparing my path to the one in the instructions:

Mine:
v<<A>>^Av<A<AA>>^AAvAA^<A>Av<<A>>^AAvA^Av<A>^AA<A>Av<A<A>>^AAAvA<^A>A
Authors:
<v<A>>^A<vA<A>>^AAvAA<^A>A<v<A>>^AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A

Huh. One less than mine.

Only 28 commands. One less than mine.

How?

I have to walk the author's path backward:
<Av<AA>>^A<AA>AvAA^A<vAAA>^A

28 commands.

Walking that back:
^<<A^^A>>AvvvA

14 commands.

Comparing to mine:

Mine:
^<<A^^A>>AvvvA

Authors:
^<<A^^A>>AvvvA

Identical!

So, what about the 28-command one?

Mine:
<Av<<AA>>^A<AA>AvAA^Av<AAA>^A

Authors:
<Av<AA>>^A<AA>AvAA^A<vAAA>^A

Wow. A typo. I mistakenly added an extra < at the 5th spot.

Well, good news is I got it right. Bad news is I have to be careful when transcribing.

Third full walkthrough

Next code is 456A.

Paths:

^^<<A>A>AvvA
<AAv<AA>>^AvA^AvA^Av<AA>^A
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^A<A>Av<A>^A<A>Av<A<A>>^AAvA<^A>A

Comparing mine and the authors:

Mine:
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^A<A>Av<A>^A<A>Av<A<A>>^AAvA<^A>A

Authors:
<v<A>>^AA<vA<A>>^AAvAA<^A>A<vA>^A<A>A<vA>^A<A>A<v<A>A>^AAvA<^A>A

Same length! Woohoo!

Fourth full walkthrough

Last example code is 379A.

Paths:

^A^^<<A>>AvvvA
<A>A<AAv<AA>>^ AvAA^Av<AAA>^A
v<<A>>^AvA^Av<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<A<A>>^AAAvA<^A>A

Comparing mine and the authors:

Mine:
v<<A>>^AvA^Av<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<A<A>>^AAAvA<^A>A

Authors:
<v<A>>^AvA^A<vA<AA>>^AAvA<^A>AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A

Wow. Mine has four steps extra.

Could that be due to going up then left from 3 to 7, instead of going left then up?

Only one way - for me, lacking sufficient CS skills - to find out!

Paths:

^A<<^^A>>AvvvA
<A>Av<<AA>^AA>AvAA^Av<AAA>^A
v<<A>>^AvA^Av<A<AA>>^AAvA^<A>AAvA^Av<A>^AA<A>Av<A<A>>^AAAvA^<A>A

Comparing mine and the authors:

Mine:
v<<A>>^AvA^Av<A<AA>>^AAvA^<A>AAvA^Av<A>^AA<A>Av<A<A>>^AAAvA^<A>A

Authors:
<v<A>>^AvA^A<vA<AA>>^AAvA<^A>AAvA^A<vA>^AA<A>A<v<A>A>^AAAvA<^A>A

Yup, that was it.

Maybe it has to do with putting the ^ and A closer to one another?

I'm not entirely sure. But it seems like a good strategy.

Inspecting my input codes

These are my five codes:

985A
540A
463A
671A
382A

Considering the shortest path based on the strategies I learned from walking through the examples:

Rectangle
Tricky
Similar to 456A
Seems obvious
Tricky

Hmm. 2 and 5 have me re-thinking walking through all five only to come out wrong.

It's worth a try, right?

First straight-forward code: `985A`

Paths:

^^^A<AvAvv>A
<AAA>Av<<A>>^Av<A>^Av<AA>A^A
v<<A>^^AAAvA^Av<A<AA>>^AvAA^<A>Av<A<A>>^AvA^<A>Av<A<A>>^AAvA^A<A>A

^^^A<AvA>vvA
<AAA>Av<<A>>^Av<A>^AvA<AA>^A
v<<A>^^AAAvA^Av<A<AA>>^AvAA^<A>Av<A<A>>^AvA^<A>Av<A^>Av<<A>>^AAvA^<A>A

I walked through two paths, where the only difference was how it goes from the 5 to the A: go right first or last?

Turns out that going right last can save four steps!

Hopefully the shorter of my two paths is one of the shortest paths for that code.

Second straight-forward code: `463A`

Paths:

^^<<A>>AvAvA
<AAv<AA>>^AvAA^Av<A^>Av<A^>A
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<A<A>>^A<Av>A^Av<A<A>>^A<Av>A^A

<AAv<AA>>^AvAA^A<vA^>A<vA^>A
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<<A>A>^A<Av>A^Av<<A>A>^A<Av>A^A

I walked two paths again, one being a very minor variant of the other. Both paths ended up being the same length.

Third code: `671A`

Paths:

^^A   <<^A       vvA     >>vA
<AA>A v<<AA>^A>A v<AA^>A vAA<A^>A
v<<A>>^AAvA^A v<A<AA>>^AAvA^<A>AvA^A v<A<A>>^AA<Av>A^A v<A^>AAv<<A>>^A<Av>A^A

      ^<<A
      <Av<AA>>^A
              v<<A>>^Av<A<A>>^AAvAA^<A>A

Again, I explored one path and one variant of part of that path.

The pattern is emerging: avoid <A as much as possible. That makes sense.

Fourth code: `382A`

Paths:

^A   <^^A       vvA     v>A
<A>A v<<A>^AA>A <vAA^>A <vA>A^A
v<<A>>^AvA^A v<A<AA>>^AvA^<A>AAvA^A v<<A>A>^AA<Av>A^A v<<A>A>^AvA^A<A>A

     ^^<A               >vA
     <AAv<A>>^A         vA<A>^A
             v<<A>>^AAv<A<A>>^AvAA^<A>A v<<A>A>^AA<Av>A^A v<A>^Av<<A>>^AVA^<A>A

This time I explored two variants of a single path. Each variant was longer because it featured an extra <A.

Fifth code: `540A`

Paths:

<^^A <A >vvA >A
v<<A>^AA>A v<<A>>^A vA<AA>^A vA^A
v<A<AA>>^AvA^<A>AAvA^A v<A<AA>>^AvAA^<A>A v<A>^Av<<A>>^AAvA^<A>A v<A^>A<A>A

I feel good about that path. No need to explore variants.

I think that's all of them.

Collecting shortest paths

All paths:

985A
v<<A>^^AAAvA^Av<A<AA>>^AvAA^<A>Av<A<A>>^AvA^<A>Av<A<A>>^AAvA^A<A>A
66

540A
v<A<AA>>^AvA^<A>AAvA^Av<A<AA>>^AvAA^<A>Av<A>^Av<<A>>^AAvA^<A>Av<A^>A<A>A
72

463A
v<<A>>^AAv<A<A>>^AAvAA^<A>Av<A>^AA<A>Av<A<A>>^A<Av>A^Av<A<A>>^A<Av>A^A
70

671A
v<<A>>^AAvA^Av<A<AA>>^AAvA^<A>AvA^Av<A<A>>^AA<Av>A^Av<A^>AAv<<A>>^A<Av>A^A
74

382A
v<<A>>^AvA^Av<A<AA>>^AvA^<A>AAvA^Av<<A>A>^AA<Av>A^Av<<A>A>^AvA^A<A>A
68

And now for my equation:

  985*66  65010
+ 540*72  38880
+ 463*70  32410
+ 671*74  49654
+ 382*68  25976
--------
  211930

To be clear, even with my thorough walkthroughs, I still don't expect this to be the correct answer.

Why not? Because I don't think I'm that lucky. And I probably mis-typed something.

But, here goes nothing...

Submitting my answer

...

OH MY GOODNESS, IT IS THE CORRECT ANSWER!!!

Wow. I was not expecting that.

Incredible!

Well, Part 2 is likely to require a performant algorithm.

Let's see what twist it brings.

Part 2

Yup, more robots

I'm not about to walk through over 20 paths for each code by hand.

Part 1 was a fun manual test.

But my journey today stops here.

I am beyond happy to have a hard-earned - though not programmatic - gold star.

Race Condition

Robert Mion — Fri, 28 Nov 2025 14:28:17 +0000

Advent of Code 2024 Day 20

Part 1

Gonna be a swift defeat

It's times like this that I wish I had stronger computer science skills.

What I expect to need for this challenge:

Path exploration algorithm
Where each step in the path has up to three variations to check

My last few attempts at path exploration have resulted in an underperforming program.

I suspect this will be even worse, given the need to explore paths with walls swapped for open spaces.

Given that, I sadly am not excited to try this one.

I'm usually up for a challenge. But this seems out of reach for me from the start.

Maybe tomorrow's challenge will be more accessible to me.

Linen Layout

Robert Mion — Mon, 17 Nov 2025 20:45:33 +0000

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.

RAM Run

Robert Mion — Thu, 18 Sep 2025 01:45:31 +0000

Advent of Code 2024 Day 18

Part 1

Another variation of smallest possible answer

A few of the last several puzzles required finding the smallest valid answer.

One recent puzzle felt nearly identical to this one in that I had to explore every path within a maze from start to finish in order to identify the shortest path.

I don't love these puzzle types because I haven't learned how to re-create a proper shortest-path algorithm, commonly referred to as Djikstra's algorithm or an A* algorithm, I believe.

Instead, when I attempt them, I leverage the skills I have: recursion, novice memoization, and brute force

Sadly, most of these puzzle variations show up after Day 12, where Part 2 is usually a test of identifying some pattern in the data to jump straight to the answer, or of building an algorithm that can quickly eliminate billions or trillions of incorrect paths.

I say all of that only to admit once again:

I'll be proud to come away with one gold star today
And I won't be mad if I come away with zero

Process part of the input and create the grid

The input is a list of X,Y coordinates in a 70x70 grid.

Except the example grid is 6x6.

Making the grid is simple:

function makeGrid(width, height) {
  return new Array(height + 1)
    .fill(0)
    .map(
      el => new Array(width + 1).fill('.')
    )
}

Calling my function looks like:

let grid = makeGrid(6,6)

And seeing it as a grid looks like:

console.log(grid.map(line => line.join('')).join('\n'))

Viola!

.......
.......
.......
.......
.......
.......
.......

Now to generate the list of coordinates from the input:

let coords = input.split('\n').map(coord => coord.split(',').map(Number))

An explanation:

Split the text at each new line
Split each coordinate string at the comma
Convert each string to a number

Lastly, changing only up to a certain amount of cells to corrupted:

function updateGrid(amt) {
  coords.slice(0, amt).forEach(coord => {
    grid[coord[1]][coord[0]] = '#'
  })
}

When I call it with 12:

updateGrid(12)

I correctly see this:

...#...
..#..#.
....#..
...#..#
..#..#.
.#..#..
#.#....

Well, that was fun and easy!

Next, I'll employ my usual strategy of adding a border around the grid to prevent the need for overly-complex conditions in my main loop.

Pad the grid with a 1-cell-wide border

I need to add a cell around each bordering cell in the grid.

The way I've done this in past challenges is with the following function:

function addGridBorder() {
  grid = grid.map(row => ['#', ...row, '#'])
  grid = [
    new Array(size + 2).fill('#'),
    ...grid,
    new Array(size + 2).fill('#'),
  ]
}

What it does:

Adds a cell to each existing row, at the beginning and end
Adds two rows to the grid, at the beginning and end, containing the new amount of cells

And with that, my example grid now looks like this:

#########
#...#...#
#..#..#.#
#....#..#
#...#..##
#..#..#.#
#.#..#..#
##.#....#
#########

The only change I have to pay attention to is my new start and end coordinates, since they will now be one off for both X and Y coordinates:

let start = [1, 1]
let end = [size, size]

...where size is the width/height of the grid when counting from 0 (e.g. size 7 equates to a grid from 0-6 like in the example)

Now for the super hard part...

A program that explores all possible paths and hopefully terminates eventually

The beginnings of a recursive function

If I'm charting a path through a grid, I'm gonna use recursion.

function walkGrid(n) {
  if () {
  } else {
    walkGrid(n - 1)
  }
}

The conditions will be more robust than n, of course.

What will I need to keep track of?

The current cell in the grid
The cells previously visited (doubling as the number of steps taken)

And what should the base cases be?

Adjacent cells are dead ends or already visited
Number of steps taken is greater than the current winner for least number of steps

I'll build each of these parts of the algorithm in the next few sections.

Which cells came before?

Throughout the recursive function, I need to keep track of which cells have been visited.

Only by doing this can I arrive at a base case where all four of the next cells are one of either:

A dead end
A backstep

So, I need a list that can store a unique set of points:

let visited = new Set()

And I won't add the list of X,Y coordinates to it. First, I'll convert to a string so it is seen as unique in JavaScript's brain:

visited.add([X,Y].join(','))

Which cells could come next?

First, the usual list of four nearby cell relative coordinates:

let nearby = [
  [0,1],
  [1,0],
  [0,-1],
  [-1,0]
]

Those represent each possible next move ($) for any given originating cell (*):

.$.
$*$
.$.

What will the function invocation look like?

The first time I call walkGrid(), what might the call look like?

let start = [1,1]
let visited = new Set()
walkGrid(start, visited)

Is that enough arguments? Only one way to find out!

Time for some pseudocode!

function walkGrid(start, visited) {
  if ( /* arrived at bottom-right corner of grid */ ) {
    // how many cells were visited?
       // compare to current winner and update if appropriate
  } else {
    // check all adjacent cells
    if ( /* no adjacent cells can come next */ ) {
      // exit this iteration
    } else {
      // call function again for each possible next move
      nearby.forEach(walkGrid(next, visited))
    }
  }
}

That only took a few minutes to think through.

It feels like it accounts for the main things, but I may very well have missed something.

I'm ready to flesh it out into actual code.

A first attempt at putting the pieces together

After filling in the first base case, my function now looks like this:

function walkGrid(current, visited) {
  visited.add(current.join(','))
  if ( current.join(',') == end.join(',') ) {
    fewestSteps = Math.min(visited.size, fewestSteps);
    return false;
  } else {}
}

I added a variable to track the winning number of steps:

let fewestSteps = Infinity

After another few minutes, I added code to the else clause:

function walkGrid(current, visited) {
  visited.add(current.join(','))
  if ( current.join(',') == end.join(',') ) {
    fewestSteps = Math.min(visited.size, fewestSteps);
    return false;
  } else {
    let next = nearby.map(
      coord => grid[coord[0] + current[0]][coord[1] + current[1]] == '#' ? false : true
    )
    if ( next.every(el => el == false) ) {
      return false;
    } else {
      next.forEach((el, index) => {
        el ? walkGrid([current[0] + nearby[index][0], current[1] + nearby[index][1]], visited) : null
      })
    }
  }
}

It may not be eloquent, but it should make sense after you can decipher the array accessing syntax and math.

The big question is: does it even work?

Before I run it, I'll add some logging statements.

Well, just one for now:

if ( current.join(',') == end.join(',') ) {
  console.log(current, visited.size)
  fewestSteps = Math.min(visited.size, fewestSteps);
  return false;
}

I'll know it works if it can reach this base case and at some point print out the correct answer, 22.

Time to press run and see what kind of errors I see!

So. Many. Bugs.

Max call stack exceeded
Can't access some variable before it's defined
Visited coordinate list isn't growing beyond three items

Turns out, I had syntax errors and logic gaps.

Thankfully, it's kind of fun to debug.

After fixing those issues, I saw longer lists of visited coordinates print.

But the coordinates included dead ends.

Why is that?

Oh, right, because every time I enter the function, I add the current coordinate to the visited list.

So, even if the shortest path doesn't include that point, since it was visited as part of an earlier iteration, it gets added.

How might I prevent this from happening?

Thankfully, I can delete an item from a Set():

visited.delete(current.join(',))

I do that in the condition checking for all adjacent cells being dead ends or already visited:

if ( next.every(el => el == false) ) {
  visited.delete(current.join(','))
  return false;
}

Running again with fewer logging statements:

I see whenever it hits a dead end
I see a number printed when it hits the target end point

But I'm seeing a number one greater than the expected answer.

Why? Because I include the starting location in my visited list.

The answer asks for the number of steps taken.

That's one less than an amount that includes the starting location.

Accounting for that, my algorithm spits out the correct answer!

But something seems odd still:

Why doesn't it print any of the possible higher numbers associated with paths that initially lead down?

To test this, I adjust the order of my adjacent cells...to go down first.

Running again, I get a different answer - a larger one.

Why is my function seemingly only exploring one path?

Hmmmm.

My hunch is I'm doing two things wrong:

I need to use a unique set of visited points each time I further recurse into the function
I need to clean up my condition for recursing

After both are complete, my larger last condition looks like this:

if ( next.every(el => el == false) ) {
  visited.delete(current.join(','))
  return false;
} else {
  next.forEach((el, index) => {
    if (el) {
      walkGrid(
        [
         current[0] + nearby[index][0], 
         current[1] + nearby[index][1]
        ], new Set(visited))
    } else {
      return false
    }
  })
}

Oh, and I forgot to add my performance-boosting condition that breaks early if a path is longer than the current shortest:

if (visited.size - 1 > fewestSteps) {
  return false
}

And with that, I press run again...

and see the correct answer!

In fact, regardless of the order of adjacent cell coordinates, I see the correct answer!

Woohoo!

Now for the real test: my puzzle input.

Will my algorithm ever finish?

Will it generate the correct answer?

I wonder...

Processing my puzzle input

I see numbers.

They are decreasing gradually.

No errors yet.

Still waiting.

This may take a while.

As long as the program doesn't abruptly stop, I can wait.

...

I let my program run for several hours.

The number it printed last was only a dozen less than the number it printed several hours prior.

I'm 100% positive it is not the correct answer.

And I was 99% positive I wouldn't get even one gold star today because of this shortest-path challenge.

It's a bummer, but expected by Day 18.

It's also time to move on.

Forem: Robert Mion

Printing Department

The ease of Part 1 concerns me

Writing another adjacent grid cell inspector

Part 2

What a delightful twist

Building on Part 1

Lobby

Part 1

Considering my options, from worst to best

Brute force

Brute force but optimized

Getting creative: find the two biggest numbers

Building the creative algorithm

Part 2

More digits, more problems

Maybe my Part 1 algorithm was on to something

Writing my algorithm...very gradually

Running on my puzzle input

Gift Shop

Part 1

Optimizing a brute force algorithm

How might I optimize a brute force algorithm?

Stepping through a few examples to plot out my algorithm

Split apart and increment, am I right?

Summarizing the tasks in order

Writing an algorithm

Writing IDchecker()

Correcting for one last major oversight

Testing on both inputs

Part 2

Feels like this just got exponentially harder

Working through examples from my puzzle input by hand

Is optimization worth the headache?

How many numbers will a brute force algorithm have to check?

I just need to start coding

Testing and celebrating

Secret Entrance

Part 1

Round and round we go!

Writing my algorithm

Testing on my puzzle input

Part 2

Of course, now number of rotations is critical

Updating my algorithm

Testing my algorithm

Am I overthinking things?

Fixing my mistakes one by one

Code Chronicle

Part 1

A cool way to end the year

Writing my lock-key matching algorithm

Comparing most keys to every lock

Running on my puzzle input

Year in review

Crossed Wires

Part 1

Hurry up and wait...and see

Understanding how to architect the example input

Understanding how to process the example input's gates

Turning puzzle input into a state machine

The harder part: processing each set of ready gates

Piecing together the decimal

Running my algorithm on my puzzle input

Part 2

Confusion and intimidation

LAN Party

Part 1

An exercise in triangle classification

Walking through a possible algorithm

Writing actual code

Running my algorithm on my puzzle input

Part 2

Surprse, surprise

Monkey Market

Part 1

Another math gauntlet

A slow burn of programming

Mixing and Pruning functions

The sequence of three calculations

Writing `IDchecker()`

First straight-forward code: `985A`

Second straight-forward code: `463A`

Third code: `671A`

Fourth code: `382A`

Fifth code: `540A`