Solution to Advent of Code 2020 Day 11 Part 2

AOC_2020_Day11_Part2.js

const { parseInputFile } = require('../utils/parser');

/**
 * @readonly
 * @enum {number}
 */
const Seat = {
    FLOOR: 0,
    EMPTY: 1,
    TAKEN: 2
};

/**
 * @readonly
 * @enum {Seat}
 */
const SeatLookup = {
    '.': Seat.FLOOR,
    'L': Seat.EMPTY,
    '#': Seat.TAKEN
};

/**
 * @typedef Sig Hash-like signature that identifies a distinct room configuration
 * @type {number}
 */

/**
 * @typedef Room
 * @type {object}
 * @property {Seat[][]} seats 2D array of seats in the room
 * @property {number} iteration Current iteration number
 * @property {Sig[]} trace Array of signatures representing all past states
 */

 /**
  * @param {Seat[][]} seats 
  * @returns {Room}
  */
function createRoom(seats) {
    return {
        seats,
        iteration: 0,
        trace: [ computeSig(seats) ]
    };
}

// parse input file into 2D aray
/** @type {Seat[][]} */
const initialSeats = parseInputFile('day11-input.txt', /^([\.L#]+)$/gm)
    .map(([_, line]) => Array.from(line).map(seatCode => SeatLookup[seatCode]))
;

function createFreshRoom() {
    return createRoom(initialSeats.map(row => Array.from(row)));
}

/**
 * @param {Seat[][]} seats 
 * @returns {Sig}
 */
function computeSig(seats) {
    let sig = 0;
    let i = 1;
    for (let y = 0; y < seats.length; y++) {
        const row = seats[y];
        const sigY = Math.max(Math.pow(y + 1, 3), 1);
        for (let x = 0; x < row.length; x++) {
            const sigX = Math.max(Math.pow(x + 1, 2), 1);
            sig = sig ^ (sigY * sigX * (row[x] + 1) * i);
            i++;
        }
    }
    return sig;
}

/**
 * @param {Seat[][]} seats 
 * @param {number} startX
 * @param {number} startY
 * @param {number} xOff
 * @param {number} yOff
 * @returns {number}
 */
function countRay(seats, startX, startY, xOff, yOff) {
    for (let x = startX + xOff, y = startY + yOff; y >= 0 && y < seats.length && x >= 0 && x < seats[y].length; x += xOff, y += yOff) {
        const seat = seats[y][x];
        if (seat !== Seat.FLOOR) {
            return (seats[y][x] === Seat.TAKEN) ? 1 : 0;
        }
    }
    return 0;
}

/**
 * @param {Seat[][]} seats 
 * @param {number} x 
 * @param {number} y 
 * @returns {number}
 */
function countAdjacentSeats(seats, x, y) {
    return (
        countRay(seats, x, y,  1,  0) +
        countRay(seats, x, y,  1,  1) +
        countRay(seats, x, y,  0,  1) +
        countRay(seats, x, y, -1,  1) +
        countRay(seats, x, y, -1,  0) +
        countRay(seats, x, y, -1, -1) +
        countRay(seats, x, y,  0, -1) +
        countRay(seats, x, y,  1, -1)
    );
}

/**
 * @param {Seat[][]} seats 
 * @param {number} x 
 * @param {number} y 
 * @returns {Seat}
 */
function getNextSeat(seats, x, y) {
    const seat = seats[y][x];

    // floor doesn't change
    if (seat === Seat.FLOOR) {
        return Seat.FLOOR;
    }

    const numAdjacentSeats = countAdjacentSeats(seats, x, y);
    if (seat === Seat.EMPTY) {
        return (numAdjacentSeats === 0) ? Seat.TAKEN : Seat.EMPTY;
    } else {
        return (numAdjacentSeats >= 5) ? Seat.EMPTY : Seat.TAKEN;
    }
}

/**
 * @param {Room} room
 * @returns {Sig} signature of this stage
 */
function simulateStage(room) {
    room.iteration++;

    const oldSeats = room.seats;
    const newSeats = oldSeats.map(row => Array.from(row));
    room.seats = newSeats;

    for (let y = 0; y < newSeats.length; y++) {
        const row = newSeats[y];
        for (let x = 0; x < row.length; x++) {
            row[x] = getNextSeat(oldSeats, x, y);
        }
    }

    const newSig = computeSig(newSeats);
    room.trace.push(newSig);

    return newSig;
}

/**
 * @param {Room} room
 */
function simulateToStable(room) {
    let lastSig = null;

    // loop until this trace shows up more than once
    while (room.trace.filter(s => s === lastSig).length < 2) {
        lastSig = simulateStage(room);

        console.log(`Iteration ${ room.iteration }: sig=${ lastSig }`);
    }
}

/**
 * @param {Seat[][]} seats
 * @returns {number}
 */
function countOccupiedSeats(seats) {
    let count = 0;
    for (let y = 0; y < seats.length; y++) {
        const row = seats[y];
        for (let x = 0; x < row.length; x++) {
            if (row[x] === Seat.TAKEN) {
                count++;
            }
        }
    }
    return count;
}

// Part 2
const part2Room = createFreshRoom();
simulateToStable(part2Room);
const part2Occupied = countOccupiedSeats(part2Room.seats);
console.log(`Part 2: Reached stability after ${ part2Room.iteration } rounds. Found ${ part2Occupied } occupied seats.`);