- commit
- 51e3359997a003402bf9f171eb2bfc680764962d
- parent
- fd924f36e44c59a8e79d91dd7854ce3f5ab9dc2e
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-19 14:40
2022-12-19
Diffstat
| A | 2022/19/input.txt | 30 | ++++++++++++++++++++++++++++++ |
| A | 2022/19/solution.rs | 188 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/19/test.txt | 2 | ++ |
3 files changed, 220 insertions, 0 deletions
diff --git a/2022/19/input.txt b/2022/19/input.txt
@@ -0,0 +1,30 @@ -1 1 Blueprint 1: 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 15 obsidian. -1 2 Blueprint 2: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 17 clay. Each geode robot costs 2 ore and 13 obsidian. -1 3 Blueprint 3: 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. -1 4 Blueprint 4: Each ore robot costs 2 ore. Each clay robot costs 2 ore. Each obsidian robot costs 2 ore and 20 clay. Each geode robot costs 2 ore and 14 obsidian. -1 5 Blueprint 5: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 12 clay. Each geode robot costs 2 ore and 10 obsidian. -1 6 Blueprint 6: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 3 ore and 7 clay. Each geode robot costs 4 ore and 11 obsidian. -1 7 Blueprint 7: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 9 clay. Each geode robot costs 3 ore and 15 obsidian. -1 8 Blueprint 8: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 10 clay. Each geode robot costs 2 ore and 7 obsidian. -1 9 Blueprint 9: 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 4 ore and 9 obsidian. -1 10 Blueprint 10: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 19 clay. Each geode robot costs 2 ore and 18 obsidian. -1 11 Blueprint 11: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 17 clay. Each geode robot costs 3 ore and 10 obsidian. -1 12 Blueprint 12: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 10 clay. Each geode robot costs 4 ore and 10 obsidian. -1 13 Blueprint 13: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 16 clay. Each geode robot costs 3 ore and 14 obsidian. -1 14 Blueprint 14: 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. -1 15 Blueprint 15: Each ore robot costs 3 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 18 clay. Each geode robot costs 3 ore and 8 obsidian. -1 16 Blueprint 16: Each ore robot costs 2 ore. Each clay robot costs 4 ore. Each obsidian robot costs 4 ore and 11 clay. Each geode robot costs 3 ore and 8 obsidian. -1 17 Blueprint 17: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 17 clay. Each geode robot costs 4 ore and 8 obsidian. -1 18 Blueprint 18: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 6 clay. Each geode robot costs 3 ore and 11 obsidian. -1 19 Blueprint 19: 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 3 ore and 18 obsidian. -1 20 Blueprint 20: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 14 clay. Each geode robot costs 4 ore and 11 obsidian. -1 21 Blueprint 21: 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. -1 22 Blueprint 22: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 19 clay. Each geode robot costs 2 ore and 12 obsidian. -1 23 Blueprint 23: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 17 clay. Each geode robot costs 3 ore and 13 obsidian. -1 24 Blueprint 24: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 2 ore and 16 clay. Each geode robot costs 2 ore and 8 obsidian. -1 25 Blueprint 25: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 19 clay. Each geode robot costs 2 ore and 9 obsidian. -1 26 Blueprint 26: Each ore robot costs 2 ore. Each clay robot costs 2 ore. Each obsidian robot costs 2 ore and 7 clay. Each geode robot costs 2 ore and 14 obsidian. -1 27 Blueprint 27: Each ore robot costs 4 ore. Each clay robot costs 3 ore. Each obsidian robot costs 4 ore and 5 clay. Each geode robot costs 3 ore and 10 obsidian. -1 28 Blueprint 28: Each ore robot costs 4 ore. Each clay robot costs 4 ore. Each obsidian robot costs 2 ore and 15 clay. Each geode robot costs 3 ore and 16 obsidian. -1 29 Blueprint 29: Each ore robot costs 3 ore. Each clay robot costs 3 ore. Each obsidian robot costs 2 ore and 14 clay. Each geode robot costs 3 ore and 17 obsidian. -1 30 Blueprint 30: 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.
diff --git a/2022/19/solution.rs b/2022/19/solution.rs
@@ -0,0 +1,188 @@
-1 1 use std::collections::HashSet;
-1 2 use std::thread;
-1 3
-1 4 #[path = "../lib.rs"] mod lib;
-1 5
-1 6 fn get_blueprints() -> Vec<[[usize; 4]; 4]> {
-1 7 let mut blueprints = vec![];
-1 8 for line in lib::iter_input() {
-1 9 let parts = line.split(" ").collect::<Vec<&str>>();
-1 10 let ore_robot_ore_cost = parts[6].parse().unwrap();
-1 11 let clay_robot_ore_cost = parts[12].parse().unwrap();
-1 12 let obsidian_robot_ore_cost = parts[18].parse().unwrap();
-1 13 let obsidian_robot_clay_cost = parts[21].parse().unwrap();
-1 14 let geode_robot_ore_cost = parts[27].parse().unwrap();
-1 15 let geode_robot_obsidian_cost = parts[30].parse().unwrap();
-1 16 blueprints.push([
-1 17 [ore_robot_ore_cost, 0, 0, 0],
-1 18 [clay_robot_ore_cost, 0, 0, 0],
-1 19 [obsidian_robot_ore_cost, obsidian_robot_clay_cost, 0, 0],
-1 20 [geode_robot_ore_cost, 0, geode_robot_obsidian_cost, 0],
-1 21 ]);
-1 22 }
-1 23 return blueprints;
-1 24 }
-1 25
-1 26 fn get_baseline(blueprint: &[[usize; 4]; 4], turns: usize) -> usize {
-1 27 // thought up strategy that should yield good results.
-1 28 // I am not sure if this is ideal though, so we will do a thorough search afterwards.
-1 29
-1 30 let mut n = turns;
-1 31 let mut resources = [0, 0, 0, 0];
-1 32 let mut robots = [1, 0, 0, 0];
-1 33
-1 34 // build enough ore robots to sustain geode robot production
-1 35 while n > 0 && robots[0] < blueprint[3][0] {
-1 36 let build = (0..4).all(|j| resources[j] >= blueprint[0][j]);
-1 37 n -= 1;
-1 38 for j in 0..4 {
-1 39 resources[j] += robots[j];
-1 40 }
-1 41 if build {
-1 42 for j in 0..4 {
-1 43 resources[j] -= blueprint[0][j];
-1 44 }
-1 45 robots[0] += 1;
-1 46 }
-1 47 }
-1 48
-1 49 // build enough obsidian robots to sustain geode robot production
-1 50 // and then only build geode robots
-1 51 while n > 0 {
-1 52 let can_clay = (0..4).all(|j| resources[j] >= blueprint[1][j]);
-1 53 let can_obsidian = (0..4).all(|j| resources[j] >= blueprint[2][j]);
-1 54 let can_geode = (0..4).all(|j| resources[j] >= blueprint[3][j]);
-1 55
-1 56 let need_obsidian = robots[2] < blueprint[3][2];
-1 57 let need_clay = need_obsidian && robots[1] < blueprint[2][1] && resources[1] < blueprint[2][1];
-1 58
-1 59 n -= 1;
-1 60 for j in 0..4 {
-1 61 resources[j] += robots[j];
-1 62 }
-1 63
-1 64 if can_geode {
-1 65 for j in 0..4 {
-1 66 resources[j] -= blueprint[3][j];
-1 67 }
-1 68 robots[3] += 1;
-1 69 } else if need_obsidian && can_obsidian {
-1 70 for j in 0..4 {
-1 71 resources[j] -= blueprint[2][j];
-1 72 }
-1 73 robots[2] += 1;
-1 74 } else if need_clay && can_clay {
-1 75 for j in 0..4 {
-1 76 resources[j] -= blueprint[1][j];
-1 77 }
-1 78 robots[1] += 1;
-1 79 }
-1 80 }
-1 81
-1 82 return resources[3];
-1 83 }
-1 84
-1 85 fn get_max_geodes(blueprint: &[[usize; 4]; 4], turns: usize) -> usize {
-1 86 let mut best_geodes = get_baseline(blueprint, turns);
-1 87 let mut queue = vec![
-1 88 ([0, 0, 0, 0], [1, 0, 0, 0], turns),
-1 89 ];
-1 90 let mut used = HashSet::new();
-1 91
-1 92 while let Some((resources, robots, n)) = queue.pop() {
-1 93 let min_geodes = resources[3] + robots[3] * n;
-1 94 let potential = n * (n - 1) / 2;
-1 95 if min_geodes + potential <= best_geodes {
-1 96 continue;
-1 97 }
-1 98
-1 99 if used.contains(&(resources, robots, n)) {
-1 100 continue;
-1 101 } else {
-1 102 used.insert((resources, robots, n));
-1 103 }
-1 104
-1 105 let mut build = vec![];
-1 106
-1 107 // if it is possible to build a geode, always do that
-1 108 if (0..4).all(|j| resources[j] >= blueprint[3][j]) {
-1 109 build.push(3);
-1 110 } else {
-1 111 let need_obsidian = robots[2] < blueprint[3][2];
-1 112 let need_clay = need_obsidian && robots[1] < blueprint[2][1];
-1 113 let need_ore = robots[0] < blueprint[3][0] || (
-1 114 need_obsidian && robots[0] < blueprint[2][0]
-1 115 ) || (
-1 116 need_clay && robots[0] < blueprint[1][0]
-1 117 );
-1 118
-1 119 build.push(4);
-1 120 if need_ore && (0..4).all(|j| resources[j] >= blueprint[0][j]) {
-1 121 build.push(0);
-1 122 }
-1 123 if need_clay && (0..4).all(|j| resources[j] >= blueprint[1][j]) {
-1 124 build.push(1);
-1 125 }
-1 126 if need_obsidian && (0..4).all(|j| resources[j] >= blueprint[2][j]) {
-1 127 build.push(2);
-1 128 }
-1 129 }
-1 130
-1 131 for i in build {
-1 132 let mut next_resources = [
-1 133 resources[0] + robots[0],
-1 134 resources[1] + robots[1],
-1 135 resources[2] + robots[2],
-1 136 resources[3] + robots[3],
-1 137 ];
-1 138 let mut next_robots = robots.clone();
-1 139 if i < 4 {
-1 140 for j in 0..4 {
-1 141 next_resources[j] -= blueprint[i][j];
-1 142 }
-1 143 next_robots[i] += 1;
-1 144 }
-1 145
-1 146 let min_geodes = next_resources[3] + next_robots[3] * (n - 1);
-1 147 if min_geodes > best_geodes {
-1 148 best_geodes = min_geodes;
-1 149 }
-1 150
-1 151 queue.push((next_resources, next_robots, n - 1));
-1 152 }
-1 153 }
-1 154
-1 155 return best_geodes;
-1 156 }
-1 157
-1 158 fn part1(blueprints: &Vec<[[usize; 4]; 4]>) -> usize {
-1 159 let mut handles = vec![];
-1 160 for (i, blueprint) in blueprints.iter().enumerate() {
-1 161 let b = blueprint.clone();
-1 162 handles.push(thread::spawn(move || {
-1 163 return get_max_geodes(&b, 24) * (i + 1);
-1 164 }));
-1 165 }
-1 166 return handles.into_iter()
-1 167 .map(|handle| handle.join().unwrap())
-1 168 .sum();
-1 169 }
-1 170
-1 171 fn part2(blueprints: &Vec<[[usize; 4]; 4]>) -> usize {
-1 172 let mut handles = vec![];
-1 173 for blueprint in blueprints.iter().take(3) {
-1 174 let b = blueprint.clone();
-1 175 handles.push(thread::spawn(move || {
-1 176 return get_max_geodes(&b, 32);
-1 177 }));
-1 178 }
-1 179 return handles.into_iter()
-1 180 .map(|handle| handle.join().unwrap())
-1 181 .product();
-1 182 }
-1 183
-1 184 fn main() {
-1 185 let blueprints = get_blueprints();
-1 186 println!("part1: {}", part1(&blueprints));
-1 187 println!("part2: {}", part2(&blueprints));
-1 188 }
diff --git a/2022/19/test.txt b/2022/19/test.txt
@@ -0,0 +1,2 @@ -1 1 Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian. -1 2 Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian.