diff options
Diffstat (limited to 'year2021/day16')
| -rw-r--r-- | year2021/day16/part1.clj | 67 | ||||
| -rw-r--r-- | year2021/day16/part2.cpp | 131 |
2 files changed, 198 insertions, 0 deletions
diff --git a/year2021/day16/part1.clj b/year2021/day16/part1.clj new file mode 100644 index 0000000..2358e59 --- /dev/null +++ b/year2021/day16/part1.clj @@ -0,0 +1,67 @@ +(require '[clojure.string :as str]) +(require '[clojure.set :as set]) + +(def hex-lookup + {\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"}) + +(defn binary-to-num [binstr] + (reduce + #(cond-> %1 true (* 2) (= \1 %2) inc) + 0 + binstr)) + +(defn take-packet-version [packet] + (-> (split-at 3 packet) + (update 0 binary-to-num))) + +(defn take-literal-value [packet] + (let [[tid data] (split-at 3 packet)] + (when (= '(\1 \0 \0) tid) + (let [sd (into [] data) + spl (split-with #(= \1 (first %)) (partition 5 sd)) + nums (map rest (concat (first spl) (take 1 (second spl))))] + [(binary-to-num (reduce concat nums)) + (drop (* 5 (inc (count (first spl)))) sd)] + )))) + +(defn take-operator [packet] + (let [id (first packet) ps (str/join (rest packet))] + (if (= \0 id) + (let [bits (binary-to-num (subs ps 0 15))] + [(subs ps 15) bits :bits]) + (let [pkts (binary-to-num (subs ps 0 11))] + [(subs ps 11) pkts :pkts])))) + +(defn process-packet [[input vcnt]] + (let [[version data] (take-packet-version input)] + (if (every? #(= \0 %) data) + ['() vcnt] + (do + (if-let [value (take-literal-value data)] + [(second value) (+ vcnt version)] + (do + (let [info (take-operator (drop 3 data))] + (if (= :bits (get info 2)) + (loop [inpt [(subs (first info) 0 (get info 1)) (+ vcnt version)]] + (if (empty? (first inpt)) + [(subs (first info) (get info 1)) (second inpt)] + (recur (process-packet inpt)))) + (loop [n (get info 1) inpt [(get info 0) (+ vcnt version)]] + (if (pos? n) + (recur (dec n) (process-packet inpt)) + inpt)))))))))) + +(loop [packet (->> (slurp "./in") + (map hex-lookup) + (take-while some?) + (reduce concat) + (str/join) + (#(vector % 0)) + (process-packet))] + (if (not (empty? (first packet))) + (recur (process-packet packet)) + (println (second packet)))) + diff --git a/year2021/day16/part2.cpp b/year2021/day16/part2.cpp new file mode 100644 index 0000000..5a02df9 --- /dev/null +++ b/year2021/day16/part2.cpp @@ -0,0 +1,131 @@ +#include <algorithm> +#include <cstdint> +#include <iostream> +#include <list> +#include <map> +#include <string> +#include <string_view> +#include <tuple> + +static const std::map<char, const char *> hexToBin = { + {'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"} +}; + +static std::pair<uint64_t, std::string_view> solve(std::string_view packet); + +int main(int argc, const char *argv[]) +{ + if (argc != 2) + return -1; + + std::string packetBin; + std::string packetHex (argv[1]); + for (char c : packetHex) + packetBin += hexToBin.at(c); + + std::cout << solve(packetBin).first << std::endl; + + return 0; +} + +uint64_t binStrToInt(std::string_view bin) +{ + uint64_t n = 0; + + for (char c : bin) { + n = n * 2ull; + if (c == '1') + ++n; + } + + return n; +} + +bool isEmptyPacket(std::string_view packet) +{ + return packet.empty() || + std::all_of(packet.cbegin(), packet.cend(), + [](char c) { return c == '0'; }); +} + +std::pair<uint64_t, std::string_view> solve(std::string_view packet) +{ + // Remove version + packet = packet.substr(3); + // Pull type ID + const auto typeId = packet.substr(0, 3); + packet = packet.substr(3); + + if (typeId == "100") { + std::string numberStr; + while (1) { + const auto chunk = packet.substr(0, 5); + packet = packet.substr(5); + numberStr += chunk.substr(1); + if (chunk.front() == '0') + break; + } + + return {binStrToInt(numberStr), isEmptyPacket(packet) ? "" : packet}; + } else { + const bool isLengthBits = packet.front() == '0'; + packet = packet.substr(1); + const auto lengthStr = packet.substr(0, isLengthBits ? 15 : 11); + const auto length = binStrToInt(lengthStr); + packet = packet.substr(isLengthBits ? 15 : 11); + + std::list<uint64_t> args; + if (isLengthBits) { + auto rem = packet.substr(0, length); + while (1) { + const auto ret = solve(rem); + args.emplace_front(ret.first); + if (ret.second.empty() || isEmptyPacket(ret.second)) + break; + rem = ret.second; + } + packet = packet.substr(length); + } else { + for (uint64_t i = 0; i < length; ++i) { + const auto ret = solve(packet); + args.emplace_front(ret.first); + packet = ret.second; + if (isEmptyPacket(packet)) + break; + } + } + + uint64_t result; + if (typeId == "000") { + result = 0; + for (auto a : args) + result += a; + } else if (typeId == "001") { + result = 1; + for (auto a : args) + result *= a; + } else if (typeId == "010") { + result = *std::min_element(args.cbegin(), args.cend()); + } else if (typeId == "011") { + result = *std::max_element(args.cbegin(), args.cend()); + } else if (typeId == "101") { + const auto a1 = args.back(); + args.pop_back(); + result = args.back() < a1; + } else if (typeId == "110") { + const auto a1 = args.back(); + args.pop_back(); + result = args.back() > a1; + } else if (typeId == "111") { + const auto a1 = args.back(); + args.pop_back(); + result = args.back() == a1; + } + + return {result, isEmptyPacket(packet) ? "" : packet}; + } +} + |