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.
177 lines
5.3 KiB
177 lines
5.3 KiB
import { readFileSync } from 'node:fs'; |
|
|
|
const input = readFileSync('input', 'utf-8'); |
|
|
|
// Materials |
|
const M = { |
|
ORE: 0, |
|
CLAY: 1, |
|
OBSIDIAN: 2, |
|
GEODE: 3 |
|
}; |
|
|
|
const blueprints = input |
|
.split('\n') |
|
.filter(line => !!line.trim()) |
|
.map(line => { |
|
const [details, robotsData] = line.split(/:\s+/); |
|
const blueprintId = parseInt(details.match(/\d+/)[0]); |
|
|
|
const robots = robotsData |
|
.split(/\.\s*(?!$)/) |
|
.map(robotData => { |
|
const robotType = robotData.match(/(\w+)\s+robot/)[1]; |
|
const index = Object.entries(M).find(([name]) => |
|
name === robotType.toUpperCase() |
|
)[1]; |
|
const costs = [ |
|
parseInt(robotData.match(/\d+(?=\s+ore)/)?.[0] ?? 0), |
|
parseInt(robotData.match(/\d+(?=\s+clay)/)?.[0] ?? 0), |
|
parseInt(robotData.match(/\d+(?=\s+obsidian)/)?.[0] ?? 0), |
|
0 |
|
]; |
|
return [index, costs]; |
|
}) |
|
.reduce((arr, [index, costs]) => { |
|
arr[index] = costs; |
|
return arr; |
|
}, []); |
|
|
|
return { |
|
id: blueprintId, |
|
robots |
|
}; |
|
}); |
|
|
|
// Attempt to build the given robot and apply changes to the inventory. Return |
|
// new robots and inventory arrays, or undefined if unable to build |
|
function build(blueprint, robotType, inventory, robots) { |
|
const newInventory = []; |
|
for (const [material, cost] of blueprint.robots[robotType].entries()) { |
|
const newQuantity = inventory[material] - cost; |
|
if (newQuantity < 0) return; |
|
newInventory.push(newQuantity); |
|
} |
|
const newRobots = [...robots]; |
|
newRobots[robotType] += 1; |
|
return [newInventory, newRobots]; |
|
} |
|
|
|
// Calculate the maximum possible number of geodes that could be cracked within |
|
// the remaining time assuming an infinite inventory |
|
function getMaxPossibleGeodes(state, timeRemaining) { |
|
const geodeRobotCount = state[1][M.GEODE]; |
|
const geodeCount = state[0][M.GEODE]; |
|
|
|
return ( |
|
geodeCount + |
|
(timeRemaining * geodeRobotCount) + |
|
((timeRemaining * Math.max(0, timeRemaining - 1)) / 2) |
|
); |
|
} |
|
|
|
|
|
function getMaximumGeodes(blueprint, totalTime) { |
|
let states = [[[0, 0, 0, 0], [1, 0, 0, 0]]]; |
|
|
|
// Determine the worst case scenario per-turn requirements for each material |
|
const requirements = Object.keys(M).map(material => |
|
blueprint.robots.reduce( |
|
(max, r) => Math.max(max, r[M[material]]), |
|
-Infinity |
|
) |
|
); |
|
|
|
for (let time = 0; time < totalTime; time++) { |
|
const timeRemaining = totalTime - time; |
|
const newStates = []; |
|
|
|
// Prune |
|
states = states.filter((stateA, ia, states) => { |
|
// Remove duplicates |
|
return states.findLastIndex(stateB => |
|
stateB[0].every((c, i) => c === stateA[0][i]) && |
|
stateB[1].every((c, i) => c === stateA[1][i]) |
|
) === ia; |
|
}).filter((stateA, ia) => { |
|
// Maximum possible number of geodes that could be created from this |
|
// state assuming an infinite inventory |
|
const fantasyA = getMaxPossibleGeodes(stateA, timeRemaining); |
|
|
|
// Filter out states where there exists a better state |
|
for (let ib = 0; ib < states.length; ib++) { |
|
const stateB = states[ib]; |
|
|
|
// If stateB has more geodes than stateA could ever possibly hope to |
|
// gather then discard stateA (minor optimization) |
|
if (stateB[0][M.GEODE] > fantasyA) { |
|
return false; |
|
} |
|
|
|
// Discard stateA if stateB is objectively better (all values larger or |
|
// the same, at least one larger) |
|
if ( |
|
ib !== ia && |
|
stateB[0].every((c, i) => c >= stateA[0][i]) && |
|
stateB[1].every((c, i) => c >= stateA[1][i]) && ( |
|
stateB[0].some((c, i) => c > stateA[0][i]) || |
|
stateB[1].some((c, i) => c > stateA[1][i]) |
|
) |
|
) { |
|
return false; |
|
} |
|
} |
|
return true; |
|
}); |
|
|
|
// Process states |
|
for (const [inventory, robots] of states) { |
|
// Calculate inventory thresholds after which there is no longer any |
|
// incentive to build more of that robot |
|
const thresholds = Object.keys(M).map(material => |
|
(requirements[M[material]] - robots[M[material]]) * (timeRemaining - 1) |
|
); |
|
const buildOre = inventory[M.ORE] < thresholds[M.ORE]; |
|
const buildClay = inventory[M.CLAY] < thresholds[M.CLAY]; |
|
const buildObsidian = inventory[M.OBSIDIAN] < thresholds[M.OBSIDIAN]; |
|
|
|
let choices = [ |
|
// do nothing |
|
[[...inventory], [...robots]], |
|
buildOre && build(blueprint, M.ORE, inventory, robots), |
|
buildClay && build(blueprint, M.CLAY, inventory, robots), |
|
buildObsidian && build(blueprint, M.OBSIDIAN, inventory, robots), |
|
build(blueprint, M.GEODE, inventory, robots) |
|
].filter(choice => !!choice); |
|
|
|
choices = choices.map(([cInv, cRob]) => [ |
|
cInv.map((c, i) => c + robots[i]), |
|
cRob |
|
]); |
|
|
|
newStates.push(...choices); |
|
} |
|
states = newStates; |
|
} |
|
return states.reduce((max, state) => Math.max(max, state[0][M.GEODE]), 0); |
|
} |
|
|
|
|
|
|
|
let totalQuality = 0; |
|
for (const blueprint of blueprints) { |
|
const geodes = getMaximumGeodes(blueprint, 24); |
|
const quality = blueprint.id * geodes; |
|
totalQuality += quality |
|
} |
|
console.log('The sum of all blueprint quality levels is:', totalQuality); |
|
|
|
|
|
let totalMultiplied = 1; |
|
for (const blueprint of blueprints.slice(0, 3)) { |
|
totalMultiplied *= getMaximumGeodes(blueprint, 32); |
|
} |
|
console.log( |
|
'Multiplication of max geodes for first three blueprints:', |
|
totalMultiplied |
|
);
|
|
|