2022 day7

1 files changed, 100 insertions, 1 deletions

diff --git a/src/2022/day7/aoc.cpp b/src/2022/day7/aoc.cpp
index 857e87b..940d9be 100644
--- a/src/2022/day7/aoc.cpp
+++ b/src/2022/day7/aoc.cpp
@@ -1,9 +1,108 @@
 #include "aoc.h"
+#include <iostream>
+#include <algorithm>
 
 namespace aoc2022 {
+static dir root{"/"};
+
+// ls
+void load(dir* d, line_view lv) {
+  per_line(lv, [&d](line_view l) {
+      dir* n = new dir(l);
+      n->parent = d;
+      d->dirs.push_back(n);
+      return true;
+  });
+}
+
+// cd /
+void get_root(dir** current) {
+  *current = &root;
+}
+
+// cd ..
+void get_parent(dir** current) {
+  dir* parent = (*current)->parent;
+  *current = parent;
+}
+
+// cd xxxx
+void get_dir(dir** current, line_view n) {
+  dir* d = *current; 
+  for(auto& s : d->dirs) {
+    if (s->name == n) {
+      *current = s;
+      break;
+    }
+  }
+}
+
+struct dst {
+  dir* d;
+  int s;
+};
+
+void get_size(dir* d, std::vector<dir*> & dirs, std::vector<dst>& ds, int target) {
+  int s = d->get_size();
+  if (d->size == 0) {
+    ds.push_back({d, s});
+  }
+  if (s <= target && d->size == 0) {
+    // std::cout << d->name << " size is " << s << std::endl;
+    dirs.push_back(d);
+  }
+  for (auto& x: d->dirs) {
+    get_size(x, dirs, ds, target);
+  }
+}
 
 std::pair<int,int> day7(line_view file) {
-  return {0, 0};
+  dir* current = nullptr;
+  const char* p = file.line;
+  while(p < file.line + file.length) {
+    if (p[0] == '$') {
+      if (p[2] == 'c' && p[3] == 'd') {
+        if (p[5] == '/') get_root(&current);
+        else if (p[5] == '.') get_parent(&current);
+        else {
+          const char *p0 = p + 5;
+          while(*p0 != '\n') p0++;
+          get_dir(&current, line_view{p + 5, p0});
+        }
+        while(*p != '\n') p++;
+      } 
+      if (p[2] == 'l' && p[3] == 's') {
+        const char* p0 = p + 5;
+        while (*p0 != '$') p0++;
+        load(current, line_view{p + 5, p0});
+        p = p0 - 1;
+      }
+    }
+    p++;
+  }
+
+  int rootsize = root.get_size();
+  // printf("root size is %d\n", rootsize);
+  std::vector<dir*> dirs;
+  std::vector<dst> ds;
+  get_size(&root, dirs, ds, 100000);
+  int total{0};
+  for(auto& d : dirs) {
+     total += d->get_size();
+  }
+  std::sort(ds.begin(), ds.end(), [](const dst&d1, const dst&d2) {
+      return d1.s < d2.s;
+  });
+  int smallest{0};
+  for (auto& d: ds) {
+    int x = 70000000 - rootsize + d.s;
+    // std::cout << d.d->name << ": " << d.s << " avail: " << x << std::endl;
+    if ( x >= 30000000) {
+      smallest = d.s;
+      break;
+    }
+  }
+  return {total, smallest};
 }
 
 }