1 files changed, 82 insertions, 1 deletions
diff --git a/src/2016/day20/aoc.cpp b/src/2016/day20/aoc.cpp
index 2a438aa..16e3e0a 100644
--- a/src/2016/day20/aoc.cpp
+++ b/src/2016/day20/aoc.cpp
@@ -1,6 +1,87 @@
 #include "aoc.h"
+#include <algorithm>
 
 namespace aoc2016 {
 
-std::pair<int64_t, int64_t> day20(line_view) { return {0, 0}; }
+static void get_number(const char** pp, uint32_t* d) {
+  const char* p = *pp;
+  while (*p >= '0' && *p <= '9') {
+    *d = *d * 10 + *p - '0';
+    p++;
+  }
+  *pp = p;
+}
+
+struct ipdigit {
+  uint32_t ds[2] = {0};
+
+  void print() const noexcept { printf("%u-%u\n", ds[0], ds[1]); }
+  ipdigit(line_view lv) {
+    const char* p = lv.line;
+    int i{0};
+    while (p < lv.line + lv.length) {
+      if (*p >= '0' && *p <= '9') {
+        get_number(&p, ds + i);
+        i++;
+      }
+      p++;
+    }
+  }
+
+  friend bool operator<(ipdigit ip1, ipdigit ip2) {
+    return ip1.ds[0] < ip2.ds[0] ? true : ip1.ds[0] > ip2.ds[0] ? false : ip1.ds[1] < ip2.ds[1];
+  }
+};
+
+static bool merge(ipdigit& ip, const ipdigit& ipx) {
+  if (ip.ds[1] >= ipx.ds[1]) {
+    return true;
+  }
+  if (ip.ds[1] < ipx.ds[1] && ip.ds[1] + 1 >= ipx.ds[0]) {
+    ip.ds[1] = ipx.ds[1];
+    return true;
+  }
+  return false;
+}
+
+static std::vector<ipdigit> merge(const std::vector<ipdigit>& ips) {
+  std::vector<ipdigit> ds;
+  ipdigit ip = ips[0];
+  for (size_t i = 1; i < ips.size(); i++) {
+    if (!merge(ip, ips[i])) {
+      ds.push_back(ip);
+      ip = ips[i];
+    }
+  }
+  ds.push_back(ip);
+  return ds;
+}
+
+static size_t count(std::vector<ipdigit>& ips) {
+  size_t c{0};
+  for (size_t i = 1; i < ips.size(); i++) {
+    c += ips[i].ds[0] - ips[i - 1].ds[1] - 1;
+  }
+  uint32_t max{UINT32_MAX};
+  auto& last = ips[ips.size() - 1];
+  c += max - last.ds[1];
+  return c;
+}
+
+std::pair<int64_t, int64_t> day20(line_view file) {
+  std::vector<ipdigit> ips;
+  per_line(file, [&ips](line_view lv) {
+    ips.emplace_back(lv);
+    return true;
+  });
+
+  std::sort(ips.begin(), ips.end());
+  auto ds = merge(ips);
+  // printf("%zu\n", count(ds));
+  // for (auto ip : ds) {
+  //   ip.print();
+  // }
+
+  return {0, count(ds)};
+}
 } // namespace aoc2016