Day 3 - No Matter How You Slice It

Dec 3, 2018

This was probably the hardest problem I’ve had to work on since college. The problem isn’t so much “hard” as I’m very weak at graph/coordinate based problems. Things that involve calculating anything spatial is my weakness, not only in programming but also in general mathematics as well. So when I saw Day 3’s visual diagram, I knew I was going to be in for severe challenge. So for this problem, we are given a list of inputs that represent “claims” into a fabric that could be cuts for Santa’s suit. The example input they give:

#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2

Results in this:

........
...2222.
...2222.
.11XX22.
.11XX22.
.111133.
.111133.
........

Where the . represents empty spaces, the numbers represent the elf’s id who claims this would be a great spot to cut in for Santa’s suit, and X represents where two or more claims overlap. Now this particular problem has a lot of complexities.

We have to be very good at making sure our data is parsed for each claim; It must be able to read the id, the distances from top and left and the width and height for each line.
It must be able to maintain a running count of all the crossed points in our claims

Part 1

My first attack at this problem was extremely brute force. Being able to push out code effectively I couldn’t see anything easier in front of me. I would do what many do, enumerate every point and keep a running note of these overlaps. The naive algorithm:

Parse the input and generate a claim per iteration
Iterate through each point of the square
Generate a running list of points and their respective number of overlaps
Count up all the points who have 2 or more claims at that point

To go into parsing the input, I just wrote the parse logic separate from everything else:

function parseInput(string) {
  // string example:
  // #1 @ 1,3: 4x4
  let parsedInput = string.split(' ')

  let id = parsedInput[0]
  let left = +parsedInput[2].split(',')[0]
  let top = +parsedInput[2].split(',')[1].slice(0, -1)

  let width = +parsedInput[3].split('x')[0]
  let height = +parsedInput[3].split('x')[1]
  return { id, left, top, width, height }
}

Then to make maintaining this information slightly easier for myself, I decided to create a Claim class using ES5 syntax just because I wanted slightly more practice in the older version:

function Claim({ id, left, top, width, height}) {
    this.id = id
    this.left = left
    this.top = top
    this.width = width
    this.height = height
    this.coordinates = new Set()
  }
}

Now the solution is here!

function part1(input) {
  let record = new Map()

  for (let n = 0; n < input.length; n++) {
    let newClaim = new Claim(parseInput(input[n]))

    for (let i = newClaim.left; i < newClaim.left + newClaim.width; i++) {
      for (let j = newClaim.top; j < newClaim.top + newClaim.height; j++) {
        newClaim.coordinates.add(`${i}x${j}`)
        if (!record.has(`${i}x${j}`)) {
          record.set(`${i}x${j}`, 1)
        } else {
          record.set(`${i}x${j}`, record.get(`${i}x${j}`) + 1)
        }
      }
    }
  }

  let count = 0
  for (let val of record.values()) {
    if (val >= 2) {
      count++
    }
  }
  return count
}

I have record exist to keep a running list of points as keys and the value being the number of times it has been claimed. As we iterate through each claim, we add each point to a running list of points for that particular claim so we can see the number of times we have overlap. Then after we’ve done that, we go and see the number of points that have two or more claims to them. Though the big question is, was this the best we could do?

Part 2

The second part of the problem actually was much easier than the first for me! Though it is was exceptionally inefficient. It would take about 20-30 seconds for me to get an answer.

function part2(input) {
  let record = new Map()
  let someList = []

  for (let n = 0; n < input.length; n++) {
    let newClaim = new Claim(parseInput(input[n]))

    someList.push(newClaim)
    for (let i = newClaim.left; i < newClaim.left + newClaim.width; i++) {
      for (let j = newClaim.top; j < newClaim.top + newClaim.height; j++) {
        newClaim.coordinates.add(`${i}x${j}`)
        if (!record.has(`${i}x${j}`)) {
          record.set(`${i}x${j}`, 1)
        } else {
          record.set(`${i}x${j}`, record.get(`${i}x${j}`) + 1)
          someList.forEach(x => {
            if (x.coordinates.has(`${i}x${j}`)) {
              x.overLap = true
            }
          })
        }
      }
    }
  }

  return someList.find(x => x.overLap === false).id
}

With this approach, I ended up changing my algorithm. It is because I needed to somehow maintain which points haven’t had overlap and make sure to denote they now do. With this flow, I also had to somehow keep a running list of all the claims otherwise I would lose track of them after I created them. But I just added a simple overLap flag to each claim. When I go test a claim for no overlap, I see if it has no overlap with any other claims after it. This works but is *very**

After reflecting the next day, I thought of a different approach. I took advantage of my definition and changed it around slightly. Now it will include the calculation of the right and bottom point. The reason is because I went back to math! I went and drew out the relationship between the rectangles and saw how could I actually make sure that there is an overlap. Fortunately, we are working in a 2D plane so this becomes a less dauting approach.

My Claim class changed like so:

const Claim = (function() {
  let all = []
  let newClaim = function({ id, left, top, width, height }) {
    this.id = id
    this.left = left
    this.top = top
    this.right = left + width
    this.bottom = top + height
    this.width = width
    this.height = height
    this.overLap = false
    all.push(this)
  }

  newClaim.all = function() {
    return all.slice()
  }

  return newClaim
})()

We will now be utilizing a closure for our Claim so we can maintain a running list within the class. I also compute the right and bottom of the box so I know each point