Skip to content

Instantly share code, notes, and snippets.

@chowder

chowder/main.cpp

Created December 16, 2021 22:01
Show Gist options
  • Save chowder/59526c90a2ad281d9283f35e633cca89 to your computer and use it in GitHub Desktop.
Save chowder/59526c90a2ad281d9283f35e633cca89 to your computer and use it in GitHub Desktop.
Download ZIP
Advent of Code 2021 - Day 16 - State Machine
Raw
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment