1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include "input.h"
#define ABS(x) (x < 0 ? -(x) : x)
#define MIN(x, y) (x < y ? x : y)
#define INPUT "input/07.txt"
#define INPUT_DOMAIN_MAX 2000
#define EXPECTED1 349769L
#define EXPECTED2 99540554L
void part1(struct input_str* input) {
char* start = input->lines[0];
char* end = start;
int sub_count_by_alt[INPUT_DOMAIN_MAX] = { 0 };
// parse input
long sub_count = 0;
while(*end != '\n') {
long alt = strtol(start, &end, 0);
start = end;
if(*end == ',')
start++;
sub_count_by_alt[alt]++;
sub_count++;
}
// brute force
long fuel_min = LONG_MAX;
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] * ABS(b - a);
}
fuel_min = MIN(fuel_min, current_fuel);
}
CHECK(fuel_min, EXPECTED1);
}
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) {
char* start = input->lines[0];
char* end = start;
int sub_count_by_alt[INPUT_DOMAIN_MAX] = { 0 };
// parse input
long sub_count = 0;
while(*end != '\n') {
long alt = strtol(start, &end, 0);
start = end;
if(*end == ',')
start++;
sub_count_by_alt[alt]++;
sub_count++;
}
// 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), lookup_table);
}
fuel_min = MIN(fuel_min, current_fuel);
}
CHECK(fuel_min, EXPECTED2);
}
int main() {
// read input
struct input_str input;
input_str_read(&input, INPUT);
// do stuff
part1(&input);
part2(&input);
// cleanup & exit
input_str_free(&input);
return 0;
}
|
