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