Solution to Advent of Code 2020 Day 17 that supports any arbitrary number of dimensions (version 2 - optimized)

AOC_2020-17_Ubounded2.js

const startTime = process.hrtime.bigint();

// Parameters
const DIMENSIONS = 6;
const ROUNDS = 6;

console.log(`Starting with ${ ROUNDS } rounds in ${ DIMENSIONS } dimensions.`);

/**
 * 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;
        }
    }

    /**
     * Gets the value stored at "i" if present.
     * If the value is not present or is undefined, then valueProducer is called.
     * The value returned by valueProducer is stored at "i" and returned.
     * 
     * @callback Producer Produces a value when invoked
     * @returns {TValue}
     * 
     * @param {number} i 
     * @param {Producer} valueProducer 
     */
    getOrSet(i, valueProducer) {
        let value = this.get(i);
        if (value === undefined) {
            value = valueProducer();
            this.set(i, value);
        }
        return 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;
    }
}

/**
 * @typedef {Axis<GridAxis | number | boolean>} GridAxis
 */

/**
 * @typedef {object} Grid
 * @property {GridAxis} axis0
 * @property {number[]} minBounds
 * @property {number[]} maxBounds
 * @property {number} numActiveCubes
 * @property {function} toString
 */

/**
 * @param {GridAxis} axis 
 * @param {GridAxis} newAxis 
 * @param {GridAxis} offAxis 
 * @param {number} d 
 * @param {boolean} prevIsLastOff 
 * @param {Grid} grid
 */
function getNextGridAt(axis, newAxis, offAxis, d, prevIsLastOff, grid) {
    // loop through the axis
    const pMin = grid.minBounds[d];
    const pMax = grid.maxBounds[d];
    for (let p = pMin; p <= pMax; p++) {

        // loop through each offset
        for (let off = -1; off <= 1; off++) {

            // check if this is the last offset (up to now)
            const isLastOff = prevIsLastOff && off === 1;

            // check if this is the last axis
            if (d === DIMENSIONS - 1) {
                // if it is, then update neighbors

                // skip neighbor calculation if offset is centered, AKA 0*
                if (axis === offAxis && off === 0) {
                    continue;
                }

                // if neighbor is active, then increment
                if (offAxis.get(p + off) === true) {
                    newAxis.set(p, (newAxis.get(p) || 0) + 1);
                }

                // if this is the last offset (and therefore last neighbor), then compute final value
                if (isLastOff) {
                    // get the number of neighbors found
                    const numActiveNeighbors = (newAxis.get(p) || 0);

                    // if cube is currently active
                    if (axis.get(p) === true) {
                        // stay active if 2 or 3 neighbors
                        const isActive = numActiveNeighbors === 2 || numActiveNeighbors === 3;

                        // update status
                        newAxis.set(p, isActive);
                        if (isActive) {
                            grid.numActiveCubes++;
                        }

                    // if cube is NOT active
                    } else {
                        // become active if 3 neighbors
                        const isActive = numActiveNeighbors === 3;

                        // update status
                        newAxis.set(p, isActive);
                        if (isActive) {
                            grid.numActiveCubes++;
                        }
                    }
                }
            } else {

                // compute values for next iteration
                // TODO move to top
                const nextAxis = axis.getOrSet(p, () => new Axis());
                const nextNewAxis = newAxis.getOrSet(p, () => new Axis());
                const nextOffAxis = offAxis.getOrSet(p + off, () => new Axis());

                // recurse
                getNextGridAt(nextAxis, nextNewAxis, nextOffAxis, d + 1, isLastOff, grid);
            }
        }
    }
}

function expandBounds(minBounds, maxBounds) {
    for (let i = 0; i < DIMENSIONS; i++) {
        minBounds[i]--;
        maxBounds[i]++;
    }
}

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

    expandBounds(grid.minBounds, grid.maxBounds);
    getNextGridAt(grid.axis0, newAxis0, grid.axis0, 0, true, grid);

    return newAxis0;
}

/*
 * part 2
 */

