From 2e85da91bb8ff59faa74213d9b2428abacb8dcc9 Mon Sep 17 00:00:00 2001 From: Adam Spragg Date: Sun, 29 Jan 2023 16:30:46 +0000 Subject: Puzzle 19: Separate "exhaustive" and "exhaustive w/ shortcuts" builds Allows playing with the shortcuts more easily, while keeping a strictly exhaustive strategy around for comparison. --- 19.c | 99 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 87 insertions(+), 12 deletions(-) diff --git a/19.c b/19.c index c147555..20c5bf5 100644 --- a/19.c +++ b/19.c @@ -243,7 +243,84 @@ inventory_build_basic(struct inventory * i, struct blueprint const * b, int rema } -// Exhastive(ish) build strategy +// Exhastive build strategy +// +// Try all combinations of building different robots at different times +void +inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int remaining) +{ + struct inventory best, test; + + if (inventory_build_max(i, b, remaining)) + return; + + best = *i; + 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); + inventory_tick(&test); + inventory_build_exhaustive(&test, b, remaining - 1); + if (inventory_cmp(&test, &best) > 0) + best = test; + test = *i; + } + + // Try building a obsidian robot, and checking if that's better than anything else + 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); + if (inventory_cmp(&test, &best) > 0) + best = test; + test = *i; + } + + // Try building a clay robot, and checking if that's better than anything else + 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); + if (inventory_cmp(&test, &best) > 0) + best = test; + test = *i; + } + + // Try building a ore robot, and checking if that's better than anything else + 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); + if (inventory_cmp(&test, &best) > 0) + best = test; + test = *i; + } + + *i = best; +} + + +// Shortcuts to the exhastive build strategy // // Try all^Wmost combinations of building different robots at different times // @@ -269,7 +346,7 @@ inventory_build_basic(struct inventory * i, struct blueprint const * b, int rema // 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) +inventory_build_shortcut(struct inventory * i, struct blueprint const * b, int remaining) { struct inventory best, test; @@ -285,8 +362,7 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int || i->bsdn.amount < b->max_bsdn) { inventory_tick(&test); -// fprintf(stderr, "%d: doing nothing\n", remaining); - inventory_build_exhaustive(&test, b, remaining - 1); + inventory_build_shortcut(&test, b, remaining - 1); if (inventory_cmp(&test, &best) > 0) best = test; test = *i; @@ -294,9 +370,8 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int // 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); inventory_tick(&test); - inventory_build_exhaustive(&test, b, remaining - 1); + inventory_build_shortcut(&test, b, remaining - 1); if (inventory_cmp(&test, &best) > 0) best = test; test = *i; @@ -309,9 +384,8 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int || 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); inventory_tick(&test); - inventory_build_exhaustive(&test, b, remaining - 1); + inventory_build_shortcut(&test, b, remaining - 1); if (inventory_cmp(&test, &best) > 0) best = test; test = *i; @@ -324,9 +398,8 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int && remaining > 5 && 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); + inventory_build_shortcut(&test, b, remaining - 1); if (inventory_cmp(&test, &best) > 0) best = test; test = *i; @@ -339,9 +412,8 @@ inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int && remaining > 10 && 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); + inventory_build_shortcut(&test, b, remaining - 1); if (inventory_cmp(&test, &best) > 0) best = test; test = *i; @@ -440,6 +512,9 @@ main(int argc, char ** argv) else if (strcmp(build, "exhaustive") == 0) { inventory_build_exhaustive(&i, &b, rounds); } + else if (strcmp(build, "shortcut") == 0) { + inventory_build_shortcut(&i, &b, rounds); + } else { fprintf(stderr, "Unknown build strategy: %s\n", build); regfree(&reblueprint); -- cgit v1.2.1