Lavaduct Lagoon

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!