Advent of Code day 20 part 2

d20p2.js

'use strict';

const rawInput = require('fs').readFileSync(process.argv[2], 'utf8').trim().split('\n');
const input = rawInput.map(line => {
    const [p, v, a] = line.split(', ').map(part => part.slice(3, -1).split(',').map(n => parseInt(n, 10)));

    return { p, v, a };
});

function isNaturalNumber(num) {
    return num >>> 0 === num;
}

// Provides only solutions which are natural numbers.
function solveQuadratic(a, b, c) {
  if (a === 0) {
    const solution = -c / b;

    return isNaturalNumber(solution) ? [solution] : [];
  }

  const rootDiscriminant = Math.sqrt(b * b - 4 * a * c);

  return [
    (-b + rootDiscriminant) / (2 * a),
    (-b - rootDiscriminant) / (2 * a)
  ].filter(isNaturalNumber);
}

// Calculate the solutions for each axis and initialise or whittle down
// commonSolutions.
function collisionTime(a, b) {
    let commonSolutions;

    // Calculate the solutions for each axis and push them into times.
    for (let i = 0; i < 3; i++) {
        const dp = a.p[i] - b.p[i];
        const dv = a.v[i] - b.v[i];
        const da = a.a[i] - b.a[i];

        const axisSolutions = solveQuadratic(da, 2 * dv + da, 2 * dp);

        // Most of the time there are no solutions, so we can take this
        // shortcut.
        if (axisSolutions.length === 0) {
            return null;
        }

        if (!commonSolutions) {
            // Initialise the set with solutions for the first axis.
            commonSolutions = new Set(axisSolutions);
        } else {
            // Remove solutions for other axes which this axis does't have.
            for (const solution of commonSolutions) {
                if (!axisSolutions.includes(solution)) {
                    commonSolutions.delete(solution);
                }
            }
        }

        // If the set of common solutions is ever empty, there will be no
        // collision.
        if (commonSolutions.size === 0) {
            return null;
        }
    }

    // We only want the earliest collision.
    return Math.min(...commonSolutions);
}

const collisions = [];

// Check collisions between all pairs of particles.
for (let i = 0; i < input.length - 1; i++) {
    for (let j = i + 1; j < input.length; j++) {
        const t = collisionTime(input[i], input[j]);

        if (t !== null) {
            if (!collisions[t]) {
                collisions[t] = [];
            }

            collisions[t].push([i, j]);
        }
    }
}

const particles = new Set(Array.from({ length: input.length }, (v, i) => i));

// Only count collisions when both particles have not been in a prior collision.
// Since collisions may be between more than just two particles, the particles
// set should not have entries removed until all collisions have been checked.
for (const collisionsAtTime of collisions) {
    if (!collisionsAtTime) {
        continue;
    }

    const toDelete = new Set();

    for (const [a, b] of collisionsAtTime) {
        if (particles.has(a) && particles.has(b)) {
            toDelete.add(a);
            toDelete.add(b);
        }
    }

    for (const index of toDelete) {
        particles.delete(index);
    }
}

console.log(particles.size);