This Would Be Easier If I Had Graph Paper

Today's problem involves a lot of rectangles, and just a few drawings.

The Problem

The input data describes a set of rectangles. The descriptions look like

#123 @ 3,2: 5x4

where the numbers represent id (123), bottom left corner (3 for the bottom, 2 for the left), width (5) and height (guess). There are a bunch of lines like that in the input data, and I'm supposed to figure out how much overlap there is among all of the rectangles described therein.

The Solution

Massaging the Input Data

Data is provided in the usual kind of file, and we begin extracting it in the usual way:

const fs = require('fs')
const input = fs
  .readFileSync(`./input/day3.txt`, 'utf8')
  .trim()
  .split('\n')

That gets an array of strings, each with data about what the problem calls a claim (and I call a rectangle, because I'm fancy). What I care about are the numbers in each string, and what they represent - the bottom, left, etc for each claim. I'd like to hold on to each number along with each label. For instance, for the example line I showed above, I would change it into

// '123 @ 3, 2: 5x4'
{
  id: 123,
  left: 3,
  bottom: 2,
  width: 5,
  height: 4
}

-and store the data in an object. That way I can get the left edge or the bottom or whatever back out easily. Actually, as I look at the object, I'm not quite satisfied with it. The labels "left" and "bottom" don't really pair naturally with "width" and "height", "right" and "top" do. I could calculate those. If the left is 3, and the width is 5, then the right should be...7. (I thought it should have been 8, and it messed me up for an hour. See the footnote for what I figured out.)

OK, I'm starting with an array of strings, and I want to transform each string into an object. That's a job for map. I know what the "shape" of each object will be, so I have to figure out a callback function for map that will turn one string into one object. The string has numbers in it, mixed in with other characters like # and : and x, and I need to get the numbers out. That sounds like a job for a regular expression. I'll get the numbers out, put them in the object, Bob's your uncle.

Here's the callback function I came up with:

const parseClaim = claimString => {
  const match = claimString
    .match(/#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/)
    .map(Number)
  return {
    id: match[1],
    left: match[2],
    bottom: match[3],
    right: match[4] + match[2] - 1,
    top: match[5] + match[3] - 1,
  }
}

That's a function that will take a string, claimString, and match it against a regular expression. The argument to .match() is a regular expression that includes all of the formatting characters like # and : and x that I know claimString will have. The regular expression also has five separate (\d+). The \d means "find a digit (any of 0 - 9)." Adding a + to make \d+ means "find one or more digits, in a row". Adding parentheses to make (\d+) means "hold on to those digits, I might need them later". If I used that call to .match() on my trusty example line, the return value would have the digits 123, 3, 2, 4, and 5 in an array¹. Since the digits are coming out of a regular expression match on a string, they're strings too. That's why I mapped the array through Number, to get an array of numbers.

I want to use parseClaim on every string in my input array, so I give it to map as the callback function:

const parsedData = input.map(parseClaim)

Using the Parsed Data

I'm supposed to calculate the number of square inches that are part of multiple claims. The first approach I thought of was to iterate over the entire grid, and for each point, try to find how many claims it was part of. The drawback to that is that some points are not in any of the claims, and it would be a waste of time to look at them. Instead, I decided to iterate over each of the claims, and compare it to each of the others:

for (let i = 0; i < parsedData.length; i += 1) {
  for (let j = i + 1; j < parsedData.length; j += 1) {
    const [claim1, claim2] = [parsedData[i], parsedData[j]]
    // find the overlap between claim1 and claim2
  }
}

There are a few similarities between what I'm doing here and what I did for the second part of yesterday's problem - nested for loops, starting the inner index with the value after the value of the outer index, and getting the two values to compare based on each index. That's a nice little reminder of how you start to see familiar patterns if you work at this long enough.

Next I needed a function to find the overlap between two claims. Then again, many claims will have no overlap; it would be nice to have a quick way to make sure the claims overlap at all before looking at them in more detail:

const [claim1, claim2] = [parsedData[i], parsedData[j]]
if (hasOverlap(claim1, claim2)) {
  // find the overlap between claim1 and claim2
}

I can tell hasOverlap is going to return a boolean value, both because I'm using it in a conditional and because it's expressing the answer to a yes/no kind of question, do two things overlap or not. Writing a function for hasOverlap seems hard, so I'm not going to do it. Instead, I'll look at a related problem: how to find if two claims don't overlap. I'll write a function called noOverlap. Any time noOverlap is true, hasOverlap would have to be false. Any time noOverlap is false, hasOverlap would be true. So I could define one in terms of the other:

const hasOverlap(claim1, claim2) => !noOverlap(claim1, claim2)

That means I'll get hasOverlap - as soon as I figure out noOverlap. This is where the drawing I mentioned at the start of the post comes in. I need to look at a couple of rectangles that don't overlap, and figure out a way to express their "non-overlappiness" using the information I have about each one. Here's one situation in which claim A does not overlap claim B, with numbers along the top of the grid to denote inches from the edge:

01234567
........
.AA..BB.
.AA..BB.
........

I had to express how I knew those claims were non-overlapping using the information I have about each claim, which is stored in an object with the properties left, top, right, bottom. Imagine moving or expanding either of those rectangles until they overlapped. I'd have to move the right edge of A further right, and/or the left edge of B further left. It wouldn't matter if I move either of them up or down. They don't overlap because A is not far enough to the right, or B is not far enough left, depending on how you want to look at it. In terms of the numerical properties the claims have, I could say that they don't overlap because the right edge of A (which is 2) is less than the left edge of B (which is 5).

Likewise, if I have claim A below claim B:

4.......
3..BB...
2..BB...
1.......
0..AA...

I can say that the top edge of A is less than the bottom edge of B. If had A and B switch places, it would work the same - then the top edge of B would be less than the bottom edge of A. Now it wouldn't matter if I moved either claim to the left or right - they don't overlap top-to-bottom, so they can't overlap at all.

I can use those kinds of numerical comparisons to write my noOverlap function, which I know will take two claim objects as parameters and return a boolean:

const noOverlap = (claim1, claim2) =>
  claim1.right < claim2.left ||
  claim2.right < claim1.left ||
  claim1.top < claim2.bottom ||
  claim2.top < claim1.bottom

Let's Put All the Code Together

Here's the code I have so far, which reads data from a file into a string, converts the data from a string into an array of objects, then has a nested loop over that array which checks whether each pair of objects has any overlap:

const fs = require('fs')
const input = fs
  .readFileSync(`./input/day3.txt`, 'utf8')
  .trim()
  .split('\n')
const parseClaim = claimString => {
  const match = claimString
    .match(/#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/)
    .map(Number)
  return {
    id: match[1],
    left: match[2],
    bottom: match[3],
    right: match[4] + match[2] - 1,
    top: match[5] + match[3] - 1,
  }
}
const parsedData = input.map(parseClaim)
const noOverlap = (claim1, claim2) =>
  claim1.right < claim2.left ||
  claim2.right < claim1.left ||
  claim1.top < claim2.bottom ||
  claim2.top < claim1.bottom
const hasOverlap = (claim1, claim2) => !noOverlap(claim1, claim2)
for (let i = 0; i < parsedData.length; i += 1) {
  for (let j = i + 1; j < parsedData.length; j += 1) {
    const [claim1, claim2] = [parsedData[i], parsedData[j]]
    if (hasOverlap(claim1, claim2)) {
      // findAllOverlap(claim1, claim2)
    }
  }
}

I have a comment in there to remind myself that it's not enough to get a boolean answer to hasOverlap. If there is any overlap between two claim objects, I have to calculate how much. To find the overlap between two claims, I can take one claim and iterate over it inch by inch, from the left edge to the right and from bottom to top, and check each square inch to see if it was inside the other claim. The fact that I'm measuring overlap between two claim objects makes me think those will be the parameters to the hasOverlap function. When I find some overlap, I'll have to keep track of it somehow. The requirement of calculating an amount of something made me think the findAllOverlap function would return a number. Then I realized I need to keep track of all the overlap,for all pairs of claims, and be careful not to double-count any square inch that's part of more than one pair. I don't know what the return value will be yet, but I can write the iterations I have to go through in findAllOverlap:

const findAllOverlap = (claim1, claim2) => {
  for (let x = claim1.left; x <= claim1.right; x += 1) {
    for (let y = claim1.bottom; y <= claim1.top; y += 1) {
      if (inside(claim2, x, y)) {
        // keep track of overlap at point (x, y)
      }
    }
  }
}

I snuck in a call to a function I haven't defined yet: inside, which takes a claim and a pair of (x, y) coordinates to see if the coordinates are inside the claim, returning true if they are and false if they're not. What does it mean, in terms of the data we have, to say that x and y mark a spot inside a claim? Well, I can make another drawing to illustrate. This time I'll show one rectangular claim A, and highlight one point that overlaps A with a *.

 01234
4.....
3.A*..
2.AA..
1.....
0.....

Clearly, the * overlaps with A, and it still would even if I moved the * down a bit and/or left a bit. It would not overlap if I moved it up and/or to the right. If I wrote the claims object for A, it would look like

{ top: 3, bottom: 2, left: 1, right: 2 }

The (x, y) coordinates for the overlapping point with the * are (2, 3). Comparing those sets of numbers while looking at the picture, I can tell that there's overlap if the x is greater than or equal to the claim's left edge - but less than or equal to the claim's right edge. Same for the top and bottom vs y. Translating that logic into code produces:

const inside = (claim, x, y) =>
  x >= claim.left && x <= claim.right && y >= claim.bottom && y <= claim.top

All that is left for findAllOverlap is to keep track of the overlapping points. The need to store data takes me back into the array vs object debate. At the end, I'll have to calculate how many points of overlap there are, which is a strong argument for using an array. On the other hand, if I push each overlapping point into an array, I'd have to take care not to duplicate any points (which could happen if a point is contained within three or more claims). I decided to go with an object.

let claimConflicts = {}
const findAllOverlap = (claim1, claim2) => {
  for (let x = claim1.left; x <= claim1.right; x += 1) {
    for (let y = claim1.bottom; y <= claim1.top; y += 1) {
      if (inside(claim2, x, y)) {
        claimConflicts[`${x},${y}`] = true
      }
    }
  }
}

I defined the claimConflicts object outside of findAllOverlap, so that every time I use findAllOverlap I will be reusing the same claimConflicts. That way it will end up with all of the overlap for every pair of claims.

Note the transformation of the x,y pair into a single string with ${x},${y}. I did that because the keys of my claimConflicts object (or any other JavaScript object) have to be strings. Using x and y to make the key saves me from worrying about hitting the same x, y point twice, because I'd just end up reassigning the same key-value pair.

Come to think of it, if I already have an x, y point stored as a key in claimConflicts, there's no point in making the call to inside. I could make the code more efficient (how much I'm not sure) by checking claimConflicts in the last conditional:

let claimConflicts = {}
const findAllOverlap = (claim1, claim2) => {
  for (let x = claim1.left; x <= claim1.right; x += 1) {
    for (let y = claim1.bottom; y <= claim1.top; y += 1) {
      if (!claimConflicts[`${x},${y}`] && inside(claim2, x, y)) {
        claimConflicts[`${x},${y}`] = true
      }
    }
  }
}

That gives the final answer to part one:

const fs = require('fs')
const input = fs
  .readFileSync(`./input/day3.txt`, 'utf8')
  .trim()
  .split('\n')
const parseClaim = claimString => {
  const match = claimString
    .match(/#(\d+) @ (\d+),(\d+): (\d+)x(\d+)/)
    .map(Number)
  return {
    id: match[1],
    left: match[2],
    bottom: match[3],
    right: match[4] + match[2] - 1,
    top: match[5] + match[3] - 1,
  }
}
const parsedData = input.map(parseClaim)
const noOverlap = (claim1, claim2) =>
  claim1.right < claim2.left ||
  claim2.right < claim1.left ||
  claim1.top < claim2.bottom ||
  claim2.top < claim1.bottom
const hasOverlap = (claim1, claim2) => !noOverlap(claim1, claim2)
const inside = (claim, x, y) =>
  claim.left <= x && claim.right >= x && claim.bottom <= y && claim.top >= y
let claimConflicts = {}
const findAllOverlap = (claim1, claim2) => {
  for (let x = claim1.left; x <= claim1.right; x += 1) {
    for (let y = claim1.bottom; y <= claim1.top; y += 1) {
      if (!claimConflicts[`${x},${y}`]) {
        if (inside(claim2, x, y)) {
          claimConflicts[`${x},${y}`] = true
        }
      }
    }
  }
}
for (let i = 0; i < parsedData.length; i += 1) {
  for (let j = i + 1; j < parsedData.length; j += 1) {
    const [claim1, claim2] = [parsedData[i], parsedData[j]]
    if (hasOverlap(claim1, claim2)) {
      findAllOverlap(claim1, claim2)
    }
  }
}
console.log(Object.keys(claimConflicts).length)

Part two asks us to find the one claim that has no overlap with any others. To solve that problem, I'll be able to reuse most of the code I alrady have. If anything, part two is simpler, because for any pair of claims, hasOverlap is what we care about. To find the one claim with no overlap, we'll find all the other claims that do have overlap. Then the claim we want will be the only one missing from the list of overlappers.

As I said, we have code to find if two claims hasOverlap. Similar to storing the x,y values of each overlapping point in the claimConflicts before, we can store something about each claim that has overlap in an overlappingClaims object. Since all of the claims are in the parsedData array, and we're iterating over that array in a couple of loops, it will be convenient to use the array index of each claim as a key in overlappingClaims:

let overlappingClaims = {}
for (let i = 0; i < parsedData.length; i += 1) {
  for (let j = i + 1; j < parsedData.length; j += 1) {
    const [claim1, claim2] = [parsedData[i], parsedData[j]]
    if (hasOverlap(claim1, claim2)) {
      overlappingClaims[i] = true
      overlappingClaims[j] = true
    }
  }
}

By the end of it, overlappingClaims will be an object that has a key for all but one of the index values of the parsedData array's elements. Now we can find which index value is missing from that collection of keys, and that will be the index value of the claim that has no overlap. As it happens, there is an array method called find, and it can be invoked with a callback function that takes two parameters, an array element and that element's index. In this case, the array element itself doesn't matter in the callback function, so I'll indicate that by using a _ for the first parameter. (That doesn't mean anything special to JavaScript, but other developers can take it as a sign that I had to put something in for a parameter but I'm never going to use it.) Rather than finding based on the array element, this callback function will depend on the index value. We want to find the index value that is not a key in the overlappingClaims object:

const remainingClaim = parsedData.find((_, i) => !overlappingClaims[i])
console.log(remainingClaim)

For the sake of completeness, I should say that JavaScript is cheating a bit behind the scenes for us. I mentioned earlier that every key in a JavaScript object is a string. But in the for loops as well as in the callback function for find, I used array index values as object keys - and those are numbers! What the?!?! It turns out JavaScript sees that kind of shenanigans coming a mile off, and it turns anything that gets used as a key into a string for you. So what you thought was overlappingClaims[0] was actually overlappingClaimns["0"] the whole time.

*I missed the -1 for about an hour, until I finished the algorithm and got the wrong answer a few times. Then I went back to the sample data to see if I could parse it correctly, using the problem statement's pictures to guide me. From the problem statement:

A claim like #123 @ 3,2: 5x4 means that claim ID 123 specifies a rectangle 3 inches from the left edge, 2 inches from the top edge, 5 inches wide, and 4 inches tall. Visually, it claims the square inches of fabric represented by # (and ignores the square inches of fabric represented by .) in the diagram below:
...........
...........
...#####...
...#####...
...#####...
...#####...
...........
...........
...........

As you can see, if the left side of the claim is three inches from the edge, then it makes sense to think of the dots as numbers starting from 0:

...........
012345678..
...#####...

So if the left edge is at index 3, the right edge is at index 7, which is 3 + 5 - 1.