1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
const std = @import("std");
const Input = struct {
compressed: []Entry,
const Entry = struct { taken: u8, free: u8 };
};
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',
});
}
return .{ .compressed = compressed.items };
}
const test_input = "2333133121414131402";
test "part1" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const output = try part1(arena.allocator(), try parse(arena.allocator(), test_input));
std.debug.print("got {}\n", .{output});
std.debug.assert(output == 1928);
}
pub fn part1(allocator: std.mem.Allocator, input: Input) !u64 {
var filesystem = std.ArrayList(u32).init(allocator);
var unmoved: u32 = 0;
var moved: u32 = @intCast(input.compressed.len);
var moved_left: u8 = 0;
while (unmoved < moved) {
try filesystem.appendNTimes(unmoved, input.compressed[unmoved].taken);
for (0..input.compressed[unmoved].free) |_| {
while (moved_left == 0) {
moved -= 1;
moved_left = input.compressed[moved].taken;
}
try filesystem.append(moved);
moved_left -= 1;
}
unmoved += 1;
}
try filesystem.appendNTimes(moved, moved_left);
// for (filesystem.items) |item| {
// std.debug.print("{}", .{item});
// }
// std.debug.print("\n", .{});
var sum: u64 = 0;
for (0.., filesystem.items) |pos, id| {
sum += pos * @as(u64, @intCast(id));
}
return sum;
}
test "part2" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const output = try part2(arena.allocator(), try parse(arena.allocator(), test_input));
std.debug.print("got {}\n", .{output});
std.debug.assert(output == 2858);
}
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) {
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;
}
|
