day 8HEADmaster

3 files changed, 234 insertions, 2 deletions

diff --git a/08.c b/08.c
new file mode 100644
index 0000000..403e88d
--- /dev/null
+++ b/08.c
@@ -0,0 +1,212 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <err.h>
+#include <math.h>
+#include "input.h"
+
+#define INPUT "input/08.txt"
+
+#define INPUT_DIGIT_SIZE 10
+#define OUTPUT_DIGIT_SIZE 4
+
+#define EXPECTED1 504L
+#define EXPECTED2 1073431L
+
+void part1(struct input_str* input) {
+	long sum = 0;
+	for(size_t i = 0; i < input->line_count; i++) {
+		// copy string as strtok will mess with it
+		int len = strlen(input->lines[i]);
+		char* line = malloc(len * sizeof(char));
+		memset(line, '\0', len);
+		strncpy(line, input->lines[i], len);
+		char* output_start = strchr(line, '|');
+		char* token = strtok(output_start + 1, " ");
+		while(token != NULL) {
+			int token_length = strlen(token);
+			// respectively digists 1, 4, 7 and 8
+			if(token_length == 2 || token_length == 4 || token_length == 3 || token_length == 7)
+				sum++;
+
+			token = strtok(NULL, " ");
+		}
+		//free(line); TODO causes memory corruption
+	}
+
+	CHECK(sum, EXPECTED1);
+}
+
+int count_segment(int digit) {
+	int count = 0;
+	for(int p = 0; p < 10; p++) {
+		int segment_mask = 1 << p;
+		if((digit & segment_mask) == segment_mask)
+			count++;
+	}
+	return count;
+}
+
+int parse_digit(char* token) {
+	// digits are parsed with segments mapped to bits as follows : 0abcdefg
+	int result = 0;
+	int p = 0;
+	while(token[p] != '\0') {
+		switch(token[p]) {
+			case 'a':
+				result |= (1 << 6);
+				break;
+			case 'b':
+				result |= (1 << 5);
+				break;
+			case 'c':
+				result |= (1 << 4);
+				break;
+			case 'd':
+				result |= (1 << 3);
+				break;
+			case 'e':
+				result |= (1 << 2);
+				break;
+			case 'f':
+				result |= (1 << 1);
+				break;
+			case 'g':
+				result |= 1;
+				break;
+			default:
+				err(1, "unexpected token");
+		}
+		p++;
+	}
+	return result;
+}
+
+void part2(struct input_str* input) {
+	long sum = 0;
+	for(size_t i = 0; i < input->line_count; i++) {
+		int digits[INPUT_DIGIT_SIZE];
+		// copy string as strtok will mess with it
+		int len = strlen(input->lines[i]);
+		char* line = malloc(len * sizeof(char));
+		memset(line, '\0', len);
+		strncpy(line, input->lines[i], len);
+		char* token = strtok(line, " ");
+		for(int t = 0; t < INPUT_DIGIT_SIZE; t++) {
+			digits[t] = parse_digit(token);
+			token = strtok(NULL, " ");
+		}
+
+		int digits_code[10] = { 0 };
+		// first pass to identify 1, 4, 7, 8
+		for(int p = 0; p < 10; p++) {
+			int digit = digits[p];
+			int segment_count = count_segment(digit);
+			if(segment_count == 3) {
+				digits_code[7] = digit; // this is 7
+				digits[p] = 0;
+			}
+			else if(segment_count == 4) {
+				digits_code[4] = digit; // this is 4
+				digits[p] = 0;
+			}
+			else if(segment_count == 2) {
+				digits_code[1] = digit; // this is 0
+				digits[p] = 0;
+			}
+			else if(segment_count == 7) {
+				digits_code[8] = digit; // this is 8
+				digits[p] = 0;
+			}
+		}
+		// second pass identifies 2, 3 and 5
+		for(int p = 0; p < 10; p++) {
+			int digit = digits[p];
+			if(digit == 0)
+				continue; // this digit was identified by previous pass
+
+			int digit_segment_count = count_segment(digit);
+			if(digit_segment_count == 5) {
+				if(count_segment(digits[p] & digits_code[7]) == 3) {
+					digits_code[3] = digit; // this is 3 (5 segments and those of 7)
+					digits[p] = 0;
+				}
+				else if(count_segment(digits[p] & digits_code[4]) == 2) {
+					digits_code[2] = digit; // this is 2 (5 segments and 2 in common with 4)
+					digits[p] = 0;
+				}
+				else if(count_segment(digits[p] & digits_code[4]) == 3) {
+					digits_code[5] = digit; // this si 5 (5 segments and 3 in common with 4)
+					digits[p] = 0;
+				}
+			}
+		}
+		// third pass identifies 0, 6 and 9
+		for(int p = 0; p < 10; p++) {
+			int digit = digits[p];
+			if(digit == 0)
+				continue;
+
+#ifdef DEBUG
+			// at this stage the remaining digits should have 6 segments
+			if(count_segment(digit) != 6)
+				printf("digit has %d segments while 6 expected\n", count_segment(digit));
+#endif
+
+			int segments_five_and_one = digits_code[5] | digits_code[1];
+			if((segments_five_and_one & digit) == segments_five_and_one) {
+				digits_code[9] = digit; // this is 9 (6 segments and has those of 5 and 1)
+				digits[p] = 0;
+			}
+			else if((digits_code[5] & digit) == digits_code[5]) {
+				digits_code[6] = digit; // this is 6 (6 segments, has those of 5 but not 1)
+				digits[p] = 0;
+			}
+			else {
+				digits_code[0] = digit; // this is 0
+				digits[p] = 0;
+			}
+		}
+
+#ifdef DEBUG
+		// check that we found all digits
+		for(int d = 0; d < 10; d++) {
+			if(digits_code[d] == 0)
+				printf("missing digit %d\n", d);
+		}
+#endif
+
+		// use the table to parse output digits
+		token = strtok(NULL, " "); // skip the '|' separator
+		int current_number = 0;
+		for(int n = 0; n < OUTPUT_DIGIT_SIZE && token != NULL; n++) {
+			int parsed_digit = parse_digit(token);
+			// search real digit
+			for(int d = 0; d < 10; d++) {
+				if(parsed_digit == digits_code[d]) {
+					current_number += (int) pow(10, OUTPUT_DIGIT_SIZE - 1 - n) * d;
+					break;
+				}
+			}
+			// next digit
+			token = strtok(NULL, " ");
+		}
+		sum += current_number;
+		//free(line); TODO causes memory corruption
+	}
+	CHECK(sum, 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;
+}
diff --git a/Makefile b/Makefile
index a2e394d..bc5c865 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 CC=cc
 CFLAGS=-std=c1x -W -Wall -g
-LDFLAGS=
-EXEC=01 02 03 04 05 06 07
+LDFLAGS=-lm
+EXEC=01 02 03 04 05 06 07 08
 
 all: $(EXEC)
 
@@ -29,5 +29,8 @@ all: $(EXEC)
 07: input.o 07.o
 	$(CC) -o $@ $> $(LDFLAGS)
 
+08: input.o 08.o
+	$(CC) -o $@ $> $(LDFLAGS)
+
 clean:
 	rm -rf *.o $(EXEC)
diff --git a/input.c b/input.c
index 1c72194..02461a1 100644
--- a/input.c
+++ b/input.c
@@ -40,6 +40,20 @@ void input_int_read(struct input_int* result, char* filename) {
 	fclose(file);
 }
 
+int str_replace(char* string, char a, char b) {
+	size_t i = 0;
+	int replace_count = 0;
+	while(string[i] != '\0') {
+		if(string[i] == a) {
+			string[i] = b;
+			replace_count++;
+		}
+		i++;
+	}
+
+	return replace_count;
+}
+
 void input_str_read(struct input_str* result, char* filename) {
 	// open input file
 	FILE* file=fopen(filename, "r");
@@ -57,6 +71,9 @@ void input_str_read(struct input_str* result, char* filename) {
 		char** dst = &(result->lines[lineIndex]);
 		if(getline(dst, &lineSize, file) < 0)
 			err(1, "read error line %ld\n", lineIndex);
+
+		// cleanup line end char
+		str_replace(result->lines[lineIndex], '\n', '\0');
 	}
 
 	fclose(file);