DEV Community

Cover image for Hoof It
Robert Mion
Robert Mion

Posted on

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])
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
                )
            }
        })
    }
}
Enter fullscreen mode Exit fullscreen mode

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

pathFinder(-1, zeroCoordinate, matches)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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.

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay