Discussion on: AoC Day 7: The Sum of Its Parts

View post

Javascript solution

I decided to create a tree to represent each Step, adding dependencies and dependents for each steap, and a sorting algorithm to sort steps about to processed (i.e. when it has no dependents).

Then, I use a BFS traversal, employing a queue to visit the steps. In the 1st part, if a step has been processed but still has dependents, I re-add it to the end queue. For the 2nd part, I don't need this because then it won't be picked up by another worker, it remains with the same worker for the rest of the duration of that step.

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

07-common.js

class Step {
    constructor(letter) {
        this.letter = letter;
        this.dependents = [];
        this.dependencies = [];
    }    

    addDependent(dependent) {
        this.dependents.push(dependent);
        dependent.dependencies.push(this);
    }
}

const regex = /^Step\s(?<dependency>\w)\smust\sbe\sfinished\sbefore\sstep\s(?<dependent>\w)\scan\sbegin\.$/;

const getStep = (steps, id) => {
    let step;
    if (steps.has(id)) {
        step = steps.get(id);
    }
    else {
        step = new Step(id);
        steps.set(id, step);
    }
    return step;
}

const buildSteps = lines => {
    const steps = new Map();
    for (let line of lines) {
        const { dependency, dependent } = line.match(regex).groups;
        const dependencyStep = getStep(steps, dependency);
        const dependentStep = getStep(steps, dependent);
        dependencyStep.addDependent(dependentStep);
    }
    return steps;
};

const getFirstSteps = steps => {
    const firstSteps = [...steps.values()].filter(step => step.dependencies.length === 0);

    return sortSimilarSteps(firstSteps);        
};

const sortSimilarSteps = steps => {
    return steps.sort((a, b) => a.letter.charCodeAt(0) - b.letter.charCodeAt(0));
};

module.exports = {
    Step,
    getStep,
    buildSteps,
    getFirstSteps,
    sortSimilarSteps
};

07a.js

const { readFile } = require('./reader');
const {
    Step,
    getStep,
    buildSteps,
    getFirstSteps,
    sortSimilarSteps
} = require('./07-common');

const getStepsOrder = steps => {    
    let stepsOrder = '';
    while (steps.length > 0) {
        const step = steps.shift();
        stepsOrder += step.letter;
        for (let dependent of step.dependents) {
            const index = dependent.dependencies.indexOf(step);
            dependent.dependencies.splice(index, 1);
            if (dependent.dependencies.length === 0) {
                steps.push(dependent);
            }
        }
        sortSimilarSteps(steps);
    }
    return stepsOrder;
};

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

    const steps = buildSteps(lines);
    const firstSteps = getFirstSteps(steps);
    const stepsOrder = getStepsOrder(firstSteps);

    console.log(`The steps order is ${stepsOrder}`);
})();

07b.js

const { readFile } = require('./reader');
const {
    Step,
    getStep,
    buildSteps,
    getFirstSteps,
    sortSimilarSteps
} = require('./07-common');

const WARM_UP = 60;
const WORKERS = 15;

const getStepDuration = step => WARM_UP + step.letter.charCodeAt(0) - 64;

const getStepsTime = steps => {
    const workers = Array.from({ length: WORKERS }, w => new Object({ step: null }));

    let isThereWorkLeft = steps.length > 0;
    let stepsOrder = '';
    let totalSeconds = 0;
    while (isThereWorkLeft) {
        for (let worker of workers) {
            let step = worker.step;

            // If worker is done, go over dependents and get yourself a new step
            if (step && step.elapsedSeconds === getStepDuration(step)) {
                stepsOrder += step.letter;
                for (let dependent of step.dependents) {
                    const index = dependent.dependencies.indexOf(step);
                    dependent.dependencies.splice(index, 1);
                    if (dependent.dependencies.length === 0) {
                        steps.push(dependent);
                    }
                }
                sortSimilarSteps(steps);

                worker.step = null;
                step = null;
            }

            // Assigning new step
            if (!step) {
                step = steps.shift();
                if (!step) {
                    continue;
                }
                worker.step = step;
                step.worker = worker;
                step.elapsedSeconds = 0;
            }

            if (step.elapsedSeconds < getStepDuration(step)) {
                step.elapsedSeconds++;
            }
        }
        isThereWorkLeft = !!workers.find(w => !!w.step);
        if (isThereWorkLeft) {
            totalSeconds++;
        }
    }
    return { stepsOrder, totalSeconds };
};

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

    const steps = buildSteps(lines);
    const firstSteps = getFirstSteps(steps);
    const { totalSeconds } = getStepsTime(firstSteps);

    console.log(`The steps time is ${totalSeconds}`);
})();