diff options
Diffstat (limited to '2023/05/src/part2.cpp')
-rw-r--r-- | 2023/05/src/part2.cpp | 142 |
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 @@ | |||
1 | #include <algorithm> | ||
2 | #include <iostream> | ||
3 | #include <fstream> | ||
4 | #include <sstream> | ||
5 | #include <set> | ||
6 | #include <tuple> | ||
7 | #include <vector> | ||
8 | |||
9 | #include "util.h" | ||
10 | |||
11 | using SeedRange = std::tuple<int,long,long>; | ||
12 | using Seeds = std::set<SeedRange>; | ||
13 | |||
14 | using Map = std::tuple<long,long,long>; | ||
15 | using Step = std::vector<Map>; | ||
16 | using Almanac = std::vector<Step>; | ||
17 | |||
18 | constexpr char SEEDS[] = "seeds:"; | ||
19 | |||
20 | std::pair<Seeds,Almanac> parse_input() | ||
21 | { | ||
22 | Seeds seeds; | ||
23 | Almanac almanac; | ||
24 | |||
25 | std::ifstream input{ "resources/input.txt" }; | ||
26 | if (input.is_open()) | ||
27 | { | ||
28 | std::string line; | ||
29 | long from, to, size; | ||
30 | |||
31 | /* Seeds */ | ||
32 | std::getline(input,line); | ||
33 | std::istringstream sline{ line }; | ||
34 | sline >> util::skip<SEEDS>; | ||
35 | while (sline >> from >> size) | ||
36 | { | ||
37 | seeds.insert(std::make_tuple(0, from, from + size)); | ||
38 | } | ||
39 | |||
40 | /* Mappings */ | ||
41 | Step step; | ||
42 | while (not std::getline(input,line).eof()) | ||
43 | { | ||
44 | if (line.empty()) continue; | ||
45 | |||
46 | if (std::isdigit(line[0])) | ||
47 | { | ||
48 | std::istringstream{ line } >> to >> from >> size; | ||
49 | step.push_back(std::make_tuple(from, from + size, to - from)); | ||
50 | } | ||
51 | else if (not step.empty()) | ||
52 | { | ||
53 | almanac.push_back(std::move(step)); | ||
54 | step = {}; | ||
55 | } | ||
56 | } | ||
57 | almanac.push_back(std::move(step)); | ||
58 | } | ||
59 | input.close(); | ||
60 | |||
61 | return std::make_pair(std::move(seeds), std::move(almanac)); | ||
62 | } | ||
63 | |||
64 | Seeds map_to_range(int step, const SeedRange& seed_range, const Map& map) | ||
65 | { | ||
66 | int s; | ||
67 | long rbegin, rend; | ||
68 | long mbegin, mend, diff; | ||
69 | std::tie(s, rbegin, rend) = seed_range; | ||
70 | std::tie(mbegin, mend, diff) = map; | ||
71 | |||
72 | if (mbegin <= rbegin) | ||
73 | { | ||
74 | if (mend >= rend) | ||
75 | { | ||
76 | return { | ||
77 | std::make_tuple(step + 1, rbegin + diff, rend + diff) | ||
78 | }; | ||
79 | } | ||
80 | else if (mend > rbegin) | ||
81 | { | ||
82 | return { | ||
83 | std::make_tuple(step + 1, rbegin + diff, mend + diff), | ||
84 | std::make_tuple(step, mend, rend), | ||
85 | }; | ||
86 | } | ||
87 | } | ||
88 | else if (mbegin < rend) | ||
89 | { | ||
90 | if (mend >= rend) | ||
91 | { | ||
92 | return { | ||
93 | std::make_tuple(step, rbegin, mbegin), | ||
94 | std::make_tuple(step + 1, mbegin + diff, rend + diff), | ||
95 | }; | ||
96 | } | ||
97 | else | ||
98 | { | ||
99 | return { | ||
100 | std::make_tuple(step, rbegin, mbegin), | ||
101 | std::make_tuple(step + 1, mbegin + diff, mend + diff), | ||
102 | std::make_tuple(step, mend, rend), | ||
103 | }; | ||
104 | } | ||
105 | } | ||
106 | return { seed_range }; | ||
107 | } | ||
108 | |||
109 | int main(void) | ||
110 | { | ||
111 | Seeds seeds; | ||
112 | Almanac almanac; | ||
113 | std::tie(seeds, almanac) = parse_input(); | ||
114 | |||
115 | for (int s = 0; s < almanac.size(); ++s) | ||
116 | { | ||
117 | const auto& step = almanac[s]; | ||
118 | for (const auto& map : step) | ||
119 | { | ||
120 | std::set<SeedRange> new_seeds; | ||
121 | for(auto& seed : seeds) | ||
122 | { | ||
123 | if (std::get<0>(seed) <= s) | ||
124 | { | ||
125 | auto res = map_to_range(s, seed, map); | ||
126 | new_seeds.insert(res.begin(), res.end()); | ||
127 | } | ||
128 | else | ||
129 | { | ||
130 | new_seeds.insert(seed); | ||
131 | } | ||
132 | } | ||
133 | seeds = std::move(new_seeds); | ||
134 | } | ||
135 | } | ||
136 | |||
137 | auto min = std::min_element(seeds.cbegin(), seeds.cend(), | ||
138 | [](auto s1, auto s2) { return std::get<1>(s1) < std::get<1>(s2); }); | ||
139 | std::cout << std::get<1>(*min) << std::endl; | ||
140 | |||
141 | return 0; | ||
142 | } | ||