function parse(input) {
const [valves, g] = [{}, new Graph()];
for (const line of input.split("\n")) {
const tokens = line.split(" ");
const name = tokens[1];
valves[name] = { rate: Number(tokens[4].slice(5, -1)), open: false };
tokens.slice(9).forEach((other) => g.addEdge(name, other.replace(",", "")));
}
return { valves: valves, graph: g };
}
function removeZeroValves(input) {
const network = parse(input);
const g = network.graph;
const toRemove = Object.entries(network.valves).reduce(
(zeros, [name, obj]) =>
obj.rate === 0 && name !== "AA" ? [...zeros, name] : zeros,
[]
);
for (const n of toRemove) {
const [inNodes, outNodes] = [g.inNodes(n), g.adjacent(n)];
inNodes.forEach((inNode) => {
for (const outNode of outNodes) {
if (inNode != outNode) {
g.addEdge(
inNode,
outNode,
g.getEdgeWeight(inNode, n) + g.getEdgeWeight(n, outNode)
);
}
}
});
g.removeNode(n);
}
return network;
}
function findSeqs(network, valves, costs, maxTime, excluded = []) {
const allSeqs = [];
const releasePressure = (v0, open, t) => {
if (t == 0) {
// We've run out of time, so store this sequence
if (open.length > 0) {
allSeqs.push(open);
}
return;
}
for (const v1 of valves) {
if (!open.includes(v1) && !excluded.includes(v1) && costs[v0][v1] <= t) {
const newOpen = [...open];
newOpen.push(v1);
releasePressure(v1, newOpen, t - costs[v0][v1] - 1);
}
}
// We've visited all valves within the time.
if (open.length > 0) {
allSeqs.push(open);
}
return;
};
releasePressure("AA", [], maxTime);
return allSeqs;
}
function calcScore(openValves, costs, valves, maxTime) {
let [t,p] = [maxTime, 0];
let prev = "AA";
for (let i = 0; i < openValves.length; i++) {
t -= costs[prev][openValves[i]] + 1;
p += t * valves[openValves[i]].rate;
prev = openValves[i];
}
return p;
}
function part1(input) {
const maxTime = 30;
const network = removeZeroValves(input);
const valves = network.graph.nodes().filter((v) => v != "AA");
const costs = network.graph.costMatrix();
return findSeqs(network, valves, costs, maxTime).reduce(
(maxScore, seq) =>
Math.max(maxScore, calcScore(seq, costs, network.valves, maxTime)),
0
);
}
function part2(input) {
const maxT = 26;
const network = removeZeroValves(input);
const costs = network.graph.costMatrix();
const scores = new Map();
const seqs = findSeqs(
network,
network.graph.nodes().filter((v) => v !== "AA"),
costs,
maxT
).map((seq) => [seq, calcScore(seq, costs, network.valves, maxT)]);
for (const [seq, score] of seqs) {
const key = seq.sort().join(",");
scores.set(key, Math.max(score, scores.get(key) || 0));
}
const sortedSeqs = [...scores.keys()].map((str) => str.split(","));
let maxScore = 0;
for (let i = 0; i < sortedSeqs.length; i++) {
for (let j = i + 1; j < sortedSeqs.length; j++) {
let [seq1, seq2] = [sortedSeqs[i], sortedSeqs[j]];
let [areDisjoint, p1, p2] = [true, 0, 0];
while (p1 < seq1.length && p2 < seq2.length) {
if (seq1[p1] === seq2[p2]) {
areDisjoint = false;
break;
}
seq1[p1] < seq2[p2] ? p1++ : p2++;
}
if (areDisjoint) {
maxScore = Math.max(
maxScore,
scores.get(seq1.join(",")) + scores.get(seq2.join(","))
);
}
}
}
return maxScore;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
