summaryrefslogtreecommitdiff
path: root/2023/05/src/part2.cpp
diff options
context:
space:
mode:
Diffstat (limited to '2023/05/src/part2.cpp')
-rw-r--r--2023/05/src/part2.cpp142
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
11using SeedRange = std::tuple<int,long,long>;
12using Seeds = std::set<SeedRange>;
13
14using Map = std::tuple<long,long,long>;
15using Step = std::vector<Map>;
16using Almanac = std::vector<Step>;
17
18constexpr char SEEDS[] = "seeds:";
19
20std::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
64Seeds 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
109int 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}