Hoof It

Advent of Code 2024 Day 10

Part 1

Brief terror, then excitement

I usually skim a page before reading everything closely.

Today, I saw:

• A grid
• and what looked like paths

And I feared this would be another shortest path challenge.

Then I read it.

And breathed a sigh of relief...at least for Part 1.

I need to find all valid paths.

That...I can do!

Start from 0

I have to find all the 0s:

input = input
  .split('\n')
  .map(
    line => line.split('').map(char => +char)
  )
let zeros = []
for (let r = 0; r < input.length; r++) {
    for (let c = 0; c < input[0].length; c++) {
        if (input[r][c] == 0) {
            zeros.push([r,c])
        }
    }
}

0s: found!

Attempt to move in increments of 1

From each 0, a valid path is nine steps where each number is one greater than the last, ending at 9.

This sounds like a job for recursion.

I need a base case:

1. Current number is not exactly one greater than the previous
2. Current number is 9

Here's how my algorithm should work:

Input:
1. Originating number
2. Current coordinates

Get current number

If it is not exactly one greater than the originating number
  Return false
Else
  If it is 9
    Return the current coordinates
  If it is not 9
    Continue with the coordinates in each orthogonal direction

Having now written it, the part I missed was tracking the ledger of valid end coordinates.

I struggled with this for some time.

I kept getting an error that wrongly made me think I couldn't pass in a Set or even an array.

But, thankfully, I just forgot to pass it into further calls of the recursive function.

Here's my working recursive algorithm:

let dirs = [[-1,0],[0,-1],[0,1],[1,0]]
function pathFinder(num, coord, memo) {
    let current = input[coord[0]][coord[1]]
    if (current - num !== 1) {
        return false
    } else if (current == 9) {
        memo.add(coord.join(','))
        return
    } else {
        dirs.forEach(dir => {
            if (
                coord[0] + dir[0] >= 0 &&
                coord[0] + dir[0] < input.length &&
                coord[1] + dir[1] >= 0 &&
                coord[1] + dir[1] < input[0].length
            ) {
                pathFinder(
                  current, 
                  [coord[0] + dir[0], coord[1] + dir[1]], 
                  memo
                )
            }
        })
    }
}

Since I must start with the coordinates of 0s, my first call uses -1:

pathFinder(-1, zeroCoordinate, matches)

Lastly, to get the correct score, I iterate through each zero, generating the unique set of destination 9s, keep and sum up the sizes of the sets:

let part1 = zeros.map(z => {
    let matches = new Set()
    pathFinder(-1, z, matches)
    return matches.size
}).reduce((a, c) =>  a + c)

Quick tests, quick results

It generated the correct answer for the small example input.

And for the larger example input.

And...

...for my puzzle input!!!

Woohoo!!!

What will Part 2 challenge me with?

Part 2

Umm, that seems too easy

Is it possible that the way I wrote my algorithm in Part 1 means this will only require a few small changes to get the correct answer?

Count 'em all!

Right now, I add each valid 9 to a set.

For Part 2, I think I just need to increment a counter for each valid 9.

Worth a try!

Change Set to Array and voila!

Correct answer for the example.

Correct answer for my puzzle input.

Wow. Wow. Wow.

On to the next day...which is likely to be much harder.

The above is the detailed content of Hoof It. For more information, please follow other related articles on the PHP Chinese website!