Again with the Geometry

These geometry problems are tough.

The Problem

This is best explained by the Advent of Code site itself, so I'm going to copy.

For example, consider the following list of coordinates:

1, 1
1, 6
8, 3
3, 4
5, 5
8, 9

If we name these coordinates A through F, we can draw them on a grid, putting 0,0 at the top left:

..........
.A........
..........
........C.
...D......
.....E....
.B........
..........
..........
........F.

This view is partial - the actual grid extends infinitely in all directions. Using the Manhattan distance^manhattan, each location's closest coordinate can be determined, shown here in lowercase:

aaaaa.cccc
aAaaa.cccc
aaaddecccc
aadddeccCc
..dDdeeccc
bb.deEeecc
bBb.eeee..
bbb.eeefff
bbb.eeffff
bbb.ffffFf

Locations shown as . are equally far from two or more coordinates, and so they don't count as being closest to any.

The goal is to find the coordinate that has the largest finite (that is, not infinite) number of spaces that are closer to it than to any of the other coordinates.

The Solution

It starts with the usual data read, plus a bit of processing to turn each line into an array of two numbers:

const fs = require('fs')
let input = fs
  .readFileSync(`./input/day6.txt`, 'utf8')
  .trim()
  .split('\n')
  .map(line => line.split(', ').map(Number))

This goes a bit against my philosophy of always preferring objects over arrays to store data unless there's a good reason to choose arrays. In this case my reason was that arrays seemed just a little bit easier.

Then gather all the x values and all the y values and find maxes:

const xMax = Math.max(...input.map(([x, y]) => x))
const yMax = Math.max(...input.map(([x, y]) => y))

Clearly a Bad idea

At first I thought I would have to iterate over the whole grid, measuring the distance from each point on the grid to the nearest point from the input. That was going to be a lot of calculation; the grid is about 350x350, meaning over a million points, and there are about 250 points in the input list. I didn't see an obvious solution for deciding which input was closest to a given grid point without calculating every distance.

So Many Questions

Instead I decided to measure outward, starting at each input point and finding its neighboring points, then all the neighbors of those points, etc. I would sort of build concentric circles around each input point¹, and each loop through the code would increase the radius of the circles. Then the total area for each point would be the sum of the points in all of the concentric circles. How would I know when to stop looping? I had no idea. What would I do when the expanding circles around each input point started to overlap? Not sure. What did I know how to do? Well, given a point, I could find the four points adjacent to it, and check to find which of them were on the grid:

const findNeighbors = ([x, y]) => {
  let prospects = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]
  return prospects.filter(
    ([X, Y]) => X >= 0 && Y >= 0 && X <= xMax && Y <= xMax
  )
}

On to Data Storage

Once I found the nearest neighbors for an coordinate, I'd need to store them somewhere. An object didn't seem like the right answer, because there was no clear candidate for a key to associate with each value. The other option was an array.

A Confession

I tried to solve the Advent of Code problems, and write up these explanations, as the problems came available, during December 2018. I got almost all of the problems done on the day they were released. I wrote up most of the explanations as soon as I had the solutions. Apparently for this problem, my explanation write up got as far as the end of the last paragraph. I haven't touched this write up since December 7, 2018. It is now May 5, 2019. The rest of this explanation is going to be an attempt to recreate my thoughts based on my code.

Back to Data Storage

I want to store all of the coordinates that are nearest to each of the coordinates in the input list. The problem with using an object to store each neighbor by itself is figuring out the right key. Suppose I wanted all the neighbors for [1, 1], which would include the points [0, 1] and [2, 1]. I couldn't do something like

{ "1, 1": [0, 1], "1, 1": [2, 1] }

because the keys in an object have to be unique. Another option would be to store everything in an object, but have each value be an array of the points closest to the coordinate represented by the key. Taking the above example, the data structure would look like

{ "1, 1": [ [0, 1], [2, 1] ] }

The key is a coordinate from the input list, the value is an array, and each element of that array is a point closer to the coordinate key than to any other coordinate in the input list.

