You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
152 lines
3.9 KiB
152 lines
3.9 KiB
|
|
import { readFileSync } from 'node:fs'; |
|
|
|
const input = readFileSync('input', 'utf-8'); |
|
|
|
|
|
const valves = new Map(input |
|
.split('\n') |
|
.filter(Boolean) |
|
.map(line => { |
|
const valve = line.match(/Valve (\w+)/)[1]; |
|
const rate = parseInt(line.match(/rate=(\d+)/)[1]); |
|
const to = line.match(/valves? (.*)/)[1].split(', '); |
|
return [valve, {valve, rate, to}]; |
|
}) |
|
); |
|
|
|
function shortestPath(v, vDest, path=[]) { |
|
const valve = valves.get(v); |
|
|
|
if (valve.to.includes(vDest)) { |
|
return [...path, v, vDest]; |
|
} |
|
return valve.to |
|
.filter(to => !path.includes(to)) |
|
.map(to => shortestPath(to, vDest, [...path, v])) |
|
.filter(Boolean) |
|
.sort((p1, p2) => p1.length - p2.length)[0]; |
|
} |
|
|
|
// Add a property to all valves containing links to all other valves with a |
|
// flow rate greater than 0 and the time it will take to reach them |
|
const valvesWithFlow = [...valves.values()] |
|
.filter(valve => valve.rate > 0); |
|
for (const valve of valves.values()) { |
|
valve.usefulTo = valvesWithFlow |
|
.filter(vDest => vDest.valve !== valve.valve) |
|
.map(vDest => ({ |
|
valve: vDest.valve, |
|
time: shortestPath(valve.valve, vDest.valve).length - 1, |
|
rate: vDest.rate |
|
})); |
|
} |
|
|
|
function product(...arrs) { |
|
if (!arrs.length) return []; |
|
return arrs.reduce((result, arr) => |
|
result.flatMap(r => |
|
arr.map(a => [...r, a]) |
|
), |
|
[[]] |
|
) |
|
} |
|
|
|
// General solution for n players |
|
function solve(players, rate=0) { |
|
for (const player of players) { |
|
const valve = valves.get(player.path[player.path.length - 1]); |
|
|
|
if (valve.rate > 0 && !player.opened) { |
|
player.opened = true; |
|
player.timeRemaining -= 1; |
|
rate += valve.rate * Math.max(0, player.timeRemaining); |
|
} |
|
} |
|
|
|
// Array of valve names which haven't been visited |
|
const unvisitedValves = valvesWithFlow |
|
.map(v => v.valve) |
|
.filter(valve => !players.find(p => p.path.includes(valve))); |
|
|
|
// Exit conditions |
|
if ( |
|
unvisitedValves.length === 0 || |
|
players.every(player => player.timeRemaining <= 0) |
|
) { |
|
return [rate, players]; |
|
} |
|
|
|
// Decide who is moving |
|
const maxTimeRemaining = players.reduce( |
|
(max, player) => Math.max(max, player.timeRemaining), |
|
0 |
|
); |
|
const movingPlayers = players.filter( |
|
player => player.timeRemaining === maxTimeRemaining |
|
); |
|
const nonMovingPlayers = players.filter( |
|
player => !movingPlayers.includes(player) |
|
); |
|
|
|
const playerMoves = product(...movingPlayers |
|
.map(player => { |
|
const valve = valves.get(player.path[player.path.length - 1]); |
|
const destinations = valve.usefulTo |
|
.filter(to => unvisitedValves.includes(to.valve)) |
|
.filter((to, _, tos) => !tos.find((otherTo) => |
|
otherTo.rate > to.rate && |
|
otherTo.time <= to.time |
|
)); |
|
if (destinations.length < movingPlayers.length) { |
|
destinations.push(undefined); |
|
} |
|
return destinations; |
|
}) |
|
).filter(moves => { |
|
const valves = moves.filter(Boolean).map(to => to.valve); |
|
return ( |
|
valves.length !== 0 && |
|
new Set(valves).size === valves.length |
|
); |
|
}); |
|
|
|
return playerMoves |
|
.map(moves => { |
|
const movedPlayers = moves.map((to, i) => { |
|
const player = movingPlayers[i]; |
|
if (to === undefined) { |
|
// Not moving |
|
return player; |
|
} |
|
return { |
|
timeRemaining: player.timeRemaining - to.time, |
|
opened: false, |
|
path: [...player.path, to.valve] |
|
}; |
|
}); |
|
|
|
return solve([...nonMovingPlayers, ...movedPlayers], rate); |
|
}) |
|
.filter(Boolean) |
|
.sort(([rate1], [rate2]) => rate2 - rate1)[0]; |
|
} |
|
|
|
|
|
const solution1 = solve([{ |
|
timeRemaining: 30, |
|
opened: false, |
|
path: ['AA'] |
|
}]); |
|
console.log(`Max pressure released in 30 minutes: ${solution1[0]}`); |
|
|
|
const solution2 = solve([{ |
|
timeRemaining: 26, |
|
opened: false, |
|
path: ['AA'] |
|
}, { |
|
timeRemaining: 26, |
|
opened: false, |
|
path: ['AA'] |
|
}]); |
|
console.log(`Max pressure released with elephant: ${solution2[0]}`);
|
|
|