diff options
author | jacopograndi <jacopo.grandi@outlook.it> | 2022-02-01 12:55:38 +0100 |
---|---|---|
committer | jacopograndi <jacopo.grandi@outlook.it> | 2022-02-01 12:55:38 +0100 |
commit | bd82dc679199db7bbcd3a8d8757730822b997440 (patch) | |
tree | 8859930fa81f4bbc718f7f5a1dcc6c2cdbed4b79 /2021/day16 | |
parent | 4bfd90a11af7c1e597c4e30bbd6d7e1818911562 (diff) |
day16
Diffstat (limited to '2021/day16')
-rwxr-xr-x | 2021/day16/day16 | bin | 0 -> 102992 bytes | |||
-rw-r--r-- | 2021/day16/day16.cpp | 151 | ||||
-rw-r--r-- | 2021/day16/day16_input.txt | 1 | ||||
-rw-r--r-- | 2021/day16/makefile | 2 |
4 files changed, 154 insertions, 0 deletions
diff --git a/2021/day16/day16 b/2021/day16/day16 Binary files differnew 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 |