Solution to Advent of Code 2020 Day 17 Part 2

AOC_2020-17-2.js

/**
 * An array-like structure that extends infinitely in both positive and negative directions
 * @template TValue Type of value stored in this Axis
 */
class Axis {
    constructor() {
        /** @type {TValue[]} */
        this._posArray = [];
        /** @type {TValue[]} */
        this._negArray = [];
    }

    /**
     * Gets a value from this Axis
     * @param {number} i Index to get
     * @returns {TValue} Value stored at this position, or undefined if not specified
     */
    get(i) {
        if (i < 0) {
            i = -1 - i;
            return this._negArray[i];
        } else {
            return this._posArray[i];
        }
    }

    /**
     * Stores a value in this Axis
     * @param {number} i Index to set
     * @param {TValue} value Value to store at this position
     */
    set(i, value) {
        if (i < 0) {
            i = -1 - i;
            this._negArray[i] = value;
        } else {
            this._posArray[i] = value;
        }
    }

    /**
     * Checks if a value is stored at the specified index.
     * @param {number} i Index to check
     * @returns {boolean} True if a value exists for the index, false otherwise
     */
    has(i) {
        return this.length > 0 && i >= this.min && i <= this.max;
    }

    /**
     * Returns an array containing all elements of this Axis.
     * @returns {TValue[]}
     */
    toArray() {
        return Array.from(this._negArray).reverse().concat(Array.from(this._posArray));
    }

    /**
     * Gets the total number of elements stored in this Axis.
     * @returns {number} Number of elements in this Axis
     */
    get length() {
        return this._posArray.length + this._negArray.length;
    }

    /**
     * Gets the lowest index with a value defined.
     * Returns 0 if there is none.
     * @returns {number} Lowest index or 0
     */
    get min() {
        return 0 - this._negArray.length;
    }

    /**
     * Gets the highest index with a value defined.
     * Returns -1 if there is none.
     * @returns {number} Highest index or -1
     */
    get max() {
        return this._posArray.length - 1;
    }
}

/**
 * Infinite 4D grid of cube states
 */
class Grid {
    constructor() {
        /** @type {Axis<Axis<Axis<Axis<boolean>>>>} */
        this._grid = new Axis();
        this.minW = 0;
        this.maxW = 0;
        this.minZ = 0;
        this.maxZ = 0;
        this.minX = 0;
        this.maxX = 0;
        this.minY = 0;
        this.maxY = 0;
    }

    /**
     * 
     * @param {number} x 
     * @param {number} y 
     * @param {number} z 
     * @param {number} w 
     * @returns {boolean}
     */
    isCubeActive(x, y, z, w) {
        const cube = this._grid.get(w);
        if (!cube) return false;
        const slice = cube.get(z);
        if (!slice) return false;
        const row = slice.get(x);
        if (!row) return false;
        const value = row.get(y);
        return value !== undefined ? value : false;
    }

    /**
     * @param {number} x 
     * @param {number} y 
     * @param {number} z 
     * @param {number} w 
     * @param {boolean} active 
     */
    setCubeActive(x, y, z, w, active) {
        // update bounts
        if (x < this.minX) {
            this.minX = x;
        }
        if (x > this.maxX) {
            this.maxX = x;
        }
        if (y < this.minY) {
            this.minY = y;
        }
        if (y > this.maxY) {
            this.maxY = y;
        }
        if (z < this.minZ) {
            this.minZ = z;
        }
        if (z > this.maxZ) {
            this.maxZ = z;
        }
        if (w < this.minW) {
            this.minW = w;
        }
        if (w > this.maxW) {
            this.maxW = w;
        }

        const row = this.getRow(x, z, w);
        row.set(y, active);
    }

    /**
     * @param {number} w 
     * @returns {Axis<Axis<Axis<boolean>>>}
     */
    getCube(w) {
        let cube = this._grid.get(w);
        if (!cube) {
            cube = new Axis();
            this._grid.set(w, cube);
        }
        return cube;
    }

    /**
     * @param {number} z 
     * @param {number} w
     * @returns {Axis<Axis<boolean>>}
     */
    getSlice(z, w) {
        const cube = this.getCube(w);
        let slice = cube.get(z);
        if (!slice) {
            slice = new Axis();
            cube.set(z, slice);
        }
        return slice;
    }

    /**
     * @param {number} x 
     * @param {number} z 
     * @param {number} w
     * @returns {Axis<boolean>}
     */
    getRow(x, z, w) {
        const slice = this.getSlice(z, w);
        let row = slice.get(x);
        if (!row) {
            row = new Axis();
            slice.set(x, row);
        }
        return row;
    }

    /** @returns {number} */
    countActiveCubes() {
        return this._grid.toArray()
            .map(cube => cube.toArray()
                .map(slice => slice.toArray()
                    .map(row => row.toArray()
                        .map(active => active === true ? 1 : 0)
                    )
                )
            )
            .flat(4)
            .reduce((sum, active) => sum + active, 0)
        ;
    }

    /** @returns {string} */
    toString() {
        return this._grid.toArray()
            .map((cube, wOff) => 
                cube.toArray()
                .map((slice, zOff) => 
                    [
                        `W=${ this._grid.min + wOff }, Z=${ cube.min + zOff }`,
                        ...slice.toArray()
                        .map(row => row.toArray()
                            .map(active => active ? '#' : '.')
                            .join('')
                        )
                    ]
                    .join('\n')
                )
                .join('\n\n')
            )
            .join('\n\n')
        ;
    }
}

