days 19-25, aoc 2016

1 files changed, 128 insertions, 0 deletions

diff --git a/2016/src/day20.cpp b/2016/src/day20.cpp
new file mode 100644
index 0000000..49a9ec1
--- /dev/null
+++ b/2016/src/day20.cpp
@@ -0,0 +1,128 @@
+#include <algorithm>
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+struct Range {
+        long long start;
+        long long end;
+};
+
+vector<Range>
+readFile(const filesystem::path& filename)
+{
+        ifstream      file{ filename };
+        vector<Range> ranges;
+
+        for ( string line; getline(file, line); ) {
+                stringstream stream{ line };
+                char         dash{};
+                long long    start{};
+                long long    end{};
+
+                stream >> start >> dash >> end;
+
+                ranges.emplace_back(start, end);
+        }
+
+        return ranges;
+}
+
+void
+sortRanges(vector<Range>& ranges)
+{
+        ranges::sort(ranges, [](const auto& lhs, const auto& rhs) {
+                if ( lhs.start != rhs.start ) {
+                        return lhs.start < rhs.start;
+                }
+                return lhs.end < rhs.end;
+        });
+}
+
+void
+mergeRanges(vector<Range>& ranges)
+{
+        if ( ranges.empty() ) {
+                return;
+        }
+
+        vector<Range> mergedRanges;
+
+        auto current = ranges[0];
+        for ( size_t i = 1; i != ranges.size(); ++i ) {
+                if ( ranges[i].start <= current.end + 1 ) {
+                        current.end = max(current.end, ranges[i].end);
+                }
+                else {
+                        mergedRanges.emplace_back(current);
+                        current = ranges[i];
+                }
+        }
+        mergedRanges.emplace_back(current);
+
+        ranges.swap(mergedRanges);
+}
+
+long long
+findLowestAllowedIP(const vector<Range>& ranges)
+{
+        if ( ranges.empty() || ranges[0].start > 0 ) {
+                return 0;
+        }
+        return ranges[0].end + 1;
+}
+
+long long
+countAllowedIPs(const vector<Range>& ranges, long long max_ip)
+{
+        long long allowed_count = 0;
+
+        for ( size_t i = 0; i < ranges.size() - 1; ++i ) {
+                allowed_count += ranges[i + 1].start - ranges[i].end - 1;
+        }
+
+        if ( !ranges.empty() && ranges.back().end < max_ip ) {
+                allowed_count += max_ip - ranges.back().end;
+        }
+
+        if ( ranges.empty() ) {
+                allowed_count = max_ip + 1;
+        }
+
+        return allowed_count;
+}
+
+void
+part1(vector<Range> ranges)
+{
+        sortRanges(ranges);
+        mergeRanges(ranges);
+
+        cout << findLowestAllowedIP(ranges) << '\n';
+}
+
+void
+part2(vector<Range> ranges, long long max_ip = 4294967295)
+{
+        sortRanges(ranges);
+        mergeRanges(ranges);
+
+        cout << countAllowedIPs(ranges, max_ip) << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto ranges = readFile("data/day20.txt");
+        part1(ranges);
+        part2(ranges);
+}