aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjacopograndi <jacopo.grandi@outlook.it>2022-02-01 12:55:38 +0100
committerjacopograndi <jacopo.grandi@outlook.it>2022-02-01 12:55:38 +0100
commitbd82dc679199db7bbcd3a8d8757730822b997440 (patch)
tree8859930fa81f4bbc718f7f5a1dcc6c2cdbed4b79
parent4bfd90a11af7c1e597c4e30bbd6d7e1818911562 (diff)
day16
-rwxr-xr-x2021/day16/day16bin0 -> 102992 bytes
-rw-r--r--2021/day16/day16.cpp151
-rw-r--r--2021/day16/day16_input.txt1
-rw-r--r--2021/day16/makefile2
-rw-r--r--README.md3
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
Binary files differ
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