Advent of Code 2023 Day 18
Part 1
Enclosed loop - redux
Day 10 Part 2 featured a similar challenge:
- Identify and sum up the cells enclosed by the loop
I did not solve Day 10 Part 2.
I don't plan to solve Day 18 Part 1.
But I do intend to build program that can draw the loop.
Here I go!
Been here. Done that. Forgot when.
In previous years there were puzzles requiring the traversal of a 2D grid with unknown start and end points.
I recall building programs that successfully tracked each relative coordinate - relative to 0,0
that is - and plotted them on an exact-size grid.
I forget which days of which years those puzzles were.
And I don't feel like looking back.
Instead, I'll do it from scratch again!
Where to start?
At 0,0
of course!
let here = [0,0]
How to track where we've been?
With an array, of course!
let path = [here]
How to determine the right direction?
With a dictionary mapping directions to relative coordinate changes, or course!
const directions = {
'R': [0,1],
'D': [1,0],
'L': [0,-1],
'U': [-1,0]
}
How to actually move in the right direction?
With a for
loop that runs i
times, each time adding both X
and Y
coordinates by each relative coordinate amount.
for (i = 0; i < STEPS; i++;) {
here = [
here[0] + directions[RDLU][0],
here[1] + directions[RDLU][1]
]
path.push(here)
}
How to extract the direction and step?
With split
, map
and slice
, of course!
const moves = input
.split('\n')
.map(
line => line.split(' ').slice(0,2)
)
How to put it altogether?
Just a simple change of variable names, of course!
moves.forEach(move => {
for (i = 0; i < +move[1]; i++) {
here = [
here[0] + directions[move[0]][0],
here[1] + directions[move[0]][1]
]
path.push(here)
}
})
How do I check if it works?
console.log()
of course!
[
[ 0, 0 ], [ 0, 1 ], [ 0, 2 ], [ 0, 3 ],
[ 0, 4 ], [ 0, 5 ], [ 0, 6 ], [ 1, 6 ],
[ 2, 6 ], [ 3, 6 ], [ 4, 6 ], [ 5, 6 ],
[ 5, 5 ], [ 5, 4 ], [ 6, 4 ], [ 7, 4 ],
[ 7, 5 ], [ 7, 6 ], [ 8, 6 ], [ 9, 6 ],
[ 9, 5 ], [ 9, 4 ], [ 9, 3 ], [ 9, 2 ],
[ 9, 1 ], [ 8, 1 ], [ 7, 1 ], [ 7, 0 ],
[ 6, 0 ], [ 5, 0 ], [ 5, 1 ], [ 5, 2 ],
[ 4, 2 ], [ 3, 2 ], [ 2, 2 ], [ 2, 1 ],
[ 2, 0 ], [ 1, 0 ], [ 0, 0 ]
]
It sure looks like it works!
A convenient example. A difficult input.
The example moves largely right and down, then back to the start.
My puzzle input instead moves left and up immediately.
Because...of course!
So, I need to expect negative numbers in my path for both X and Y coordinates.
Crafting the grid and drawing the path
What's the minimum and maximum X and Y coordinates?
let minX = Math.min(...path.map(step => step[0]))
let maxX = Math.max(...path.map(step => step[0]))
let minY = Math.min(...path.map(step => step[1]))
let maxY = Math.max(...path.map(step => step[1]))
These values tell me that the grid for the example input is exactly contained within a rectangle that is 7 cells tall and 10 cells wide:
let grid = new Array(maxX - minX + 1).fill(null).map(el => new Array(maxY - minY + 1).fill(null).map(el => '.'))
With the grid made, I need to update the appropriate .
s with #
s:
path.forEach(coord => {
grid[coord[0]][coord[1]] = '#'
})
And viola! I see the grid just like in the example!
#######
#.....#
###...#
..#...#
..#...#
###.###
#...#..
##..###
.#....#
.######
Now to account for negative numbers...
How to account for a path that moves all over the place?
Thankfully, it just took some Math.abs()
to account for the shifted starting location:
path.forEach(coord => {
grid[Math.abs(minX) + coord[0]][Math.abs(minY) + coord[1]] = '#'
})
How to piece together this giant loop?
I printed the output, but replit.com only printed the last hundred rows or so.
With some copy-pasting and slice()
ing, I eventually pieced together the full, stair-steppy loop:
How to identify all cells enclosed by the loop?
I. Just. Don't. Know.
Programmatically, that is.
I could, of course, manually change each .
in my copied output to a #
, but that's not the point of these puzzles.
...
After some serious thought, I think I may have a strategy.
It's overly complicated.
But it seems like it may be programmable.
I'll describe how it works with sample lines of the grid.
Say this is the top-most line:
.......####.....
What's the index of the left-most #
?
8
What's the next character to the right?
- If it's a
#
, this is an edge of the loop - If it's a
.
, this is not an edge and is inside the loop because we started from the left-most#
Proceeding on an edge:
- Continue right until the next character is a
.
- Check the substring of all characters remaining in the line
- If there's a
#
, then all.
s between the previous#
and the next one are inside the loop - If there's no
#
, then the only contents of the loop on this line were the edge
Proceeding with a .
:
- All characters from here to the next
#
are enclosed in the loop. There are no edges that are a single#
in length.
Toggling whether .
s are enclosed or not:
- For each line, a variable will start as
false
to indicate.
s are not in the loop - The variable will toggle to true only when one of two conditions is met
- A series of
#
s is followed by a substring of.
s that contains a#
- A single
#
is followed by a.
- It will toggle false when the opposite is true, generally speaking
This all feels good in theory.
But it's going to be a lot of work to prototype and then troubleshoot.
I feel like I can make it work.
So I have to try.
Off I go to struggle through a bunch of code!
Hours later: the struggle was real
As described above, my strategy was to process each line, moving left-to-right, identifying cells that are enclosed by the loop.
Success: I wrote a recursive function that accomplished this task
Fail: It wasn't 100% accurate, for reasons I'll share in a moment.
Running my algorithm on the grid produced the picture to the right in the image below:
So close...right?
There's a pattern with the lines that are incorrect:
- My flag for whether a section is 'in' or not gets tripped up by encountering a bottom- or top-most portion of a section of the loop
I tried adding all sorts of conditions and variables to account for these occurrences in the loop.
Sadly, any time I thought I was getting closer, something was pulling further away.
What may demonstrate that best is the image below, where the right-most filled-in grid is looking better...except for the bottom-left quadrant:
Another strategy: recursion from the corners
What if, instead of filling in the loop directly, I work from the corners in?
I can flag all cells that are definitely outside of the loop...since I'd be starting from the corners.
Then, I can iterate through every cell and only mark ones not in the list of unenclosed cells as enclosed cells.
I've got a good feeling about this!
Off I go once again to struggle through the code.
...
Well, my attempt to do this using recursion exceeded the call stack.
I think I know why:
- The space outside the grid even in the small upper left quadrant is hundreds of cells in volume
- My algorithm was reaching stack sizes of over 3k
Another strategy: walking the edges outward-in
The problem with recursion is I was digging holes that I had to climb out of.
I just want to walk along an area, being sure to visit every cell until I hit a loop edge, and not re-visit any visited cells.
The way I see it:
From any starting point (each of the four corners)
Check each of the four ordinal directions for valid next moves
Pick the first valid one
Continue in that direction
Fast-forward about an hour.
I wrote that algorithm.
Sadly, it only traversed a slim border of cells, indicated by the *
s in the image below:
To be fair, it's doing exactly what I wrote:
- Check directions clockwise
- Continue in the first valid direction
- Don't revisit any visited cells
But it's not visiting all of the .
s in any given outer quadrant.
I think I know what's wrong!
Instead of only continuing to the first valid next cell, I should track each possible next valid cell, and process that list repeatedly, as long as there are items in it to process.
How might this work?
- The list would start with the four corner cells
- I'll process the top-left cell first
- That will traverse the same cells that my algorithm already collects
- But it will add to the list all of the valid cells that could have been visited
- And it will remove from the list each visited cell - namely the cell it chooses to visit next each time
- Eventually, it should visit every unenclosed cell exactly once
Fingers crossed this actually works!
...
Fast-forward about two hours.
Reader...look!
It works!
It actually works!!!
Calculating the number of enclosed loop cells
I convert my 2D grid into one giant string:
let oneBigStr = grid.map(line => line.join('')).join('')
I use regex
to count all enclosed cells:
let enclosedCount = [...giantStr.matchAll(/[\.#]/g)].length
For good measure, I also count unenclosed cells and compare the sum of unenclosed and enclosed to the total number of cells:
let outsideCount = [...giantStr.matchAll(/X/g)].length
let isSame = enclosedCount + outsideCount == oneBigStr.length
Yes, they are the same!
And yes, that is the correct number of enclosed loop cells!
I did it!!!
This feels so rewarding, especially after all of my failed attempts.
I'm so glad I stuck with this one.
I really hope Part 2 does something fun with the colors.
Part 2
Nope. Zero color fun.
Just an exercise in scale.
Which I'm sure I can't accomplish, seeing as I have no idea how I would have solved this challenge any other way than to generate the grid.
So...Part 2 will remain unsolved.
But I come away with one very-hard-earned gold star!
I'm up to 30 gold stars for the year with seven days left.
My goal is to match my lowest score: 34 stars.
Let's hope I can squeeze out at least four more gold stars from the Part 1s of the next few days.
See you soon for Day 19!
Top comments (0)