|
|
back to boardShow all messages Hide all messagesEven after reading all the posts here. Please help. 1. assert program is shorter than input 2. assert no long lines in source code 3. split string literal into vectors 4. assert no '\r' but '\n' after reading input 5. output with std::cout and '\n' 6. many tests and asserts ===this is an example of archive=== might be overkill to use Huffman and base64 shorten variable names in actual archive =================================== //CPP #include <iostream> #include <string> #include <unordered_map> #include <vector> int length = 37; std::vector<std::string> encoded{ "7VKh", "7lg=" }; std::unordered_map<std::string, char> table{ {"00", 'o'}, {"01", 'l'}, {"100", 'w'}, {"1010", ' '}, {"1011", '!'}, {"1100", 'd'}, {"1101", 'e'}, {"1110", 'h'}, {"1111", 'r'} }; struct HuffmanTree { char ch; struct HuffmanTree* left; struct HuffmanTree* right; ~HuffmanTree() { delete left; delete right; } }; void build_tree(HuffmanTree* root, std::string code, char ch) { auto node{root}; for (auto x : code) if (x == '1') { if (node->right == nullptr) node->right = new HuffmanTree(); node = node->right; } else { if (node->left == nullptr) node->left = new HuffmanTree(); node = node->left; } node->ch = ch; } char lookup(std::vector<bool>::iterator& it, const HuffmanTree* tree) { auto node{tree}; while (true) { if (node->left == nullptr) break; if (*it) node = node->right; else node = node->left; it++; } return node->ch; } void huffman_decode(std::vector<bool> bits, const HuffmanTree* tree) { auto it{bits.begin()}; while (it != bits.end()) std::cout << lookup(it, tree); } int six(char c) { if (c >= 'A' and c <= 'Z') return c-'A'; if (c >= 'a' and c <= 'z') return c-'a' + 26; if (c >= '0' and c <= '9') return c-'0' + 52; if (c == '+') return 62; if (c == '/') return 63; return 0; } std::vector<std::string> base64_decode(std::vector<std::string> encoded) { std::vector<std::string> decoded; for (auto s : encoded) { std::string t; auto i{0u}; while (i < s.size()) { auto p0{six(s[i])}; auto p1{six(s[i+1])}; auto p2{six(s[i+2])}; auto p3{six(s[i+3])}; t.push_back((p0<<2) + ((p1&0x30)>>4)); if (s[i+2] != '=') t.push_back(((p1&0x0f)<<4) + ((p2&0x3c)>>2)); if (s[i+3] != '=') t.push_back(((p2&0x03)<<6) + p3); i += 4; } decoded.push_back(t); } return decoded; } std::vector<bool> string_to_bits(int n, std::vector<std::string> v) { std::vector<bool> bits; for (auto s : v) for (auto byte : s) for (auto i{7}; i >= 0; i--) bits.push_back((byte >> i) & 1); while (int(bits.size()) > n) bits.pop_back(); return bits; } int main() { auto decoded{base64_decode(encoded)}; auto bits{string_to_bits(length, decoded)}; auto root{new HuffmanTree()}; for (auto [code, ch] : table) build_tree(root, code, ch); huffman_decode(bits, root); } For a much simpler algorithm, the c++ program got accepted easily. However, the python version still got WA#1. Probably some I/O issue for the python interpreter. Maybe newlines are handled differently for python "print(s, end='')" and c++ "std::cout << s". Edited by author 04.02.2022 08:15 |
|
|