#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;
}