// Parse input data
/** @type {number[]} */
const initialMinBounds = [];
/** @type {number[]} */
const initialMaxBounds = [];
/** @type {GridAxis} */
const initialAxis0 = new Axis();
let initialXAxis = initialAxis0;
for (let d = 0; d < DIMENSIONS - 2; d++) {
    initialXAxis = initialXAxis.getOrSet(0, () => new Axis());
}
require('fs').readFileSync('day17-test.txt', 'utf-8').split('\r\n').forEach((line, x) => Array.from(line).forEach((cell, y) => {
    const isActive = cell === '#';
    initialXAxis.getOrSet(x, () => new Axis()).set(y, isActive);
}));
for (let i = 0; i < DIMENSIONS; i++) {
    // initial min bounds are all zero
    initialMinBounds.push(0);

    if (i < DIMENSIONS - 2) {
        // initial max is zero for axis > XY
        initialMaxBounds.push(0);

    } else {
        if (i === DIMENSIONS - 2) {
            // X axis
            initialMaxBounds.push(initialXAxis.length - 1);

        } else {
            // Y axis
            initialMaxBounds.push(
                initialXAxis.toArray().map(axis => axis.length - 1).reduce((max, curr) => curr > max ? curr : max, 0)
            );
        }
    }
}

/**
 * @param {GridAxis} axis0 
 * @param {number[]} maxBounds 
 * @param {number[]} minBounds 
 * @param {number} numActiveCubes
 * @returns {Grid}
 */
function createGrid(axis0, maxBounds, minBounds, numActiveCubes) {
    return {
        axis0,
        minBounds: Array.from(minBounds),
        maxBounds: Array.from(maxBounds),
        numActiveCubes,
        toString() {
            const parts = [];
        
            /**
             * @param {GridAxis} axis 
             * @param {number} d 
             * @param {number[]} coords 
             */
            const toStringAt = (axis, d, coords) => {
                if (d < DIMENSIONS - 2) {
                    // if this is a middle axis, then recurse
                    for (let c = this.minBounds[d]; c <= this.maxBounds[d]; c++) {
                        const nextCoords = [ ...coords, c ];
                        toStringAt(axis.get(c) || new Axis(), d + 1, nextCoords);
                    }
                } else {
                    // if this is the last 2 axis, then print grid
                    const gridParts = [ `At [${ coords.join(', ') }, *, *]` ];
                    for (let x = this.minBounds[DIMENSIONS - 2]; x <= this.maxBounds[DIMENSIONS - 2]; x++) {
                        const yAxis = axis === undefined ? undefined : axis.get(x);
                        const rowParts = [];
                        for (let y = this.minBounds[DIMENSIONS - 1]; y <= this.maxBounds[DIMENSIONS - 1]; y++) {
                            if (yAxis === undefined) {
                                rowParts.push('.');
                            } else {
                                rowParts.push(yAxis.get(y) === true ? '#' : '.');
                            }
                        }
                        gridParts.push(rowParts.join(''));
                    }
                    parts.push(gridParts.join('\n'));
                    /*parts.push(`At [${ coords.join(', ') }, *, *]\n${ 
                        axis.toArray()
                        .map(innerAxis => (innerAxis || new Axis()).toArray()
                            .map(active => active ? '#' : '.')
                            .join('')
                        )
                        .join('\n')
                    }`);*/
                }
            };
            toStringAt(this.axis0, 0, []);
        
            return parts.join('\r\n');
        }
    };
}

// Do rounds
let grid = createGrid(initialAxis0, initialMaxBounds, initialMinBounds, 0);
//console.log(`Initial grid:`);
//console.log(grid.toString());
//console.log('\n');
(function () {
    // simulate rounds
    for (let round = 0; round < ROUNDS; round++) {
        //console.log(`Starting round ${ round + 1 }: `);

        // simulate
        grid.numActiveCubes = 0;
        const newAxis0 = getNextGrid(grid);
        grid = createGrid(newAxis0, grid.maxBounds, grid.minBounds, grid.numActiveCubes);

        //console.log(grid.toString());
        //console.log(`After round ${ round + 1 }: ${ grid.numActiveCubes } active cubes.`);
    }
})();

// Get answer
const answer = grid.numActiveCubes;
const endTime = process.hrtime.bigint();

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

const totalTimeS = Number((endTime / 1000000n) - (startTime / 1000000n)) / 1000;
console.log(`Total time: ${ totalTimeS.toFixed(3) }s`);

const simTimeRoundS = totalTimeS / ROUNDS;
console.log(`Time per round: ${ simTimeRoundS.toFixed(3) }s`);