diff options
Diffstat (limited to 'aoc/2021/15/part-one.zig')
-rw-r--r-- | aoc/2021/15/part-one.zig | 53 |
1 files changed, 53 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 }); +} |