index.js (7825B)
1 const fs = require('fs'); 2 3 String.prototype.startsWith = function(subject) { 4 return this.substr(0, subject.length) === subject; 5 }; 6 7 const blueprints = fs.readFileSync('input', 'utf-8') 8 // const blueprints = fs.readFileSync('sample', 'utf-8') 9 .split('\n') 10 .filter(l => l) 11 .map(l => l.match(/\d+/g).map(d => parseInt(d))) 12 .map(l => ({ 13 id : l[0], 14 ore : { ore: l[1] }, 15 clay : { ore: l[2] }, 16 obsidian: { ore: l[3], clay : l[4] }, 17 geode : { ore: l[5], obsidian: l[6] }, 18 })) 19 ; 20 21 function canBuild(blueprint, resources, name) { 22 for(const resourceType in blueprint[name]) { 23 if (blueprint[name][resourceType] > resources[resourceType]) return false; 24 } 25 return true; 26 } 27 28 function step(resources, robots, amount = 1) { 29 for(const resourceType in robots) { 30 resources[resourceType] += robots[resourceType] * amount; 31 } 32 } 33 34 function when(blueprint, resources, robots, name) { 35 let timeCost = 0; 36 resources = {...resources}; 37 while(!canBuild(blueprint, resources, name)) { 38 timeCost++; 39 step(resources, robots); 40 } 41 return timeCost; 42 } 43 44 function simulate(blueprint, time) { 45 let maxGeodes = 0; 46 let counter = 0; 47 const max = { 48 clay: blueprint.obsidian.clay, 49 ore : Math.max( 50 blueprint.geode.ore, 51 blueprint.obsidian.ore, 52 ), 53 }; 54 const openset = [{ 55 time: 0, 56 resources: { 57 ore : 0, 58 clay : 0, 59 obsidian : 0, 60 geode : 0, 61 }, 62 robots: { 63 ore : 1, 64 clay : 0, 65 obsidian : 0, 66 geode : 0, 67 }, 68 }]; 69 let minlen = Infinity; 70 let maxlen = -Infinity; 71 let mintime = Infinity; 72 let logint = 1e4; 73 let logtime = Date.now() + logint; 74 while(openset.length) { 75 // Calculate END state 76 const state = openset.pop(); 77 const total = { 78 ore : state.resources.ore + (state.robots.ore * (time - state.time)), 79 clay : state.resources.clay + (state.robots.clay * (time - state.time)), 80 obsidian: state.resources.obsidian + (state.robots.obsidian * (time - state.time)), 81 geode : state.resources.geode + (state.robots.geode * (time - state.time)), 82 }; 83 84 if (openset.length < minlen ) minlen = openset.length; 85 if (openset.length > maxlen ) maxlen = openset.length; 86 if (state.time < mintime) mintime = state.time; 87 counter++; 88 if (Date.now() >= logtime) { 89 logtime += logint; 90 console.log(JSON.stringify({ 91 time: mintime, 92 l: minlen, 93 h: maxlen, counter, 94 maxGeodes, 95 })); 96 minlen = Infinity; 97 maxlen = -Infinity; 98 mintime = Infinity; 99 counter = 0; 100 } 101 102 // Keep track of max geodes 103 if (total.geode > maxGeodes) { 104 maxGeodes = total.geode; 105 } 106 107 // Build geode robot 108 if (canBuild(blueprint, total, 'geode')) { 109 const skip = 1 + when(blueprint, state.resources, state.robots, 'geode'); 110 // console.log(`Can build obsidian after after ${skip} minute(s) at ${state.time + skip}`); 111 if ((state.time + skip) < time) { 112 // console.log(` Building`); 113 openset.push({ 114 time: state.time + skip, 115 resources: { 116 ore : state.resources.ore + (state.robots.ore * skip) - blueprint.geode.ore, 117 clay : state.resources.clay + (state.robots.clay * skip), 118 obsidian : state.resources.obsidian + (state.robots.obsidian * skip) - blueprint.geode.obsidian, 119 geode : state.resources.geode + (state.robots.geode * skip), 120 }, 121 robots: { 122 ...state.robots, 123 geode : state.robots.geode + 1, 124 }, 125 }); 126 } else { 127 // console.log(` Takes too much time, ditching state: ${state.time + skip} >= ${time}`); 128 } 129 } 130 131 // Build obsidian robot 132 if (canBuild(blueprint, total, 'obsidian')) { 133 const skip = 1 + when(blueprint, state.resources, state.robots, 'obsidian'); 134 // console.log(`Can build obsidian after after ${skip} minute(s) at ${state.time + skip}`); 135 if ((state.time + skip + 1) < time) { 136 // console.log(` Building`); 137 openset.push({ 138 time: state.time + skip, 139 resources: { 140 ore : state.resources.ore + (state.robots.ore * skip) - blueprint.obsidian.ore, 141 clay : state.resources.clay + (state.robots.clay * skip) - blueprint.obsidian.clay, 142 obsidian : state.resources.obsidian + (state.robots.obsidian * skip), 143 geode : state.resources.geode + (state.robots.geode * skip), 144 }, 145 robots: { 146 ...state.robots, 147 obsidian : state.robots.obsidian + 1, 148 }, 149 }); 150 } else { 151 // console.log(` Takes too much time, ditching state: ${state.time + skip} >= ${time}`); 152 } 153 } 154 155 // Build clay robot 156 if (canBuild(blueprint, total, 'clay') && state.robots.clay < max.clay) { 157 const skip = 1 + when(blueprint, state.resources, state.robots, 'clay'); 158 // console.log(`Can build clay after after ${skip} minute(s) at ${state.time + skip}`); 159 if ((state.time + skip + 2) < time) { 160 // console.log(` Building`); 161 openset.push({ 162 time: state.time + skip, 163 resources: { 164 ore : state.resources.ore + (state.robots.ore * skip) - blueprint.clay.ore, 165 clay : state.resources.clay + (state.robots.clay * skip), 166 obsidian : state.resources.obsidian + (state.robots.obsidian * skip), 167 geode : state.resources.geode + (state.robots.geode * skip), 168 }, 169 robots: { 170 ...state.robots, 171 clay : state.robots.clay + 1, 172 }, 173 }); 174 } else { 175 // console.log(` Takes too much time, ditching state: ${state.time + skip} >= ${time}`); 176 } 177 178 // state.time += skip; 179 // step(state.resources, state.robots, skip); 180 // state.resources.ore -= blueprint.clay.ore; 181 182 // console.log(`Can build clay after after ${skip} minute(s)`); 183 } 184 185 // Build ore robot 186 if (canBuild(blueprint, total, 'ore') && state.robots.ore < max.ore) { 187 const skip = 1 + when(blueprint, state.resources, state.robots, 'ore'); 188 // console.log(`Can build ore after after ${skip} minute(s) at ${state.time + skip}`); 189 if ((state.time + skip + 1) < time) { 190 // console.log(` Building`); 191 openset.push({ 192 time: state.time + skip, 193 resources: { 194 ore : state.resources.ore + (state.robots.ore * skip) - blueprint.ore.ore, 195 clay : state.resources.clay + (state.robots.clay * skip), 196 obsidian : state.resources.obsidian + (state.robots.obsidian * skip), 197 geode : state.resources.geode + (state.robots.geode * skip), 198 }, 199 robots: { 200 ...state.robots, 201 ore : state.robots.ore + 1, 202 }, 203 }); 204 } else { 205 // console.log(` Takes too much time, ditching state: ${state.time + skip} >= ${time}`); 206 } 207 } 208 209 // Sort by most important resources 210 openset.sort((a, b) => { 211 return 0 || 212 (a.resources.geode - b.resources.geode ) || 213 (a.resources.obsidian - b.resources.obsidian) || 214 (a.resources.clay - b.resources.clay ) || 215 (a.resources.ore - b.resources.ore ); 216 }); 217 218 } 219 220 console.log({ id: blueprint.id, time, maxGeodes }); 221 return maxGeodes; 222 } 223 224 let step1 = 0; 225 let step2 = 1; 226 for(let i=0; i<blueprints.length; i++) 227 step1 += simulate(blueprints[i], 24) * blueprints[i].id; 228 229 for(let i=0; i<Math.min(blueprints.length, 3); i++) 230 step2 *= simulate(blueprints[i], 32); 231 232 console.log({ step1, step2 });