diff options
| -rw-r--r-- | 06.c | 101 | ||||
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | list.c | 46 | ||||
| -rw-r--r-- | list.h | 22 |
4 files changed, 173 insertions, 1 deletions
@@ -0,0 +1,101 @@ +#include <stdlib.h> +#include <stdio.h> +#include <err.h> +#include <stdbool.h> +#include "input.h" +#include "list.h" + +#define INPUT "input/06.txt" +#define INPUT_SIZE 300L +#define EXPECTED1 380758L +#define EXPECTED2 1710623015163L + +void part1(struct input_str* input) { + char* start = input->lines[0]; + char* end = start; + struct long_list* lanterns = long_list_init(INPUT_SIZE); + + // parse input + while(*end != '\n') { + long timer = strtol(start, &end, 0); + start = end; + if(*end == ',') + start++; + + long_list_add(lanterns, timer); + } + + // time flies + for(int day = 0; day < 80; day++) { + size_t init_length = lanterns->length; // we should leave alone the new lanterns + for(size_t i = 0; i < init_length; i++) { + long timer = long_list_get(lanterns, i); + if(timer == 0) { + timer = 7; + long_list_add(lanterns, 8); + } + timer--; + long_list_set(lanterns, i, timer); + } + } + + CHECK(lanterns->length, EXPECTED1); + long_list_free(lanterns); +} + +void part2(struct input_str* input) { + // simulating 256 days with the naive approach from part1 is too long and uses up too much memory + // we need to count lanternfishes based on their timer + long* lantern_count_by_timer = calloc(9, sizeof(long)); + char* start = input->lines[0]; + char* end = start; + + // parse input + while(*end != '\n') { + long timer = strtol(start, &end, 0); + start = end; + if(*end == ',') + start++; + + lantern_count_by_timer[timer]++; + } + + long* lantern_count_2 = calloc(9, sizeof(long)); + for(int day = 0; day < 256; day++) { + // simulate the timers decreasing + for(int i = 8; i > 0; i--) { + lantern_count_2[i-1] = lantern_count_by_timer[i]; + } + // handle special cases of lanternfishes with timer 0 + lantern_count_2[8] = lantern_count_by_timer[0]; + lantern_count_2[6] += lantern_count_by_timer[0]; + + // switch arrays for the next day + long* lantern_count_tmp = lantern_count_by_timer; + lantern_count_by_timer = lantern_count_2; + lantern_count_2 = lantern_count_tmp; + } + + // compute total of lanternfish + long sum = 0; + for(int i = 0; i < 9; i++) + sum += lantern_count_by_timer[i]; + + free(lantern_count_by_timer); + free(lantern_count_2); + 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; +} @@ -1,7 +1,7 @@ CC=cc CFLAGS=-std=c1x -W -Wall -g LDFLAGS= -EXEC=01 02 03 04 05 +EXEC=01 02 03 04 05 06 all: $(EXEC) @@ -23,5 +23,8 @@ all: $(EXEC) 05: input.o 05.o $(CC) -o $@ $> $(LDFLAGS) +06: input.o list.o 06.o + $(CC) -o $@ $> $(LDFLAGS) + clean: rm -rf *.o $(EXEC) @@ -0,0 +1,46 @@ +#include <err.h> +#include "list.h" + +#define LIST_SIZE 50 + +struct long_list* long_list_init(size_t size) { + struct long_list* list = malloc(sizeof(struct long_list)); + list->list = malloc(sizeof(long) * size); + list->alloc_size = size; + list->length = 0; + return list; +} + +void long_list_free(struct long_list* list) { + if(list == NULL) + return; + + if(list->list != NULL) + free(list->list); + + free(list); +} + +void long_list_add(struct long_list* list, long value) { + // increase space if needed + if(list->length >= list->alloc_size) { + list->list = realloc(list->list, sizeof(long) * (list->alloc_size + LIST_SIZE)); + list->alloc_size += LIST_SIZE; + } + list->list[list->length] = value; + list->length = list->length + 1; +} + +long long_list_get(struct long_list* list, size_t index) { + if(index >= list->length) + err(1, "index %ld out of bounds (%ld)", index, list->length); + + return list->list[index]; +} + +void long_list_set(struct long_list* list, size_t index, long value) { + if(index >= list->length) + err(1, "index %ld out of bounds (%ld)", index, list->length); + + list->list[index] = value; +} @@ -0,0 +1,22 @@ +#ifndef DEF_LISTH +#define DEF_LISTH + +#include <stdlib.h> + +struct long_list { + long* list; + size_t alloc_size; + size_t length; +}; + +struct long_list* long_list_init(size_t size); + +void long_list_free(struct long_list* list); + +void long_list_add(struct long_list* list, long value); + +long long_list_get(struct long_list* list, size_t index); + +void long_list_set(struct long_list* list, size_t index, long value); + +#endif |