Advent of Code 2017, Day 7 - Recursive Circus

Question

This is my solution to Advent of Code 2017, Day 7 – Recursive Circus (both parts, you might not be able to see the second part unless you're logged in and solved the first part, but I'll summarize it here).

Problem description

There is a tower of "programs":

One program at the bottom supports the entire tower. It's holding a large disc, and on the disc are balanced several more sub-towers. At the bottom of these sub-towers, standing on the bottom disc, are other programs, each holding their own disc, and so on. At the very tops of these sub-sub-sub-...-towers, many programs stand simply keeping the disc below them balanced but with no disc of their own.

Part 1

[...] You ask each program to yell out their name, their weight, and (if they're holding a disc) the names of the programs immediately above them balancing on that disc. You write this information down (your puzzle input).

For example, if your list is the following:

pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)

[...] tknk is at the bottom of the tower (the bottom program).

The first part consists of parsing the list of "programs" formatted as in the example above and determining which program is at the bottom of the tower. (Now I'm noticing that I've called it the "base" of the tower in my code.)

Part 2

For any program holding a disc, each program standing on that disc forms a sub-tower. Each of those sub-towers are supposed to be the same weight, or the disc itself isn't balanced. The weight of a tower is the sum of the weights of the programs in that tower.

In the example above, this means that for ugml's disc to be balanced, gyxo, ebii, and jptl must all have the same weight, and they do: 61.

However, for tknk to be balanced, each of the programs standing on its disc and all programs above it must each match. This means that the following sums must all be the same:

ugml + (gyxo + ebii + jptl) = 68 + (61 + 61 + 61) = 251
padx + (pbga + havc + qoyq) = 45 + (66 + 66 + 66) = 243
fwft + (ktlj + cntj + xhth) = 72 + (57 + 57 + 57) = 243

As you can see, tknk's disc is unbalanced: ugml's stack is heavier than the other two. Even though the nodes above ugml are balanced, ugml itself is too heavy: it needs to be 8 units lighter for its stack to weigh 243 and keep the towers balanced. If this change were made, its weight would be 60.

Given that exactly one program is the wrong weight, what would its weight need to be to balance the entire tower?

My code

Specific concerns:

• Is my use of std::swap in order to reuse one constructor in another constructor, or in operator>>, appropriate?

• I fear that the implementation of check_balance is not clear enough, given that I felt the need to add comments at each step. Is there a way to improve this?

recursive_circus.h

#ifndef RECURSIVE_CIRCUS_H
#define RECURSIVE_CIRCUS_H

#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

class Program {
public:
    using Name = std::string;
    using Weight = int;

    struct InvalidFormat : public std::runtime_error {
        InvalidFormat();
    };

    Program() = default;
    Program(const Name& n, Weight w, std::vector<Name> supported);
    Program(const std::string& line);

    friend std::istream& operator>>(std::istream& input, Program& prog);

    const Name& name() const { return name_; }
    Weight weight() const { return weight_; }
    const std::vector<Name>& supported() const { return supported_; }

private:
    Name name_;
    Weight weight_;
    std::vector<Name> supported_;
};

class ProgramTower {
public:
    // Map from name to program with that name.
    using NameMap = std::unordered_map<Program::Name, Program>;

    struct NoBase : public std::runtime_error {
        NoBase();
    };

    ProgramTower() = default;
    ProgramTower(const NameMap& programs);
    ProgramTower(const std::vector<Program>& programs);

    friend std::istream& operator>>(std::istream& input, ProgramTower& tower);

    // Return the total weight of the program with the given name, and all
    // sub-towers it is supporting.
    Program::Weight total_weight(const Program::Name& name) const;
    Program::Weight total_weight() const { return total_weight(base()); }

    // Determine which program in the tower supported by the program with the
    // given name has the wrong weight (i.e. causes a sub-tower to be
    // unbalanced), assuming that there is exactly one such program.
    struct BalanceResult {
        bool balanced;
        Program::Name wrong_program;
        Program::Weight correct_weight;
    };
    BalanceResult check_balance(const Program::Name& name) const;
    BalanceResult check_balance() const { return check_balance(base()); }

    Program::Name base() const { return base_; }

private:
    using SupportMap = std::unordered_map<Program::Name, Program::Name>;

    // Build a map from each program to the one it is supported by
    // (will contain all programs except the base of the tower).
    static SupportMap build_support_map(const NameMap&);
    // Find the base program (the one which is not supported by any other).
    static Program::Name find_base(const NameMap&, const SupportMap&);

    NameMap programs_;
    SupportMap support_;
    Program::Name base_;
};

#endif

recursive_circus.cpp

#include "recursive_circus.h"
#include <regex>

Program::InvalidFormat::InvalidFormat()
  : std::runtime_error("Line has invalid format.")
{}

Program::Program(const Name& n, Weight w, std::vector<Name> supported)
  : name_{n}, weight_{w}, supported_{supported}
{}

