From 90f8da4f146227effae7a9b6fc694731a7329fd9 Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Thu, 16 Dec 2021 08:35:09 +0100
Subject: [PATCH] day 16

---
 16.txt   |   1 +
 16a.c    |  78 ++++++++++++++++++++++++++++++++++++++++
 16b.c    | 108 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 16e.txt  |   1 +
 16e2.txt |   1 +
 16e3.txt |   1 +
 16e4.txt |   1 +
 16e5.txt |   1 +
 16e6.txt |   1 +
 16e7.txt |   1 +
 10 files changed, 194 insertions(+)
 create mode 100644 16.txt
 create mode 100644 16a.c
 create mode 100644 16b.c
 create mode 100644 16e.txt
 create mode 100644 16e2.txt
 create mode 100644 16e3.txt
 create mode 100644 16e4.txt
 create mode 100644 16e5.txt
 create mode 100644 16e6.txt
 create mode 100644 16e7.txt

diff --git a/16.txt b/16.txt
new file mode 100644
index 0000000..b60e296
--- /dev/null
+++ b/16.txt
@@ -0,0 +1 @@
+E0529D18025800ABCA6996534CB22E4C00FB48E233BAEC947A8AA010CE1249DB51A02CC7DB67EF33D4002AE6ACDC40101CF0449AE4D9E4C071802D400F84BD21CAF3C8F2C35295EF3E0A600848F77893360066C200F476841040401C88908A19B001FD35CCF0B40012992AC81E3B980553659366736653A931018027C87332011E2771FFC3CEEC0630A80126007B0152E2005280186004101060C03C0200DA66006B8018200538012C01F3300660401433801A6007380132DD993100A4DC01AB0803B1FE2343500042E24C338B33F5852C3E002749803B0422EC782004221A41A8CE600EC2F8F11FD0037196CF19A67AA926892D2C643675A0C013C00CC0401F82F1BA168803510E3942E969C389C40193CFD27C32E005F271CE4B95906C151003A7BD229300362D1802727056C00556769101921F200AC74015960E97EC3F2D03C2430046C0119A3E9A3F95FD3AFE40132CEC52F4017995D9993A90060729EFCA52D3168021223F2236600ECC874E10CC1F9802F3A71C00964EC46E6580402291FE59E0FCF2B4EC31C9C7A6860094B2C4D2E880592F1AD7782992D204A82C954EA5A52E8030064D02A6C1E4EA852FE83D49CB4AE4020CD80272D3B4AA552D3B4AA5B356F77BF1630056C0119FF16C5192901CEDFB77A200E9E65EAC01693C0BCA76FEBE73487CC64DEC804659274A00CDC401F8B51CE3F8803B05217C2E40041A72E2516A663F119AC72250A00F44A98893C453005E57415A00BCD5F1DD66F3448D2600AC66F005246500C9194039C01986B317CDB10890C94BF68E6DF950C0802B09496E8A3600BCB15CA44425279539B089EB7774DDA33642012DA6B1E15B005C0010C8C917A2B880391160944D30074401D845172180803D1AA3045F00042630C5B866200CC2A9A5091C43BBD964D7F5D8914B46F040
diff --git a/16a.c b/16a.c
new file mode 100644
index 0000000..75b3404
--- /dev/null
+++ b/16a.c
@@ -0,0 +1,78 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+
+char *hex2bin[] = { ['0'] = "0000" , ['1'] = "0001" , ['2'] = "0010" , ['3'] = "0011" , ['4'] = "0100" , ['5'] = "0101" , ['6'] = "0110" , ['7'] = "0111" , ['8'] = "1000" , ['9'] = "1001" , ['A'] = "1010" , ['B'] = "1011" , ['C'] = "1100" , ['D'] = "1101" , ['E'] = "1110" , ['F'] = "1111", ['\n'] = "0000"};
+
+struct stream {
+	int pos;
+	char *buf;
+};
+
+int next(struct stream *f)
+{
+	if (*f->buf == '\0') {
+		int c = getchar();
+		if (c == EOF) {
+			printf("EOF\n");
+			exit(1);
+		}
+		f->buf = hex2bin[c];
+	}
+	int r =*f->buf == '1' ? 1 : 0;
+	f->buf++;
+	f->pos++;
+	return r;
+}
+
+int bin2int(struct stream *f, int n)
+{
+	int r = 0;
+	for (int i = 0; i<n; i++)
+		r = 2*r+next(f);
+	return r;
+}
+
+int parse_packet(struct stream *f)
+{
+	int packetversion = bin2int(f, 3);
+	int packettype = bin2int(f, 3);
+
+	switch (packettype) {
+	//Literal value
+	case 4: {
+		int num = 0;
+		while (next(f) == 1) {
+			num = num*16+bin2int(f, 4);
+		}
+		num = num*16+bin2int(f, 4);
+		break;
+	}
+	default: {
+		int lengthtypeid = next(f);
+
+		//length is 15
+		if (lengthtypeid == 0) {
+			int lengthsubpackets = bin2int(f, 15);
+			int oldpos = f->pos;
+
+			while (f->pos - oldpos < lengthsubpackets)
+				packetversion += parse_packet(f);
+		} else {
+			int numsubpackets = bin2int(f, 11);
+			for (int i = 0; i<numsubpackets; i++)
+				packetversion += parse_packet(f);
+		}
+		break;
+	}}
+	return packetversion;
+}
+
+int main()
+{
+	struct stream f = {.pos=0, .buf=""};
+
+	int r = parse_packet(&f);
+	printf("r: %d\n", r);
+}
diff --git a/16b.c b/16b.c
new file mode 100644
index 0000000..4310a7b
--- /dev/null
+++ b/16b.c
@@ -0,0 +1,108 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+
+char *hex2bin[] =
+	{ ['0'] = "0000", ['1'] = "0001", ['2'] = "0010", ['3'] = "0011"
+	, ['4'] = "0100", ['5'] = "0101", ['6'] = "0110", ['7'] = "0111"
+	, ['8'] = "1000", ['9'] = "1001", ['A'] = "1010", ['B'] = "1011"
+	, ['C'] = "1100", ['D'] = "1101", ['E'] = "1110", ['F'] = "1111"
+	, ['\n'] = "0000"};
+
+struct stream { int pos; char *buf; };
+
+int next(struct stream *f)
+{
+	int r;
+	if (*f->buf == '\0') {
+		if ((r = getchar()) == EOF) {
+			printf("EOF\n");
+			exit(1);
+		}
+		f->buf = hex2bin[r];
+	}
+	r =*(f->buf++) == '1' ? 1 : 0;
+	f->pos++;
+	return r;
+}
+
+unsigned long bin2int(struct stream *f, int n)
+{
+	unsigned long r = 0;
+	for (int i = 0; i<n; i++)
+		r = 2*r+next(f);
+	return r;
+}
+
+unsigned long parse_packet(struct stream *f)
+{
+	int packetversion  __attribute__((unused)) = bin2int(f, 3);
+	int packettype = bin2int(f, 3);
+	unsigned long result = 0;
+
+	//literal
+	if (packettype == 4) {
+		while (next(f) == 1)
+			result = result*16+bin2int(f, 4);
+		result = result*16+bin2int(f, 4);
+	//operator
+	} else {
+		int lengthtypeid = next(f);
+		unsigned long packets[100] = {0};
+		int npackets = 0;
+
+		//number of bits
+		if (lengthtypeid == 0) {
+			int lengthsubpackets = bin2int(f, 15);
+			int oldpos = f->pos;
+			while (f->pos - oldpos < lengthsubpackets)
+				packets[npackets++] = parse_packet(f);
+		//number of packets
+		} else {
+			npackets = bin2int(f, 11);
+			for (int i = 0; i<npackets; i++)
+				packets[i] = parse_packet(f);
+		}
+
+		//sum
+		if (packettype == 0) {
+			for (int i = 0; i<npackets; i++)
+				result += packets[i];
+		//product
+		} else if (packettype == 1) {
+			result = 1;
+			for (int i = 0; i<npackets; i++)
+				result *= packets[i];
+		//minimum
+		} else if (packettype == 2) {
+			result = ULONG_MAX;
+			for (int i = 0; i<npackets; i++)
+				result = packets[i] < result ? packets[i] : result;
+		//maximum
+		} else if (packettype == 3) {
+			result = 0;
+			for (int i = 0; i<npackets; i++)
+				result = packets[i] > result ? packets[i] : result;
+		//greater than
+		} else if (packettype == 5) {
+			result = packets[0] > packets[1];
+		//less than
+		} else if (packettype == 6) {
+			result = packets[0] < packets[1];
+		//equal to
+		} else if (packettype == 7) {
+			result = packets[0] == packets[1];
+		//unknown
+		} else {
+			fprintf(stderr, "unknown operator: %d\n", packettype);
+			exit(1);
+		}
+	}
+	return result;
+}
+
+int main()
+{
+	struct stream f = {.pos=0, .buf=""};
+	printf("r: %lu\n", parse_packet(&f));
+}
diff --git a/16e.txt b/16e.txt
new file mode 100644
index 0000000..3f0eda1
--- /dev/null
+++ b/16e.txt
@@ -0,0 +1 @@
+D2FE28
diff --git a/16e2.txt b/16e2.txt
new file mode 100644
index 0000000..a7f8f25
--- /dev/null
+++ b/16e2.txt
@@ -0,0 +1 @@
+38006F45291200
diff --git a/16e3.txt b/16e3.txt
new file mode 100644
index 0000000..bcc798c
--- /dev/null
+++ b/16e3.txt
@@ -0,0 +1 @@
+EE00D40C823060
diff --git a/16e4.txt b/16e4.txt
new file mode 100644
index 0000000..0d2cbff
--- /dev/null
+++ b/16e4.txt
@@ -0,0 +1 @@
+8A004A801A8002F478
diff --git a/16e5.txt b/16e5.txt
new file mode 100644
index 0000000..ed3b78a
--- /dev/null
+++ b/16e5.txt
@@ -0,0 +1 @@
+620080001611562C8802118E34
diff --git a/16e6.txt b/16e6.txt
new file mode 100644
index 0000000..827e51b
--- /dev/null
+++ b/16e6.txt
@@ -0,0 +1 @@
+C0015000016115A2E0802F182340
diff --git a/16e7.txt b/16e7.txt
new file mode 100644
index 0000000..0a1278e
--- /dev/null
+++ b/16e7.txt
@@ -0,0 +1 @@
+A0016C880162017C3686B18A3D4780
-- 
2.20.1