2022 day25 done

3 files changed, 58 insertions, 31 deletions

diff --git a/src/2022/day25/README.md b/src/2022/day25/README.md
index 98b4a33..94d4274 100644
--- a/src/2022/day25/README.md
+++ b/src/2022/day25/README.md
@@ -91,3 +91,18 @@ As you go to input this number on Bob's console, you discover that some buttons
 Reversing the process, you can determine that for the decimal number 4890, the SNAFU number you need to supply to Bob's console is 2=-1=0.
 
 The Elves are starting to get cold. What SNAFU number do you supply to Bob's console?
+
+--- Part Two ---
+The hot air balloons quickly carry you to the North Pole. As soon as you land, most of the expedition is escorted directly to a small building attached to the reindeer stables.
+
+The head smoothie chef has just finished warming up the industrial-grade smoothie blender as you arrive. It will take 50 stars to fill the blender. The expedition Elves turn their attention to you, and you begin emptying the fruit from your pack onto the table.
+
+As you do, a very young Elf - one you recognize from the expedition team - approaches the table and holds up a single star fruit he found. The head smoothie chef places it in the blender.
+
+Only 49 stars to go.
+
+If you like, you can .
+
+Both parts of this puzzle are complete! They provide two gold stars: **
+
+At this point, all that is left is for you to admire your Advent calendar.
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};
 }
diff --git a/test/test_2022.cpp b/test/test_2022.cpp
index feaa1f4..b8c8ab1 100644
--- a/test/test_2022.cpp
+++ b/test/test_2022.cpp
@@ -198,7 +198,7 @@ TEST_CASE("Unstable Diffusion", "[2022]") {
 // }
 
 TEST_CASE("Full of Hot Air", "[2022]") {
-  line_view lv = load_file("../src/2022/day25/input0");
+  line_view lv = load_file("../src/2022/day25/input");
   auto p = aoc2022::day25(lv);
   REQUIRE(0 == p.first);
   REQUIRE(0 == p.second);