Program::Program(const std::string& line)
{
    std::smatch line_match;
    if (!std::regex_match(line, line_match,
            std::regex{R"((\w+) \((\d+)\)(?: -> ((?:\w+(, |$))+))?)"}
    )) throw InvalidFormat{};

    name_ = line_match[1];
    weight_ = std::stoi(line_match[2]);

    auto names{line_match[3]};
    if (!names.length()) return;

    auto names_str{names.str()};
    std::smatch names_match;
    while (std::regex_search(names_str, names_match,
            std::regex{R"(\w+)"}
    )) {
        supported_.push_back(names_match.str());
        names_str = names_match.suffix();
    }
}

std::istream& operator>>(std::istream& input, Program& prog)
{
    std::string line;
    while (std::getline(input, line)) {
        try {
            Program dummy{line};
            std::swap(prog, dummy);
            break;
        } catch (Program::InvalidFormat) {
            continue;
        }
    }
    return input;
}


ProgramTower::NoBase::NoBase()
  : std::runtime_error("The base of the tower cannot be determined.")
{}

ProgramTower::SupportMap
ProgramTower::build_support_map(const NameMap& programs)
{
    SupportMap result;
    for (auto const& name_prog : programs) {
        auto supporter{name_prog.second};
        for (auto const& supported : supporter.supported()) {
            result.insert({supported, supporter.name()});
        }
    }
    return result;
}

Program::Name
ProgramTower::find_base(const NameMap& programs, const SupportMap& support)
{
    for (auto const& name_prog : programs) {
        auto name{name_prog.first};
        if (support.find(name) == std::end(support)) return name;
    }
    throw NoBase{};
}

ProgramTower::ProgramTower(const NameMap& programs)
  : programs_{programs},
    support_{build_support_map(programs_)},
    base_{find_base(programs_, support_)}
{}

ProgramTower::ProgramTower(const std::vector<Program>& programs)
{
    NameMap names;
    for (auto const& prog : programs) names.insert({prog.name(), prog});
    ProgramTower dummy{names};
    std::swap(*this, dummy);
}

std::istream& operator>>(std::istream& input, ProgramTower& tower)
{
    ProgramTower::NameMap programs;
    Program prog;
    while (input >> prog) programs.insert({prog.name(), prog});
    ProgramTower dummy{programs};
    std::swap(tower, dummy);
    return input;
}

Program::Weight ProgramTower::total_weight(const Program::Name& name) const
{
    auto base{programs_.at(name)};
    Program::Weight result{base.weight()};
    for (auto const& sub : base.supported()) {
        result += total_weight(sub);
    }
    return result;
}

ProgramTower::BalanceResult
ProgramTower::check_balance(const Program::Name& name) const
{
    // Map from weight to list of supported sub-towers with that weight.
    std::unordered_map<Program::Weight, std::vector<Program::Name>> weights;
    for (auto const& sub : programs_.at(name).supported()) {
        weights[total_weight(sub)].push_back(sub);
    }

    // All sub-towers have the same weight or there are no sub-towers.
    // -> This tower is balanced, no program in it has the wrong weight.
    if (weights.size() <= 1) {
        return {true, "", 0};
    }

    // Not all supported sub-towers have the same total weight.
    // According to the problem description we can assume that there is exactly
    // one sub-tower that has a different weight than all the others, and that
    // this is caused by exactly one program with the wrong weight.
    int correct_total_weight{0};
    Program::Name wrong_program{""};

    for (auto const& weight_subs : weights) {
        auto subs{weight_subs.second};
        if (subs.size() != 1) {
            // Found the "correct" total weight of all but one sub-tower.
            correct_total_weight = weight_subs.first;
            continue;
        }
        // The one sub-tower with the wrong total weight.
        for (auto const& sub : subs) {
            auto result{check_balance(sub)};
            if (result.balanced) {
                // The sub-tower is balanced, its base is the wrong program.
                wrong_program = sub;
                continue;
            }
            // The sub-tower is not balanced, the wrong program is further up.
            return result;
        }
    }

    // Determine the correct weight of the "wrong" program.
    auto correct_weight{
        programs_.at(wrong_program).weight()
        + correct_total_weight - total_weight(wrong_program)
    };
    return {false, wrong_program, correct_weight};
}

Main program

#include "recursive_circus.h"
#include <iostream>

int main()
{
    ProgramTower tower;
    std::cin >> tower;

    std::cout << "Program '" << tower.base()
              << "' is the base of the tower of programs.\n";

    std::cout << "The total weight of the tower is "
              << tower.total_weight() << ".\n";

    auto balance{tower.check_balance()};
    std::cout << "The tower is "
              << (balance.balanced ? "" : "not ") << "balanced.\n";

    if (!balance.balanced) {
        std::cout << "Program '" << balance.wrong_program
                  << "' has the wrong weight.\n";

        std::cout << "Its weight would need to be "
                  << balance.correct_weight << ".\n";
    }
}

Tests

#include "recursive_circus.h"
#include <cassert>
#include <string>
#include <vector>

struct ProgramInputTest {
    std::string input;
    Program::Name name;
    Program::Weight weight;
    std::vector<Program::Name> supported;
};

