DEV Community

Cover image for Lavaduct Lagoon
Robert Mion
Robert Mion

Posted on

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

How to track where we've been?

With an array, of course!

let path = [here]
Enter fullscreen mode Exit fullscreen mode

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

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

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

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

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

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

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

With the grid made, I need to update the appropriate .s with #s:

path.forEach(coord => {
  grid[coord[0]][coord[1]] = '#'
})
Enter fullscreen mode Exit fullscreen mode

And viola! I see the grid just like in the example!

#######
#.....#
###...#
..#...#
..#...#
###.###
#...#..
##..###
.#....#
.######
Enter fullscreen mode Exit fullscreen mode

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

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:

My puzzle input's enclosed 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:

.......####.....
Enter fullscreen mode Exit fullscreen mode

What's the index of the left-most #?

       8
Enter fullscreen mode Exit fullscreen mode

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

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

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

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

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

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

I use regex to count all enclosed cells:

let enclosedCount = [...giantStr.matchAll(/[\.#]/g)].length
Enter fullscreen mode Exit fullscreen mode

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

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)