2018 day8 part1

3 files changed, 69 insertions, 0 deletions

diff --git a/src/2018/day8/README.md b/src/2018/day8/README.md
index f486d0f..1a5e6f6 100644
--- a/src/2018/day8/README.md
+++ b/src/2018/day8/README.md
@@ -34,4 +34,19 @@ The first check done on the license file is to simply add up all of the metadata
 
 What is the sum of all metadata entries?
 
+--- Part Two ---
+The second check is slightly more complicated: you need to find the value of the root node (A in the example above).
 
+The value of a node depends on whether it has child nodes.
+
+If a node has no child nodes, its value is the sum of its metadata entries. So, the value of node B is 10+11+12=33, and the value of node D is 99.
+
+However, if a node does have child nodes, the metadata entries become indexes which refer to those child nodes. A metadata entry of 1 refers to the first child node, 2 to the second, 3 to the third, and so on. The value of this node is the sum of the values of the child nodes referenced by the metadata entries. If a referenced child node does not exist, that reference is skipped. A child node can be referenced multiple time and counts each time it is referenced. A metadata entry of 0 does not refer to any child node.
+
+For example, again using the above nodes:
+
+Node C has one metadata entry, 2. Because node C has only one child node, 2 references a child node which does not exist, and so the value of node C is 0.
+Node A has three metadata entries: 1, 1, and 2. The 1 references node A's first child node, B, and the 2 references node A's second child node, C. Because node B has a value of 33 and node C has a value of 0, the value of node A is 33+33+0=66.
+So, in this example, the value of the root node is 66.
+
+What is the value of the root node?
diff --git a/src/2018/day8/aoc.cpp b/src/2018/day8/aoc.cpp
index 585f144..2f7729f 100644
--- a/src/2018/day8/aoc.cpp
+++ b/src/2018/day8/aoc.cpp
@@ -1,5 +1,58 @@
 #include "aoc.h"
+#include <stack>
+#include <vector>
 
 namespace aoc2018 {
 
+static void get_number(const char** pp, int* d) {
+  const char* p = *pp;
+  *d = 0;
+  while (*p >= '0' && *p <= '9') {
+    *d = *d * 10 + *p - '0';
+    p++;
+  }
+  *pp = p;
 }
+
+struct header {
+  int nodes;
+  int metas;
+};
+
+int day8(line_view file) {
+  std::vector<int> is;
+  const char* p1 = file.line;
+  const char* p2 = file.line + file.length;
+  while (p1 < p2) {
+    if (*p1 >= '0' && *p1 <= '9') {
+      int d{0};
+      get_number(&p1, &d);
+      is.push_back(d);
+    }
+    p1++;
+  }
+
+  std::stack<header> hs;
+  size_t index{0};
+  int total{0};
+  hs.push({is[index], is[index + 1]});
+  index += 2;
+  while (!hs.empty()) {
+    auto& h = hs.top();
+    if (h.nodes > 0) {
+      hs.push({is[index], is[index + 1]});
+      index += 2;
+      h.nodes -= 1;
+    } else {
+      while (h.metas > 0) {
+        total += is[index];
+        index += 1;
+        h.metas -= 1;
+      }
+      hs.pop();
+    }
+  }
+  return total;
+}
+
+} // namespace aoc2018
diff --git a/src/2018/day8/aoc.h b/src/2018/day8/aoc.h
index 4bfdbf3..22b2d3e 100644
--- a/src/2018/day8/aoc.h
+++ b/src/2018/day8/aoc.h
@@ -3,4 +3,5 @@
 
 namespace aoc2018 {
 
+int day8(line_view);
 }