day10

1 files changed, 133 insertions, 0 deletions

diff --git a/day10/solution.zig b/day10/solution.zig
new file mode 100644
index 0000000..8028c94
--- /dev/null
+++ b/day10/solution.zig
@@ -0,0 +1,133 @@
+const std = @import("std");
+const print = std.debug.print;
+const assert = std.debug.assert;
+const ArrayList = std.ArrayList;
+const HashMap = std.HashMap;
+const mem = std.mem;
+
+const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
+var gpa = std.heap.GeneralPurposeAllocator(.{}){};
+const allocator = gpa.allocator();
+
+const Pair = struct {
+    row: isize,
+    col: isize,
+
+    pub fn eql(lhs: @This(), rhs: @This()) bool {
+        return lhs.col == rhs.col and lhs.row == rhs.row;
+    }
+};
+
+const Direction = enum(u4) {
+    N = 0,
+    U = 1 << 0,
+    R = 1 << 1,
+    D = 1 << 2,
+    L = 1 << 3,
+};
+
+const c2dir = blk: {
+    var res: [256]u4 = undefined;
+    res['S'] =
+        @intFromEnum(Direction.U) | @intFromEnum(Direction.R) |
+        @intFromEnum(Direction.D) | @intFromEnum(Direction.L);
+    res['|'] = @intFromEnum(Direction.U) | @intFromEnum(Direction.D);
+    res['J'] = @intFromEnum(Direction.U) | @intFromEnum(Direction.L);
+    res['L'] = @intFromEnum(Direction.U) | @intFromEnum(Direction.R);
+    res['7'] = @intFromEnum(Direction.D) | @intFromEnum(Direction.L);
+    res['F'] = @intFromEnum(Direction.D) | @intFromEnum(Direction.R);
+    res['-'] = @intFromEnum(Direction.L) | @intFromEnum(Direction.R);
+    res['.'] = @intFromEnum(Direction.N);
+    break :blk res;
+};
+
+const dir2off = blk: {
+    var res: [256][2]i64 = undefined;
+    res[@intFromEnum(Direction.U)] = .{ -1, 0 };
+    res[@intFromEnum(Direction.R)] = .{ 0, 1 };
+    res[@intFromEnum(Direction.D)] = .{ 1, 0 };
+    res[@intFromEnum(Direction.L)] = .{ 0, -1 };
+    break :blk res;
+};
+
+pub fn solve(grid: []const []const u8) !void {
+    const height = grid.len;
+    const width = grid[0].len;
+    const start = find_start: {
+        for (grid, 0..) |row, i| {
+            if (mem.indexOfScalar(u8, row, 'S')) |j| {
+                break :find_start Pair{
+                    .row = @bitCast(i),
+                    .col = @bitCast(j),
+                };
+            }
+        }
+        unreachable;
+    };
+
+    var pathNodes = ArrayList(Pair).init(allocator);
+    defer pathNodes.deinit();
+    try pathNodes.append(start);
+    var blocked: u4 = 0b0000;
+
+    outer: while (true) {
+        const curr = pathNodes.getLast();
+        const cdirs = c2dir[grid[@bitCast(curr.row)][@bitCast(curr.col)]];
+
+        for (0..4) |i| {
+            const d: u4 = @shlExact(@as(u4, 1), @intCast(i));
+            const nrow: i64 = curr.row + dir2off[d][0];
+            const ncol: i64 = curr.col + dir2off[d][1];
+
+            if (nrow < 0 or nrow >= height or ncol < 0 or ncol >= width) {
+                continue;
+            }
+
+            const next = Pair{
+                .row = nrow,
+                .col = ncol,
+            };
+            const ndirs = std.math.rotl(u4, c2dir[grid[@bitCast(next.row)][@bitCast(next.col)]], @as(u2, 2));
+
+            if (d & cdirs & ndirs & ~blocked != 0) {
+                // Wrapped back to the beginning
+                if (next.eql(start)) {
+                    break :outer;
+                }
+                blocked = std.math.rotl(u4, d, @as(u2, 2));
+                try pathNodes.append(next);
+                break;
+            }
+        } else {
+            unreachable;
+        }
+    }
+
+    const pathLen = pathNodes.items.len;
+    const part1 = pathLen / 2;
+    print("{d}\n", .{part1});
+
+    // Use shoelace formula to calculate the area of the polygon
+    // https://en.wikipedia.org/wiki/Shoelace_formula#Shoelace_formula
+    var a2: isize = 0;
+    for (pathNodes.items, 1..) |f, j| {
+        const s = pathNodes.items[j % pathLen];
+        a2 += f.row * s.col - f.col * s.row;
+    }
+    const a: isize = @divTrunc(if (a2 > 0) a2 else -a2, 2);
+    // Use Pick's formula to find the number of internal points
+    // https://en.wikipedia.org/wiki/Pick's_theorem#Formula
+    const part2 = a - @as(isize, @bitCast(part1)) + 1;
+
+    print("{d}\n", .{part2});
+}
+
+pub fn main() !void {
+    var splitLines = mem.splitScalar(u8, fin, '\n');
+    var grid = ArrayList([]const u8).init(allocator);
+
+    while (splitLines.next()) |line| {
+        try grid.append(line);
+    }
+    try solve(grid.items);
+}