Solution to Advent of Code 2020 Day 17 that supports an arbitary number of dimensions

AOC_2020-17_Unbounded1.js

const startTime = process.hrtime.bigint();

// Parameters
const DIMENSIONS = 5;
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;
    }
}

/**
 * Infinite 4D grid of cube states
 */
class Grid {
    /** @param {number} dimensions */
    constructor(dimensions) {
        if (this.dimensions < 1) throw new Error('Number of dimensions must be greater than zero');

        /**
         * @typedef {Axis<GridAxis | boolean>} GridAxis
         * @type {GridAxis} */
        this._axis0 = new Axis();

        /** @type {number[]} */
        this.minBounds = [];
        /** @type {number[]} */
        this.maxBounds = [];

        for (let d = 0; d < dimensions; d++) {
            this.minBounds.push(0);
            this.maxBounds.push(0);
        }

        this.dimensions = dimensions;
    }

    /**
     * @param {...number} coords 
     * @returns {boolean}
     */
    isCubeActive(...coords) {
        //console.log('coords', coords);
        if (coords.length !== this.dimensions) throw new Error(`Invalid args: wrong number of coords: ${ coords.length }`);

        let axis = this._axis0;
        for (let d = 0; d < coords.length - 1; d++) {
            axis = axis.get(coords[d]);
            if (!axis) return false;
        }
        return axis.get(coords[coords.length - 1]) || false;
    }

    /**
     * @param {boolean} active 
     * @param {...number} coords 
     */
    setCubeActive(active, ...coords) {
        if (coords.length !== this.dimensions) throw new Error(`Invalid args: wrong number of coords: ${ coords.length }`);

        // find innermost axis
        for (let d = 0, axis = this._axis0; d < coords.length; d++) {
            const coord = coords[d];
            
            // update bounds
            if (coord < this.minBounds[d]) {
                this.minBounds[d] = coord;
            }
            if (coord > this.maxBounds[d]) {
                this.maxBounds[d] = coord;
            }
            
            if (d < coords.length - 1) {
                // keep moving to find final axis
                axis = axis.getOrSet(coord, () => new Axis());

            } else {

                // update value
                axis.set(coords[coords.length - 1], active);
            }
        }
    }

    _countActiveCubesAt(axis, d) {
        let activeCubes = 0;
        for (let p = this.minBounds[d]; p <= this.maxBounds[d]; p++) {
            if (d < this.dimensions - 1) {
                // recurse for next axis
                activeCubes += this._countActiveCubesAt(axis.get(p), d + 1);

            } else {
                // count cubes
                if (axis.get(p) === true) {
                    activeCubes++;
                }
            }
        }
        return activeCubes;
    }

    /** @returns {number} */
    countActiveCubes() {
        return this._countActiveCubesAt(this._axis0, 0);
    }

    _toStringGrid(yAxis) {
        return yAxis.toArray()
            .map(xAxis => xAxis.toArray()
                .map(active => active ? '#' : '.')
                .join('')
            )
            .join('\n')
        ;
    }

    _toStringMiddle(axis, d, coords, parts) {
        if (d < this.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 ];
                this._toStringMiddle(axis.get(c), d + 1, nextCoords, parts);
            }
        } else {
            // if not a middle axis, then move to grid
            parts.push(`At [${ coords.join(', ') }, *, *]\n${ this._toStringGrid(axis)}`);
        }
    }

    /** @returns {string} */
    toString() {
        const parts = [];
        this._toStringMiddle(this._axis0, 0, [], parts);
        return parts.join('\n\n');
    }
}

