69 lines
1.7 KiB
C++
69 lines
1.7 KiB
C++
//
|
|
// Created by Matthew Gretton-Dann on 01/12/2022.
|
|
//
|
|
|
|
#include <algorithm>
|
|
#include <cstdlib>
|
|
#include <iomanip>
|
|
#include <iostream>
|
|
#include <map>
|
|
#include <numeric>
|
|
#include <regex>
|
|
#include <utility>
|
|
|
|
struct Step
|
|
{
|
|
explicit Step(std::string const& dependencies) : done_(false), dependencies_(dependencies) {}
|
|
|
|
bool done_;
|
|
std::string dependencies_;
|
|
};
|
|
|
|
using UInt = std::int64_t;
|
|
using StepMap = std::map<char, Step>;
|
|
|
|
auto main() -> int
|
|
{
|
|
std::string line;
|
|
StepMap step_map;
|
|
std::regex const re{"Step ([A-Z]) must be finished before step ([A-Z]) can begin."};
|
|
|
|
// Read data
|
|
while (std::getline(std::cin, line)) {
|
|
std::smatch m;
|
|
if (!std::regex_match(line, m, re)) {
|
|
std::cerr << "Unable to interpret: " << line << "\n";
|
|
return EXIT_FAILURE;
|
|
}
|
|
char id{m.str(2)[0]};
|
|
auto [it, success] = step_map.insert({id, Step(m.str(1))});
|
|
if (!success) {
|
|
it->second.dependencies_ += m.str(1);
|
|
}
|
|
|
|
// Ensure we have every id we've seen present in the map even if it has no dependencies
|
|
step_map.insert({m.str(1)[0], Step("")});
|
|
}
|
|
|
|
std::string order;
|
|
while (!std::all_of(step_map.begin(), step_map.end(),
|
|
[](auto const& step) { return step.second.done_; })) {
|
|
char to_do{'Z' + 1};
|
|
for (auto& step : step_map) {
|
|
if (step.second.done_) {
|
|
continue;
|
|
}
|
|
auto const& dependencies{step.second.dependencies_};
|
|
if (std::all_of(dependencies.begin(), dependencies.end(),
|
|
[&step_map](auto c) { return step_map.find(c)->second.done_; })) {
|
|
to_do = std::min(step.first, to_do);
|
|
}
|
|
}
|
|
order += to_do;
|
|
step_map.find(to_do)->second.done_ = true;
|
|
}
|
|
|
|
std::cout << "Order: " << order << "\n";
|
|
return EXIT_SUCCESS;
|
|
}
|