diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/day10.zig | 172 |
1 files changed, 172 insertions, 0 deletions
diff --git a/src/day10.zig b/src/day10.zig new file mode 100644 index 0000000..b72c9e3 --- /dev/null +++ b/src/day10.zig @@ -0,0 +1,172 @@ +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 dfs(grid: []const []const usize, row: i32, col: i32, previous: i32, seen: [][]bool) !i32 { + if (row >= 0 and row < grid.len and col >= 0 and col < grid.len and !seen[@intCast(row)][@intCast(col)]) { + const value = grid[@intCast(row)][@intCast(col)]; + + if (previous + 1 != value) return 0; + seen[@intCast(row)][@intCast(col)] = true; + + if (value == 9) { + return 1; + } + + var out: i32 = 0; + out += try dfs(grid, row + 1, col, @intCast(value), seen); + out += try dfs(grid, row - 1, col, @intCast(value), seen); + out += try dfs(grid, row, col + 1, @intCast(value), seen); + out += try dfs(grid, row, col - 1, @intCast(value), seen); + return out; + } else { + return 0; + } +} + +fn part1(buffer: []const u8, allocator: std.mem.Allocator) !void { + var lines = std.mem.splitScalar(u8, buffer, '\n'); + const width = lines.next().?.len; + + lines.reset(); + + var grid: [][]usize = try allocator.alloc([]usize, width); + defer allocator.free(grid); + + for (0..width) |i| { + grid[i] = try allocator.alloc(usize, width); + @memset(grid[i], 0); + } + + var row: usize = 0; + while (lines.next()) |line| { + if (line.len == 0) break; + for (line, 0..) |item, col| { + if (item == '.') { + grid[row][col] = 15; + } else { + grid[row][col] = item - '0'; + } + } + row += 1; + } + + var out: i32 = 0; + for (0..width) |r| { + for (0..width) |c| { + if (grid[r][c] == 0) { + var seen: [][]bool = try allocator.alloc([]bool, width); + defer allocator.free(seen); + for (0..width) |i| { + seen[i] = try allocator.alloc(bool, width); + @memset(seen[i], false); + } + + out += try dfs(grid, @intCast(r), @intCast(c), -1, seen); + + for (0..width) |i| { + allocator.free(seen[i]); + } + } + } + } + + for (0..width) |i| { + allocator.free(grid[i]); + } + print("{d}\n", .{out}); +} + +//-------------------------PART2----------------------------------------- + +fn dfs2(lookup: [][]i32, grid: []const []const usize, row: i32, col: i32, previous: i32) !i32 { + if (row >= 0 and row < grid.len and col >= 0 and col < grid.len) { + const value = grid[@intCast(row)][@intCast(col)]; + const look = lookup[@intCast(row)][@intCast(col)]; + + if (previous + 1 != value) return 0; + + if (look > 0) return look; + + if (value == 9) { + return 1; + } + + lookup[@intCast(row)][@intCast(col)] += try dfs2(lookup, grid, row + 1, col, @intCast(value)); + lookup[@intCast(row)][@intCast(col)] += try dfs2(lookup, grid, row - 1, col, @intCast(value)); + lookup[@intCast(row)][@intCast(col)] += try dfs2(lookup, grid, row, col + 1, @intCast(value)); + lookup[@intCast(row)][@intCast(col)] += try dfs2(lookup, grid, row, col - 1, @intCast(value)); + + return lookup[@intCast(row)][@intCast(col)]; + } else { + return 0; + } +} + +fn part2(buffer: []const u8, allocator: std.mem.Allocator) !void { + var lines = std.mem.splitScalar(u8, buffer, '\n'); + const width = lines.next().?.len; + + lines.reset(); + + var grid: [][]usize = try allocator.alloc([]usize, width); + defer allocator.free(grid); + + for (0..width) |i| { + grid[i] = try allocator.alloc(usize, width); + @memset(grid[i], 0); + } + + var row: usize = 0; + while (lines.next()) |line| { + if (line.len == 0) break; + for (line, 0..) |item, col| { + if (item == '.') { + grid[row][col] = 15; + } else { + grid[row][col] = item - '0'; + } + } + row += 1; + } + + var out: i32 = 0; + for (0..width) |r| { + for (0..width) |c| { + if (grid[r][c] == 0) { + var lookup: [][]i32 = try allocator.alloc([]i32, width); + defer allocator.free(lookup); + + for (0..width) |i| { + lookup[i] = try allocator.alloc(i32, width); + @memset(lookup[i], 0); + } + + out += try dfs2( + lookup, + grid, + @intCast(r), + @intCast(c), + -1, + ); + + for (0..width) |i| { + allocator.free(lookup[i]); + } + } + } + } + + for (0..width) |i| { + allocator.free(grid[i]); + } + print("{d}\n", .{out}); +} |