// pre-generate directions table
const directions = [];
(function () {
    // Adds a coordinate to the directions generation
    function generateDirectionsAt(d, coords) {
        // Generate offsets for this axis
        const c0 = [ ...coords, -1 ];
        const c1 = [ ...coords,  0 ];
        const c2 = [ ...coords,  1 ];

        if (d === DIMENSIONS - 1) {
            // If this is the last axis, then insert directions
            directions.push(c0);
            directions.push(c1);
            directions.push(c2);
        } else {
            // If not the last axis, then recurse for each possible offset
            generateDirectionsAt(d + 1, c0);
            generateDirectionsAt(d + 1, c1);
            generateDirectionsAt(d + 1, c2);
        }
    }

    // Kick off at axis 0
    generateDirectionsAt(0, []);

    // Remove the center point (where all axis = 0)
    directions.splice(directions.findIndex(coords => coords.every(c => c === 0)), 1);
})();
//console.log('directions', directions);

function computeChanges(grid) {
    const changes = [];

    return changes;
}

//function getNextGridAt(axis, newAxis, offAxis, d, coords) {
    // loop through axis
    // loop through offset
        // compute current coords

        // if at the last axis
            // if offset cell is active, then increment

        // else
            // recurse
            // if completed, then break
//}

function getNextGridAt(grid, newGrid, d, coords) {
    // Loop through this entire axis
    for (let p = grid.minBounds[d] - 1; p <= grid.maxBounds[d] + 1; p++) {
        // Add current coord
        const coordsHere = [ ...coords, p ];

        if (d < DIMENSIONS - 1) {
            // recurse to next axis
            getNextGridAt(grid, newGrid, d + 1, coordsHere);

        } else {
            //console.log(`d=${d} coords=[${coordsHere.join(',')}]`);
            // we have reached a cube, lets do stuff

            // Count active neighbors
            let activeNeighbors = 0;
            for (const offset of directions) {
                const nCoords = coordsHere.map((p, i) => p + offset[i]);
                
                // if cube is active, then count it
                if (grid.isCubeActive(...nCoords)) {
                    activeNeighbors++;
                }

                // short circuit when we reach the max that matter
                if (activeNeighbors.length >= 3) {
                    break;
                }
            }

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

/**
 * @param {Grid} grid
 * @returns {Grid}
 */
function getNextGrid(grid) {
    const newGrid = new Grid(DIMENSIONS);
    getNextGridAt(grid, newGrid, 0, []);
    return newGrid;
}

/*
 * part 2
 */

// Parse input data
const initialGrid = new Grid(DIMENSIONS);
require('fs').readFileSync('test.txt', 'utf-8').split('\r\n').forEach((line, x) => Array.from(line).forEach((cell, y) => {
    const isActive = cell === '#';
    const coords = [];
    for (let d = 0; d < DIMENSIONS - 2; d++) {
        coords.push(0);
    }
    coords.push(x);
    coords.push(y);

    initialGrid.setCubeActive(isActive, ...coords);
}));

//console.log('initialGrid', initialGrid);
//console.log(`Initial Grid:\n${ initialGrid }`);

// Do rounds
let currentGrid = initialGrid;
for (let round = 0; round < ROUNDS; round++) {
    currentGrid = getNextGrid(currentGrid);
    //console.log(`After round ${ round + 1}:\n${ currentGrid }`);
}

// Get answer
const startCountTime = process.hrtime.bigint();
const answer = currentGrid.countActiveCubes();
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 simTimeS = Number((startCountTime / 1000000n) - (startTime / 1000000n)) / 1000;
const simTimePercent = (simTimeS / totalTimeS) * 100;
console.log(`Sim time (total): ${ simTimeS.toFixed(3) }s / ${ simTimePercent.toFixed(1) }%`);

const simTimeRoundS = simTimeS / ROUNDS;
const simTimeRoundPercent = (simTimeRoundS / totalTimeS) * 100;
console.log(`Sim time (per round): ${ simTimeRoundS.toFixed(3) }s / ${ simTimeRoundPercent.toFixed(1) }%`);

const countTimeS = Number((endTime / 1000000n) - (startCountTime / 1000000n)) / 1000;
const countTimePercent = (countTimeS / totalTimeS) * 100;
console.log(`Counting time: ${ countTimeS.toFixed(3) }s / ${ countTimePercent.toFixed(1) }%`);