2f:T12f2,inputs = `Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 12 clay. Each geode robot costs 4 ore and 19 obsidian. Blueprint 2: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 11 clay. Each geode robot costs 4 ore and 12 obsidian. Blueprint 3: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 18 clay. Each geode robot costs 2 ore and 11 obsidian. Blueprint 4: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 4 ore and 20 obsidian. Blueprint 5: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 16 clay. Each geode robot costs 4 ore and 17 obsidian. Blueprint 6: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 19 clay. Each geode robot costs 2 ore and 12 obsidian. Blueprint 7: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 9 clay. Each geode robot costs 2 ore and 10 obsidian. Blueprint 8: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 5 clay. Each geode robot costs 3 ore and 7 obsidian. Blueprint 9: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 11 clay. Each geode robot costs 4 ore and 8 obsidian. Blueprint 10: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 16 clay. Each geode robot costs 2 ore and 15 obsidian. Blueprint 11: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 20 clay. Each geode robot costs 2 ore and 19 obsidian. Blueprint 12: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 16 clay. Each geode robot costs 3 ore and 20 obsidian. Blueprint 13: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 3 ore and 14 obsidian. Blueprint 14: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 2 ore and 15 obsidian. Blueprint 15: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 3 ore and 12 obsidian. Blueprint 16: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 17 clay. Each geode robot costs 3 ore and 19 obsidian. Blueprint 17: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 4 ore and 9 obsidian. Blueprint 18: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 6 clay. Each geode robot costs 3 ore and 16 obsidian. Blueprint 19: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 6 clay. Each geode robot costs 2 ore and 14 obsidian. Blueprint 20: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 11 clay. Each geode robot costs 3 ore and 15 obsidian. Blueprint 21: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 18 clay. Each geode robot costs 4 ore and 19 obsidian. Blueprint 22: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 15 clay. Each geode robot costs 2 ore and 20 obsidian. Blueprint 23: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 5 clay. Each geode robot costs 2 ore and 10 obsidian. Blueprint 24: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 10 clay. Each geode robot costs 2 ore and 14 obsidian. Blueprint 25: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 7 clay. Each geode robot costs 4 ore and 13 obsidian. Blueprint 26: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 20 clay. Each geode robot costs 2 ore and 20 obsidian. Blueprint 27: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 18 clay. Each geode robot costs 2 ore and 19 obsidian. Blueprint 28: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 10 clay. Each geode robot costs 2 ore and 7 obsidian. Blueprint 29: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 15 clay. Each geode robot costs 3 ore and 7 obsidian. Blueprint 30: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 20 clay. Each geode robot costs 4 ore and 18 obsidian.`30:T1127,// outer function to encapsulate the recursive one nextMinute = (minute, blueprint, robots, cash, processed, maxMinutes) => { nextMinuteRec(minute, blueprint, robots, cash, processed); // main search functionn (recursive) function nextMinuteRec(minute, blueprint, robots, cash, processed) { blueprint.history[minute] = { cash: Object.assign({}, cash), robots: Object.assign({}, robots) }; if (minute < maxMinutes) { /* alternative with swapped caches? // 1st cache: by cash values -> getting cache of robot values let keyCash = [...Object.values(cash)].join("-"); let minProcessedCash = processed.get(keyCash); if (minProcessedCash == null) { minProcessedCash = new Map(); processed.set(keyCash, minProcessedCash); } // 2nd cache: by robot values -> getting minimum minute to reach these values let keyRobots = [...Object.values(robots)].join("-"); let minProcessedRobots = minProcessedCash.get(keyRobots); if (minProcessedRobots == null || minute < minProcessedRobots) { minProcessedCash.set(keyRobots, minute); */ // 1st cache: by robot values -> getting cache of cash values let keyRobots = [...Object.values(robots)].join("-"); let minProcessedRobots = processed.get(keyRobots); if (minProcessedRobots == null) { minProcessedRobots = new Map(); processed.set(keyRobots, minProcessedRobots); } // 2nd cache: by cash values -> getting minimum minute to reach these values let keyCash = [...Object.values(cash)].join("-"); let minProcessedCash = minProcessedRobots.get(keyCash); if (minProcessedCash == null || minute < minProcessedCash) { minProcessedRobots.set(keyCash, minute); let maxCashReached = true; // loop robots keys.forEach((k) => { // useful to build this robot? -> i.e. less robots than maximum needed minerals for any robot in the blueprint if (!(blueprint.maxCash[k] <= robots[k])) { // should we go on without building a robot? -> i.e. saving minerals for future use if (!(blueprint.maxCash[k] <= cash[k])) { maxCashReached = false; } // eval if enough cash available to build a new robot let notEnough = Object.keys(blueprint[k]).filter( (c) => cash[c] < blueprint[k][c] ); if (notEnough.length == 0) { // there are enough minerals available to build a new robot 'k' let copyRobots = Object.assign({}, robots); copyRobots[k] += 1; let copyCash = Object.assign({}, cash); Object.keys(blueprint[k]).forEach( (c) => (copyCash[c] -= blueprint[k][c]) ); Object.keys(copyRobots).forEach( (k) => (copyCash[k] += robots[k]) ); // recursive call (with a new set of objects for robots & cash) nextMinuteRec( minute + 1, blueprint, copyRobots, copyCash, processed ); } } }); // did we found a reason to go on without building a robot? -> i.e. saving minerals for future use if (!maxCashReached) { // yes, useful to save -> less than maximum needed minerals for any robot in the blueprint let copyRobots = Object.assign({}, robots); let copyCash = Object.assign({}, cash); Object.keys(copyRobots).forEach((k) => (copyCash[k] += robots[k])); // recursive call (with a new set of objects for robots & cash) nextMinuteRec(minute + 1, blueprint, copyRobots, copyCash, processed); } } } else { // maximum minutes for simulation reached -> eval max value of geodes blueprint.cnt++; if (cash.geode > blueprint.max.value) { // reached a new maximum level -> remember it blueprint.max = { value: cash.geode, robots: Object.assign({}, robots), cash: Object.assign({}, cash), history: blueprint.history.map((hist) => ({ cash: Object.assign({}, hist.cash), robots: Object.assign({}, hist.robots) })) }; } } } return; }31:T1565,// loop all blueprints and process each one searching for maximum output iterateBlueprints = function* (blueprints, minutes) { let resultBlueprints = []; for (let blueprint of blueprints) { // init robots and cash values let robots = Object.fromEntries(keys.map((k) => [k, k == "ore" ? 1 : 0])); let cash = Object.fromEntries(keys.map((k) => [k, 0])); // some more initial values to track blueprint.max = { value: 0 }; blueprint.todo = [ { robots: robots, cash: cash, history: [] } ]; resultBlueprints.push(blueprint); // run recursively all possibilities until maximum minutes is reached let nextTodoCache = new Set(); let processed = new Map(); for (let minute = 0; minute <= minutes; minute++) { let nextTodo = []; for (let bpState of blueprint.todo) { let robots = bpState.robots; let cash = bpState.cash; if ( cash.geode + robots.geode * (minutes - minute + 1) < blueprint.max.value ) { // we won't reach the maximum anymore -> just skip it! continue; } bpState.history.push({ cash: Object.assign({}, cash), robots: Object.assign({}, robots) }); // maximum minutes for simulation reached -> eval max value of geodes if (cash.geode > blueprint.max.value) { // reached a new maximum level -> remember it blueprint.max = { value: cash.geode, robots: Object.assign({}, robots), cash: Object.assign({}, cash), history: bpState.history.map((hist) => hist) }; } if (minute < minutes) { // 1st cache: by robot values -> getting cache of cash values let keyRobots = [...Object.values(robots)].join("-"); let minProcessedRobots = processed.get(keyRobots); if (minProcessedRobots == null) { minProcessedRobots = new Map(); processed.set(keyRobots, minProcessedRobots); } // 2nd cache: by cash values -> getting minimum minute to reach these values let keyCash = [...Object.values(cash)].join("-"); let minProcessedCash = minProcessedRobots.get(keyCash); if (minProcessedCash == null || minute < minProcessedCash) { minProcessedRobots.set(keyCash, minute); let maxCashReached = true; // loop robots keys.forEach((k) => { // useful to build this robot? -> i.e. less robots than maximum needed minerals for any robot in the blueprint if (!(blueprint.maxCash[k] <= robots[k])) { // should we go on without building a robot? -> i.e. saving minerals for future use if (!(1.1 * blueprint.maxCash[k] <= cash[k])) { maxCashReached = false; } // eval if enough cash available to build a new robot let notEnough = Object.keys(blueprint[k]).filter( (c) => cash[c] < blueprint[k][c] ); if (notEnough.length == 0) { // there are enough minerals available to build a new robot 'k' let copyRobots = Object.assign({}, robots); copyRobots[k] += 1; let copyCash = Object.assign({}, cash); Object.keys(blueprint[k]).forEach( (c) => (copyCash[c] -= blueprint[k][c]) ); Object.keys(copyRobots).forEach( (k) => (copyCash[k] += robots[k]) ); // remember as todo in next iteration let cacheKey = [ ...Object.values(copyRobots), ...Object.values(copyCash) ].join("-"); if (!maxCashReached && !nextTodoCache.has(cacheKey)) { nextTodoCache.add(cacheKey); nextTodo.push({ robots: copyRobots, cash: copyCash, history: bpState.history.map((hist) => hist) }); } } } }); // did we found a reason to go on without building a robot? -> i.e. saving minerals for future use if (!maxCashReached) { // yes, useful to save -> less than maximum needed minerals for any robot in the blueprint let copyRobots = Object.assign({}, robots); let copyCash = Object.assign({}, cash); Object.keys(copyRobots).forEach( (k) => (copyCash[k] += robots[k]) ); // remember as todo in next iteration let cacheKey = [ ...Object.values(copyRobots), ...Object.values(copyCash) ].join("-"); if (!nextTodoCache.has(cacheKey)) { nextTodoCache.add(cacheKey); nextTodo.push({ robots: copyRobots, cash: copyCash, history: bpState.history.map((hist) => hist) }); } } } } } blueprint.todo = nextTodo; yield resultBlueprints; } delete blueprint.todo; yield resultBlueprints; } yield resultBlueprints; }32:T940,// plot results into small multiple (lines=blueprints, columns=minerals, bar height=cash, line height=robot count) plotResults = (blueprints) => { // some precalculations const processedBPs = blueprints.filter( (bp) => bp.max != undefined && bp.todo == undefined ).length; const todo = blueprints.find((bp) => bp.todo != undefined)?.todo.length || 0; const maxBPs = blueprints.filter((bp) => bp.max.history != undefined).length; const maxGeodes = Math.max(...blueprints.map((bp) => bp.max.value)); const bestBPs = blueprints .filter((bp) => bp.max.value == maxGeodes) .map((bp) => bp.id); // reformat into flat array with attributes to be used in plot let plotArray = blueprints .filter((bp) => bp.max.history != undefined) .sort((a, b) => a.max.value - b.max.value) .reduce((acc1, bp) => { bp.max.history.reduce((acc2, minute, idx) => { Object.keys(minute.cash).forEach((k) => acc2.push({ blueprint: bp.id, minute: idx, type: k, robots: minute.robots[k], cash: minute.cash[k] }) ); return acc2; }, acc1); return acc1; }, []); // the main plots return Plot.plot({ caption: `${processedBPs} blueprints processed ` + (todo > 0 ? `(todo: ${todo}) ` : ``) + `- best blueprint(s): #${bestBPs} - total quality level: ${qualityLevel( blueprints )} - geodes product: ${geodesProduct(blueprints)}`, height: 60 + 60 * maxBPs, width, x: { ticks: d3.range(0, 32, 10) }, y: { grid: true, //ticks: d3.range(0, maxGeodes, Math.min(maxGeodes - 1, 10)), domain: [0, 2 * maxGeodes] }, fx: { domain: keys }, fy: { domain: blueprints .filter((bp) => bp.max.history != undefined) .map((bp) => bp.id) }, facet: { data: plotArray, x: "type", y: "blueprint", marginRight: 50 }, marks: [ Plot.ruleX([0], { stroke: "lightgray" }), Plot.ruleY([0], { stroke: "lightgray" }), Plot.barY(plotArray, { x: "minute", y: "cash", fill: "type", clip: true }), Plot.line(plotArray, { x: "minute", y: "robots", clip: true }) ], color: { legend: true } }); }33:[] 2d:{"title":"Day 19 - Not Enough Minerals","cells":[{"id":0,"value":"# Day 19 - [Not Enough Minerals](https://adventofcode.com/2022/day/19)","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"inputs0 = `Blueprint 1:\n Each ore robot costs 4 ore.\n Each clay robot costs 2 ore.\n Each obsidian robot costs 3 ore and 14 clay.\n Each geode robot costs 2 ore and 7 obsidian.\n\nBlueprint 2:\n Each ore robot costs 2 ore.\n Each clay robot costs 3 ore.\n Each obsidian robot costs 3 ore and 8 clay.\n Each geode robot costs 3 ore and 12 obsidian.\n`\n .split(\"\\n\\n\")\n .map((block) => block.split(\"\\n \").join(\"\"))\n .join(\"\\n\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":284,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"// reformat inputs into objects having minerals als attributes\ninputObjects = inputs\n .split(\"\\n\")\n .filter((line) => line.length > 0)\n .map((line) => line.split(/[:.][ ]/).map((el) => el.split(\" \")))\n .map((line) => {\n return {\n id: line[0][1],\n ore: {\n ore: line[1][4]\n },\n clay: {\n ore: line[2][4]\n },\n obsidian: {\n ore: line[3][4],\n clay: line[3][7]\n },\n geode: {\n ore: line[4][4],\n obsidian: line[4][7]\n }\n };\n })","pinned":true,"hidden":false,"mode":"ojs"},{"id":147,"value":"// our 4 minerals\nkeys = [\"ore\", \"clay\", \"obsidian\", \"geode\"]","pinned":true,"hidden":false,"mode":"ojs"},{"id":149,"value":"// calculate maximun needed cash values (to stop searching in later steps early)\nblueprints = inputObjects.map((blueprint) => {\n blueprint.maxCash = [];\n keys.forEach((k) => {\n Object.keys(blueprint[k]).forEach((c) => {\n blueprint.maxCash[c] =\n (blueprint.maxCash[c] == undefined && blueprint[k][c] != undefined) ||\n blueprint.maxCash[c] < blueprint[k][c]\n ? blueprint[k][c]\n : blueprint.maxCash[c];\n });\n });\n return blueprint;\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":29,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":474,"value":"// loop all blueprints and process each one searching for maximum output\nprocessBlueprints = function* (blueprints, minutes) {\n for (let blueprint of blueprints) {\n // init robots and cash values\n let robots = Object.fromEntries(keys.map((k) => [k, k == \"ore\" ? 1 : 0]));\n let cash = Object.fromEntries(keys.map((k) => [k, 0]));\n\n // some more initial values to track\n blueprint.max = {\n value: 0\n };\n blueprint.cnt = 0;\n blueprint.history = [];\n\n // run recursively all possibilities until maximum minutes is reached\n let processed = new Map();\n nextMinute(0, blueprint, robots, cash, processed, minutes);\n\n yield blueprints;\n }\n yield blueprints;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":662,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":491,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":902,"value":"// calculate sum of quality levels for blueprints, based on ID and maximum geode output\nqualityLevel = (blueprint) =>\n blueprint.reduce(\n (acc, blueprint) => acc + Number(blueprint.id) * blueprint.max.value,\n 0\n )","pinned":true,"hidden":false,"mode":"ojs"},{"id":909,"value":"// multiply max. number of geodes of these three blueprints\ngeodesProduct = (blueprint) =>\n blueprint.reduce((acc, curr) => acc * curr.max.value, 1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":156,"value":"## Part 1","pinned":false,"hidden":false,"mode":"md"},{"id":584,"value":"minutes1 = 24","pinned":true,"hidden":false,"mode":"ojs"},{"id":127,"value":"// process all blueprints (for 24 minutes)\nblueprintResults1 = iterateBlueprints(\n blueprints.map((bp) => Object.assign({}, bp)),\n minutes1\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":268,"value":"// calculate sum of quality levels for blueprints, based on ID and maximum geode output\nresult1 = qualityLevel(blueprintResults1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":500,"value":"plotResults(blueprintResults1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":166,"value":"## Part 2","pinned":false,"hidden":false,"mode":"md"},{"id":560,"value":"minutes2 = 32","pinned":true,"hidden":false,"mode":"ojs"},{"id":670,"value":"// process only the first 3 blueprints, but for 32 minutes)\nblueprintResults2 = iterateBlueprints(\n blueprints.slice(0, 3).map((bp) => Object.assign({}, bp)),\n minutes2\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":886,"value":"// multiply max. number of geodes of these three blueprints\nresult2 = geodesProduct(blueprintResults2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":551,"value":"plotResults(blueprintResults2)","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}