day16

5 files changed, 156 insertions, 1 deletions

diff --git a/2021/day16/day16 b/2021/day16/day16
new file mode 100755
index 0000000..42a6b47
--- /dev/null
+++ b/2021/day16/day16
diff --git a/2021/day16/day16.cpp b/2021/day16/day16.cpp
new file mode 100644
index 0000000..6fc22e5
--- /dev/null
+++ b/2021/day16/day16.cpp
@@ -0,0 +1,151 @@
+#include <iostream>
+#include <fstream>
+#include <vector>
+#include <map>
+
+
+long bin_to_int (std::string bin) {
+	long num = 0, exp = 1;
+	for (int i=bin.size()-1; i>=0; i--) { 
+		int bit = bin[i] == '1' ? 1 : 0;
+		num += bit * exp;
+		exp *= 2;
+	}
+	return num;
+}
+
+std::string hex_to_bin (std::string hex) {
+	std::map<char, std::string> convert {
+		{ '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" },
+	};
+	std::string bin;
+	for (char c : hex) { bin += convert[c]; }
+	return bin;
+}
+
+long parse_literal (std::string raw) {
+	std::string lit;
+	for (int i=0; i<raw.size(); i++) {
+		auto group = raw.substr(i*5, 5);
+		lit += group.substr(1, 4);
+		if (group[0] == '0') break;
+	}
+	return bin_to_int(lit);
+}
+
+class Packet {
+	public: 
+	Packet () { }
+
+	int version;
+	int id;
+	long literal;
+	std::vector<Packet> packets;
+
+	int parse (std::string raw) {
+		int parsed = 0;
+		version = bin_to_int(raw.substr(0, 3));
+		id = bin_to_int(raw.substr(3, 3));
+		parsed += 6;
+
+
+		if (id == 4) {
+			std::string lit;
+			for (int i=0; ; i++) {
+				auto group = raw.substr(parsed, 5);
+				parsed += 5;
+				lit += group.substr(1, 4);
+				if (group[0] == '0') break;
+			}
+			literal = bin_to_int(lit);
+		} else {
+			parsed += 1;
+			if (raw[6] == '0') {
+				int len = bin_to_int(raw.substr(7, 15));
+				parsed += 15;
+				int local = 0;
+				while (local < len) {
+					Packet pack;
+					int size = pack.parse(raw.substr(parsed));
+					local += size;
+					parsed += size;
+					packets.push_back(pack);
+				}
+			} else {
+				int len = bin_to_int(raw.substr(7, 11));
+				parsed += 11;
+				int local = 0;
+				while (local < len) {
+					Packet pack;
+					int size = pack.parse(raw.substr(parsed));
+					local += 1;
+					parsed += size;
+					packets.push_back(pack);
+				}
+			}
+		}
+		return parsed;
+	}
+
+	int sum_version () {
+		int s = version;
+		for (Packet pack : packets) { s += pack.sum_version(); }
+		return s;
+	}
+
+	long eval () {
+		long res = 0;
+		if (id == 4) { 
+			res = literal;
+	   	}
+		else if (id == 5) {
+			res = packets[0].eval() > packets[1].eval() ? 1 : 0;
+		}
+		else if (id == 6) {
+			res = packets[0].eval() < packets[1].eval() ? 1 : 0;
+		}
+		else if (id == 7) {
+			res = packets[0].eval() == packets[1].eval() ? 1 : 0;
+		}
+		else {
+			bool first = true;
+			for (Packet pack : packets) { 
+				if (first) {
+					res = pack.eval();
+					first = false;
+					continue;
+				}
+				if (id == 0) res += pack.eval();
+				if (id == 1) res *= pack.eval();
+				if (id == 2) res = std::min(res, pack.eval());
+				if (id == 3) res = std::max(res, pack.eval());
+			}
+		}
+		return res;
+	}
+};
+
+
+int main (int argc, char *argv[]) {
+	std::string raw;
+	if (std::string({ argv[1] }) == "-i") {
+		raw = std::string({ argv[2] });
+	} else {
+		std::getline(std::ifstream(argv[1]), raw, '\0');
+	}
+	std::cout << raw << std::endl;
+
+	std::string bin = hex_to_bin(raw);
+
+	std::cout << bin << std::endl;
+	Packet packet;
+	packet.parse(bin);
+
+	std::cout << "version sum: "  <<  packet.sum_version() << std::endl;
+	std::cout << "eval to: " << packet.eval() << std::endl;
+
+	return 0;
+}
diff --git a/2021/day16/day16_input.txt b/2021/day16/day16_input.txt
new file mode 100644
index 0000000..adc5ada
--- /dev/null
+++ b/2021/day16/day16_input.txt
@@ -0,0 +1 @@
+A059141803C0008447E897180401F82F1E60D80021D11A3DC3F300470015786935BED80A5DB5002F69B4298A60FE73BE41968F48080328D00427BCD339CC7F431253838CCEFF4A943803D251B924EC283F16D400C9CDB3180213D2D542EC01092D77381A98DA89801D241705C80180960E93469801400F0A6CEA7617318732B08C67DA48C27551C00F972830052800B08550A277416401A5C913D0043D2CD125AC4B1DB50E0802059552912E9676931530046C0141007E3D4698E20008744D89509677DBF5759F38CDC594401093FC67BACDCE66B3C87380553E7127B88ECACAD96D98F8AC9E570C015C00B8E4E33AD33632938CEB4CD8C67890C01083B800E5CBDAB2BDDF65814C01299D7E34842E85801224D52DF9824D52DF981C4630047401400042E144698B2200C4328731CA6F9CBCA5FBB798021259B7B3BBC912803879CD67F6F5F78BB9CD6A77D42F1223005B8037600042E25C158FE0008747E8F50B276116C9A2730046801F29BC854A6BF4C65F64EB58DF77C018009D640086C318870A0C01D88105A0B9803310E2045C8CF3F4E7D7880484D0040001098B51DA0980021F17A3047899585004E79CE4ABD503005E610271ED4018899234B64F64588C0129EEDFD2EFBA75E0084CC659AF3457317069A509B97FB3531003254D080557A00CC8401F8791DA13080391EA39C739EFEE5394920C01098C735D51B004A7A92F6A0953D497B504F200F2BC01792FE9D64BFA739584774847CE26006A801AC05DE180184053E280104049D10111CA006300E962005A801E2007B80182007200792E00420051E400EF980192DC8471E259245100967FF7E6F2CF25DBFA8593108D342939595454802D79550C0068A72F0DC52A7D68003E99C863D5BC7A411EA37C229A86EBBC0CB802B331FDBED13BAB92080310265296AFA1EDE8AA64A0C02C9D49966195609C0594223005B80152977996D69EE7BD9CE4C1803978A7392ACE71DA448914C527FFE140
diff --git a/2021/day16/makefile b/2021/day16/makefile
new file mode 100644
index 0000000..635131f
--- /dev/null
+++ b/2021/day16/makefile
@@ -0,0 +1,2 @@
+all day16.cpp:
+	g++ -std=c++20 day16.cpp -o day16
diff --git a/README.md b/README.md
index 0273f2f..a0e0143 100644
--- a/README.md
+++ b/README.md
@@ -1,3 +1,4 @@
 # Advent of code exercises
 Solved exercises from [advent of code](https://adventofcode.com/)  
-Solved in C++20, each program solves both parts
+
+- 2021: Solved in C++20, each program solves both parts