Lavaduct Lagoon
Tags: adventofcode, algorithms, javascript, programming
Published: 2024-02-23 14:03:38

## [Advent of Code 2023 Day 18](https://adventofcode.com/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!
```js
let here = [0,0]
```

#### How to track where we've been?
With an array, of course!
```js
let path = [here]
```

#### How to determine the right direction?
With a dictionary mapping directions to relative coordinate changes, or course!
```js
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.
```js
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!
```js
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!
```js
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!

```js
[
  [ 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?
```js
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:
```js
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:
```js
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:
```js
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](https://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:

![My puzzle input's enclosed loop](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lsi4szqfx13y11xnpkfo.png)

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

![Nearly accurate grid filled in](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p4nfpycfwjl7ywcfml9v.png)

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:

![Making progress, kind of](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dkbu0oa6l2sj8hgt75wn.png)

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

![First attempt at this strategy](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3fjzrk0t40n9m5d68jcv.png)

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!

![All unenclosed cells marked](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l5gancv8g75efjf57lnl.png)

It works!

It actually works!!!

#### Calculating the number of enclosed loop cells
I convert my 2D grid into one giant string:
```js
let oneBigStr = grid.map(line => line.join('')).join('')
```

I use `regex` to count all enclosed cells:
```js
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:
```js
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!