2016 day19

1 files changed, 44 insertions, 3 deletions

diff --git a/src/2016/day19/aoc.cpp b/src/2016/day19/aoc.cpp
index a4b9d32..8d08886 100644
--- a/src/2016/day19/aoc.cpp
+++ b/src/2016/day19/aoc.cpp
@@ -23,6 +23,27 @@ elf* del_elf(elf* e1) {
   return e;
 }
 
+elf* cross(elf* e, int n) {
+  n = n / 2 - 1;
+  while (n > 0) {
+    e = e->next;
+    n--;
+  }
+  return e;
+}
+
+elf* del_elf(elf* e1, size_t n) {
+  elf* e = e1;
+  while (e->next != e) {
+    elf* ex = cross(e, n);
+    elf* en = ex->next->next;
+    ex->next = en;
+    e = e->next;
+    n -= 1;
+  }
+  return e;
+}
+
 elf* make_elf(int n) {
   elf* e1 = new elf;
   e1->i = 1;
@@ -53,13 +74,33 @@ size_t last_elf(size_t n) {
   return a;
 }
 
+size_t final_elf(size_t n) {
+  if (n == 1) return 1;
+  size_t x{0};
+  size_t i{1};
+  while (x + 1 < n) {
+    x += i + i;
+    i *= 3;
+  }
+
+  x -= (i / 3) * 2;
+  x += 1;
+  size_t m = x + i / 3;
+  size_t a{1};
+  while (x != n) {
+    a += x < m ? 1 : 2;
+    x += 1;
+  }
+  return a - 1;
+}
+
 std::pair<int64_t, int64_t> day19(line_view) {
   // for (int i = 1; i < 100; i++) {
   //   elf* e = make_elf(i);
-  //   elf* x = del_elf(e);
-  //   printf("%d\n", x->i);
+  //   elf* x = del_elf(e, i);
+  //   printf("%d: %d %zu\n", i, x->i, final_elf(i));
   // }
-  return {last_elf(3005290), 0};
+  return {last_elf(3005290), final_elf(3005290)};
 }
 
 } // namespace aoc2016