From 4ebc66911da17b6f5abdc7629dff3eccd7f37ce2 Mon Sep 17 00:00:00 2001
From: Christian Segundo
Date: Wed, 7 Dec 2022 16:37:04 +0100
Subject: add day 7

---
 day_07.zig | 129 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 129 insertions(+)
 create mode 100644 day_07.zig

(limited to 'day_07.zig')

diff --git a/day_07.zig b/day_07.zig
new file mode 100644
index 0000000..01c71a2
--- /dev/null
+++ b/day_07.zig
@@ -0,0 +1,129 @@
+const std = @import("std");
+const Result = @import("util/aoc.zig").Result;
+
+const NodeType = union(enum) { File, Dir };
+const Node = struct {
+    Name: []const u8,
+    Childs: struct {
+        len: usize = 0,
+        items: [300]?*Node = [_]?*Node{null} ** 300,
+    } = .{},
+    Parent: ?*Node = null,
+    Type: NodeType,
+    Size: usize = 0,
+
+    pub fn append(self: *Node, node: *Node) void {
+        self.Childs.items[self.Childs.len] = node;
+        self.Childs.len += 1;
+    }
+
+    fn cd(self: *Node, to: []const u8) *Node {
+        if (to.len == 1 and to[0] == '/') {
+            if (self.Parent == null) return self;
+            return self.Parent.?.cd("/");
+        }
+
+        if (std.mem.eql(u8, "..", to)) {
+            return self.Parent.?;
+        }
+
+        for (self.Childs.items[0..self.Childs.len]) |child| {
+            if (std.mem.eql(u8, child.?.Name, to)) return child.?;
+        }
+
+        unreachable;
+    }
+
+    fn size(self: Node) usize {
+        if (self.Type == .File) return self.Size;
+        var s: usize = 0;
+        for (self.Childs.items[0..self.Childs.len]) |child| s += child.?.size();
+        return s;
+    }
+};
+
+fn compute_puzzle_1(node: Node) usize {
+    var size: usize = 0;
+    for (node.Childs.items[0..node.Childs.len]) |child| {
+        if (child.?.Type != NodeType.Dir) continue;
+        if (child.?.size() <= 100000) size += child.?.size();
+        size += compute_puzzle_1(child.?.*);
+    }
+    return size;
+}
+
+fn compute_puzzle_2(node: Node, min: usize, target: usize) usize {
+    var new_min = min;
+    for (node.Childs.items[0..node.Childs.len]) |child| {
+        if (child.?.Type != NodeType.Dir) continue;
+        const child_size = child.?.size();
+        if (child_size < new_min and child_size >= target) new_min = child_size;
+        new_min = compute_puzzle_2(child.?.*, new_min, target);
+    }
+    return new_min;
+}
+
+fn build_tree(allocator: std.mem.Allocator, root: *Node, input: []const u8) !void {
+    var iter = std.mem.split(u8, input, "\n");
+
+    var current_root = &root;
+
+    while (iter.next()) |line| {
+        if (line[0] == '$') {
+            if (std.mem.eql(u8, line[2..4], "cd")) current_root = &current_root.*.cd(line[5..]);
+            continue;
+        }
+
+        var node = try allocator.create(Node);
+        node.* = .{
+            .Name = line[std.mem.indexOf(u8, line, " ").? + 1 ..],
+            .Parent = current_root.*,
+            .Type = blk: {
+                if (std.mem.eql(u8, line[0..3], "dir")) break :blk NodeType.Dir;
+                break :blk NodeType.File;
+            },
+            .Size = blk: {
+                break :blk std.fmt.parseInt(
+                    usize,
+                    line[0..std.mem.indexOf(u8, line, " ").?],
+                    0,
+                ) catch 0;
+            },
+        };
+        current_root.*.append(node);
+    }
+}
+
+pub fn puzzle_1(allocator: std.mem.Allocator, input: []const u8) Result {
+    var arena = std.heap.ArenaAllocator.init(allocator);
+    defer arena.deinit();
+
+    var node = Node{
+        .Name = "/",
+        .Type = .Dir,
+    };
+
+    build_tree(arena.allocator(), &node, input) catch unreachable;
+
+    return .{ .int = @intCast(i32, compute_puzzle_1(node)) };
+}
+
+pub fn puzzle_2(allocator: std.mem.Allocator, input: []const u8) Result {
+    var arena = std.heap.ArenaAllocator.init(allocator);
+    defer arena.deinit();
+
+    var node = Node{
+        .Name = "/",
+        .Type = .Dir,
+    };
+
+    build_tree(arena.allocator(), &node, input) catch unreachable;
+
+    const target: usize = 30000000 - (70000000 - node.size());
+
+    return .{ .int = @intCast(i32, compute_puzzle_2(
+        node,
+        node.size(),
+        target,
+    )) };
+}
-- 
cgit v1.2.3