From b043397f2718dec1879e4b438518378ad70dbace Mon Sep 17 00:00:00 2001 From: Adam Spragg Date: Sat, 31 Dec 2022 15:23:31 +0000 Subject: Puzzle 19: Never build more robots than needed Because we can only build one robot at a time, if the most expensive robot in terms of ore takes 4 ore to build, we'll never need more than 4 ore robots. Because they can always collect enough ore to build one robot of any type per turn. Drops time by 90% on 20-round test data (5.4s -> 0.5s) --- 19.c | 22 +++++++++++++++++++--- 1 file changed, 19 insertions(+), 3 deletions(-) (limited to '19.c') diff --git a/19.c b/19.c index 4e1cfb3..a534090 100644 --- a/19.c +++ b/19.c @@ -8,6 +8,8 @@ #define arrlen(x) (sizeof(x)/sizeof((x)[0])) +#define max(a, b) ((a) > (b) ? (a) : (b)) + enum MATERIAL { ORE, @@ -25,6 +27,10 @@ struct blueprint { int bsdn_clay; int geod_ore; int geod_bsdn; + + int max_ore; + int max_clay; + int max_bsdn; }; @@ -39,6 +45,10 @@ blueprint_ctor(struct blueprint * b, int id, int ore_ore, int clay_ore, b->bsdn_clay = bsdn_clay; b->geod_ore = geod_ore; b->geod_bsdn = geod_bsdn; + + b->max_ore = max(max(b->ore_ore, b->clay_ore), max(b->bsdn_ore, b->geod_ore)); + b->max_clay = b->bsdn_clay; + b->max_bsdn = b->geod_bsdn; } @@ -237,7 +247,9 @@ 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 (inventory_build(&test, b, BSDN) == 0) { + if (i->bsdn.robots < b->max_bsdn + && inventory_build(&test, b, BSDN) == 0) + { // fprintf(stderr, "%d: building a bsdn robot (%ld)\n", remaining, test.bsdn.amount); inventory_tick(&test); inventory_build_exhaustive(&test, b, remaining - 1); @@ -247,7 +259,9 @@ 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 (inventory_build(&test, b, CLAY) == 0) { + if (i->clay.robots < b->max_clay + && inventory_build(&test, b, CLAY) == 0) + { // fprintf(stderr, "%d: building a clay robot (%ld)\n", remaining, test.clay.amount); inventory_tick(&test); inventory_build_exhaustive(&test, b, remaining - 1); @@ -257,7 +271,9 @@ 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 (inventory_build(&test, b, ORE) == 0) { + if (i->ore.robots < b->max_ore + && inventory_build(&test, b, ORE) == 0) + { // fprintf(stderr, "%d: building a ore robot (%ld)\n", remaining, test.ore.amount); inventory_tick(&test); inventory_build_exhaustive(&test, b, remaining - 1); -- cgit v1.2.1