[aoc/2021] Finish day 15

2 files changed, 108 insertions, 0 deletions

diff --git a/aoc/2021/15/part-one.zig b/aoc/2021/15/part-one.zig
new file mode 100644
index 0000000..a99e1cb
--- /dev/null
+++ b/aoc/2021/15/part-one.zig
@@ -0,0 +1,53 @@
+const FixedBufferAllocator = std.heap.FixedBufferAllocator;
+const Order = std.math.Order;
+const PQ = std.PriorityQueue;
+const input = @embedFile("input");
+const order = std.math.order;
+const print = std.debug.print;
+const std = @import("std");
+
+const Risk = packed struct {
+    x: u7,
+    y: u7,
+    v: u18,
+
+    pub fn lt(self: Risk, other: Risk) Order {
+        return order(@bitCast(u32, self), @bitCast(u32, other));
+    }
+
+    pub fn move(self: Risk, queue: *PQ(Risk), dx: i8, dy: i8) !void {
+        switch (self.x + dx) {
+            0...99 => |x| switch (self.y + dy) {
+                0...99 => |y| try queue.add(.{
+                    .x = @intCast(u7, x), .y = @intCast(u7, y),
+                    .v = self.v + input[@intCast(usize, x)
+                        + @intCast(usize, y) * 101] - '0',
+                }),
+                else => {},
+            },
+            else => {},
+        }
+    }
+};
+
+pub fn main() !void {
+    var visited = [_][100]bool{ [_]bool{ false } ** 100 } ** 100;
+    var buffer: [0xbeef]u8 = undefined;
+    var fba = FixedBufferAllocator.init(buffer[0..]);
+    var queue = PQ(Risk).init(&fba.allocator, Risk.lt);
+    try queue.add(.{ .x = 0, .y = 0, .v = 0 });
+    const result = while (queue.count() > 0) {
+        const best = queue.remove();
+        if (best.x == 99 and best.y == 99)
+            break best.v;
+        if (visited[best.x][best.y])
+            continue
+        else
+            visited[best.x][best.y] = true;
+        try best.move(&queue, 1, 0);
+        try best.move(&queue, 0, 1);
+        try best.move(&queue, -1, 0);
+        try best.move(&queue, 0, -1);
+    } else unreachable;
+    print("{}\n", .{ result });
+}
diff --git a/aoc/2021/15/part-two.zig b/aoc/2021/15/part-two.zig
new file mode 100644
index 0000000..cc77035
--- /dev/null
+++ b/aoc/2021/15/part-two.zig
@@ -0,0 +1,55 @@
+const FixedBufferAllocator = std.heap.FixedBufferAllocator;
+const Order = std.math.Order;
+const PQ = std.PriorityQueue;
+const input = @embedFile("input");
+const order = std.math.order;
+const print = std.debug.print;
+const std = @import("std");
+
+const Risk = packed struct {
+    x: u9,
+    y: u9,
+    v: u22,
+
+    pub fn lt(self: Risk, other: Risk) Order {
+        return order(@bitCast(u40, self), @bitCast(u40, other));
+    }
+
+    pub fn move(self: Risk, queue: *PQ(Risk), dx: i10, dy: i10) !void {
+        switch (self.x + dx) {
+            0...499 => |x| switch (self.y + dy) {
+                0...499 => |y| try queue.add(.{
+                    .v = self.v + @intCast(u22,
+                        input[@intCast(usize, @rem(x, 100))
+                              + @intCast(usize, @rem(y, 100)) * 101] - '1'
+                        + @divTrunc(x, 100) + @divTrunc(y, 100)) % 9 + 1,
+                    .x = @intCast(u9, x), .y = @intCast(u9, y),
+                }),
+                else => {},
+            },
+            else => {},
+        }
+    }
+};
+
+pub fn main() !void {
+    var visited = [_][500]bool{ [_]bool{ false } ** 500 } ** 500;
+    var buffer: [0xbeef]u8 = undefined;
+    var fba = FixedBufferAllocator.init(buffer[0..]);
+    var queue = PQ(Risk).init(&fba.allocator, Risk.lt);
+    try queue.add(.{ .x = 0, .y = 0, .v = 0 });
+    const result = while (queue.count() > 0) {
+        const best = queue.remove();
+        if (best.x == 499 and best.y == 499)
+            break best.v;
+        if (visited[best.x][best.y])
+            continue
+        else
+            visited[best.x][best.y] = true;
+        try best.move(&queue, 1, 0);
+        try best.move(&queue, 0, 1);
+        try best.move(&queue, -1, 0);
+        try best.move(&queue, 0, -1);
+    } else unreachable;
+    print("{}\n", .{ result });
+}