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
102
103
104
105
106
107
108
109
|
#include <stdlib.h>
#include <stdio.h>
#include <err.h>
#include <stdbool.h>
#include "input.h"
#define INPUT "input/03.txt"
#define INPUT_SIZE 12
unsigned long parse_line(char* binary_line, char expected_end) {
char* endp = NULL;
unsigned long result = strtoul(binary_line, &endp, 2);
if(*endp != expected_end)
err(1, "cannot parse line: %s\n", binary_line);
return result;
}
unsigned long compute_gamma(struct input_str* input) {
int oneCount[INPUT_SIZE];
// TODO is that necessary ?
for(int k = 0; k < INPUT_SIZE; k++) {
oneCount[k] = 0;
}
for(size_t i = 0; i < input->line_count; i++) {
char* line = input->lines[i];
for(int j = 0; j < INPUT_SIZE; j++) {
if(line[j] == '1')
oneCount[j]++;
}
}
// null terminated string
char binary[INPUT_SIZE + 1];
for(int h = 0; h < INPUT_SIZE; h++) {
binary[h] = oneCount[h] >= input->line_count / 2.0f ? '1' : '0';
}
binary[INPUT_SIZE] = '\0';
unsigned long gamma = parse_line(binary, '\0');
return gamma;
}
unsigned long compute_epsilon(unsigned long gamma) {
unsigned long epsilon = gamma ^ 0xFFF;
return epsilon;
}
void part1(struct input_str* input) {
unsigned long gamma = compute_gamma(input);
unsigned long epsilon = compute_epsilon(gamma);
printf("%ld\n", gamma * epsilon);
}
unsigned long search_criteria(struct input_str* input, unsigned long criteria) {
unsigned long match;
bool foundLine = false;
unsigned long mask = 1 << (INPUT_SIZE - 1); // we start by checking only the first bit
for(int linePos = 0; linePos < INPUT_SIZE; linePos++) {
for(size_t is = 0; is < input->line_count; is++) {
// TODO this parsing step could be outside of this loop
unsigned long parsedLine = parse_line(input->lines[is], '\n');
if((parsedLine & mask) == (criteria & mask)) {
// this line fits the criteria
if(foundLine) {
// more than one line fits, we need to consider another bit
foundLine = false;
mask = (mask >> 1) | (1 << (INPUT_SIZE - 1));
break;
}
else {
// save it for later
foundLine = true;
match = parsedLine;
}
}
}
// checked all lines, if we found one matching then it is the one we want
if(foundLine)
break;
}
if(!foundLine)
err(1, "cannot find line matching mask %ld\n", mask);
return match;
}
void part2(struct input_str* input) {
unsigned long o2_criteria = compute_gamma(input);
unsigned long o2_rate = search_criteria(input, o2_criteria);
unsigned long co2_criteria = compute_epsilon(o2_criteria);
unsigned long co2_scrub = search_criteria(input, co2_criteria);
printf("%ld\n", o2_rate * co2_scrub);
}
int main() {
// read input data
struct input_str input;
input_str_read(&input, INPUT);
// do stuff
part1(&input);
part2(&input);
// cleanup & exit
input_str_free(&input);
return 0;
}
|
