aoc2023_day05.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <limits>
#include <map>
#include <algorithm>

struct Range {
	int64_t start, end;
	bool operator<(const Range &other) const {
		return start < other.start;
	}
};

std::vector<Range> crush_ranges(std::vector<Range> &&ranges) {
	std::sort(ranges.begin(), ranges.end());
	std::vector<Range> out;
	auto it = ranges.begin();
	while (it != ranges.end()) {
		Range next = *it++;
		while (it != ranges.end() && it->start <= next.end) {
			next.end = it++->end;
		}
		out.emplace_back(next);
	}
	return out;
}

struct Map {
	using Mapping = std::map<int64_t, int64_t, std::greater<int64_t>>;
	Mapping mappings;
	int64_t take_offset(const Mapping::const_iterator &it) const {
		return it == mappings.end() ? 0 : it->second;
	}
	int64_t operator()(int64_t value) const {
		return value + take_offset(mappings.lower_bound(value));
	}
	std::vector<Range> operator()(const std::vector<Range> &values) const {
		std::vector<Range> out;
		for (const Range &range : values) {
			auto index = range.start;
			auto start = mappings.lower_bound(index);
			auto end = mappings.upper_bound(range.end);
			while (start != end) {
				auto offset = take_offset(start);
				--start;
				auto next_index = start->first;
				out.emplace_back(Range { index + offset, next_index + offset });
				index = next_index;
			}
			auto offset = take_offset(end);
			out.emplace_back(Range { index + offset, range.end + offset });
		}
		return crush_ranges(std::move(out));
	}
};

template<typename T>
struct Compose {
	std::vector<T> ops;

	Compose(std::vector<T> &&ops) : ops(ops) {}

	template<typename U>
	U operator()(U &&in) {
		for (const auto &op : ops) {
			in = op(in);
		}
		return in;
	}
};

Map parse_map(std::istream &in) {
	Map out {};
	auto &mappings = out.mappings;
	std::string buf;
	std::getline(in, buf);
	while (std::getline(in, buf)) {
		if (!buf.size()) {
			break;
		}
		std::stringstream ss {buf};
		int64_t target, start, length;
		ss >> target >> start >> length;
		mappings.insert_or_assign(start, target - start);
		mappings.emplace(std::pair {start + length, 0});
	}
	return out;
}

std::vector<int64_t> start_seeds(std::istream &in) {
	std::vector<int64_t> seeds;
	std::string buf, scratch;
	std::getline(in, buf);
	std::stringstream ss {buf};
	int64_t seed;
	ss >> scratch;
	while (ss >> seed) {
		seeds.push_back(seed);
	}
	std::getline(in, buf);
	return seeds;
}

std::vector<Range> make_range(const std::vector<int64_t> &in) {
	std::vector<Range> out;
	for (size_t i = 0; i < in.size(); i += 2) {
		auto pos = in[i];
		auto len = in[i + 1];
		out.emplace_back(Range { pos, pos + len });
	}
	return out;
}

int main() {
	const auto &seeds = start_seeds(std::cin);
	std::vector<Map> maps;
	while (std::cin) {
		maps.emplace_back(parse_map(std::cin));
	}
	Compose run_maps {std::move(maps)};
	auto best = std::numeric_limits<int64_t>::max();
	for (auto candidate : seeds) {
		best = std::min(run_maps(candidate), best);
	}
	std::cout << best << std::endl;
	std::cout << run_maps(make_range(seeds))[0].start << std::endl;
	return 0;
}