Solution to Advent of Code 2020 Day 20

AOC_2020-20.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;
        }
    }

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

    /**
     * Creates an Axis instance from a plain object.
     * The object must have _minArray and _maxArray properties.
     * @template TValue Type of Axis to create
     * @param {object} object Object to create
     * @returns {Axis<TValue>}
     */
    static create(object) {
        Object.setPrototypeOf(object, this.prototype);
        return object;
    }
}

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

const INPUT_FILE = 'day20-input.txt';
const TILE_SIZE = 10;
const SEA_MONSTER_WIDTH = 20;
const SEA_MONSTER_HEIGHT = 3;
const SEA_MONSTER_SEQUENCE = [
    [  1,  0 ],
    [  1,  1 ],
    [  0,  3 ],
    [ -1,  1 ],
    [  0,  1 ],
    [  1,  1 ],
    [  0,  3 ],
    [ -1,  1 ],
    [  0,  1 ],
    [  1,  1 ],
    [  0,  3 ],
    [ -1,  1 ],
    [ -1,  1 ],
    [  1,  0 ],
    [  0,  1 ]
];

/**
 * @typedef {boolean[][]} Bitmap 2D array of image data
 */
/**
 * @typedef {number} Edge Number representing the exact configuration of pixels on an edge of a bitmap.
 */
/**
 * @typedef {object} Edges Edge data for all edges of a bitmap
 * @property {Edge} top The top edge
 * @property {Edge} right The right edge
 * @property {Edge} bottom The bottom edge
 * @property {Edge} left The left edge
 */
/**
 * @typedef {object} Tile A tile from the satelite imagery
 * @property {number} tileID ID of the tile
 * @property {Bitmap} bitmap Image data.
 * @property {number} tileSize Dimensions of each axis
 */
/**
 * @typedef {object} MovingTile A tile that can be flipped or rotated
 * @property {number} tileID ID of the tile
 * @property {function} getBit Gets a bit at the specified location
 * @property {function} getTopEdge Gets the top edge
 * @property {function} getRightEdge Gets the right edge
 * @property {function} getBottomEdge Gets the bottom edge
 * @property {function} getLeftEdge Gets the left edge
 * @property {function} flipY Flips the tile accross the Y axis
 * @property {function} flipX Flips the tile accross the X axis
 * @property {function} rotateRight Rotates the tile right
 * @property {function} rotateLeft Rotates the tile left
 * @property {number} _rotation 0 = normal, 1 = 90, 2 = 180, 3 = 270 (clockwise)
 * @property {boolean} _flippedX If true, tile is flipped across X axis
 * @property {boolean} _flippedY If true, tile is flipped across Y axis
 * @property {function} toString
 * @property {function} toBorderlessTile
 * 
 */

/** @param {MovingTile} tile @param {number} startX @param {number} startY @param {number} lenX @param {number} lenY @returns {string} */
function getEdge(tile, startX, startY, lenX, lenY) {
    /** @type {string[]} */
    const edgeArr = [];
    for (let yOff = 0; yOff < lenY; yOff++) {
        for (let xOff = 0; xOff < lenX; xOff++) {
            const y = startY + yOff;
            const x = startX + xOff;
            edgeArr.push(tile.getBit(x, y) ? '#' : '.');
        }
    }
    //return parseInt(edgeArr.map(bit => bit ? 1 : 0).join(''), 2);
    return edgeArr.join('');
}