const std::vector<ProgramInputTest> program_input_tests {
    {"a (1)",                         "a",     1, {}},
    {"a (2) -> b",                    "a",     2, {"b"}},
    {"pbga (66)",                     "pbga", 66, {}},
    {"fwft (72) -> ktlj, cntj, xhth", "fwft", 72, {"ktlj", "cntj", "xhth"}}
};

void test_program_input()
{
    for (auto const& test : program_input_tests) {
        Program p{test.input};
        assert(p.name() == test.name);
        assert(p.weight() == test.weight);
        assert(p.supported() == test.supported);
    }
}


struct ProgramTowerTest {
    std::vector<Program> programs;
    Program::Name base;
    Program::Weight total_weight;
    bool balanced;
    Program::Name wrong_program;
    Program::Weight correct_weight;
};

const std::vector<ProgramTowerTest> program_tower_tests {
    {{{"a", 3, {}}
     },
     "a", 3, true, "", 0},

    {{{"a", 3, {"b", "c"}},
      {"b", 1, {}},
      {"c", 1, {}}
     },
     "a", 5, true, "", 0},

    {{{"a", 3, {"b", "c", "d"}},
      {"b", 1, {}},
      {"c", 2, {}},
      {"d", 2, {}}
     },
     "a", 8, false, "b", 2},

    {{{"pbga", 66, {}},
      {"xhth", 57, {}},
      {"ebii", 61, {}},
      {"havc", 66, {}},
      {"ktlj", 57, {}},
      {"fwft", 72, {"ktlj", "cntj", "xhth"}},
      {"qoyq", 66, {}},
      {"padx", 45, {"pbga", "havc", "qoyq"}},
      {"tknk", 41, {"ugml", "padx", "fwft"}},
      {"jptl", 61, {}},
      {"ugml", 68, {"gyxo", "ebii", "jptl"}},
      {"gyxo", 61, {}},
      {"cntj", 57, {}}
     },
     "tknk", 778, false, "ugml", 60},
};

void test_program_tower()
{
    for (auto const& test : program_tower_tests) {
        ProgramTower tower{test.programs};

        assert(tower.base() == test.base);
        assert(tower.total_weight() == test.total_weight);

        ProgramTower::BalanceResult b{tower.check_balance()};
        assert(b.balanced == test.balanced);
        assert(b.wrong_program == test.wrong_program);
        assert(b.correct_weight == test.correct_weight);
    }
}

int main()
{
    test_program_input();
    test_program_tower();
}

Answer 1

// Determine which program in the tower supported by the program with the
// given name has the wrong weight (i.e. causes a sub-tower to be
// unbalanced), assuming that there is exactly one such program.
struct BalanceResult {
    bool balanced;
    Program::Name wrong_program;
    Program::Weight correct_weight;
};
BalanceResult check_balance(const Program::Name& name) const;
BalanceResult check_balance() const { return check_balance(base()); }

The description of this function is slightly inaccurate (too pessimistic). The function does handle the case where no program in the tower has the wrong weight and the tower is therefore balanced. The returned type is even designed to represent this result:

// All sub-towers have the same weight or there are no sub-towers.
// -> This tower is balanced, no program in it has the wrong weight.
if (weights.size() <= 1) {
    return {true, "", 0};
}

The description could be improved to:

// Determine whether the tower supported by the program with the given name
// is balanced, and if not, which program in it has the wrong weight
// (i.e. causes a sub-tower to be unbalanced), and what its correct weight
// would be, assuming that there is only one such program.

---

Considering this loop in check_balance:

for (auto const& weight_subs : weights) {
    auto subs{weight_subs.second};
    if (subs.size() != 1) {
        // Found the "correct" total weight of all but one sub-tower.
        correct_total_weight = weight_subs.first;
        continue;
    }

At this point we know that subs.size() must be equal to 1. So in the following, it would make the code clearer when, instead of using a loop over a single-item vector, that item would be used directly, without a loop:

    // The one sub-tower with the wrong total weight.
    for (auto const& sub : subs) {

The continue statement inside this nested loop is meant to continue with the next item from weights (the enclosing for loop). Technically wrong, as it actually continues with the next item from subs. However, by luck, this works, because there is no next item in subs and then the control flow naturally reaches the end of the outer loop body.

        auto result{check_balance(sub)};
        if (result.balanced) {
            // The sub-tower is balanced, its base is the wrong program.
            wrong_program = sub;
            continue;
        }
        // The sub-tower is not balanced, the wrong program is further up.
        return result;
    }
}

Once the unnecessary inner loop is removed, its body can remain unchanged and works by design, not by luck. Also, to improve clarity, the amount of auto could be reduced, if practical:

for (auto const& weight_subs : weights) {
    auto subs{weight_subs.second};
    if (subs.size() != 1) {
        // Found the "correct" total weight of all but one sub-tower.
        correct_total_weight = weight_subs.first;
        continue;
    }
    // The one sub-tower with the wrong total weight.
    assert(subs.size() == 1);
    const Program::Name& sub{subs[0]};
    auto result{check_balance(sub)};
    if (result.balanced) {
        // The sub-tower is balanced, its base is the wrong program.
        wrong_program = sub;
        continue;
    }
    // The sub-tower is not balanced, the wrong program is further up.
    return result;
}