That didn't seem quite right either. I was pretty sure I wanted to work with expanding concentric circles around each input coordinate. In order to build the next concentric circle, it would help to know where the last concentric circle was. To do that, I should store all of the points that made up each "circle" together in the data structure, without mixing all of the coordinates from every "circle" together. I finally settled on something like this:

const concentricCircles = {
  "key representing an input coordinate": [
    [ /* the input coordinate itself */ ],
    [ /* the points 1 space out from the coordinate */ ],
    [ /* the points 2 spaces out from the coordinate */ ],
    ...
  ]
}

My strategy would be to create a loop, which would:

• iterate over the input coordinates
• find the array associated with each coordinate, in my data structure
• take the last element of that array, representing the biggest concentric circle so far
• build a new concentric circle using that (somehow)
• stop expanding a circle when I detected I was running into another coordinate's neighbors (somehow)

and then stop the overall loop (somehow). "Strategy" is perhaps too strong a word.

Creating a Starting Point

I could start my concentricCircles object by associating each input coordinate with an empty array, to hold the concentric circles around the coordinate. The first element of that array would be an array containing the center of the circles: the coordinate itself.

let concentricCircles = input.reduce((total, current) => {
  total[current] = []
  total[current][0] = [current]
  return total
}, {})

Beginning by Hand

I could start creating the concentric circles "by hand", without an ongoing loop, by iterating over the input coordinates. I can use my findNeighbors function from a while ago to get the neighbors of each input coordinate, and store them in concentricCircles:

const findNeighbors = ([x, y]) => {
  let prospects = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]
  return prospects.filter(
    ([X, Y]) => X >= 0 && Y >= 0 && X <= xMax && Y <= xMax
  )
}
input.forEach(point => {
  const neighbors = findNeighbors(point)
  concentricCircles[point][1] = neighbors
})

That gets me one "circle" around each of my input coordinates. Let me draw one example to remind you why I use quote marks when I talk about a "circle" using Manhattan distances. The "0" marks the center, and all the "1"s form the "circle":

.....
..1..
.101.
..1..
.....

Since diagonal movement isn't allowed, only those four places are part of the first "circle". Now I'll add the next "circle":

..2..
.212.
21012
.212.
..2..

It was pretty straightforward to use JavaScript to calculate where all the "1"s should go: they are all of the neighbors of the "0". But how can we calculate where all of the "2"s should go? That takes a few steps:

• take all of the "1"s
• find all of their neighbors
• without double-counting (because some "2"s are neighbor to two "1"s)
• and excluding the "0" (which is a neighbor to all the "1"s but is obviously not a "2")

Moving back from the example to the real problem, I want to write code to run through those steps for every point in input. That...is a lot. I'll start with the first two steps.

Take All of the "1"s

Getting all of the "1"s can be done quickly. I calculated those in the last bit of code. For one point in input, which in my diagram would be the "0", the "1"s - that is, the neighbors of the point - are in concentricCircles[point][1], That's an array.

Find All of Their Neighbors

I have an array with a lot of points, and I want to make a different array that has all of the neighbors of those points. My first thought in that situation is to reach for .map(). But nobody ever says that kind of thing unless This Time Is Different. And this time is different. Why is that? Why is .map() not a good choice? The problem is that .map() produces an array that's the same size as the one you start with, and I know from my last diagram that there will be more "2"s in the array I make than "1"s in the array I start with. You know what will work better, despite its name? .reduce(). It's a strange name to make something bigger, but it really means "reduce into just one thing". The "one thing" I want is an array. Just happens to be a relatively large array.

input.forEach(point => {
  const lastCircle = concentricCircles[point][1]
  const nextCircle = lastCircle.reduce((total, pt) => {
    const neighbors = findNeighbors(pt)
    return [...total, ...neighbors]
  }, [])
  concentricCircles[point][2] = nextCircle
})

That almost works. I will get every neighbor of all of the "1"s into nextCircle, but I'll get most of them twice. I need to prevent those duplicates.

Without Double-Counting

