Discussion on: AoC Day 6: Chronal Coordinates

[Tiago Romero Garcia]

Javascript solution

I enjoyed doing this one. It somehow felt satisfying. Maybe it's because for this one I was able to realize it's a series of steps and I could develop and test each one of them step-by-step, so I felt confident I was moving into the right direction.

reader.js

const fs = require('fs');
const readline = require('readline');

const readLines = (file, onLine) => {
    const reader = readline.createInterface({
        input: fs.createReadStream(file),
        crlfDelay: Infinity
    });

    reader.on('line', onLine);

    return new Promise(resolve => reader.on('close', resolve));
};

const readFile = async file => {
    const lines = [];
    await readLines(file, line => lines.push(line));  
    return lines;
}

module.exports = {
    readLines,
    readFile
};

06-common.js

class Coordinate {
    constructor(x, y, id) {
        this.x = x;
        this.y = y;
        this.id = id;
    }
}

const buildCoordinates = lines => {
    return lines.map((line, index) => {
        const [x, y] = line.split(', ');
        return new Coordinate(+x, +y, index);
    });
};

const getGridDimension = coordinates => {
    let largestX = 0;
    let largestY = 0;
    for (let coordinate of coordinates) {
        const { x, y } = coordinate;
        largestX = Math.max(largestX, x);
        largestY = Math.max(largestY, y);
    }
    return Math.max(largestX, largestY) + 1;
}

const plotCoordinates = coordinates => {
    const n = getGridDimension(coordinates);

    const grid = Array.from({ length: n }, row => Array.from({ length: n }));
    for (let coordinate of coordinates) {
        const { x, y } = coordinate;
        grid[x][y] = coordinate;
    }
    return grid;
};

const calculateManhattanDistance = (c1, c2) => {
    return Math.abs(c1.x - c2.x) + Math.abs(c1.y - c2.y);
};

module.exports = {
    Coordinate,
    buildCoordinates,
    getGridDimension,
    plotCoordinates,
    calculateManhattanDistance
};

06a.js

const { readFile } = require('./reader');

const {
    Coordinate,
    buildCoordinates,
    getGridDimension,
    plotCoordinates,
    calculateManhattanDistance
} = require('./06-common');

const plotLocations = (coordinates, grid) => {
    const n = grid.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (!grid[i][j]) {
                const location = new Coordinate(i, j);
                grid[i][j] = location;

                let smallestDistance;
                let closestCoordinates;
                for (let coordinate of coordinates) {
                    const distance = calculateManhattanDistance(location, coordinate);

                    if (!closestCoordinates || distance < smallestDistance) {
                        smallestDistance = distance;
                        closestCoordinates = [coordinate];
                    }
                    else if (distance === smallestDistance) {
                        closestCoordinates.push(coordinate);
                    }
                }

                if (closestCoordinates.length === 1) {
                    location.closestCoordinate = closestCoordinates[0];
                }
            }
        }
    }
};

const getFiniteCoordinateIds = (coordinates, grid) => {
    const n = grid.length;
    const infiniteCoordinateIds = new Set();

    // Top and bottom edges
    for (let i = 0; i < n; i += n-1) {
        for (let j = 0; j < n; j++) {
            const closestCoordinate = grid[i][j].closestCoordinate;
            if (closestCoordinate) {
                infiniteCoordinateIds.add(closestCoordinate.id);
            }
        }
    }

    // Left and right edges
    for (let j = 0; j < n; j += n-1) {
        for (let i = 0; i < n; i++) {
            const closestCoordinate = grid[i][j].closestCoordinate;
            if (closestCoordinate) {
                infiniteCoordinateIds.add(closestCoordinate.id);
            }
        }
    }

    const finiteCoordinateIds = coordinates
        .filter(coordinate => !infiniteCoordinateIds.has(coordinate.id))
        .map(coordinate => coordinate.id);

    return new Set(finiteCoordinateIds);
};

const calculateCoordinateRegions = (finiteCoordinates, grid) => {
    const n = grid.length;
    const frequencyMap = new Map();
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const closestCoordinate = grid[i][j].closestCoordinate;
            if (closestCoordinate && finiteCoordinates.has(closestCoordinate.id)) {
                const { id } = closestCoordinate;
                const frequency = frequencyMap.get(id) || 1;
                frequencyMap.set(id, frequency+1);
            }
        }
    }
    return frequencyMap;
};

(async () => {
    const lines = await readFile('06-input.txt');

    const coordinates = buildCoordinates(lines);
    const grid = plotCoordinates(coordinates);
    plotLocations(coordinates, grid);
    const finiteCoordinateIds = getFiniteCoordinateIds(coordinates, grid);
    const coordinateRegions = calculateCoordinateRegions(finiteCoordinateIds, grid);
    const largestRegion = Math.max(...coordinateRegions.values());

    console.log(`The largest region is ${largestRegion}`);
})();

06b.js

const { readFile } = require('./reader');

const {
    Coordinate,
    buildCoordinates,
    getGridDimension,
    plotCoordinates,
    calculateManhattanDistance
} = require('./06-common');

const MAX_TOTAL_DISTANCE = 10000;

const plotLocations = (coordinates, grid) => {
    const n = grid.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            let location = grid[i][j];
            if (!grid[i][j]) {
                location = new Coordinate(i, j);
                grid[i][j] = location;
            }

            const totalDistance = coordinates.reduce((sum, coordinate) =>{
                return sum + calculateManhattanDistance(location, coordinate);
            }, 0);

            location.inSafeRegion = totalDistance < MAX_TOTAL_DISTANCE;
        }
    }
};

const getSafeRegionSize = grid => {
    const n = grid.length;
    let safeRegionSize = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const location = grid[i][j];
            safeRegionSize += +location.inSafeRegion;
        }
    }
    return safeRegionSize;
};

(async () => {
    const lines = await readFile('06-input.txt');

    const coordinates = buildCoordinates(lines);
    const grid = plotCoordinates(coordinates);
    plotLocations(coordinates, grid);
    const safeRegionSize = getSafeRegionSize(grid);

    console.log(`The safe region size is ${safeRegionSize}`);
})();