advent2021

Advent of Code 2021 Solutions
git clone git://bsandro.tech/advent2021
Log | Files | Refs

commit 0870cb87f14280ff5bc804ce8b7f4be494278fce
parent 9b245784798f928a344ae72ca76b7b26f5474600
Author: bsandro <brian.drosan@gmail.com>
Date:   Fri, 17 Dec 2021 03:58:04 +0200

Day 16, puzzle 2

Diffstat:
Mday16/Makefile | 6+++---
Mday16/puzzle.c | 119+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------
Aday16/test.txt | 1+
Dday16/test1.txt | 1-
Dday16/test2.txt | 1-
Dday16/test3.txt | 1-
Dday16/test4.txt | 1-
Dday16/test5.txt | 1-
Dday16/test6.txt | 1-
Dday16/test7.txt | 1-
10 files changed, 102 insertions(+), 31 deletions(-)

diff --git a/day16/Makefile b/day16/Makefile @@ -1,8 +1,8 @@ NAME=$(shell basename ${PWD}) -SRC=$(wildcard *.c ../common/*.c) +SRC=$(wildcard *.c) DEPS:=$(wildcard *.h ../common/*.h) OBJ:=$(SRC:.c=.o) -CFLAGS=-O0 -g -std=c99 -Werror -Wall -Wextra -I. -I../common +CFLAGS=-O2 -std=c99 -Werror -Wall -Wextra -I. -I../common LDFLAGS=-lc all: $(NAME) @@ -22,4 +22,4 @@ run: $(NAME) @./$(NAME) input.txt test: $(NAME) - @./$(NAME) test4.txt + @./$(NAME) test.txt diff --git a/day16/puzzle.c b/day16/puzzle.c @@ -7,23 +7,31 @@ #include <strings.h> #include <assert.h> -#define BUF_SIZE 16 +#define BUF_SIZE 65 struct packet_t { uint8_t version; uint8_t type; - uint32_t value; + uint64_t value; uint16_t packets_size; struct packet_t **packets; }; uint8_t hex2int(const int symbol); char * int2bin(const uint8_t digit); -uint16_t str2int(char *str, size_t size); -uint32_t get_value(char *str, size_t *offset); +uint64_t str2int(char *str, size_t size); +uint64_t get_value(char *str, size_t *offset); struct packet_t * get_packet(char *str, size_t *offset); -uint32_t calc_packet_sum(struct packet_t *packet); void delete_packet(struct packet_t *packet); +uint64_t calc_packet_sum(struct packet_t *packet); +uint64_t calc_packet(struct packet_t *packet); +uint64_t packet_sum(struct packet_t *packet); +uint64_t packet_mul(struct packet_t *packet); +uint64_t packet_min(struct packet_t *packet); +uint64_t packet_max(struct packet_t *packet); +uint64_t packet_gt(struct packet_t *packet); +uint64_t packet_lt(struct packet_t *packet); +uint64_t packet_eq(struct packet_t *packet); void puzzle(const char *filename, long long *result1, long long *result2) { FILE *infile = fopen(filename, "r"); @@ -54,8 +62,8 @@ void puzzle(const char *filename, long long *result1, long long *result2) { size_t offset = 0; struct packet_t *packet = get_packet(binary, &offset); assert(packet != NULL); - //printf("final offset: %zu\n", offset); *result1 = calc_packet_sum(packet); + *result2 = calc_packet(packet); delete_packet(packet); free(binary); @@ -63,7 +71,7 @@ void puzzle(const char *filename, long long *result1, long long *result2) { fclose(infile); } -uint32_t calc_packet_sum(struct packet_t *packet) { +uint64_t calc_packet_sum(struct packet_t *packet) { uint32_t sum = packet->version; if (packet->type != 4) { for (uint16_t i = 0; i < packet->packets_size; ++i) { @@ -73,6 +81,85 @@ uint32_t calc_packet_sum(struct packet_t *packet) { return sum; } +uint64_t calc_packet(struct packet_t *packet) { + switch (packet->type) { + case 0: + return packet_sum(packet); + case 1: + return packet_mul(packet); + case 2: + return packet_min(packet); + case 3: + return packet_max(packet); + case 4: + return packet->value; + case 5: + return packet_gt(packet); + case 6: + return packet_lt(packet); + case 7: + return packet_eq(packet); + } + return 0; +} + +uint64_t packet_sum(struct packet_t *packet) { + uint64_t val = 0; + for (uint16_t i = 0; i < packet->packets_size; ++i) { + val += calc_packet(packet->packets[i]); + } + return val; +} + +uint64_t packet_mul(struct packet_t *packet) { + uint64_t val = 1; + for (uint16_t i = 0; i < packet->packets_size; ++i) { + val *= calc_packet(packet->packets[i]); + } + return val; +} + +uint64_t packet_min(struct packet_t *packet) { + assert(packet->packets_size > 0); + uint64_t val = calc_packet(packet->packets[0]); + for (uint16_t i = 1; i < packet->packets_size; ++i) { + uint64_t v = calc_packet(packet->packets[i]); + val = v < val ? v : val; + } + return val; +} + +uint64_t packet_max(struct packet_t *packet) { + assert(packet->packets_size > 0); + uint64_t val = 0; + for (uint16_t i = 0; i < packet->packets_size; ++i) { + uint64_t v = calc_packet(packet->packets[i]); + val = v > val ? v : val; + } + return val; +} + +uint64_t packet_gt(struct packet_t *packet) { + assert(packet->packets_size == 2); + uint64_t v1 = calc_packet(packet->packets[0]); + uint64_t v2 = calc_packet(packet->packets[1]); + return v1 > v2 ? 1 : 0; +} + +uint64_t packet_lt(struct packet_t *packet) { + assert(packet->packets_size == 2); + uint64_t v1 = calc_packet(packet->packets[0]); + uint64_t v2 = calc_packet(packet->packets[1]); + return v1 < v2 ? 1 : 0; +} + +uint64_t packet_eq(struct packet_t *packet) { + assert(packet->packets_size == 2); + uint64_t v1 = calc_packet(packet->packets[0]); + uint64_t v2 = calc_packet(packet->packets[1]); + return v1 == v2 ? 1 : 0; +} + void delete_packet(struct packet_t *packet) { if (packet->type != 4) { for (uint16_t i = 0; i < packet->packets_size; ++i) { @@ -102,20 +189,16 @@ char * int2bin(const uint8_t digit) { return bin; } -uint16_t str2int(char *str, size_t size) { +uint64_t str2int(char *str, size_t size) { assert(size < BUF_SIZE); - static char data[BUF_SIZE] = {0}; strlcpy(data, str, size+1); - return strtoull(data, NULL, 2); } struct packet_t * get_packet(char *str, size_t *offset) { struct packet_t *packet = malloc(sizeof(struct packet_t)); bzero(packet, sizeof(struct packet_t)); - - //printf("%s\n", str); size_t total_offset = 0; packet->version = str2int(str+total_offset, 3); @@ -123,13 +206,9 @@ struct packet_t * get_packet(char *str, size_t *offset) { packet->type = str2int(str+total_offset, 3); total_offset += 3; - //printf("type: %u\n", packet->type); - //printf("version: %u\n", packet->version); - if (packet->type == 4) { // literal values type size_t local_offset = 0; packet->value = get_value(str+total_offset, &local_offset); - //printf("value: %u\n", packet->value); total_offset += local_offset; } else { // operator packet @@ -139,7 +218,6 @@ struct packet_t * get_packet(char *str, size_t *offset) { if (len_type == 0) { // next 15 bits are length in bits len = str2int(str+total_offset, 15); - //printf("length nested packets: %u bits\n", len); total_offset += 15; size_t sum_offset = 0; @@ -158,7 +236,6 @@ struct packet_t * get_packet(char *str, size_t *offset) { } else { // next 11 bits are number of packets len = str2int(str+total_offset, 11); total_offset += 11; - //printf("number of nested packets: %u\n", len); packet->packets_size = len; packet->packets = calloc(len, sizeof(void *)); for (uint16_t i = 0; i < len; ++i) { @@ -176,14 +253,14 @@ struct packet_t * get_packet(char *str, size_t *offset) { return packet; } -uint32_t get_value(char *str, size_t *offset) { - uint32_t value = 0; +uint64_t get_value(char *str, size_t *offset) { + uint64_t value = 0; size_t local_offset = 0; uint16_t flag = 1; while (flag == 1) { flag = str2int(str+local_offset, 1); local_offset += 1; - uint16_t val = str2int(str+local_offset, 4); + uint64_t val = str2int(str+local_offset, 4); value = (value << 4) + val; local_offset += 4; } diff --git a/day16/test.txt b/day16/test.txt @@ -0,0 +1 @@ +9C0141080250320F1802104A08 diff --git a/day16/test1.txt b/day16/test1.txt @@ -1 +0,0 @@ -D2FE28 diff --git a/day16/test2.txt b/day16/test2.txt @@ -1 +0,0 @@ -38006F45291200 diff --git a/day16/test3.txt b/day16/test3.txt @@ -1 +0,0 @@ -EE00D40C823060 diff --git a/day16/test4.txt b/day16/test4.txt @@ -1 +0,0 @@ -8A004A801A8002F478 diff --git a/day16/test5.txt b/day16/test5.txt @@ -1 +0,0 @@ -620080001611562C8802118E34 diff --git a/day16/test6.txt b/day16/test6.txt @@ -1 +0,0 @@ -C0015000016115A2E0802F182340 diff --git a/day16/test7.txt b/day16/test7.txt @@ -1 +0,0 @@ -A0016C880162017C3686B18A3D4780