Instantly share code, notes, and snippets.

Embed
What would you like to do?
Advent of Code day 20 part 2
'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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment