From dae1e9ead3f23d4bdd4417f16e4ef756bafcc86a Mon Sep 17 00:00:00 2001
From: Mathias Magnusson <mathias@magnusson.space>
Date: Fri, 13 Dec 2024 22:50:40 +0100
Subject: aoc2024: day 9 part 2

---
 aoc24/src/day9.zig | 97 ++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 83 insertions(+), 14 deletions(-)

(limited to 'aoc24/src')

diff --git a/aoc24/src/day9.zig b/aoc24/src/day9.zig
index 520391d..f2bae47 100644
--- a/aoc24/src/day9.zig
+++ b/aoc24/src/day9.zig
@@ -2,7 +2,6 @@ const std = @import("std");
 
 const Input = struct {
     compressed: []Entry,
-    uncompressed: std.ArrayList(?u32),
 
     const Entry = struct { taken: u8, free: u8 };
 };
@@ -11,15 +10,12 @@ pub fn parse(allocator: std.mem.Allocator, data: []const u8) !Input {
     var compressed = std.ArrayList(Input.Entry).init(allocator);
     var i: usize = 0;
     while (i < data.len) : (i += 2) {
-        try compressed.append(.{ .taken = data[i] - '0', .free = if (i + 1 == data.len or data[i + 1] == '\n') 0 else data[i + 1] - '0' });
+        try compressed.append(.{
+            .taken = data[i] - '0',
+            .free = if (i + 1 == data.len or data[i + 1] == '\n') 0 else data[i + 1] - '0',
+        });
     }
-
-    var uncompressed = std.ArrayList(?u32).init(allocator);
-    for (0.., compressed.items) |j, entry| {
-        try uncompressed.appendNTimes(@intCast(j), entry.taken);
-        try uncompressed.appendNTimes(null, entry.free);
-    }
-    return .{ .compressed = compressed.items, .uncompressed = uncompressed };
+    return .{ .compressed = compressed.items };
 }
 
 const test_input = "2333133121414131402";
@@ -74,15 +70,88 @@ test "part2" {
     std.debug.assert(output == 2858);
 }
 
-pub fn part2(allocator: std.mem.Allocator, input: Input) !u32 {
-    var filesystem = std.ArrayList(u32).init(allocator);
+pub fn part2(allocator: std.mem.Allocator, input: Input) !u64 {
+    var filesystem_array_list = std.ArrayList(?u32).init(allocator);
+    for (0.., input.compressed) |i, entry| {
+        try filesystem_array_list.appendNTimes(@as(u32, @intCast(i)), entry.taken);
+        try filesystem_array_list.appendNTimes(null, entry.free);
+    }
+    var filesystem = filesystem_array_list.items;
+
+    var file: u32 = @intCast(input.compressed.len - 1);
+    while (true) : (file = std.math.sub(u32, file, 1) catch break) {
+        // for (filesystem) |item| {
+        //     if (item) |it| std.debug.print("{}", .{it}) else std.debug.print(".", .{});
+        // }
+        // std.debug.print("\n", .{});
+
+        const index = std.mem.indexOfScalar(?u32, filesystem, file).?;
+        const len = input.compressed[file].taken;
+        std.debug.assert(std.mem.allEqual(?u32, filesystem[index..][0..len], file));
+        const nulls = try allocator.alloc(?u32, len);
+        defer allocator.free(nulls);
+        @memset(nulls, null);
+        const space = std.mem.indexOf(?u32, filesystem, nulls) orelse continue;
+        if (space > index) continue;
+        @memset(filesystem[index..][0..len], null);
+        @memset(filesystem[space..][0..len], file);
+    }
+
+    // for (filesystem) |item| {
+    //     if (item) |it| std.debug.print("{}", .{it}) else std.debug.print(".", .{});
+    // }
+    // std.debug.print("\n", .{});
+
+    var sum: u64 = 0;
+    for (0.., filesystem) |pos, id| {
+        sum += pos * @as(u64, @intCast(id orelse 0));
+    }
+
+    return sum;
+}
+
+pub fn part2OptimizedButWrong(allocator: std.mem.Allocator, input: Input) !u64 {
+    var filesystem = std.ArrayList(?u32).init(allocator);
+    for (input.compressed) |entry| {
+        try filesystem.appendNTimes(null, entry.taken);
+        try filesystem.appendNTimes(null, entry.free);
+    }
 
-    _ = .{ filesystem, input };
-    filesystem = undefined;
+    var file_locations = std.ArrayList(u32).init(allocator);
+    var free_slots = std.ArrayList(struct { start: u32, size: u8 }).init(allocator);
+    var i: u32 = 0;
+    for (input.compressed) |e| {
+        try file_locations.append(i);
+        try free_slots.append(.{ .start = i + e.taken, .size = e.free });
+        i += e.taken + e.free;
+    }
+
+    var file_id: u32 = @intCast(input.compressed.len - 1);
+    while (true) {
+        const file_size = input.compressed[file_id].taken;
+        for (free_slots.items) |*slot| {
+            if (file_size <= slot.size) {
+                for (filesystem.items[slot.start..][0..file_size]) |id| std.debug.assert(id == null);
+                @memset(filesystem.items[slot.start..][0..file_size], file_id);
+                slot.size -= file_size;
+                slot.start += file_size;
+                break;
+            }
+        } else {
+            for (filesystem.items[file_locations.items[file_id]..][0..file_size]) |id| std.debug.assert(id == null);
+            @memset(filesystem.items[file_locations.items[file_id]..][0..file_size], file_id);
+        }
+        file_id = std.math.sub(u32, file_id, 1) catch break;
+    }
+
+    // for (filesystem.items) |item| {
+    //     if (item) |it| std.debug.print("{}", .{it}) else std.debug.print(".", .{});
+    // }
+    // std.debug.print("\n", .{});
 
     var sum: u64 = 0;
     for (0.., filesystem.items) |pos, id| {
-        sum += pos * @as(u64, @intCast(id));
+        sum += pos * @as(u64, @intCast(id orelse 0));
     }
 
     return sum;
-- 
cgit v1.2.3