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}); }