From 8dafc5f3d72d9670dea971174d66a5ae006900b7 Mon Sep 17 00:00:00 2001
From: Vincent Douillet <vincent@vdouillet.fr>
Date: Sat, 4 Dec 2021 18:28:50 +0100
Subject: day 4

---
 04.c     | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 Makefile |   5 ++-
 2 files changed, 156 insertions(+), 1 deletion(-)
 create mode 100644 04.c

diff --git a/04.c b/04.c
new file mode 100644
index 0000000..7077b65
--- /dev/null
+++ b/04.c
@@ -0,0 +1,152 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <err.h>
+#include <stdbool.h>
+#include "input.h"
+
+#define INPUT "input/04.txt"
+#define BOARD_COUNT 100
+#define BOARD_SIZE 5
+#define MAX_DRAW 500
+
+typedef struct {
+	long board[BOARD_SIZE][BOARD_SIZE];
+	bool board_marks[BOARD_SIZE][BOARD_SIZE];
+} t_board;
+
+bool board_is_winning(t_board* board) {
+	for(int i = 0; i < BOARD_SIZE; i++) {
+		bool winning_i = true;
+		bool winning_j = true;
+		for(int j = 0; j < BOARD_SIZE; j++) {
+			winning_i &= board->board_marks[i][j];
+			winning_j &= board->board_marks[j][i];
+		}
+		if(winning_i || winning_j)
+			return true;
+	}
+	return false;
+}
+
+bool board_mark(t_board* board, long draw) {
+	for(int i = 0; i < BOARD_SIZE; i++) {
+		for(int j = 0; j < BOARD_SIZE; j++) {
+			if(board->board[i][j] == draw)
+				board->board_marks[i][j] = true;
+		}
+	}
+	return board_is_winning(board);
+}
+
+void board_init(t_board* board) {
+	for(int i = 0; i < BOARD_SIZE; i++) {
+		for(int j = 0; j < BOARD_SIZE; j++) {
+			board->board[i][j] = 0;
+			board->board_marks[i][j] = false;
+		}
+	}
+}
+
+void board_read(t_board* board_list, struct input_str* input) {
+	for(int i = 0; i < BOARD_COUNT; i++) {
+		board_init(&(board_list[i]));
+		// read each line of the board
+		for(int j = 0; j < BOARD_SIZE; j++) {
+			// + 2 is for first line and empty line at start of board
+			int line_index = i * (BOARD_SIZE + 1) + j + 2;
+			char* line = input->lines[line_index];
+			char* start = line;
+			char* end = NULL;
+			// read each int
+			for(int k = 0; k < BOARD_SIZE; k++) {
+				board_list[i].board[j][k] = strtol(start, &end, 0);
+				start = end;
+			}
+		}
+	}
+}
+
+size_t draw_read(long* draw_list, struct input_str* input) {
+	size_t i = 0;
+	char *start = input->lines[0];
+	char *end = start;
+	while(i < MAX_DRAW && *end != '\n') {
+		draw_list[i] = strtol(start, &end, 0);
+		start = end + 1;
+		i++;
+	}
+	if(i == MAX_DRAW && *end != '\n')
+		err(1, "draw list was truncated");
+
+	return i;
+}
+
+long board_unmarked_sum(t_board* board) {
+	long sum = 0;
+	for(int i = 0; i < BOARD_SIZE; i++) {
+		for(int j = 0; j < BOARD_SIZE; j++) {
+			if(!(board->board_marks)[i][j])
+				sum += (board->board)[i][j];
+		}
+	}
+	return sum;
+}
+
+void part1(struct input_str* input) {
+	t_board board_list[BOARD_COUNT];
+	long draw_list[MAX_DRAW];
+	board_read(board_list, input);
+	size_t draw_count = draw_read(draw_list, input);
+	
+	// apply draw to each board until one is winning
+	for(size_t i = 0; i < draw_count; i++) {
+		for(size_t j = 0; j < BOARD_COUNT; j++) {
+			if(board_mark(&(board_list[j]), draw_list[i])) {
+				// winning board found, print score
+				long score = board_unmarked_sum(&(board_list[j]));
+				printf("%ld\n", draw_list[i] * score);
+				return;
+			}
+		}
+	}
+	
+	err(1, "no winning board");
+}
+
+void part2(struct input_str* input) {
+	t_board board_list[BOARD_COUNT];
+	long draw_list[MAX_DRAW];
+	board_read(board_list, input);
+	size_t draw_count = draw_read(draw_list, input);
+	
+	// apply draw to each board until one is winning
+	long last_score;
+	for(size_t i = 0; i < draw_count; i++) {
+		for(size_t j = 0; j < BOARD_COUNT; j++) {
+			// skip already winning boards
+			if(board_is_winning(&(board_list[j])))
+					continue;
+
+			if(board_mark(&(board_list[j]), draw_list[i])) {
+				// winning board found
+				last_score = draw_list[i] * board_unmarked_sum(&(board_list[j]));
+			}
+		}
+	}
+	// print last winning
+	printf("%ld\n", last_score);	
+}
+
+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 61cd769..3be3369 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 CC=cc
 CFLAGS=-std=c1x -W -Wall -g
 LDFLAGS=
-EXEC=01 02 03
+EXEC=01 02 03 04
 
 all: $(EXEC)
 
@@ -14,6 +14,9 @@ all: $(EXEC)
 03: input.o 03.o
 	$(CC) -o $@ $> $(LDFLAGS)
 
+04: input.o 04.o
+	$(CC) -o $@ $> $(LDFLAGS)
+
 .c.o:
 	$(CC) -o $@ -c $< $(CFLAGS)
 
-- 
cgit v1.2.3