aboutsummaryrefslogtreecommitdiff
path: root/src/day05.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/day05.cpp')
-rw-r--r--src/day05.cpp183
1 files changed, 0 insertions, 183 deletions
diff --git a/src/day05.cpp b/src/day05.cpp
deleted file mode 100644
index 42fda29..0000000
--- a/src/day05.cpp
+++ /dev/null
@@ -1,183 +0,0 @@
1#include <algorithm>
2#include <fstream>
3#include <iostream>
4#include <iterator>
5#include <limits>
6#include <map>
7#include <sstream>
8#include <string>
9#include <vector>
10using namespace std;
11
12struct Entry {
13 Entry(long destination, long source, long amount) // NOLINT
14 : destination_(destination)
15 , source_(source)
16 , amount_(amount)
17 {
18 }
19
20 [[nodiscard]] bool in_range(long value) const
21 {
22 return source_ <= value && value < (source_ + amount_);
23 }
24
25 [[nodiscard]] long get_destination(long value) const
26 {
27 auto delta = value - source_;
28 return destination_ + delta;
29 }
30
31 long destination_;
32 long source_;
33 long amount_;
34};
35
36vector<string>
37read_file(string_view filename)
38{
39 fstream input{ filename };
40 vector<string> data;
41
42 for ( string line; getline(input, line); ) {
43 data.emplace_back(line);
44 }
45
46 return data;
47}
48
49vector<string>
50split(const string& line, char sep)
51{
52 vector<string> parts;
53 stringstream input{ line };
54
55 for ( string part; getline(input, part, sep); ) {
56 parts.emplace_back(part);
57 }
58
59 return parts;
60}
61
62void
63part1(const vector<string>& lines)
64{
65 auto read_ints = [](const string& line) {
66 stringstream iss{ line };
67 return vector<long>{ istream_iterator<long>{ iss }, istream_iterator<long>{} };
68 };
69
70 auto seeds = read_ints(lines[0].substr(6));
71
72 map<string, string> category_mapping;
73 map<string, vector<Entry>> range_mapping;
74
75 // read blocks
76 for ( size_t idx = 1; idx < lines.size(); ) {
77 ++idx; // skip empty line
78
79 auto description = lines[idx++];
80 description.erase(description.find(' '));
81 auto parts = split(description, '-');
82
83 category_mapping[parts[0]] = parts[2];
84
85 vector<Entry> mapping;
86
87 for ( ; idx < lines.size() && !lines[idx].empty(); ++idx ) {
88 auto values = read_ints(lines[idx]);
89
90 auto destination = values[0];
91 auto source = values[1];
92 auto amount = values[2];
93
94 mapping.emplace_back(destination, source, amount);
95 }
96
97 range_mapping[parts[0]] = mapping;
98 }
99
100 auto min_value = numeric_limits<long>::max();
101 for ( auto seed: seeds ) {
102 for ( string category{ "seed" }; !category.empty(); category = category_mapping[category] ) {
103 const auto& ranges = range_mapping[category];
104
105 for (const auto& range: ranges) {
106 if (range.in_range(seed)) {
107 seed = range.get_destination(seed);
108 break;
109 }
110 }
111 }
112 min_value = min(min_value, seed);
113 }
114 cout << min_value << endl;
115}
116
117void
118part2(const vector<string>& lines)
119{
120 auto read_ints = [](const string& line) {
121 stringstream iss{ line };
122 return vector<long>{ istream_iterator<long>{ iss }, istream_iterator<long>{} };
123 };
124
125 auto seeds = read_ints(lines[0].substr(6));
126
127 map<string, string> category_mapping;
128 map<string, vector<Entry>> range_mapping;
129
130 // read blocks
131 for ( size_t idx = 1; idx < lines.size(); ) {
132 ++idx; // skip empty line
133
134 auto description = lines[idx++];
135 description.erase(description.find(' '));
136 auto parts = split(description, '-');
137
138 category_mapping[parts[0]] = parts[2];
139
140 vector<Entry> mapping;
141
142 for ( ; idx < lines.size() && !lines[idx].empty(); ++idx ) {
143 auto values = read_ints(lines[idx]);
144
145 auto destination = values[0];
146 auto source = values[1];
147 auto amount = values[2];
148
149 mapping.emplace_back(destination, source, amount);
150 }
151
152 range_mapping[parts[0]] = mapping;
153 }
154
155 // brute force -- slow, but works
156 auto min_value = numeric_limits<long>::max();
157 for ( size_t idx = 0; idx != seeds.size(); idx += 2 ) {
158 for ( auto start = seeds[idx]; start != seeds[idx] + seeds[idx+1]; ++start ) {
159 auto seed = start;
160
161 for ( string category{ "seed" }; !category.empty(); category = category_mapping[category] ) {
162 const auto& ranges = range_mapping[category];
163
164 for (const auto& range: ranges) {
165 if (range.in_range(seed)) {
166 seed = range.get_destination(seed);
167 break;
168 }
169 }
170 }
171 min_value = min(min_value, seed);
172 }
173 }
174 cout << min_value << endl;
175}
176
177int
178main()
179{
180 auto lines = read_file("data/day05.txt");
181 part1(lines);
182 part2(lines);
183}