There are npm packages that eliminate duplicate entries in an array, but I'm not going to install any of those. That's not just me being Grumpy Old Dev, either. I don't just want to keep out duplicates as I create my next current concentric circle, I also want to keep out elements from the last concentric circle. It would be easy enough to get rid of the single "0" this time around, but when I go through this loop again, and find all the "2"s' neighbors, I'll want to make sure I don't include any of the "1"s, and so on.

In order to avoid duplicates, and elements in previous circles, I need to keep track of what those elements are. I'll do that with a second data structure. This new data structure has to be able to store points, which are two-element arrays, and tell me if it's already storing a particular point or not. I thought a Set would work for that, but it doesn't, which makes me a little up...a little annoyed, but our old friend the object works fine. I'll use the points as the keys, and the value will always be true, because all I care about is whether the point has been handled in the code already. I'll want to use the same object for all of my input values, so I'll have to scope it to outside all of the callback functions:

let accountedFor = {}
input.forEach(point => {

Then I'll use it to filter out each group of neighbors, and add the neighbors that make it through the filter back to the object so they don't get duplicated:

let accountedFor = {}
input.forEach(point => {
  const lastCircle = concentricCircles[point][1]
  lastCircle.forEach(pt => (accountedFor[pt] = true))
  const nextCircle = lastCircle.reduce((total, pt) => {
    const neighbors = findNeighbors(pt).filter(pt => !accountedFor[pt])
    neighbors.forEach(pt => (accountedFor[pt] = true))
    return [...total, ...neighbors]
  }, [])
  concentricCircles[point][2] = nextCircle
})

That works great for the situation in my last diagram. Unfortunately, it has a flaw that can come up if there is more than one point in input.

Describing the Bug

Here's a closeup of the second diagram from the example problem at the start of this article:

..dDde
bb.deE
bBb.ee

The "."s are at points that are the same distance from two of the points in input. Every one of them is as far from B as from D. According to the rules, they don't count towards the total area for either B or D. But my algorithm doesn't mark any point as accountedFor until after it has been added to some point's neighbors. Instead of the diagram above, my algorithm would result in a grid that looks like this:

bbdDde
bbbdeE
bBbbee

I need a way to track the points that have been added as neighbors to more than one input, and ensure those points don't end up counted as neighbors at all. I can't get that with accountedFor, because that sets all the values to just true. I need occountedFor to track how many times each pt is a neighbor. If pt shows up as a neighbor once, accountedFor[pt] should be one. The next time pt shows up as a neighbor, I increment accountedFor[pt] to two. I can't just write

accountedFor[pt] = accountedFor[pt] + 1

The problem is that if pt has never been a neighbor, accountedFor[pt] will be undefined, and undefined + 1 doesn't work. I'll have to make sure the code replaces any undefined with 0:

accountedFor[pt] = (accountedFor[pt] || 0) + 1

That updates accountedFor to keep track of numbers. Next I need to put those numbers to use. I won't know how many neighbors get double-counted until I've iterated over every point in input, so I'll need to deal with the double counts after the iteration. At that point, I'll need to remove the doubles. I can do another iteration over input to filter out any point that appears in accountedFor as appearing more than once:

let accountedFor = {}
input.forEach(point => {
  const lastCircle = concentricCircles[point][1]
  lastCircle.forEach(pt => (accountedFor[pt] = (accountedFor[pt] || 0) + 1))
  const nextCircle = lastCircle.reduce((total, pt) => {
    const neighbors = findNeighbors(pt).filter(
      _point => !total.some(([x, y]) => _point[0] === x && _point[1] === y)
    )
    return [...total, ...neighbors]
  }, [])
  nextCircle.forEach(pt => (accountedFor[pt] = (accountedFor[pt] || 0) + 1))
  concentricCircles[point][2] = nextCircle
})
input.forEach(point => {
  concentricCircles[point][2] = concentricCircles[point][2].filter(
    pt => accountedFor[pt] === 1
  )
})

That gets the second concentric circle around each input point, with no duplicates, and no points that are equidistant between two points from input. I'd like to generalize that to get all the concentric circles, and figure out when I can stop making the circles.

A One, and a Two, and a....

Looking through the code to make the second circle, there are only a few specific numbers that tie the code to the second circle instead of the third or fourth etc: the places that use concentricCircles[point][1] and concentricCircles[point][2]. I could make the code block more general by using a variable, like let i =. Then I could replace concentricCircles[point][1] with concentricCircles[point][i], and concentricCircles[point][2] with concentricCircles[point][i + 1].

let accountedFor = {}
let i = 1
input.forEach(point => {
  const lastCircle = concentricCircles[point][i]
  lastCircle.forEach(pt => (accountedFor[pt] = (accountedFor[pt] || 0) + 1))
  const nextCircle = lastCircle.reduce((total, pt) => {
    const neighbors = findNeighbors(pt).filter(
      _point => !total.some(([x, y]) => _point[0] === x && _point[1] === y)
    )
    return [...total, ...neighbors]
  }, [])
  nextCircle.forEach(pt => (accountedFor[pt] = (accountedFor[pt] || 0) + 1))
  concentricCircles[point][i + 1] = nextCircle
})
input.forEach(point => {
  concentricCircles[point][i + 1] = concentricCircles[point][i + 1].filter(
    pt => accountedFor[pt] === 1
  )
})

Now, I could wrap the whole thing in a loop, and increment i, and it would work for the second, third, whatever circle I want. But I don't want the loop to go on forever. I don't have a pre-existing collection of circles to iterate over, so I can't use another forEach. I don't know how many circles I'm going to make, so a for loop doesn't quite seem right. This looks like a job for a while loop. I need to figure out the condition that lets the loop continue. How do I know when the loop should continue?

Well, what am I doing the looping for? I'm trying to figure out all of the areas that surround each input point. What do I know about those areas? I know they're a set of points, closer to one input point than to any other input point, and they can't go "out of bounds" of my grid. What does the loop do with those points? Each time through the loop, I look at the outermost ring around each input point, and find the neighbors of all of those. I eliminate any neighbors that are "out of bounds", or closer to another input point than to the one I'm checking at the moment. Any neighbors that make it through the filtering become a part of the newest outermost ring. What if no neighbors make it through filtering?

Aha. If no neighbors make it through filtering, for any input, then I can stop. I continue so long as at least one input point has an outermost ring that has at least one point in it. In JavaScript terms,

let i = 1
while(input.some(point => concentricCircles[point][i].length > 0)) {
  input.forEach(point => {
    ...
  })
  input.forEach(point => {
    concentricCircles[point][i + 1] = concentricCircles[point][i + 1].filter(
      pt => accountedFor[pt] === 1
    )
  })
}

That loop will continue until the whole grid gets filled up. Then I have to deal with the areas that would expand past the grid.

Finite Only

At that point, areas has been calculated for the entire grid from (0, 0) to the xMax and ymax values we calculated at the beginning. Any area that reaches an edge of that grid will go on forever, and the problem statement said we're concerned only with the finite areas. We can filter out areas that reach an edge, and we can identify those areas because at least one point in them will have at least one of the following:

x coordinate of 0
x coordinate of xMax
y coordinate of 0
y coordinate of yMax

const finites = input.filter(point => {
  return !areas[point].some(points =>
    points.some(([x, y]) => {
      return x === 0 || y === 0 || x === xMax || y === yMax
    })
  )
})

Finally

Once we have the inputs that have finite areas, the last task is to identify the biggest one. To figure out how many points are in one, remember that concentricCircles[point] is the array of arrays of points that are closest to point. To get the total number of points in that nested array, we can turn the array of arrays into an array of numbers with .map(), then turn the array of numbers into a single number with .reduce().

const finiteAreas = finites.map(pt => {
  return concentricCircles[pt]
    .map(d => d.length)
    .reduce((total, current) => total + current, 0)
})
console.log(Math.max(...finiteAreas))

Part Two is so much simpler.