2022 day25 part1

2 files changed, 145 insertions, 4 deletions

diff --git a/src/2022/day25/aoc.cpp b/src/2022/day25/aoc.cpp
index 2cc6057..a8b495c 100644
--- a/src/2022/day25/aoc.cpp
+++ b/src/2022/day25/aoc.cpp
@@ -2,8 +2,131 @@
 
 namespace aoc2022 {
 
-std::pair<int, int> day25(line_view) {
-  return {0, 0};
+static int64_t pow(size_t n) {
+  int64_t x{1};
+  for (size_t i = 0; i < n; i++) {
+    x *= 5;
+  }
+  return n == 0 ? 0 : x;
+}
+
+int64_t pow5(size_t n) {
+  static std::vector<int64_t> ns;
+  if (n >= ns.size()) {
+    auto s = ns.size();
+    ns.resize(n + 1);
+    for (size_t i = s; i < ns.size(); i++) {
+      ns[i] = pow(i);
+    }
+  }
+  return ns[n];
+}
+
+int64_t base10(snafu s) {
+  int64_t x{0};
+  for (size_t i = 0; i < s.length; i++) {
+    switch (*(s.digits + i)) {
+    case '=':
+      x = x * 5 - 2;
+      break;
+    case '-':
+      x = x * 5 - 1;
+      break;
+    case '0':
+      x = x * 5;
+      break;
+    case '1':
+      x = x * 5 + 1;
+      break;
+    case '2':
+      x = x * 5 + 2;
+      break;
+    default:
+      break;
+    }
+  }
+  return x;
 }
+
+struct snafu_digit {
+  int64_t l1;
+  int64_t l2;
+  int64_t m;
+  int64_t h1;
+  int64_t h2;
+};
+
+snafu_digit range(size_t n) {
+  int64_t m = pow5(n);
+  int64_t l1 = m;
+  int64_t h2 = 2 * m;
+  int64_t l2 = (l1 + h2) / 2;
+  int64_t h1 = l2 + 1;
+
+  for (size_t i = n; i > 0; i--) {
+    l1 -= 2 * pow5(n - 1);
+  }
+
+  for (size_t i = n; i > 0; i--) {
+    h2 += 2 * pow5(n - 1);
+  }
+  return {l1, l2, m, h1, h2};
 }
 
+void decode(int64_t x, size_t n, std::vector<int>& is) {
+  if (n == 0) {
+    is.push_back(x);
+  } else {
+    int64_t sign = x == 0 ? 0 : x > 0 ? 1 : -1;
+    auto r = range(n);
+    if (std::abs(x) < r.h1) {
+      is.push_back(sign * 1);
+      decode(x - sign * r.m, n - 1, is);
+    } else {
+      is.push_back(sign * 2);
+      decode(x - sign * r.m * 2, n - 1, is);
+    }
+  }
+}
+
+std::string baseSNAFU(int64_t x) {
+  size_t n{0};
+  while (true) {
+    auto p = range(n);
+    if (x >= p.l1 && x <= p.h2) {
+      break;
+    }
+    n++;
+  }
+
+  std::vector<int> is;
+  decode(x, n, is);
+  std::string s;
+  char encodings[] = {'0', '1', '2', '=', '-'};
+  for (auto& i : is) {
+    s.push_back(i >= 0 ? encodings[i] : encodings[i + 5]);
+  }
+  return s;
+}
+
+std::pair<int64_t, int64_t> day25(line_view file) {
+  std::vector<snafu> ss;
+  per_line(file, [&ss](line_view lv) {
+    ss.emplace_back(lv);
+    return true;
+  });
+
+  int64_t x{0};
+  for (auto& s : ss) {
+    // s.print();
+    // printf(" %ld\n", base10(s));
+    x += base10(s);
+  }
+
+  for (uint64_t i = 1; i <= 63; i++) {
+    printf("%ld %ld %s\n", x, i, baseSNAFU(i).c_str());
+  }
+
+  return {0, 0};
+}
+} // namespace aoc2022
diff --git a/src/2022/day25/aoc.h b/src/2022/day25/aoc.h
index ab55efd..e24291a 100644
--- a/src/2022/day25/aoc.h
+++ b/src/2022/day25/aoc.h
@@ -1,7 +1,25 @@
 #include "common.h"
+#include "stdint.h"
 #include <vector>
 
 namespace aoc2022 {
 
-std::pair<int, int> day25(line_view);
-}
+struct snafu {
+  char* digits = nullptr;
+  size_t length = 0;
+
+  void print() const noexcept {
+    for (size_t i = 0; i < length; i++) {
+      printf("%c", *(digits + i));
+    }
+  }
+
+  snafu(line_view lv) {
+    length = lv.length - 1;
+    digits = (char*)malloc(length);
+    memcpy(digits, lv.line, length);
+  }
+};
+
+std::pair<int64_t, int64_t> day25(line_view);
+} // namespace aoc2022