Robert Mion

Posted on

## 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.

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
``````

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?

• 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!

...

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!