From 5dde3837a6ecbd372b2d5db0b12969a4b7fbf4f7 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Thu, 16 Oct 2025 18:08:53 +0200 Subject: day 11, aoc 2016 --- 2016/src/day10.cpp | 11 ++- 2016/src/day11.cpp | 232 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 240 insertions(+), 3 deletions(-) create mode 100644 2016/src/day11.cpp (limited to '2016/src') diff --git a/2016/src/day10.cpp b/2016/src/day10.cpp index 7c1f4f9..851ad9d 100644 --- a/2016/src/day10.cpp +++ b/2016/src/day10.cpp @@ -1,3 +1,4 @@ +#include #include #include #include @@ -9,6 +10,8 @@ using namespace std; using Sink = tuple; +namespace { + vector split(const string& line, char sep) { @@ -23,7 +26,7 @@ split(const string& line, char sep) } map>> -read_file(string_view filename) +read_file(const filesystem::path& filename) { fstream input{ filename }; @@ -84,16 +87,18 @@ solve(map>> bots) // part1 if ( chips.at(0) == 17 && chips.at(1) == 61 ) { - cout << id << endl; + cout << id << '\n'; } chips.clear(); } // part2 - cout << outputs[0] * outputs[1] * outputs[2] << endl; + cout << outputs[0] * outputs[1] * outputs[2] << '\n'; } +} // namespace + int main() { diff --git a/2016/src/day11.cpp b/2016/src/day11.cpp new file mode 100644 index 0000000..af3d2df --- /dev/null +++ b/2016/src/day11.cpp @@ -0,0 +1,232 @@ +#include +#include +#include +#include +#include +#include + +using namespace std; + +struct Item { + Item() = default; + Item(size_t chip_floor, size_t generator_floor) // NOLINT + : chip_floor_{ chip_floor } + , generator_floor_{ generator_floor } + { + } + + size_t chip_floor_; + size_t generator_floor_; + + bool operator<(const Item& rhs) const + { + if ( chip_floor_ != rhs.chip_floor_ ) { + return chip_floor_ < rhs.chip_floor_; + } + return generator_floor_ < rhs.generator_floor_; + } +}; + +struct State { + explicit State(const vector& items) + : items_{ items } + { + } + + [[nodiscard]] + bool is_valid() const + { + for ( size_t i = 0; i != items_.size(); ++i ) { + const auto chip_floor = items_[i].chip_floor_; // Etage des Mikrochips + if ( chip_floor == items_[i].generator_floor_ ) { + continue; // Mikrochip ist mit seinem Generator zusammen + } + // Prüfe, ob ein fremder Generator auf derselben Etage ist + for ( size_t j = 0; j != items_.size(); ++j ) { + if ( j != i && chip_floor == items_[j].generator_floor_ ) { + return false; // Ungültig: Mikrochip mit fremdem Generator ohne eigenen Generator + } + } + } + return true; + } + + [[nodiscard]] + bool is_goal() const + { + for ( const auto& item: items_ ) { + if ( item.chip_floor_ != 3 || item.generator_floor_ != 3 ) { + return false; + } + } + return elevator_ == 3; + } + + bool operator<(const State& rhs) const + { + if ( elevator_ != rhs.elevator_ ) { + return elevator_ < rhs.elevator_; + } + return items_ < rhs.items_; + } + + size_t elevator_{}; + vector items_; +}; + +namespace { + +set +split(const string& line, char sep) +{ + set parts; + stringstream input{ line }; + + for ( string part; getline(input, part, sep); ) { + parts.insert(part); + } + + for ( const auto& word: { "The", "a", "floor", "and", "contains", "microchip", + "microchip.", "microchip,", "generator", "generator.", "generator,", "first", + "second", "third", "fourth", "nothing", "relevant." } ) { + parts.erase(word); + } + + return parts; +} + +vector +read_file(const filesystem::path& filename) +{ + fstream input{ filename }; + map data; + + auto is_microchip = [](string_view item) { + return item.ends_with("-compatible"); + }; + + string line; + for ( size_t floor = 0; getline(input, line); ++floor ) { + auto items = split(line, ' '); + + for ( auto item: items ) { + if ( is_microchip(item) ) { + item = item.erase(item.find('-')); + + data[item].chip_floor_ = floor; + } + else { + data[item].generator_floor_ = floor; + } + } + } + + vector result; + result.reserve(data.size()); + for ( const auto& item: data ) { + result.emplace_back(item.second); + } + + return result; +} + +int +part1(const State& initial) +{ + queue> queue; // {Zustand, Schritte} + set visited; + + queue.emplace(initial, 0); + visited.insert(initial); + + while ( !queue.empty() ) { + auto [current, steps] = queue.front(); + queue.pop(); + + if ( current.is_goal() ) { + return steps; + } + + // Mögliche Aufzugbewegungen: hoch oder runter + for ( int dir: { -1, 1 } ) { + auto new_elevator = current.elevator_ + size_t(dir); + if ( new_elevator < 0 || new_elevator > 3 ) { + continue; + } + + // Wähle 1 oder 2 Objekte + vector items_on_floor; + for ( size_t i = 0; i < current.items_.size(); ++i ) { + if ( current.items_[i].generator_floor_ == current.elevator_ ) { + items_on_floor.emplace_back(i * 2); // Generator + } + if ( current.items_[i].chip_floor_ == current.elevator_ ) { + items_on_floor.emplace_back((i * 2) + 1); // Mikrochip + } + } + + // Alle Kombinationen von 1 oder 2 Objekten + for ( size_t i = 0; i < items_on_floor.size(); ++i ) { + // 1 Objekt + State next = current; + next.elevator_ = new_elevator; + auto item = items_on_floor[i]; + if ( item % 2 == 0 ) { + next.items_[item / 2].generator_floor_ = new_elevator; // Generator + } + else { + next.items_[item / 2].chip_floor_ = new_elevator; // Mikrochip + } + if ( next.is_valid() && !visited.contains(next) ) { + visited.emplace(next); + queue.emplace(next, steps + 1); + } + + // 2 Objekte + for ( size_t j = i + 1; j < items_on_floor.size(); ++j ) { + State next2 = current; + next2.elevator_ = new_elevator; + auto item1 = items_on_floor[i]; + auto item2 = items_on_floor[j]; + if ( item1 % 2 == 0 ) { + next2.items_[item1 / 2].generator_floor_ = new_elevator; + } + else { + next2.items_[item1 / 2].chip_floor_ = new_elevator; + } + if ( item2 % 2 == 0 ) { + next2.items_[item2 / 2].generator_floor_ = new_elevator; + } + else { + next2.items_[item2 / 2].chip_floor_ = new_elevator; + } + if ( next2.is_valid() && !visited.contains(next2) ) { + visited.insert(next2); + queue.emplace(next2, steps + 1); + } + } + } + } + } + return -1; // Keine Lösung gefunden +} + +int +part2(State initial) +{ + initial.items_.emplace_back(0, 0); + initial.items_.emplace_back(0, 0); + return part1(initial); +} + +} // namespace + +int +main() +{ + auto floors = read_file("data/day11.txt"); + State state{ floors }; + + cout << "Part1: " << part1(state) << '\n'; + cout << "Part2: " << part2(state) << '\n'; +} -- cgit v1.3