Advent of Code 2021 - Day 16 - State Machine

main.cpp

#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

enum State { 
    PACKET_VERSION, 
    PACKET_TYPE, 
    PACKET_LITERAL, 
    PACKET_LENGTH_TYPE_ID, 
    PACKET_SUBPACKET_LENGTH, 
    PACKET_SUBPACKET, 
    PACKET_END, 
    PACKET_EOF 
};

int process(const vector<int>& bits, int start, int& version_numbers, ll& value) {

    State state = PACKET_VERSION;
    int packet_version = 0;
    int packet_type = 0;
    ll packet_literal = 0;
    int packet_length_type_id = 0;
    int subpacket_length = 0;
    int subpacket_bits = 0;
    ll packet_value = 0;

    vector<ll> subpacket_values;

    while (state != PACKET_EOF) {
        switch (state) {
            case PACKET_VERSION:
                for (int i = 0; i < 3; i++) {
                    packet_version = packet_version << 1;
                    packet_version += bits[start++];
                }
                state = PACKET_TYPE;
                break;

            case PACKET_TYPE:
                for (int i = 0; i < 3; i++) {
                    packet_type = packet_type << 1;
                    packet_type += bits[start++];
                }
                state = packet_type == 4 ? PACKET_LITERAL : PACKET_LENGTH_TYPE_ID;
                break;
            
            case PACKET_LENGTH_TYPE_ID:
                packet_length_type_id = bits[start++];
                state = PACKET_SUBPACKET_LENGTH;
                break;

            case PACKET_SUBPACKET_LENGTH:
                subpacket_bits = packet_length_type_id == 0 ? 15 : 11;
                for (int i = 0; i < subpacket_bits; i++) {
                    subpacket_length <<= 1;
                    subpacket_length += bits[start++];
                }
                state = PACKET_SUBPACKET;
                break;
            
            case PACKET_SUBPACKET: 
            {
                int end = start;
                long long subpacket_value;

                if (packet_length_type_id == 0) {
                    while (end - start != subpacket_length) {
                        end = process(bits, end, version_numbers, subpacket_value);
                        subpacket_values.push_back(subpacket_value);
                    }
                } else {
                    for (int i = 0; i < subpacket_length; i++) {
                        end = process(bits, end, version_numbers, subpacket_value);
                        subpacket_values.push_back(subpacket_value);
                    }
                }
                start = end;
                state = PACKET_END;
                break;
            }

            case PACKET_LITERAL:
            {
                bool last_packet = bits[start++] == 0;
                for (int i = 0; i < 4; i++) {
                    packet_literal <<= 1;
                    packet_literal += bits[start++];
                }
                state = last_packet ? PACKET_END : PACKET_LITERAL;
                break;
            }
            
            case PACKET_END:
                if (packet_type == 0) {
                    for (auto subpacket_value: subpacket_values)
                        packet_value += subpacket_value;
                } else if (packet_type == 1) {
                    packet_value = 1;
                    for (auto subpacket_value: subpacket_values) 
                        packet_value *= subpacket_value;
                } else if (packet_type == 2) {
                    packet_value = *min_element(subpacket_values.begin(), subpacket_values.end());
                } else if (packet_type == 3) {
                    packet_value = *max_element(subpacket_values.begin(), subpacket_values.end());
                } else if (packet_type == 4) {
                    packet_value = packet_literal;
                } else if (packet_type == 5) {
                    packet_value = subpacket_values[0] > subpacket_values[1];
                } else if (packet_type == 6) {
                    packet_value = subpacket_values[0] < subpacket_values[1];
                } else {
                    packet_value = subpacket_values[0] == subpacket_values[1];
                }
                state = PACKET_EOF;
                break;
        }
    }

    version_numbers += packet_version;
    value = packet_value;

    return start;
}

vector<int> as_bits(const string& hex_string) {
    vector<int> bits;
    for (auto character: hex_string) {
        std::bitset<4> data = character <= '9' ? character - '0' : character - 'A' + 10;
        for (int i = 3; i >= 0; i--) {
            bits.push_back(data[i]);
        }
    }
    return bits;
}

int main() {
    (void)!freopen("input.txt", "r", stdin);

    string line;
    cin >> line;

    auto bits = as_bits(line);
    int version_numbers = 0;
    long long value = 0;

    process(bits, 0, version_numbers, value);

    cout << version_numbers << endl;
    cout << value << endl;
}