somehow part 2 came out feeling much more aligned with my construction than part 1. my part 1 runs in about 1ms and my part 2 runs in about 300ms.
Part 1 and Part 2
full code on GitHub
I’ll just paste the relevant function from each part without the setup.
Here’s part 1:
const Block = struct {
id: Id,
len: u8,
const Id = union(enum) {
free: void,
file: u16,
};
};
fn process(allocator: std.mem.Allocator, input: []const u8) !usize {
var fragged: std.ArrayListUnmanaged(Block) = .{};
defer fragged.deinit(allocator);
var free = false;
var id: u16 = 0;
try fragged.ensureTotalCapacity(allocator, input.len);
for (input) |byte| {
defer free = !free;
const digit = switch (byte) {
'0'...'9' => byte - '0',
else => continue,
};
const file: Block.Id = if (free) .free else id: {
defer id += 1;
break :id .{ .file = id };
};
fragged.appendAssumeCapacity(.{ .id = file, .len = digit });
}
var defragged: std.ArrayListUnmanaged(u16) = .{};
defer defragged.deinit(allocator);
var read_head: usize = 0;
var copy_head: usize = fragged.items.len - 1;
var copy = if (fragged.items[copy_head].id == .free) copy: {
copy_head -= 1;
break :copy fragged.items[copy_head];
} else fragged.items[copy_head];
var copy_len = copy.len;
while (read_head < copy_head) {
const read = fragged.items[read_head];
switch (read.id) {
.free => {
var slice = try defragged.addManyAsSlice(allocator, read.len);
var len = @min(copy_len, slice.len);
@memset(slice[0..len], copy.id.file);
while (len < slice.len) {
// we finished reading a file
slice = slice[len..];
copy_head -= 2;
copy = fragged.items[copy_head];
copy_len = copy.len;
len = @min(copy_len, slice.len);
@memset(slice[0..len], copy.id.file);
}
// we have leftover length in copy_len
copy_len -= len;
read_head += 1;
},
.file => |file_id| {
const slice = try defragged.addManyAsSlice(allocator, read.len);
@memset(slice, file_id);
read_head += 1;
},
}
}
if (read_head == copy_head and copy_len > 0) {
const slice = try defragged.addManyAsSlice(allocator, copy_len);
@memset(slice, copy.id.file);
}
var checksum: usize = 0;
for (defragged.items, 0..) |file_id, pos| checksum += file_id * pos;
return checksum;
}
Part 2 uses the same Block struct
fn process(allocator: std.mem.Allocator, input: []const u8) !usize {
var fragged: std.ArrayListUnmanaged(Block) = .{};
defer fragged.deinit(allocator);
var free = false;
var id: u16 = 0;
try fragged.ensureTotalCapacity(allocator, input.len);
for (input) |byte| {
defer free = !free;
const digit = switch (byte) {
'0'...'9' => byte - '0',
else => continue,
};
const file: Block.Id = if (free) .free else id: {
defer id += 1;
break :id .{ .file = id };
};
fragged.appendAssumeCapacity(.{ .id = file, .len = digit });
}
var idx = fragged.items.len - 1;
var pos: usize = 0;
for (fragged.items) |block| {
pos += block.len;
}
while (idx > 0) {
const block = &fragged.items[idx];
pos -= block.len;
if (block.id == .free) {
idx -= 1;
continue;
}
var new_pos: usize = 0;
var i: usize = 0;
while (new_pos < pos) : (i += 1) {
const item = &fragged.items[i];
const item_len = item.len;
defer new_pos += item_len;
if (item.id != .free or item.len < block.len) continue;
if (item.len == block.len) {
// perfect fit
item.id = block.id;
block.id = .free;
idx -= 1;
break;
}
const rem = item.len - block.len;
item.* = block.*;
block.id = .free;
try fragged.insert(allocator, i + 1, .{ .id = .free, .len = rem });
break;
} else {
idx -= 1;
}
}
var checksum: usize = 0;
pos = 0;
for (fragged.items) |block| {
switch (block.id) {
.free => pos += block.len,
.file => |file_id| {
for (0..block.len) |i| {
checksum += file_id * (pos + i);
}
pos += block.len;
},
}
}
return checksum;
}