(Browser-based) Javascript
My initial approach was to consider each junction as a circuit, and then merge the closest circuits. Took me way to long to realize the problem statement for part 1 made this unworkable (as you need to count redundant connections as "attempts"). Thankfully part 2 doesn't care about how many connections you make, so I was able to reuse that code to solve part 2.
To solve part 1 "the right way", I first thought I had to store a circuit as a collection of pairs of junctions (literally, the collection of connections). Oh god was that messy code; 3 layers of nested for-loops and it still wasn't getting close to the answer. I eventually realized I could reference the junctions' indices in the input to simplify things, allowing me to manipulate simple sets of ints. Combine with pre-calculating the distances once before starting the connecting/merging and you end up with a surprisingly simple and snappy algorithm.
Given I realized these optimizations after restarting part 1, my solution for part 2 doesn't take advantage of any of them and takes an eye-watering 22 seconds to terminate on average. It probably re-computes more distances than it computes new ones, for each iteration...
Code
function getExampleText() {
return `162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689
`
}
function part1(inputText, maxConnections) {
const junctions = inputText.trimEnd().split('\n')
.map(line => line.split(',')
.map(strValue => Number.parseInt(strValue, 10)));
// compute the distance between each junction exactly once
const annotatedDistances = Array(Math.ceil(((junctions.length - 1) ** 2) / 2));
let counter = 0;
for (let i = 0; i < junctions.length; i++) {
const [xI, yI, zI] = junctions[i];
for (let j = i + 1; j < junctions.length; j++) {
const [xJ, yJ, zJ] = junctions[j];
const distanceSquared = (xJ - xI) ** 2 + (yJ - yI) ** 2 + (zJ - zI) ** 2;
annotatedDistances[counter] = [distanceSquared, i, j];
counter++;
}
}
// sort the pairs of junctions by closest to farthest
annotatedDistances.sort(([dA], [dB]) => dA - dB);
// connect the maxConnections-closest junctions
const circuits = [];
for (const [_, i, j] of annotatedDistances.slice(0, maxConnections)) {
// find any existing circuit(s) that already contain(s) one of the junctions
let existingCircuits = [];
for (let circuitIndex = 0; circuitIndex < circuits.length; circuitIndex++) {
const circuit = circuits[circuitIndex];
if (circuit.has(i) || circuit.has(j)) {
existingCircuits.push(circuitIndex);
}
}
// 3 possible cases:
// the junctions are not part of any existing circuits => connecting them creates a new circuit
if (existingCircuits.length === 0) {
circuits.push(new Set([i, j]));
}
// the junctions are part of 1 existing circuit => connecting them extends this existing circuit to encompass an additional junction (if only 1 junction is already in this circuit)
else if (existingCircuits.length === 1) {
const circuitToExtend = circuits[existingCircuits[0]];
circuitToExtend.add(i);
circuitToExtend.add(j);
}
// the junctions are part of 2 distinct existing circuits => connecting them merges these two circuits
else if (existingCircuits.length === 2) {
// merge circuit(s) with new connection between junctions i and j
const circuitMergerIndex = existingCircuits.shift();
for (const circuitToBeMergedIndex of existingCircuits) {
circuits[circuitMergerIndex] = circuits[circuitMergerIndex].union(circuits[circuitToBeMergedIndex]);
circuits.splice(circuitToBeMergedIndex, 1);
}
}
}
circuits.sort((a, b) => b.size - a.size);
//console.debug({ sortedCircuits: structuredClone(circuits) });
return circuits.slice(0, 3).reduce((accu, next) => accu * next.size, 1)
}
{
const start = performance.now();
//const result = part1(getExampleText(), 10);
const result = part1(document.body.textContent, 1_000);
const end = performance.now();
console.info({
day: 7,
part: 1,
time: end - start,
result
});
}
function part2(inputText) {
const circuits = inputText
.trimEnd()
.split('\n')
.map(line => ([
line.split(',')
.map(strVal => Number.parseInt(strVal, 10))
]))
let junctionA, junctionB;
while (circuits.length > 1) {
let smallestSquaredDistance = Number.POSITIVE_INFINITY;
let toConnectA, toConnectB;
for (const circuitA of circuits) {
for (const circuitB of circuits) {
if (circuitA === circuitB) {
continue;
}
let squaredCircuitDistance = Number.POSITIVE_INFINITY;
for (const [xA, yA, zA] of circuitA) {
for (const [xB, yB, zB] of circuitB) {
const distance = (xB - xA) ** 2 + (yB - yA) ** 2 + (zB - zA) ** 2;
if (distance < squaredCircuitDistance) {
squaredCircuitDistance = distance;
junctionA = [xA, yA, zA];
junctionB = [xB, yB, zB];
}
}
}
if (squaredCircuitDistance < smallestSquaredDistance) {
smallestSquaredDistance = squaredCircuitDistance;
toConnectA = circuitA;
toConnectB = circuitB;
}
}
}
if (toConnectA.length > toConnectB.length) {
toConnectA.push(...toConnectB);
const bIndex = circuits.indexOf(toConnectB);
circuits.splice(bIndex, 1);
} else {
toConnectB.push(...toConnectA);
const aIndex = circuits.indexOf(toConnectA);
circuits.splice(aIndex, 1);
}
}
return junctionA[0] * junctionB[0];
}
{
const start = performance.now();
// const result = part2(getExampleText());
const result = part2(document.body.textContent);
const end = performance.now();
console.info({
day: 7,
part: 2,
time: end - start,
result
});
}