From 81c6867fb0a0252508dbf4612da409a123d9a5cc Mon Sep 17 00:00:00 2001
From: Xander Bil <xander@biltopia.org>
Date: Tue, 10 Dec 2024 11:51:19 +0100
Subject: add solution day09

---
 main.zig      |   2 +
 src/day09.zig | 147 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 149 insertions(+)
 create mode 100644 src/day09.zig

diff --git a/main.zig b/main.zig
index 6f84de0..084ead1 100644
--- a/main.zig
+++ b/main.zig
@@ -9,6 +9,7 @@ const day05 = @import("src/day05.zig");
 const day06 = @import("src/day06.zig");
 const day07 = @import("src/day07.zig");
 const day08 = @import("src/day08.zig");
+const day09 = @import("src/day09.zig");
 
 pub fn main() !void {
     if (std.os.argv.len != 3) {
@@ -45,6 +46,7 @@ pub fn main() !void {
         6 => day06.solve(args[2], buffer, allocator),
         7 => day07.solve(args[2], buffer, allocator),
         8 => day08.solve(args[2], buffer, allocator),
+        9 => day09.solve(args[2], buffer, allocator),
         else => print("Day not yet implemented", .{}),
     };
 }
diff --git a/src/day09.zig b/src/day09.zig
new file mode 100644
index 0000000..827fd00
--- /dev/null
+++ b/src/day09.zig
@@ -0,0 +1,147 @@
+const std = @import("std");
+const mecha = @import("mecha");
+const print = std.debug.print;
+
+pub fn solve(part: []u8, buffer: []u8, allocator: std.mem.Allocator) !void {
+    if (std.mem.eql(u8, part, "1")) {
+        try part1(buffer, allocator);
+    } else {
+        try part2(buffer, allocator);
+    }
+}
+
+fn part1(buffer: []const u8, allocator: std.mem.Allocator) !void {
+    var disk = std.ArrayList(i32).init(allocator);
+    defer disk.deinit();
+
+    var free = false;
+    var id: i32 = 0;
+    for (buffer) |block_char| {
+        if (block_char == '\n') break;
+        const block = block_char - '0';
+        if (free) {
+            for (0..block) |_| {
+                try disk.append(-1);
+            }
+        } else {
+            for (0..block) |_| {
+                try disk.append(id);
+            }
+            id += 1;
+        }
+
+        free = !free;
+    }
+
+    var start_i: usize = 0;
+    var end_i: usize = disk.items.len - 1;
+
+    while (start_i < end_i) {
+        while (disk.items[start_i] != -1) : (start_i += 1) {}
+        while (disk.items[end_i] == -1) : (end_i -= 1) {}
+
+        disk.items[start_i] = disk.items[end_i];
+        start_i += 1;
+        end_i -= 1;
+    }
+
+    var checksum: usize = 0;
+    for (disk.items[0 .. end_i + 1], 0..) |file, index| {
+        if (file == -1) continue;
+        const f: usize = @intCast(file);
+        checksum += f * index;
+    }
+    print("{d}\n", .{checksum});
+}
+
+fn part2(buffer: []const u8, allocator: std.mem.Allocator) !void {
+    var categories: [9]std.ArrayList(std.meta.Tuple(&.{ usize, i32 })) = undefined;
+    for (&categories) |*cat| {
+        cat.* = std.ArrayList(std.meta.Tuple(&.{ usize, i32 })).init(allocator);
+        errdefer cat.deinit();
+    }
+    var counters: [9]usize = undefined;
+    @memset(&counters, 0);
+
+    var cid: i32 = @intCast((buffer.len - 1) / 2);
+    while (cid >= 0) {
+        const block = buffer[@intCast(cid * 2)] - '0';
+
+        for (block - 1..9) |n| {
+            try categories[n].append(.{ block, cid });
+        }
+
+        cid -= 1;
+    }
+
+    var set = std.AutoHashMap(usize, void).init(allocator);
+    defer set.deinit();
+    var checksum: usize = 0;
+    var id: usize = 0;
+    var empty = false;
+    var index: usize = 0;
+    for (buffer) |block_char| {
+        if (block_char == '\n') break;
+        var block: usize = block_char - '0';
+
+        if (empty) {
+            while (block > 0) {
+                var found_capacity: usize = 0;
+                var found_item: std.meta.Tuple(&.{ usize, i32 }) = undefined;
+                for (categories, 0..) |list, i| {
+                    if (block > i + 1) continue;
+                    if (list.items.len - counters[i] > 0) {
+                        for (counters[i]..list.items.len) |k| {
+                            if (set.contains(@intCast(list.items[k][1]))) {
+                                counters[i] += 1;
+                            } else {
+                                break;
+                            }
+                        }
+                        if (found_capacity == 0 and counters[i] < list.items.len) {
+                            found_capacity = i + 1;
+                            found_item = list.items[counters[i]];
+                            counters[i] += 1;
+                        } else {
+                            break;
+                        }
+                    } else {
+                        break;
+                    }
+                }
+                if (found_capacity == 0) {
+                    index += block;
+                    break;
+                }
+                block -= found_item[0];
+                const idd: usize = @intCast(found_item[1]);
+                if (!set.contains(idd)) {
+                    try set.put(idd, {});
+                    for (0..found_item[0]) |_| {
+                        checksum += idd * index;
+                        index += 1;
+                    }
+                }
+            }
+        } else {
+            if (!set.contains(id)) {
+                try set.put(id, {});
+                for (0..block) |_| {
+                    checksum += id * index;
+                    index += 1;
+                }
+            } else {
+                index += block;
+            }
+            id += 1;
+        }
+
+        empty = !empty;
+    }
+
+    for (&categories) |*cat| {
+        cat.*.deinit();
+    }
+
+    print("{d}\n", .{checksum});
+}
-- 
cgit v1.2.3