1 files changed, 42 insertions, 30 deletions

diff --git a/src/2022/day25/aoc.cpp b/src/2022/day25/aoc.cpp
index a8b495c..858f5a1 100644
--- a/src/2022/day25/aoc.cpp
+++ b/src/2022/day25/aoc.cpp
@@ -1,4 +1,5 @@
 #include "aoc.h"
+#include <map>
 
 namespace aoc2022 {
 
@@ -49,28 +50,35 @@ int64_t base10(snafu s) {
 }
 
 struct snafu_digit {
-  int64_t l1;
-  int64_t l2;
-  int64_t m;
-  int64_t h1;
-  int64_t h2;
+  int64_t l;
+  int64_t m1;
+  int64_t d1;
+  int64_t d2;
+  int64_t m2;
+  int64_t h;
 };
 
 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;
+  static std::map<size_t, snafu_digit> cache;
+  auto p = cache.insert({n, {}});
+  if (p.second) {
+    int64_t m1 = pow5(n);
+    int64_t m2 = 2 * m1;
+    int64_t d1 = (m1 + m2) / 2;
+    int64_t d2 = d1 + 1;
 
-  for (size_t i = n; i > 0; i--) {
-    l1 -= 2 * pow5(n - 1);
-  }
+    int64_t l = m1;
+    for (size_t i = n; i > 0; i--) {
+      l -= 2 * (i > 1 ? pow5(i - 1) : 1);
+    }
 
-  for (size_t i = n; i > 0; i--) {
-    h2 += 2 * pow5(n - 1);
+    int64_t h = m2;
+    for (size_t i = n; i > 0; i--) {
+      h += 2 * (i > 1 ? pow5(i - 1) : 1);
+    }
+    p.first->second = {l, m1, d1, d2, m2, h};
   }
-  return {l1, l2, m, h1, h2};
+  return p.first->second;
 }
 
 void decode(int64_t x, size_t n, std::vector<int>& is) {
@@ -79,12 +87,18 @@ void decode(int64_t x, size_t n, std::vector<int>& is) {
   } else {
     int64_t sign = x == 0 ? 0 : x > 0 ? 1 : -1;
     auto r = range(n);
-    if (std::abs(x) < r.h1) {
+    auto ax = std::abs(x);
+    if (ax < r.l) {
+      is.push_back(0);
+      decode(x, n - 1, is);
+    }
+    if (ax >= r.l && ax < r.d2) {
       is.push_back(sign * 1);
-      decode(x - sign * r.m, n - 1, is);
-    } else {
+      decode(x - sign * r.m1, n - 1, is);
+    }
+    if (ax >= r.d2) {
       is.push_back(sign * 2);
-      decode(x - sign * r.m * 2, n - 1, is);
+      decode(x - sign * r.m2, n - 1, is);
     }
   }
 }
@@ -93,7 +107,7 @@ std::string baseSNAFU(int64_t x) {
   size_t n{0};
   while (true) {
     auto p = range(n);
-    if (x >= p.l1 && x <= p.h2) {
+    if (x >= p.l && x <= p.h) {
       break;
     }
     n++;
@@ -116,16 +130,14 @@ std::pair<int64_t, int64_t> day25(line_view file) {
     return true;
   });
 
-  int64_t x{0};
-  for (auto& s : ss) {
-    // s.print();
-    // printf(" %ld\n", base10(s));
-    x += base10(s);
-  }
+  // 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());
-  }
+  // printf("%ld %s\n", x, baseSNAFU(x).c_str());
 
   return {0, 0};
 }