From 0fcf120446f29f4715a422744ad70eb06247c500 Mon Sep 17 00:00:00 2001 From: Adam Spragg Date: Thu, 19 Jan 2023 14:16:54 +0000 Subject: Puzzle 19: Don't build a robot if we could have built it earlier Either we don't need it, or we did but it's too late. Speeds up part 2 from 570s (9m30s) to 5.2s --- 19.c | 32 ++++++++++++++++++++++++++++++-- 1 file changed, 30 insertions(+), 2 deletions(-) diff --git a/19.c b/19.c index c1740e2..0f13c0c 100644 --- a/19.c +++ b/19.c @@ -217,6 +217,31 @@ inventory_build_basic(struct inventory * i, struct blueprint const * b, int rema long exhaustive_iter; +// Exhastive(ish) build strategy +// +// Try all^Wmost combinations of building different robots at different times +// +// We actually cheat and only try building on certain conditions: +// +// if (i->MATERIAL.robots < b->max_MATERIAL) +// +// max_MATERIAL is the maximum amount of MATERIAL it takes to build +// any robot. Given that we can only build one robot per round, we +// can never spend more than max_MATERIAL units per round, so we +// never need more than max_MATERIAL robots of that type. +// +// if (i->MATERIAL.amount < 2 * b->max_MATERIAL) +// +// If we already have a lot of MATERIAL, we probably don't need +// another robot to collect that type right now. +// +// if (i->MATERIAL.amount < 2 * b->ROBOT_MATERIAL) +// +// If we could have built a robot of a certain type some time ago, +// but didn't, then either a) this is a good build combination and +// we don't need it, or b) this is a bad build combination and we +// did, but there isn't much point in going further down that +// rabbit hole now. void inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int remaining) { @@ -257,6 +282,8 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int // Try building a obsidian robot, and checking if that's better than anything else if (i->bsdn.robots < b->max_bsdn && i->bsdn.amount < 2 * b->max_bsdn + && (i->clay.amount < 2 * b->bsdn_clay + || i->ore.amount < 2 * b->bsdn_ore) && inventory_build(&test, b, BSDN) == 0) { // fprintf(stderr, "%d: building a bsdn robot (%ld)\n", remaining, test.bsdn.amount); @@ -270,6 +297,7 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int // Try building a clay robot, and checking if that's better than anything else if (i->clay.robots < b->max_clay && i->clay.amount < 2 * b->max_clay + && i->ore.amount < 2 * b->clay_ore && remaining > 5 && inventory_build(&test, b, CLAY) == 0) { @@ -284,6 +312,7 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int // Try building a ore robot, and checking if that's better than anything else if (i->ore.robots < b->max_ore && i->ore.amount < 2 * b->max_ore + && i->ore.amount < 2 * b->ore_ore && remaining > 10 && inventory_build(&test, b, ORE) == 0) { @@ -309,8 +338,7 @@ main(int argc, char ** argv) regex_t reblueprint; char buf[BUFSIZ]; - while ((i = getopt(argc, argv, "p:b:o:r:")) != -1) - { + while ((i = getopt(argc, argv, "p:b:o:r:")) != -1) { switch (i) { case 'p': switch (atoi(optarg)) { -- cgit v1.2.1