From d9749f519f1587ce6be9acb5617fe1300d95da3b Mon Sep 17 00:00:00 2001 From: Adam Spragg Date: Sat, 31 Dec 2022 16:33:06 +0000 Subject: Puzzle 19: Don't do nothing if we could build all robots. The only reason to do nothing would be to save resources to build a robot we can't affort to build yet. But if we have enough resources to build all of them, there's no point in not building any Drops time by 35% on full 24-round test data (7.2s -> 4.6s) --- 19.c | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-) diff --git a/19.c b/19.c index cccc746..2700712 100644 --- a/19.c +++ b/19.c @@ -228,14 +228,22 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int ++exhaustive_iter; - // Try doing nothing else this round. best = *i; - inventory_tick(&best); -// fprintf(stderr, "%d: doing nothing\n", remaining); - inventory_build_exhaustive(&best, b, remaining - 1); - test = *i; + // If there are some robots we can't build yet, try doing nothing this round. + if (i->ore.amount < b->max_ore + || i->clay.amount < b->max_clay + || i->bsdn.amount < b->max_bsdn) + { + inventory_tick(&test); +// fprintf(stderr, "%d: doing nothing\n", remaining); + inventory_build_exhaustive(&test, b, remaining - 1); + if (inventory_cmp(&test, &best) > 0) + best = test; + test = *i; + } + // Try building a geode robot, and check if that's better than doing nothing. if (inventory_build(&test, b, GEOD) == 0) { // fprintf(stderr, "%d: building a geod robot (%ld)\n", remaining, test.geod.amount); -- cgit v1.2.1