add solution day10

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