/**
 * Lookup of all possible neighbors in Y,X,Z,W order.
 * Entries are arranged to simulate the view of each layer (XY plane) from above.
 * @type {[ -1|0|1, -1|0|1, -1|0|1, -1|0|1 ][]}
 */
const DIRECTIONS = [
    // W = -1
    [ -1, -1,  1, -1 ], [  0, -1,  1, -1 ], [  1, -1,  1, -1 ],
    [ -1,  0,  1, -1 ], [  0,  0,  1, -1 ], [  1,  0,  1, -1 ],
    [ -1,  1,  1, -1 ], [  0,  1,  1, -1 ], [  1,  1,  1, -1 ],
    
    [ -1, -1,  0, -1 ], [  0, -1,  0, -1 ], [  1, -1,  0, -1 ],
    [ -1,  0,  0, -1 ], [  0,  0,  0, -1 ],  [  1,  0,  0, -1 ],
    [ -1,  1,  0, -1 ], [  0,  1,  0, -1 ], [  1,  1,  0, -1 ],
    
    [ -1, -1, -1, -1 ], [  0, -1, -1, -1 ], [  1, -1, -1, -1 ],
    [ -1,  0, -1, -1 ], [  0,  0, -1, -1 ], [  1,  0, -1, -1 ],
    [ -1,  1, -1, -1 ], [  0,  1, -1, -1 ], [  1,  1, -1, -1 ],
    
    // W = 0
    [ -1, -1,  1,  0 ], [  0, -1,  1,  0 ], [  1, -1,  1,  0 ],
    [ -1,  0,  1,  0 ], [  0,  0,  1,  0 ], [  1,  0,  1,  0 ],
    [ -1,  1,  1,  0 ], [  0,  1,  1,  0 ], [  1,  1,  1,  0 ],
    
    [ -1, -1,  0,  0 ], [  0, -1,  0,  0 ], [  1, -1,  0,  0 ],
    [ -1,  0,  0,  0 ],                     [  1,  0,  0,  0 ],
    [ -1,  1,  0,  0 ], [  0,  1,  0,  0 ], [  1,  1,  0,  0 ],
    
    [ -1, -1, -1,  0 ], [  0, -1, -1,  0 ], [  1, -1, -1,  0 ],
    [ -1,  0, -1,  0 ], [  0,  0, -1,  0 ], [  1,  0, -1,  0 ],
    [ -1,  1, -1,  0 ], [  0,  1, -1,  0 ], [  1,  1, -1,  0 ],

    // W = 1
    [ -1, -1,  1,  1 ], [  0, -1,  1,  1 ], [  1, -1,  1,  1 ],
    [ -1,  0,  1,  1 ], [  0,  0,  1,  1 ], [  1,  0,  1,  1 ],
    [ -1,  1,  1,  1 ], [  0,  1,  1,  1 ], [  1,  1,  1,  1 ],
    
    [ -1, -1,  0,  1 ], [  0, -1,  0,  1 ], [  1, -1,  0,  1 ],
    [ -1,  0,  0,  1 ], [  0,  0,  0,  1 ], [  1,  0,  0,  1 ],
    [ -1,  1,  0,  1 ], [  0,  1,  0,  1 ], [  1,  1,  0,  1 ],
    
    [ -1, -1, -1,  1 ], [  0, -1, -1,  1 ], [  1, -1, -1,  1 ],
    [ -1,  0, -1,  1 ], [  0,  0, -1,  1 ], [  1,  0, -1,  1 ],
    [ -1,  1, -1,  1 ], [  0,  1, -1,  1 ], [  1,  1, -1,  1 ],
];

// Parse input data
const initialGrid = new Grid();
require('fs').readFileSync('day17-input.txt', 'utf-8').split('\r\n').forEach((line, x) => Array.from(line).forEach((cell, y) => {
    const isActive = cell === '#';
    initialGrid.setCubeActive(x, y, 0, 0, isActive);
}));

/**
 * @param {Grid} grid
 * @returns {Grid}
 */
function getNextGrid(grid) {
    const newGrid = new Grid();

    // Loop through each axis
    for (let w = grid.minW - 1; w <= grid.maxW + 1; w++) {
        for (let z = grid.minZ - 1; z <= grid.maxZ + 1; z++) {
            for (let x = grid.minX - 1; x <= grid.maxX + 1; x++) {
                for (let y = grid.minY - 1; y <= grid.maxY + 1; y++) {

                    // Count active neighbors
                    let activeNeighbors = 0;
                    for (const [ yOff, xOff, zOff, wOff ] of DIRECTIONS) {
                        const nX = x + xOff;
                        const nY = y + yOff;
                        const nZ = z + zOff;
                        const nW = w + wOff;
                        
                        if (grid.isCubeActive(nX, nY, nZ, nW)) {
                            activeNeighbors++;
                        }
                    }

                    // get new status
                    if (grid.isCubeActive(x, y, z, w)) {
                        // Stay active 2 or 3 neighbors are active
                        const active = activeNeighbors === 2 || activeNeighbors === 3;
                        newGrid.setCubeActive(x, y, z, w, active);
                    } else {
                        // Become active if exactly three neighbors are active
                        const active = activeNeighbors === 3;
                        newGrid.setCubeActive(x, y, z, w, active);
                    }
                }
            }
        }
    }

    return newGrid;
}

// part 2
let currentGrid = initialGrid;
for (let round = 0; round < 6; round++) {
    currentGrid = getNextGrid(currentGrid);
}

const answer = currentGrid.countActiveCubes();
console.log(`Part 2: Found ${ answer } active cubes.`);