From 368f3bf67f03c308994b18bcdb60ac3bb2ec7477 Mon Sep 17 00:00:00 2001
From: Vincent Douillet <vincent@vdouillet.fr>
Date: Sat, 4 Dec 2021 15:14:26 +0100
Subject: day 3
---
03.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
1 file changed, 65 insertions(+), 6 deletions(-)
diff --git a/03.c b/03.c
index d783b79..738062c 100644
--- a/03.c
+++ b/03.c
@@ -1,12 +1,21 @@
#include <stdlib.h>
#include <stdio.h>
#include <err.h>
+#include <stdbool.h>
#include "input.h"
#define INPUT "input/03.txt"
#define INPUT_SIZE 12
-void part1(struct input_str* input) {
+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++) {
@@ -24,18 +33,67 @@ void part1(struct input_str* input) {
// 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[h] = oneCount[h] >= input->line_count / 2.0f ? '1' : '0';
}
binary[INPUT_SIZE] = '\0';
- char* endp = NULL;
- unsigned long gamma = strtoul(binary, &endp, 2);
+ unsigned long gamma = parse_line(binary, '\0');
+ return gamma;
+}
+
+unsigned long compute_epsilon(unsigned long gamma) {
unsigned long epsilon = gamma ^ 0xFFF;
- if(*endp != '\0')
- err(1, "erreur de parsing du gammaat");
+ 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;
@@ -43,6 +101,7 @@ int main() {
// do stuff
part1(&input);
+ part2(&input);
// cleanup & exit
input_str_free(&input);
--
cgit v1.2.3