day 7 lookup table

1 files changed, 13 insertions, 7 deletions

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);
 	}