/** @type {Tile[]} */
const tiles = parseInputFile(INPUT_FILE, /Tile (\d+):([\.#\n\r]+)(?:[\r\n]{2,}|$)/g)
    .map(([, tileId, bitmapText]) => ({
        tileID: parseInt(tileId),
        bitmap: bitmapText.trim().split('\n').map(row => Array.from(row.trim()).map(bit => bit === '#')),
        tileSize: TILE_SIZE
    }))
;

/**
 * @param {Tile} backingTile 
 * @returns {MovingTile}
 */
function newMovingTile(backingTile) {
    return {
        _flippedX: false,
        _flippedY: false,
        _rotation: 0,
        get tileID() {
            return backingTile.tileID;
        },
        getBit(x, y) {
            // apply rotation
            if (this._rotation === 1) {
                const tmp = x;
                x = backingTile.tileSize - 1 - y;
                y = tmp;
            } else if (this._rotation === 2) {
                x = backingTile.tileSize - 1 - x;
                y = backingTile.tileSize - 1 - y;
            } else if (this._rotation === 3) {
                const tmp = x;
                x = y;
                y = backingTile.tileSize - 1 - tmp;
            }
    
            // apply x flip
            if (this._flippedX) {
                y = backingTile.tileSize - 1 - y;
            }
    
            // apply y flip
            if (this._flippedY) {
                x = backingTile.tileSize - 1 - x;
            }
    
            // get value
            return backingTile.bitmap[y][x];
        },
        getTopEdge() {
            return getEdge(this, 0, 0, backingTile.tileSize, 1);
        },
        getLeftEdge() {
            return getEdge(this, 0, 0, 1, backingTile.tileSize);
        },
        getRightEdge() {
            return getEdge(this, backingTile.tileSize - 1, 0, 1, backingTile.tileSize);
        },
        getBottomEdge() {
            return getEdge(this, 0, backingTile.tileSize - 1, backingTile.tileSize, 1);
        },
        flipX() {
            this._flippedX = !this._flippedX;
        },
        flipY() {
            this._flippedY = !this._flippedY;
        },
        rotateLeft() {
            if (this._rotation === 0) this._rotation = 3;
            else this._rotation--;
        },
        rotateRight() {
            if (this._rotation === 3) this._rotation = 0;
            else this._rotation++;
        },
        toString() {
            const bitmapView = [];
            for (let y = 0; y < backingTile.tileSize; y++) {
                const row = [];
                for (let x = 0; x < backingTile.tileSize; x++) {
                    row[x] = this.getBit(x, y) ? '#' : '.';
                }
                bitmapView[y] = row.join('');
            }
            const bitmapText = bitmapView.join('\n');
            return `Tile ${ this.tileID }:\n${ bitmapText }`;
        },
        toBorderlessTile() {
            const newBitmap = [];
            for (let y = 1; y < backingTile.tileSize - 1; y++) {
                const newRow = [];
                for (let x = 1; x < backingTile.tileSize - 1; x++) {
                    newRow.push(this.getBit(x, y));
                }
                newBitmap.push(newRow);
            }
            /** @type {Tile} */
            const newTile = {
                tileID: backingTile.tileID,
                bitmap: newBitmap,
                tileSize: backingTile.tileSize - 2
            };
            return newTile;
        }
    };
}

/** @type {MovingTile[]} */
const movingTiles = tiles.map(newMovingTile);

const gridSize = Math.sqrt(movingTiles.length);

/** @type {Axis<Axis<MovingTile>>} */
const grid = new Axis();
/** @param {number} x @param {number} y @returns {MovingTile} */
function getFromGrid(x, y) {
    const row = grid.get(y);
    if (!row) return undefined;
    return row.get(x);
}
function setInGrid(x, y, tile) {
    let row = grid.get(y);
    if (!row) {
        row = new Axis();
        grid.set(y, row);
    }
    row.set(x, tile);
}

const tilesRemaining = new Set(movingTiles);
const firstTile = movingTiles[0];
tilesRemaining.delete(firstTile);
setInGrid(0, 0, firstTile);

function testTileForFit(tile, x, y) {
    // check left
    const left = getFromGrid(x - 1, y);
    if (left !== undefined && tile.getLeftEdge() === left.getRightEdge()) {
        return true;
    }
    
    // check right
    const right = getFromGrid(x + 1, y);
    if (right !== undefined && tile.getRightEdge() === right.getLeftEdge()) {
        return true;
    }

    // check top
    const top = getFromGrid(x, y - 1);
    if (top !== undefined && tile.getTopEdge() === top.getBottomEdge()) {
        return true;
    }

    // check bottom
    const bottom = getFromGrid(x, y + 1);
    if (bottom !== undefined && tile.getBottomEdge() === bottom.getTopEdge()) {
        return true;
    }

    // no fit :(
    return false;
}

function findFittingTile(x, y) {
    // check each remaining tile
    for (const tile of tilesRemaining) {

        // check each rotation
        for (let r = 0; r < 4; r++) {
            // this will rotate back to normal by the end, if not matched
            tile.rotateRight();

            // test each flip
            for (let f = 0; f < 4; f++) {
                // this will flip back to normal if not matched
                if (f % 2 === 0) {
                    tile.flipX();
                } else {
                    tile.flipY();
                }

                if (testTileForFit(tile, x, y)) return tile;
            }
        }
    }

    return undefined;
}

// fill each place
while (tilesRemaining.size > 0) {
    
    // test each position (+1 in each direction)
    const yMin = 0 - gridSize;
    const yMax = gridSize;
    for (let y = yMin; y <= yMax; y++) {
        const xMin = 0 - gridSize;
        const xMax = gridSize;
        for (let x = xMin; x <= xMax; x++) {
            
            // skip filled positions
            if (getFromGrid(x, y) === undefined) {
                // find tile that fits
                const fittingTile = findFittingTile(x, y);
                if (fittingTile !== undefined) {
                    // remove from set
                    tilesRemaining.delete(fittingTile);
            
                    // attach
                    setInGrid(x, y, fittingTile);
                }
            }
        }
    }
}

// Part 1
{
    console.log('Part 1:');
    const idGrid = grid.toArray().map(row => row.toArray().filter(t => !!t).map(tile => tile.tileID));
    console.log(`Corners: ${ BigInt(idGrid[0][0]) * BigInt(idGrid[0][idGrid[0].length - 1]) * BigInt(idGrid[idGrid.length - 1][0]) * BigInt(idGrid[idGrid.length - 1][idGrid[0].length  - 1]) }`);
    console.log(idGrid.map(row => row.join(' ')).join('\n'));
    console.log();
    
}

/** @param {MovingTile} finalTile @param {number} bitmapSize @returns {Set<string>} */
function findSeaMonsters(finalTile, bitmapSize) {

    /** @param {number} x @param {number} y */
    function findSeaMonsterCoords(x, y) {
        /** @type {string[]} */
        const coords = [];
        for (let i = 0; i < SEA_MONSTER_SEQUENCE.length; i++) {
            const [ offY, offX ] = SEA_MONSTER_SEQUENCE[i];
            y += offY;
            x += offX;

            if (finalTile.getBit(x, y)) {
                coords.push(`${ x },${ y }`);
            } else {
                return [];
            }
        }
        return coords;
    }

    // check each rotation
    for (let r = 0; r < 4; r++) {
        // this will rotate back to normal by the end, if not matched
        finalTile.rotateRight();

        // test each flip
        for (let f = 0; f < 4; f++) {
            // this will flip back to normal if not matched
            if (f % 2 === 0) {
                finalTile.flipX();
            } else {
                finalTile.flipY();
            }

            /** @type {Set<string>} */
            const matchedCoords = new Set();

            // test each possible location
            for (let y = 0; y < bitmapSize - SEA_MONSTER_HEIGHT; y++) {
                for (let x = 0; x < bitmapSize - SEA_MONSTER_WIDTH; x++) {
                    for (const matchedCoord of findSeaMonsterCoords(x, y)) {
                        matchedCoords.add(matchedCoord);
                    }
                }
            }

            // if we had any matched coords, then assume that this is the right configuration
            if (matchedCoords.size > 0) {
                return matchedCoords;
            }
        }
    }

    throw new Error('No sea monsters found!');
}

// Part 2
{
    /** @type {Tile[][]} */
    const borderlessTiles = grid.toArray().map(row => row.toArray().map(t => t.toBorderlessTile()));

    const borderlessTileSize = TILE_SIZE - 2;
    const bitmapSize = gridSize * borderlessTileSize;

    /** @type {Bitmap} */
    const finalBitmap = [];
    for (let y = 0; y < bitmapSize; y++) {
        const row = [];
        finalBitmap.push(row);
        for (let x = 0; x < bitmapSize; x++) {
            const gY = Math.floor(y / borderlessTileSize);
            const gX = Math.floor(x / borderlessTileSize);
            const tY = y % borderlessTileSize;
            const tX = x % borderlessTileSize;

            row.push(borderlessTiles[gY][gX].bitmap[tY][tX]);
        }
    }

    /** @type {MovingTile} */
    const finalTile = newMovingTile({
        bitmap: finalBitmap,
        tileID: -1,
        tileSize: bitmapSize
    });

    console.log('Final image:');
    console.log(finalBitmap.map(row => row.map(bit => bit ? '#' : '.').join('')).join('\n'));

    // find sea monsters
    const seaMonsters = findSeaMonsters(finalTile, bitmapSize);

    // find # not part of monsters
    let numNotMonster = 0;
    for (let x = 0; x < bitmapSize; x++) {
        for (let y = 0; y < bitmapSize; y++) {
            if (finalTile.getBit(x, y) && !seaMonsters.has(`${ x },${ y }`)) {
                numNotMonster++;
            }
        }
    }

    console.log(`Part 2: ${ numNotMonster } active pixels are not part of a sea monster`);
}