173 lines
3.7 KiB
C++
173 lines
3.7 KiB
C++
#include <iostream>
|
|
#include <string>
|
|
#include <vector>
|
|
#include <cassert>
|
|
|
|
using UInt = unsigned long;
|
|
|
|
struct Item
|
|
{
|
|
UInt value_;
|
|
unsigned depth_;
|
|
};
|
|
|
|
using Items = std::vector<Item>;
|
|
|
|
auto print1(Items::const_iterator begin, Items::const_iterator end, unsigned current_depth)
|
|
-> Items::const_iterator
|
|
{
|
|
if (begin == end) {
|
|
return begin;
|
|
}
|
|
|
|
if (begin->depth_ == current_depth) {
|
|
std::cout << begin->value_;
|
|
++begin;
|
|
return begin;
|
|
}
|
|
|
|
std::cout << '[';
|
|
begin = print1(begin, end, current_depth + 1);
|
|
std::cout << ',';
|
|
begin = print1(begin, end, current_depth + 1);
|
|
std::cout << ']';
|
|
return begin;
|
|
}
|
|
|
|
void print(std::vector<Item> const& items)
|
|
{
|
|
print1(items.begin(), items.end(), 0);
|
|
std::cout << '\n';
|
|
}
|
|
|
|
void reduce(std::vector<Item>& items)
|
|
{
|
|
/* We do all the explosions followed by all the splits until done. */
|
|
std::size_t size{0};
|
|
while (size != items.size()) {
|
|
auto it{items.begin()};
|
|
/* Iterate over everything doing as many explosions as we can. */
|
|
while (it != items.end()) {
|
|
/* Explode */
|
|
if (it->depth_ > 4) {
|
|
assert(it->depth_ == 5);
|
|
assert((it + 1)->depth_ == 5);
|
|
if (it != items.begin()) {
|
|
(it - 1)->value_ += it->value_;
|
|
}
|
|
if (it + 2 != items.end()) {
|
|
(it + 2)->value_ += (it + 1)->value_;
|
|
}
|
|
it->value_ = 0;
|
|
it->depth_ -= 1;
|
|
++it;
|
|
it = items.erase(it);
|
|
}
|
|
else {
|
|
++it;
|
|
}
|
|
}
|
|
|
|
/* Note the size of items here - we only need to go around again if splitting increases the
|
|
* size. */
|
|
size = items.size();
|
|
|
|
/* Ok we've had no explosions so lets try to do a split. */
|
|
it = items.begin();
|
|
while (it != items.end()) {
|
|
if (it->value_ > 9) {
|
|
auto value{it->value_};
|
|
auto depth{it->depth_ + 1};
|
|
it = items.insert(it, {value / 2, depth});
|
|
value -= it->value_;
|
|
++it;
|
|
it->value_ = value;
|
|
it->depth_ = depth;
|
|
/* For this one we need to go back round the loop completely. */
|
|
it = items.end();
|
|
}
|
|
else {
|
|
++it;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void append(Items& items, std::string const& str)
|
|
{
|
|
unsigned current_depth{0};
|
|
for (auto c : str) {
|
|
switch (c) {
|
|
case '[':
|
|
++current_depth;
|
|
break;
|
|
case ']':
|
|
assert(current_depth != 0);
|
|
--current_depth;
|
|
break;
|
|
case ',':
|
|
continue;
|
|
case '0':
|
|
case '1':
|
|
case '2':
|
|
case '3':
|
|
case '4':
|
|
case '5':
|
|
case '6':
|
|
case '7':
|
|
case '8':
|
|
case '9':
|
|
items.push_back({static_cast<UInt>(c - '0'), current_depth});
|
|
break;
|
|
default:
|
|
std::cerr << "Can't interpret " << c << '\n';
|
|
std::exit(1);
|
|
}
|
|
}
|
|
}
|
|
|
|
auto magnitude1(Items::const_iterator begin, Items::const_iterator end, unsigned current_depth)
|
|
-> std::pair<Items::const_iterator, UInt>
|
|
{
|
|
if (begin == end) {
|
|
return {end, 0};
|
|
}
|
|
|
|
if (begin->depth_ == current_depth) {
|
|
auto value = begin->value_;
|
|
++begin;
|
|
return {begin, value};
|
|
}
|
|
|
|
auto [lhs_it, lhs] = magnitude1(begin, end, current_depth + 1);
|
|
auto [rhs_it, rhs] = magnitude1(lhs_it, end, current_depth + 1);
|
|
return {rhs_it, 3 * lhs + 2 * rhs};
|
|
}
|
|
|
|
auto magnitude(Items const& items) -> UInt
|
|
{
|
|
return magnitude1(items.begin(), items.end(), 0).second;
|
|
}
|
|
|
|
auto main() -> int
|
|
{
|
|
std::string line;
|
|
std::vector<Item> items;
|
|
if (!std::getline(std::cin, line)) {
|
|
std::cout << "Unable to read first line.";
|
|
}
|
|
append(items, line);
|
|
while (std::getline(std::cin, line) && !line.empty()) {
|
|
append(items, line);
|
|
|
|
/* Deepen everything one. */
|
|
for (auto& item : items) {
|
|
++(item.depth_);
|
|
}
|
|
|
|
reduce(items);
|
|
}
|
|
|
|
std::cout << "Magnitude: " << magnitude(items) << '\n';
|
|
}
|