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
seatsarray and throw it intopreviousSeats.previousSeatswill 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 noTAKEN_SEATaround it, then we put a butt in the seat. - If the current position is a
TAKEN_SEAT, and there are more than 4TAKEN_SEATaround it, then that butt moves.
- If the position is not the
- If the
newSeatdoesn’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:
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.
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.
RSS - Posts
Leave a Reply