day 11, aoc 2016

3 files changed, 242 insertions, 5 deletions

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 <filesystem>
 #include <fstream>
 #include <iostream>
 #include <map>
@@ -9,6 +10,8 @@ using namespace std;
 
 using Sink = tuple<string, int>;
 
+namespace {
+
 vector<string>
 split(const string& line, char sep)
 {
@@ -23,7 +26,7 @@ split(const string& line, char sep)
 }
 
 map<int, tuple<Sink, Sink, vector<int>>>
-read_file(string_view filename)
+read_file(const filesystem::path& filename)
 {
         fstream input{ filename };
 
@@ -84,16 +87,18 @@ solve(map<int, tuple<Sink, Sink, vector<int>>> 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 <fstream>
+#include <iostream>
+#include <map>
+#include <set>
+#include <sstream>
+#include <string>
+
+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<Item>& 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<Item> items_;
+};
+
+namespace {
+
+set<string>
+split(const string& line, char sep)
+{
+        set<string>  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<Item>
+read_file(const filesystem::path& filename)
+{
+        fstream           input{ filename };
+        map<string, Item> 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<Item> result;
+        result.reserve(data.size());
+        for ( const auto& item: data ) {
+                result.emplace_back(item.second);
+        }
+
+        return result;
+}
+
+int
+part1(const State& initial)
+{
+        queue<pair<State, int>> queue; // {Zustand, Schritte}
+        set<State>              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<size_t> 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';
+}
diff --git a/makefile b/makefile
index ffd0a23..6efd32d 100644
--- a/makefile
+++ b/makefile
@@ -37,14 +37,14 @@ all: $(patsubst 2015/src/%.cpp,2015/bin/%,$(wildcard 2015/src/*.cpp)) \
         c++ $(CPPFLAGS) $^ -o $@
 
 2023/bin/day24: 2023/src/day24.cpp | 2023/bin
-        c++ $(CPPFLAGS) -Wno-sign-conversion -I/usr/local/include $^ -L/usr/local/lib -lz3 -o $@
+        c++ $(CPPFLAGS) -Wno-sign-conversion $^ -lz3 -o $@
 
 # 2024
 2024/bin/%: 2024/src/%.cpp | 2024/bin
         c++ $(CPPFLAGS) $^ -o $@
 
 2024/bin/day13-z3: 2024/src/day13-z3.cpp | 2024/bin
-        c++ $(CPPFLAGS) $^ -L/usr/local/lib -lz3 -o $@
+        c++ $(CPPFLAGS) $^ -lz3 -o $@
 
 clean:
         rm -rf 2015/bin 2016/bin 2020/bin 2022/bin 2023/bin 2024/bin