diff options
Diffstat (limited to '07.c')
| -rw-r--r-- | 07.c | 20 |
1 files changed, 13 insertions, 7 deletions
@@ -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); } |