From b7a23dec32a13984a7c1c68acfff70ae3d8ca4b2 Mon Sep 17 00:00:00 2001 From: Vincent Douillet Date: Wed, 8 Dec 2021 16:08:22 +0100 Subject: day 7 lookup table --- 07.c | 20 +++++++++++++------- 1 file changed, 13 insertions(+), 7 deletions(-) (limited to '07.c') diff --git a/07.c b/07.c index 20caf95..e46c8c0 100644 --- a/07.c +++ b/07.c @@ -42,12 +42,14 @@ void part1(struct input_str* input) { CHECK(fuel_min, EXPECTED1); } -long compute_fuel(int distance) { - long fuel = 0; - for(int i = 1; i <= distance; i++) { - fuel += i; - } - return fuel; +long compute_fuel(int distance, long* lookup_table) { + if(distance <= 0) + return 0; + if(lookup_table[distance] != 0) + return lookup_table[distance]; + + lookup_table[distance] = distance + compute_fuel(distance - 1, lookup_table); + return lookup_table[distance]; } void part2(struct input_str* input) { @@ -68,11 +70,15 @@ void part2(struct input_str* input) { } // brute force + // computing the fuel needed from the distance is costly so we use a lookup table to compute fuel only the first time it's needed for a given distance + // exec time with lookup table = 0.2s + // exec time without = 12.7s long fuel_min = LONG_MAX; + long lookup_table[INPUT_DOMAIN_MAX] = { 0 }; for(int a = 0; a < INPUT_DOMAIN_MAX; a++) { long current_fuel = 0; for(int b = 0; b < INPUT_DOMAIN_MAX; b++) { - current_fuel += sub_count_by_alt[b] * compute_fuel(ABS(b - a)); + current_fuel += sub_count_by_alt[b] * compute_fuel(ABS(b - a), lookup_table); } fuel_min = MIN(fuel_min, current_fuel); } -- cgit v1.2.3