Advent of Code, Day 11

Day 11 of Advent of Code is here! We’re almost half way through! Check out Day 1 for what this is all about. See all of my solutions here.

Do your best!

I highly encourage you to get through the day’s challenge on your own. Certainly refer to this and other’s examples to help you get through. I would love to hear how you did! Did you find a better approach than I did? Do tell!

Running in NodeJS

I’ve moved from dev console to using NodeJS for my challenges. This will provide us with more capabilities to identify issues in our code much faster. Learn more about the move here. As a result, my input and scripts can be found on github.

Day 11: Seating System

Part I

“By modeling the process people use to choose (or abandon) their seat in the waiting area, you’re pretty sure you can predict the best place to sit. You make a quick map of the seat layout (your puzzle input).

The seat layout fits neatly on a grid. Each position is either floor (.), an empty seat (L), or an occupied seat (#). How many seats end up occupied?ref

Here’s a sampling of the seats

That doesn’t look like a fun airport… Before we loop, let’s get pull this data in

const fs = require('fs');
const seats = fs.readFileSync('./input.txt', 'utf-8').trim().split('\n')

Nothing fancy today, just getting all rows into an array.

The logic is rather straight forward, just grab the seats around this seat and see what’s open

const TAKEN_SEAT = '#'
const OPEN_SEAT = 'L'
const FLOOR = '.'

let seatsChanged = false
let loopCounter = 0
let previousSeats = [...seats]
do {
  const newSeats = []
  seatsChanged = false
  console.log(previousSeats)
  for(let row = 0; row < previousSeats.length; row += 1) {
    newSeats.push('')
    for(let col = 0; col < previousSeats[row].length; col += 1) {
      const theSeat = previousSeats[row][col]
      let newSeat = theSeat
      if(theSeat !== FLOOR) {
        const adjacentSeats = getAdjacentSeats(previousSeats, row, col)
        if(theSeat === OPEN_SEAT) {
          if(adjacentSeats.takenSeats === 0) {
            newSeat = TAKEN_SEAT
          }
        }
        if(theSeat === TAKEN_SEAT) {
          if(adjacentSeats.takenSeats >= 4) {
            newSeat = OPEN_SEAT
          }
        }
      } else {
        newSeat = FLOOR
      }
      if(newSeat !== theSeat) seatsChanged = true
      newSeats[row] = `${newSeats[row]}${newSeat}`
    }
  }
  previousSeats = [...newSeats]
  loopCounter += 1

Here’s what we got:

  • You’ll see some variables at the top. The ones in all caps is an older style of coding, that I think still applies nowadays, at least my eslint didn’t error about it. In all caps it tells developers that these are constants, never changing, usually just static values. This is easier instead of using the actual string everywhere. The other variables are data variables, they might change or could change.
  • Using a do while seats are changed. When they stop changing, then we have the final layout. This loop handles each attempt at matching all the seats.
  • Right before the do while, we grab the seats array and throw it into previousSeats. previousSeats will be overwritten on each loop. The requirements state to say that the assessment happens all at once, the “rules are applied to every seat simultaneously”. We can’t start with one, calculate, update the array, then do the next one. We have to treat each one as if they all ran at the same time. I am handling this by creating a copy of the array, then create a new array for the new seats. Any checking and processing happens on the previous array.
  • We then loop through each row and column.
    • If the position is not the FLOOR, we then get a count of the adjacent seats (function below).
    • If the current position is an OPEN_SEAT, and there are no TAKEN_SEAT around it, then we put a butt in the seat.
    • If the current position is a TAKEN_SEAT, and there are more than 4 TAKEN_SEAT around it, then that butt moves.
  • If the newSeat doesn’t match the current seat we’re on, then seats changed, and we want to keep looping
  • Finally we append this seat to the same row so we can remake the same array with the new seats

Something fun to try, put a breakpoint on line 12 and debug it. This will print out your entire seating area after each loop. You can watch your calculations in action, one loop at a time:

part 1 looping

My test took 72 loops to find the answer.

Oh yea, the getAdjacentSeats method:

const getAdjacentSeats = (seatArray, row, col) => {
  const adjacentSeats = []
  if(row > 0) {
    const rowAbove = seatArray[row - 1]
    adjacentSeats.push(rowAbove[col - 1]) // top left
    adjacentSeats.push(rowAbove[col]) // top middle
    adjacentSeats.push(rowAbove[col + 1]) // top right
  }

  adjacentSeats.push(seatArray[row][col - 1]) // left seat
  adjacentSeats.push(seatArray[row][col + 1]) // right seat

  if(row < seatArray.length - 1) {
    const rowBelow = seatArray[row+1]
    adjacentSeats.push(rowBelow[col - 1]) // bottom left
    adjacentSeats.push(rowBelow[col]) // bottom middle
    adjacentSeats.push(rowBelow[col + 1]) // bottom right
  }

  return { takenSeats: adjacentSeats.filter(s => s === TAKEN_SEAT).length, openSeats: adjacentSeats.filter(s => s === OPEN_SEAT).length }
}

We take that array, and check the row above, the current row, and the row below, for the seats. Pretty straight forward.

I returned a function with takenSeats and openSeats. We never use openSeats, I thought I was being crafty thinking for Part II… I wasn’t even close.

Part II

“Now, instead of considering just the eight immediately adjacent seats, consider the first seat in each of those eight directions. Also, people seem to be more tolerant than you expected: it now takes five or more visible occupied seats for an occupied seat to become empty. how many seats end up occupied?

So we’re widening our scope, giving us a little more room around each other, which is good considering the pandemic. The line of sight is important to keep in mind. I think of it like the Queen when playing chess. You can only move in a straight line up or down, left or right, or diagonally, and you have to stop when you hit another chess piece (or a seat in this case)

The first part here is VERY similar to Part 1. Some small changes, more console.logs which make debugging and visualizing the issue a little easier.

let seatsChanged = false
let loopCounter = 0
let previousSeats = [...seats]
do {
  console.log('loop', loopCounter)
  console.log(previousSeats)
  const newSeats = []
  seatsChanged = false
  for(let row = 0; row < previousSeats.length; row += 1) {
    newSeats.push('')
    for(let col = 0; col < previousSeats[row].length; col += 1) {
      const theSeat = previousSeats[row][col]
      let newSeat = theSeat
      if(theSeat !== FLOOR) {
        const visibleSeats = getLineOfSightSeats(previousSeats, row, col)
        if(theSeat === OPEN_SEAT) {
          if(visibleSeats === 0) {
            newSeat = TAKEN_SEAT
          }
        }
        if(theSeat === TAKEN_SEAT) {
          if(visibleSeats >= 5) {
            newSeat = OPEN_SEAT
          }
        }
      } else {
        newSeat = FLOOR
      }
      if(newSeat !== theSeat) seatsChanged = true
      newSeats[row] = `${newSeats[row]}${newSeat}`
    }
  }
  previousSeats = [...newSeats]
  loopCounter += 1
} while (seatsChanged)

The changes are at line 15 and 22. The new method getLineOfSightSeats is larger (below) and the new requirement for how many seats we’ll accept, up from 4.

const getLineOfSightSeats = (seatArray, row, col) => {
  const takenSeats = []
  let leftDiagonal = col
  let rightDiagonal = col
  let hasLeftDiag = false
  let hasStraight = false
  let hasRightDiag = false
  for(let topRows = row - 1; topRows >= 0; topRows -= 1) {
    const topRow = seatArray[topRows]
    leftDiagonal -= 1
    rightDiagonal += 1
    if(!hasLeftDiag && topRow[leftDiagonal] !== FLOOR) {
      takenSeats.push(topRow[leftDiagonal])
      hasLeftDiag = true
    }
    if(!hasStraight && topRow[col] !== FLOOR) {
      takenSeats.push(topRow[col])
      hasStraight = true
    }
    if(!hasRightDiag && topRow[rightDiagonal] !== FLOOR) {
      takenSeats.push(topRow[rightDiagonal])
      hasRightDiag = true
    }
    if(hasLeftDiag && hasStraight && hasRightDiag) break
  }

  leftDiagonal = col
  rightDiagonal = col
  hasLeftDiag = false
  hasStraight = false
  hasRightDiag = false
  for(let bottomRows = row + 1; bottomRows < seatArray.length; bottomRows += 1) {
    const bottomRow = seatArray[bottomRows]
    leftDiagonal -= 1
    rightDiagonal += 1
    if(!hasLeftDiag && bottomRow[leftDiagonal] !== FLOOR) {
      takenSeats.push(bottomRow[leftDiagonal])
      hasLeftDiag = true
    }
    if(!hasStraight && bottomRow[col] !== FLOOR) {
      takenSeats.push(bottomRow[col])
      hasStraight = true
    }
    if(!hasRightDiag && bottomRow[rightDiagonal] !== FLOOR) {
      takenSeats.push(bottomRow[rightDiagonal])
      hasRightDiag = true
    }
    if(hasLeftDiag && hasStraight && hasRightDiag) break
  }
  
  let hasRight = false
  let hasLeft = false
  let rightCounter = col
  let leftCounter = col
  while(!hasRight || !hasLeft) {
    const myRow = seatArray[row]
    rightCounter += 1
    leftCounter -= 1
    if(leftCounter < 0) hasLeft = true
    if(rightCounter >= myRow.length) hasRight = true
    if(!hasLeft && myRow[leftCounter] !== FLOOR) {
      takenSeats.push(myRow[leftCounter])
      hasLeft = true
    }
    if(!hasRight && myRow[rightCounter] !== FLOOR) {
      takenSeats.push(myRow[rightCounter])
      hasRight = true
    }
    if(hasLeft && hasRight) break
  }
  return takenSeats.filter(s => s === TAKEN_SEAT).length
}

At the core, this is looping from the current row and column position, from the current seat. It loops up the topRows to find the first seat that is left, straight up, and right, then loop through bottomRows doing the same. Finally, it loops through the row the seat is on, left and right. It’s just more code, not really more complexity.

part 2 looping

This one took 87 loops to finish. Nice and fast.

How did it go for you?

How did you find the answer on your own? How did you do it? Anything stump you? I’d love to hear how you did! Please comment below! I have also loaded up just the challenge and code from this and my other days on github, you can follow along there too: pretty Git pages or the code in the repo.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a free website or blog at WordPress.com.

Up ↑

%d bloggers like this: