day16

2 files changed, 168 insertions, 0 deletions

diff --git a/day16/example.txt b/day16/example.txt
new file mode 100644
index 0000000..d6805ce
--- /dev/null
+++ b/day16/example.txt
@@ -0,0 +1,10 @@
+.|...\....
+|.-.\.....
+.....|-...
+........|.
+..........
+.........\
+..../.\\..
+.-.-/..|..
+.|....-|.\
+..//.|....
diff --git a/day16/solution.zig b/day16/solution.zig
new file mode 100644
index 0000000..70da969
--- /dev/null
+++ b/day16/solution.zig
@@ -0,0 +1,158 @@
+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 step = [_][2]i64{
+    [2]i64{ -1, 0 },
+    [2]i64{ 0, 1 },
+    [2]i64{ 1, 0 },
+    [2]i64{ 0, -1 },
+};
+
+const Beam = struct {
+    i: isize,
+    j: isize,
+    d: usize,
+
+    pub inline fn next(self: @This()) Beam {
+        return self.nextd(self.d);
+    }
+
+    pub inline fn prev(self: @This()) Beam {
+        return Beam{
+            .i = self.i - step[self.d][0],
+            .j = self.j - step[self.d][1],
+            .d = self.d,
+        };
+    }
+
+    pub inline fn nextd(self: @This(), d: usize) Beam {
+        return Beam{
+            .i = self.i + step[d][0],
+            .j = self.j + step[d][1],
+            .d = d,
+        };
+    }
+
+    pub const Ctx = struct {
+        pub fn hash(_: @This(), b: Beam) u64 {
+            return @bitCast(b.i << 16 | b.j << 8 | @as(isize, @bitCast(b.d)));
+        }
+
+        pub fn eql(_: @This(), lhs: Beam, rhs: Beam) bool {
+            return lhs.i == rhs.i and lhs.j == rhs.j and lhs.d == rhs.d;
+        }
+    };
+
+    // ignore direction when comparing beams
+    pub const Ctx2 = struct {
+        pub fn hash(_: @This(), b: Beam) u64 {
+            return @bitCast(b.i << 8 | b.j);
+        }
+
+        pub fn eql(_: @This(), lhs: Beam, rhs: Beam) bool {
+            const res = lhs.i == rhs.i and lhs.j == rhs.j;
+            return res;
+        }
+    };
+};
+
+var edgesVisited = HashMap(Beam, void, Beam.Ctx2, 80).init(allocator);
+
+fn dfs(grid: []const []const u8, start: Beam) !u64 {
+    if (edgesVisited.get(start) != null) {
+        return 0;
+    }
+    const w = grid[0].len;
+    const h = grid.len;
+    var beams = ArrayList(Beam).init(allocator);
+    var visited = HashMap(Beam, void, Beam.Ctx, 80).init(allocator);
+    var uniq = HashMap(Beam, void, Beam.Ctx2, 80).init(allocator);
+    defer {
+        beams.deinit();
+        uniq.deinit();
+        visited.deinit();
+    }
+
+    try beams.append(start);
+
+    while (beams.items.len > 0) {
+        var curr = beams.pop();
+        while (0 <= curr.i and curr.i < h and 0 <= curr.j and curr.j < w) {
+            if ((try visited.getOrPut(curr)).found_existing) {
+                break;
+            }
+            const c = grid[@bitCast(curr.i)][@bitCast(curr.j)];
+            switch (c) {
+                '|' => {
+                    try beams.append(curr.nextd(2));
+                    curr = curr.nextd(0);
+                },
+                '-' => {
+                    try beams.append(curr.nextd(3));
+                    curr = curr.nextd(1);
+                },
+                '\\' => {
+                    const d = (curr.d + if (curr.d & 1 != 0) @as(usize, 1) else @as(usize, 3)) % 4;
+                    curr = curr.nextd(d);
+                },
+                '/' => {
+                    const d = (curr.d + if (curr.d & 1 != 0) @as(usize, 3) else @as(usize, 1)) % 4;
+                    curr = curr.nextd(d);
+                },
+                '.' => {
+                    curr = curr.next();
+                },
+                else => unreachable,
+            }
+        } else { // finished by hitting an edge
+            try edgesVisited.put(curr.prev(), {});
+        }
+    }
+
+    var it = visited.keyIterator();
+    while (it.next()) |k| {
+        try uniq.put(k.*, {});
+    }
+
+    return uniq.count();
+}
+
+pub fn solve(grid: []const []const u8) !void {
+    const h = grid.len;
+    const w = grid[0].len;
+    const part1 = try dfs(grid, Beam{ .i = 0, .j = 0, .d = 1 });
+
+    print("{d}\n", .{part1});
+
+    var part2: u64 = 0;
+    for (0..h) |i_| {
+        const i: i64 = @bitCast(i_);
+        part2 = @max(part2, try dfs(grid, .{ .i = i, .j = 0, .d = 1 }));
+        part2 = @max(part2, try dfs(grid, .{ .i = i, .j = @bitCast(w - 1), .d = 3 }));
+    }
+    for (0..w) |j_| {
+        const j: i64 = @bitCast(j_);
+        part2 = @max(part2, try dfs(grid, .{ .i = 0, .j = j, .d = 2 }));
+        part2 = @max(part2, try dfs(grid, .{ .i = @bitCast(h - 1), .j = j, .d = 0 }));
+    }
+
+    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);
+}