Line data Source code
1 : #include "IntegerCast.h"
2 : #include "LinewiseInput.h"
3 : #include "Parsing.h"
4 : #include "PuzzleImpl.h"
5 :
6 : #include <libassert/assert.hpp>
7 : #include <re2/re2.h>
8 :
9 : #include <algorithm>
10 : #include <cstdint>
11 : #include <string>
12 : #include <vector>
13 :
14 : namespace {
15 :
16 : // interval [begin, end)
17 : struct ValueRange {
18 : uint64_t begin = 0;
19 : uint64_t end = 0;
20 : };
21 :
22 : class Map {
23 : public:
24 14 : Map(auto begin, auto end) {
25 14 : static RE2 const headerPattern = R"((\w+)-to-(\w+) map:)";
26 14 : ASSUME(RE2::FullMatch(*begin, headerPattern, &_srcCategory, &_dstCategory));
27 14 : _ranges.assign(std::next(begin), end);
28 5428 : std::ranges::sort(_ranges, std::ranges::less{}, [](auto const &r) { return r.src.begin; });
29 14 : }
30 :
31 140 : uint64_t operator()(uint64_t const i) const {
32 140 : auto it = std::ranges::upper_bound(_ranges, i, std::ranges::less{},
33 721 : [](auto const &r) { return r.src.end; });
34 140 : if (it < _ranges.end() && i >= it->src.begin) {
35 134 : return i + it->offset;
36 134 : } else {
37 6 : return i;
38 6 : }
39 140 : }
40 :
41 681 : void operator()(ValueRange const r, auto out) const {
42 1103 : for (uint64_t i = r.begin; i < r.end;) {
43 1067 : auto it = std::upper_bound(_ranges.begin(), _ranges.end(), i,
44 5734 : [](uint64_t const x, Range const &r) { return x < r.src.end; });
45 1067 : if (it == _ranges.end()) {
46 0 : out++ = ValueRange(i, r.end);
47 0 : break;
48 1067 : } else if (i >= it->src.begin) {
49 1021 : if (r.end <= it->src.end) {
50 645 : out++ = ValueRange(i + it->offset, r.end + it->offset);
51 645 : break;
52 645 : } else {
53 376 : out++ = ValueRange(i + it->offset, it->src.end + it->offset);
54 376 : i = it->src.end;
55 376 : }
56 1021 : } else {
57 46 : out++ = ValueRange(i, it->src.begin);
58 46 : i = it->src.begin;
59 46 : }
60 1067 : }
61 681 : }
62 :
63 : private:
64 : struct Range {
65 464 : Range(std::string_view const s) {
66 464 : static RE2 const rangePattern = R"((\d+) (\d+) (\d+))";
67 464 : uint64_t dstStart = 0;
68 464 : uint64_t size = 0;
69 464 : ASSUME(RE2::FullMatch(s, rangePattern, &dstStart, &src.begin, &size));
70 464 : src.end = src.begin + size;
71 464 : offset = integerCast<int64_t>(dstStart) - integerCast<int64_t>(src.begin);
72 464 : }
73 :
74 : ValueRange src;
75 : int64_t offset = 0;
76 : };
77 :
78 : std::string _srcCategory;
79 : std::string _dstCategory;
80 : std::vector<Range> _ranges;
81 : };
82 :
83 1 : std::vector<uint64_t> parseSeeds(std::string_view s) {
84 1 : ASSUME(RE2::Consume(&s, "seeds: "));
85 1 : s.remove_prefix(s.find(':') + 1u);
86 1 : return parseRange<uint64_t>(s);
87 1 : }
88 :
89 1 : std::vector<ValueRange> parseSeedRanges(std::string_view s) {
90 1 : static RE2 const numberPattern = R"((\d+) (\d+) ?)";
91 :
92 1 : ASSUME(RE2::Consume(&s, "seeds: "));
93 1 : std::vector<ValueRange> seeds;
94 1 : ValueRange seedRange;
95 1 : uint64_t size = 0;
96 11 : while (RE2::Consume(&s, numberPattern, &seedRange.begin, &size)) {
97 10 : seedRange.end = seedRange.begin + size;
98 10 : seeds.push_back(seedRange);
99 10 : }
100 1 : return seeds;
101 1 : }
102 :
103 2 : std::vector<Map> parseMaps(auto begin, auto end) {
104 2 : std::vector<Map> maps;
105 :
106 30 : for (auto it = begin; it != end;) {
107 28 : if (it->empty()) {
108 14 : ++it;
109 14 : continue;
110 14 : }
111 14 : auto rangeBegin = it;
112 476 : it = std::find_if(std::next(it), end, [](std::string_view s) { return s.empty(); });
113 14 : maps.emplace_back(rangeBegin, it);
114 14 : }
115 :
116 2 : return maps;
117 2 : }
118 : } // namespace
119 :
120 1 : template <> std::string solvePart1<2023, 5>(std::string_view const input) {
121 1 : LinewiseInput const lines(input);
122 :
123 1 : auto it = lines.begin();
124 1 : std::vector<uint64_t> seeds = parseSeeds(*it++);
125 1 : std::vector<Map> maps = parseMaps(it, lines.end());
126 :
127 1 : std::vector<ValueRange> tmp;
128 7 : for (auto const &map : maps) {
129 7 : std::ranges::transform(seeds, seeds.begin(), map);
130 7 : }
131 :
132 1 : return std::to_string(*std::ranges::min_element(seeds));
133 1 : }
134 :
135 1 : template <> std::string solvePart2<2023, 5>(std::string_view const input) {
136 1 : LinewiseInput const lines(input);
137 :
138 1 : auto it = lines.begin();
139 1 : std::vector<ValueRange> seedRanges = parseSeedRanges(*it++);
140 1 : std::vector<Map> maps = parseMaps(it, lines.end());
141 :
142 1 : std::vector<ValueRange> tmp;
143 7 : for (auto const &map : maps) {
144 7 : tmp.reserve(seedRanges.size() * 2u);
145 681 : for (auto const &seedRange : seedRanges) {
146 681 : map(seedRange, std::back_inserter(tmp));
147 681 : }
148 7 : seedRanges.swap(tmp);
149 7 : tmp.clear();
150 7 : }
151 :
152 1 : auto minIt = std::ranges::min_element(seedRanges, std::ranges::less{}, &ValueRange::begin);
153 :
154 1 : return std::to_string(minIt->begin);
155 1 : }
|
