advent2021

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

commit 9b245784798f928a344ae72ca76b7b26f5474600
parent d4c5a6f75ea3a06a0c5f819dd8ccfdec689128cd
Author: bsandro <brian.drosan@gmail.com>
Date:   Fri, 17 Dec 2021 02:58:32 +0200

Day 16, puzzle 1

Diffstat:
Aday16/Makefile | 25+++++++++++++++++++++++++
Aday16/input.txt | 1+
Aday16/main.c | 29+++++++++++++++++++++++++++++
Aday16/puzzle.c | 192+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aday16/test1.txt | 1+
Aday16/test2.txt | 1+
Aday16/test3.txt | 1+
Aday16/test4.txt | 1+
Aday16/test5.txt | 1+
Aday16/test6.txt | 1+
Aday16/test7.txt | 1+
11 files changed, 254 insertions(+), 0 deletions(-)

diff --git a/day16/Makefile b/day16/Makefile @@ -0,0 +1,25 @@ +NAME=$(shell basename ${PWD}) +SRC=$(wildcard *.c ../common/*.c) +DEPS:=$(wildcard *.h ../common/*.h) +OBJ:=$(SRC:.c=.o) +CFLAGS=-O0 -g -std=c99 -Werror -Wall -Wextra -I. -I../common +LDFLAGS=-lc + +all: $(NAME) + +.PHONY: clean run + +clean: + rm -f $(OBJ) $(NAME) + +%.o : %.c $(DEPS) + @$(CC) $(CFLAGS) -c $< -o $@ + +$(NAME): $(OBJ) + @$(CC) $(OBJ) -o $@ $(LDFLAGS) + +run: $(NAME) + @./$(NAME) input.txt + +test: $(NAME) + @./$(NAME) test4.txt diff --git a/day16/input.txt b/day16/input.txt @@ -0,0 +1 @@ +420D610055D273AF1630010092019207300B278BE5932551E703E608400C335003900AF0402905009923003880856201E95C00B60198D400B50034400E20101DC00E10024C00F1003C400B000212697140249D049F0F8952A8C6009780272D5D074B5741F3F37730056C0149658965E9AED7CA8401A5CC45BB801F0999FFFEEE0D67050C010C0036278A62D4D737F359993398027800BECFD8467E3109945C1008210C9C442690A6F719C48A351006E9359C1C5003E739087E80F27EC29A0030322BD2553983D272C67508E5C0804639D4BD004C401B8B918E3600021D1061D47A30053801C89EF2C4CCFF39204C53C212DABED04C015983A9766200ACE7F95C80D802B2F3499E5A700267838803029FC56203A009CE134C773A2D3005A77F4EDC6B401600043A35C56840200F4668A71580043D92D5A02535BAF7F9A89CF97C9F59A4F02C400C249A8CF1A49331004CDA00ACA46517E8732E8D2DB90F3005E92362194EF5E630CA5E5EEAD1803E200CC228E70700010A89D0BE3A08033146164177005A5AEEB1DA463BDC667600189C9F53A6FF6D6677954B27745CA00BCAE53A6EEDC60074C920001B93CFB05140289E8FA4812E071EE447218CBE1AA149008DBA00A497F9486262325FE521898BC9669B382015365715953C5FC01AA8002111721D4221007E13C448BA600B4F77F694CE6C01393519CE474D46009D802C00085C578A71E4001098F518639CC301802B400E7CDDF4B525C8E9CA2188032600E44B8F1094C0198CB16A29180351EA1DC3091F47A5CA0054C4234BDBC2F338A77B84F201232C01700042A0DC7A8A0200CC578B10A65A000601048B24B25C56995A30056C013927D927C91AB43005D127FDC610EF55273F76C96641002A4F0F8C01CCC579A8D68E52587F982996F537D600 diff --git a/day16/main.c b/day16/main.c @@ -0,0 +1,29 @@ +#include <stdio.h> +#include <time.h> +#include <string.h> + +void puzzle(const char *filename, long long *res1, long long *res2); + +int main(int argc, char *argv[]) { + printf("Advent of Code: day 16\n"); + double time_start = clock(); + + if (argc <= 1) { + printf("Usage: %s inputfile.txt\n", argv[0]); + return -1; + } + + const char *filename = argv[1]; + long long counter1 = -1; + long long counter2 = -1; + + puzzle(filename, &counter1, &counter2); + + printf("Puzzle #1: %lld\n", counter1); + printf("Puzzle #2: %lld\n", counter2); + + double elapsed = clock() - time_start; + printf("Elapsed: %f\n", elapsed / CLOCKS_PER_SEC); + + return 0; +} diff --git a/day16/puzzle.c b/day16/puzzle.c @@ -0,0 +1,192 @@ +#define _DEFAULT_SOURCE + +#include <stdio.h> +#include <stdlib.h> +#include <errno.h> +#include <string.h> +#include <strings.h> +#include <assert.h> + +#define BUF_SIZE 16 + +struct packet_t { + uint8_t version; + uint8_t type; + uint32_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); +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); + +void puzzle(const char *filename, long long *result1, long long *result2) { + FILE *infile = fopen(filename, "r"); + if (infile == NULL) { + fprintf(stderr, "fopen() error: %s\n", strerror(errno)); + return; + } + + *result1 = 0; + *result2 = 0; + + int symbol = 0; + char *binary = NULL; + size_t binary_size = 1; + + binary = malloc(binary_size); + assert(binary != NULL); + binary[0] = '\0'; + + while ((symbol = fgetc(infile)) != EOF) { + if (symbol == '\n') break; + uint8_t digit = hex2int(symbol); + binary_size += 4; + binary = realloc(binary, binary_size); + strlcat(binary, int2bin(digit), binary_size); + } + + 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); + + delete_packet(packet); + free(binary); + // mutiny! ignoring feof/ferror. + fclose(infile); +} + +uint32_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) { + sum += calc_packet_sum(packet->packets[i]); + } + } + return sum; +} + +void delete_packet(struct packet_t *packet) { + if (packet->type != 4) { + for (uint16_t i = 0; i < packet->packets_size; ++i) { + delete_packet(packet->packets[i]); + } + } + free(packet); +} + +uint8_t hex2int(const int symbol) { + if (symbol >= '0' && symbol <= '9') { + return symbol - '0'; + } else if (symbol >= 'A' && symbol <= 'F') { + return symbol - 'A' + 10; + } + return 0; +} + +char * int2bin(const uint8_t digit) { + static char bin[5]; + int cnt = 0; + // only "lower" 4 bits + for (int i = 8; i > 0; i >>= 1) { + bin[cnt++] = ((digit & i) == i) ? '1' : '0'; + } + bin[4] = '\0'; + return bin; +} + +uint16_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); + total_offset += 3; + 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 + uint16_t len_type = str2int(str+total_offset, 1); + total_offset += 1; + uint16_t len = 0; + + 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; + packet->packets_size = 0; + while (sum_offset < len) { + packet->packets_size++; + size_t local_offset = 0; + struct packet_t *p = get_packet(str+total_offset, &local_offset); + assert(p != NULL); + sum_offset += local_offset; + total_offset += local_offset; + packet->packets = realloc(packet->packets, packet->packets_size * sizeof(void *)); + packet->packets[packet->packets_size - 1] = p; + } + *offset = sum_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) { + size_t local_offset = 0; + struct packet_t *p = get_packet(str+total_offset, &local_offset); + assert(p != NULL); + total_offset += local_offset; + packet->packets[i] = p; + } + } + } + + *offset = total_offset; + + return packet; +} + +uint32_t get_value(char *str, size_t *offset) { + uint32_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); + value = (value << 4) + val; + local_offset += 4; + } + *offset = local_offset; + return value; +} diff --git a/day16/test1.txt b/day16/test1.txt @@ -0,0 +1 @@ +D2FE28 diff --git a/day16/test2.txt b/day16/test2.txt @@ -0,0 +1 @@ +38006F45291200 diff --git a/day16/test3.txt b/day16/test3.txt @@ -0,0 +1 @@ +EE00D40C823060 diff --git a/day16/test4.txt b/day16/test4.txt @@ -0,0 +1 @@ +8A004A801A8002F478 diff --git a/day16/test5.txt b/day16/test5.txt @@ -0,0 +1 @@ +620080001611562C8802118E34 diff --git a/day16/test6.txt b/day16/test6.txt @@ -0,0 +1 @@ +C0015000016115A2E0802F182340 diff --git a/day16/test7.txt b/day16/test7.txt @@ -0,0 +1 @@ +A0016C880162017C3686B18A3D4780