day19 parse y

2 files changed, 112 insertions, 29 deletions

diff --git a/src/2015/day19/aoc.cpp b/src/2015/day19/aoc.cpp
index af42b23..019a120 100644
--- a/src/2015/day19/aoc.cpp
+++ b/src/2015/day19/aoc.cpp
@@ -13,10 +13,35 @@ std::pair<int, int> day19(line_view file) {
   // int shortest = INT32_MAX;
   // m.deduct(m.original, 0, &shortest);
   // m.transfer("e", 0, &shortest);
-  std::vector<molecule::pattern> ps;
-  const char* x = nullptr;
-  m.parse_pattern(m.original, 0, ps, &x);
-  std::for_each(ps.begin(), ps.end(), [](molecule::pattern p) { std::cout << p.depth << " -> " << p.lv << std::endl; });
+  int steps = 0;
+
+  line_view lv = m.original;
+
+  do {
+    lv = m.replace(lv, &steps);
+    printf("%d\n", steps);
+
+    std::vector<molecule::pattern> ps;
+    const char* x = nullptr;
+    m.parse_pattern(lv, 0, ps, &x);
+    std::for_each(ps.begin(), ps.end(),
+                  [](molecule::pattern p) { std::cout << p.depth << " -> " << p.lv << std::endl; });
+    if (ps[0].lv.contains("Y")) {
+      std::vector<line_view> ys;
+      m.parse_y(ps[0].lv, ys);
+      for (auto y : ys) {
+        if (m.transfers.find(y) == m.transfers.end()) {
+          line_view to = m.deduce(y, &steps);
+          lv = m.replace(lv, {y, to}, y.line);
+          break;
+        }
+      }
+    } else {
+      line_view to = m.deduce(ps[0].lv, &steps);
+      lv = m.replace(lv, {ps[0].lv, to}, ps[0].lv.line);
+    }
+  } while (true);
+
   return {m.distinct(changes), 0};
 }
 
diff --git a/src/2015/day19/aoc.h b/src/2015/day19/aoc.h
index 1fd4624..af2c720 100644
--- a/src/2015/day19/aoc.h
+++ b/src/2015/day19/aoc.h
@@ -17,6 +17,7 @@ struct replacement {
 struct molecule {
   std::vector<replacement> replacements;
   std::map<line_view, std::vector<line_view>> transfers;
+  std::map<line_view, line_view> backwards;
   line_view original;
 
   struct change {
@@ -29,6 +30,73 @@ struct molecule {
     line_view lv;
   };
 
+  // r.to -> r.from at p
+  line_view replace(line_view lv, const replacement& r, const char* p) const noexcept {
+    size_t len = lv.length + r.to.length - r.from.length;
+    char* s = (char*)malloc(len);
+    memset(s, 0x0, len);
+    const char* ps[] = {lv.line, p, p + r.from.length, lv.line + lv.length};
+    char* x = s;
+    for (size_t i = 0; i < 3; i++) {
+      if (i != 1) {
+        const char* p1 = ps[i];
+        const char* p2 = ps[i + 1];
+        // std::cout << line_view{p1, p2} << std::endl;
+        memcpy(x, p1, p2 - p1);
+        x += (p2 - p1);
+      } else {
+        const char* p1 = r.to.line;
+        const char* p2 = r.to.line + r.to.length;
+        // std::cout << line_view{p1, p2} << std::endl;
+        memcpy(x, p1, p2 - p1);
+        x += (p2 - p1);
+      }
+    }
+    return {s, len};
+  }
+
+  line_view deduce(line_view lv, int* step) {
+    if (transfers.find(lv) == transfers.end()) {
+      auto it = backwards.find(lv);
+      if (it != backwards.end()) {
+        *step += 1;
+        return it->second;
+      } else {
+        const char* p1 = lv.line;
+        const char* p2 = lv.line + lv.length;
+        const char* p = p1 + 1;
+        while (p < p2) {
+          auto jt = backwards.find({p1, p});
+          if (jt != backwards.end()) {
+            replacement r{{p1, p}, jt->second};
+            line_view n = replace(lv, r, p1);
+            *step += 1;
+            return deduce(n, step);
+          } else {
+            p++;
+          }
+        }
+      }
+    }
+    return lv;
+  }
+
+  void parse_y(line_view lv, std::vector<line_view>& ys) {
+    const char* p1 = lv.line;
+    const char* p2 = lv.line + lv.length;
+    while (p1 < p2) {
+      line_view x{p1, p2};
+      const char* p = x.contains("Y");
+      if (p != nullptr) {
+        ys.push_back({p1, p});
+        p1 = p + 1;
+      } else {
+        break;
+      }
+    }
+    ys.push_back({p1, p2});
+  }
+
   //...Rn..Ar
   void parse_pattern(line_view lv, int depth, std::vector<pattern>& ps, const char** a) {
     const char* p1 = lv.line;
@@ -41,6 +109,7 @@ struct molecule {
         continue;
       }
       if (*p == 'A' && *(p + 1) == 'r') {
+        // ps.push_back({depth, {p1 - 2, p + 2}});
         ps.push_back({depth, {p1, p}});
         *a = p;
         return;
@@ -118,31 +187,6 @@ struct molecule {
     return d;
   }
 
-  // r.to -> r.from at p
-  line_view replace(line_view lv, const replacement& r, const char* p) const noexcept {
-    size_t len = lv.length + r.to.length - r.from.length;
-    char* s = (char*)malloc(len);
-    memset(s, 0x0, len);
-    const char* ps[] = {lv.line, p, p + r.from.length, lv.line + lv.length};
-    char* x = s;
-    for (size_t i = 0; i < 3; i++) {
-      if (i != 1) {
-        const char* p1 = ps[i];
-        const char* p2 = ps[i + 1];
-        // std::cout << line_view{p1, p2} << std::endl;
-        memcpy(x, p1, p2 - p1);
-        x += (p2 - p1);
-      } else {
-        const char* p1 = r.to.line;
-        const char* p2 = r.to.line + r.to.length;
-        // std::cout << line_view{p1, p2} << std::endl;
-        memcpy(x, p1, p2 - p1);
-        x += (p2 - p1);
-      }
-    }
-    return {s, len};
-  }
-
   void step(int i) const noexcept {
     while (i-- > 0) {
       std::cout << "\t";
@@ -178,6 +222,19 @@ struct molecule {
     }
   }
 
+  line_view replace(line_view lv, int* steps) const noexcept {
+    for (auto kv : backwards) {
+      const char* r = kv.first.contains("Rn");
+      const char* p = lv.contains(kv.first);
+      if (r != nullptr && p != nullptr) {
+        *steps += 1;
+        line_view ln = replace(lv, {kv.first, kv.second}, p);
+        return replace(ln, steps);
+      }
+    }
+    return lv;
+  }
+
   void parse(line_view lv, std::vector<line_view>& ms) const noexcept {
     const char* p1 = lv.line;
     const char* p2 = lv.line + lv.length;
@@ -232,6 +289,7 @@ struct molecule {
       line_view v{p + 3, lv.line + lv.length - 1};
       replacements.push_back({k, v});
       transfers[k].push_back(v);
+      backwards.insert({v, k});
     } else {
       if (lv.length > 1) {
         original = {lv.line, lv.line + lv.length - 1};