1 files changed, 142 insertions, 0 deletions

diff --git a/2023/05/src/part2.cpp b/2023/05/src/part2.cpp
new file mode 100644
index 0000000..89f887e
--- /dev/null
+++ b/2023/05/src/part2.cpp
@@ -0,0 +1,142 @@
+#include <algorithm>
+#include <iostream>
+#include <fstream>
+#include <sstream>
+#include <set>
+#include <tuple>
+#include <vector>
+
+#include "util.h"
+
+using SeedRange = std::tuple<int,long,long>;
+using Seeds = std::set<SeedRange>;
+
+using Map = std::tuple<long,long,long>;
+using Step = std::vector<Map>;
+using Almanac = std::vector<Step>;
+
+constexpr char SEEDS[] = "seeds:";
+
+std::pair<Seeds,Almanac> parse_input()
+{
+    Seeds seeds;
+    Almanac almanac;
+
+    std::ifstream input{ "resources/input.txt" };
+    if (input.is_open())
+    {
+        std::string line;
+        long from, to, size;
+
+        /* Seeds */
+        std::getline(input,line);
+        std::istringstream sline{ line };
+        sline >> util::skip<SEEDS>;
+        while (sline >> from >> size)
+        {
+            seeds.insert(std::make_tuple(0, from, from + size));
+        }
+
+        /* Mappings */
+        Step step;
+        while (not std::getline(input,line).eof())
+        {
+            if (line.empty()) continue;
+
+            if (std::isdigit(line[0]))
+            {
+                std::istringstream{ line } >> to >> from >> size;
+                step.push_back(std::make_tuple(from, from + size, to - from));
+            }
+            else if (not step.empty())
+            {
+                almanac.push_back(std::move(step));
+                step = {};
+            }
+        }
+        almanac.push_back(std::move(step));
+    }
+    input.close();
+
+    return std::make_pair(std::move(seeds), std::move(almanac));
+}
+
+Seeds map_to_range(int step, const SeedRange& seed_range, const Map& map)
+{
+    int s;
+    long rbegin, rend;
+    long mbegin, mend, diff;
+    std::tie(s, rbegin, rend) = seed_range;
+    std::tie(mbegin, mend, diff) = map;
+
+    if (mbegin <= rbegin)
+    {
+        if (mend >= rend)
+        {
+            return {
+                std::make_tuple(step + 1, rbegin + diff, rend + diff)
+            };
+        }
+        else if (mend > rbegin)
+        {
+            return {
+                std::make_tuple(step + 1, rbegin + diff, mend + diff),
+                std::make_tuple(step, mend, rend),
+            };
+        }
+    }
+    else if (mbegin < rend)
+    {
+        if (mend >= rend)
+        {
+            return {
+                std::make_tuple(step, rbegin, mbegin),
+                std::make_tuple(step + 1, mbegin + diff, rend + diff),
+            };
+        }
+        else
+        {
+            return {
+                std::make_tuple(step, rbegin, mbegin),
+                std::make_tuple(step + 1, mbegin + diff, mend + diff),
+                std::make_tuple(step, mend, rend),
+            };
+        }
+    }
+    return { seed_range };
+}
+
+int main(void)
+{
+    Seeds seeds;
+    Almanac almanac;
+    std::tie(seeds, almanac) = parse_input();
+
+    for (int s = 0; s < almanac.size(); ++s)
+    {
+        const auto& step = almanac[s];
+        for (const auto& map : step)
+        {
+            std::set<SeedRange> new_seeds;
+            for(auto& seed : seeds)
+            {
+                if (std::get<0>(seed) <= s)
+                {
+                    auto res = map_to_range(s, seed, map);
+                    new_seeds.insert(res.begin(), res.end());
+                }
+                else
+                {
+                    new_seeds.insert(seed);
+                }
+            }
+            seeds = std::move(new_seeds);
+        }
+    }
+
+    auto min = std::min_element(seeds.cbegin(), seeds.cend(),
+        [](auto s1, auto s2) { return std::get<1>(s1) < std::get<1>(s2); });
+    std::cout << std::get<1>(*min) << std::endl;
+
+    return 0;
+}