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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
const std = @import("std");
const Input = [][]u4;
const test_input =
\\89010123
\\78121874
\\87430965
\\96549874
\\45678903
\\32019012
\\01329801
\\10456732
\\
;
pub fn parse(allocator: std.mem.Allocator, data: []const u8) !Input {
var lines = std.mem.split(u8, data, "\n");
var rows = std.ArrayList([]u4).init(allocator);
while (lines.next()) |line| {
if (line.len == 0) break;
const row = try allocator.alloc(u4, line.len);
for (row, line) |*r, l| {
r.* = @intCast(l - '0');
}
try rows.append(row);
}
return rows.items;
}
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));
try std.testing.expectEqual(36, output);
}
pub fn part1(allocator: std.mem.Allocator, input: Input) !u32 {
const visited = try allocator.alloc([]u1, input.len);
for (visited) |*v| {
v.* = try allocator.alloc(u1, input[0].len);
}
var curr = std.ArrayList(@Vector(2, usize)).init(allocator);
var next = std.ArrayList(@Vector(2, usize)).init(allocator);
// for (input) |row| {
// for (row) |cell| {
// std.debug.print("{}", .{cell});
// }
// std.debug.print("\n", .{});
// }
var score: u32 = 0;
for (0.., input) |y, row| for (0.., row) |x, cell| {
if (cell != 0) continue;
for (visited) |v| @memset(v, 0);
curr.clearRetainingCapacity();
next.clearRetainingCapacity();
try curr.append(.{ x, y });
var height: u4 = 0;
while (curr.items.len > 0) {
for (curr.items) |pos| {
// std.debug.print("checking {}\n", .{pos});
if (height != input[pos[1]][pos[0]] or visited[pos[1]][pos[0]] == 1) continue;
visited[pos[1]][pos[0]] = 1;
if (height == 9) score += 1;
// left
if (pos[0] > 0) try next.append(.{ pos[0] - 1, pos[1] });
// up
if (pos[1] > 0) try next.append(.{ pos[0], pos[1] - 1 });
// right
if (pos[0] < input[0].len - 1) try next.append(.{ pos[0] + 1, pos[1] });
// down
if (pos[1] < input[0].len - 1) try next.append(.{ pos[0], pos[1] + 1 });
}
curr.clearRetainingCapacity();
std.mem.swap(@TypeOf(curr), &curr, &next);
height += 1;
}
};
return score;
}
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));
try std.testing.expectEqual(81, output);
}
pub fn part2(allocator: std.mem.Allocator, input: Input) !u32 {
var curr = std.ArrayList(@Vector(2, usize)).init(allocator);
var next = std.ArrayList(@Vector(2, usize)).init(allocator);
var score: u32 = 0;
for (0.., input) |y, row| for (0.., row) |x, cell| {
if (cell != 0) continue;
curr.clearRetainingCapacity();
next.clearRetainingCapacity();
try curr.append(.{ x, y });
var height: u4 = 0;
while (curr.items.len > 0) {
for (curr.items) |pos| {
if (height != input[pos[1]][pos[0]]) continue;
if (height == 9) score += 1;
if (pos[0] > 0) try next.append(.{ pos[0] - 1, pos[1] });
if (pos[1] > 0) try next.append(.{ pos[0], pos[1] - 1 });
if (pos[0] < input[0].len - 1) try next.append(.{ pos[0] + 1, pos[1] });
if (pos[1] < input[0].len - 1) try next.append(.{ pos[0], pos[1] + 1 });
}
curr.clearRetainingCapacity();
std.mem.swap(@TypeOf(curr), &curr, &next);
height += 1;
}
};
return score;
}
|
