2022-12 in zig

4 files changed, 232 insertions, 0 deletions

diff --git a/2022/12-hill-climbing-algorithm/example b/2022/12-hill-climbing-algorithm/example
new file mode 100644
index 0000000..86e9cac
--- /dev/null
+++ b/2022/12-hill-climbing-algorithm/example
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi
diff --git a/2022/12-hill-climbing-algorithm/first.zig b/2022/12-hill-climbing-algorithm/first.zig
new file mode 100644
index 0000000..bf014b2
--- /dev/null
+++ b/2022/12-hill-climbing-algorithm/first.zig
@@ -0,0 +1,93 @@
+const std = @import("std");
+
+const example = @embedFile("example");
+const input = @embedFile("input");
+
+pub fn main() anyerror!void {
+    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
+    defer arena.deinit();
+    const allocator = arena.allocator();
+
+    try std.testing.expectEqual(try solve(example, allocator), 31);
+    const result = try solve(input, allocator);
+    try std.io.getStdOut().writer().print("{}\n", .{result});
+}
+
+const Node = struct {
+    x: u8,
+    y: u8,
+    cost: ?u64,
+    value: u8,
+    fn evalAndAdd(e: *Node, n: *Node, nq: *std.PriorityQueue(*Node, void, lesserThan)) !void {
+        if (e.cost == null and e.value <= n.value + 1) {
+            e.cost = n.cost.? + 1;
+            try nq.add(e);
+        }
+    }
+};
+
+fn lesserThan(context: void, a: *Node, b: *Node) std.math.Order {
+    _ = context;
+    return std.math.order(a.cost.?, b.cost.?);
+}
+
+fn solve(puzzle: []const u8, allocator: std.mem.Allocator) !u64 {
+    var it = std.mem.tokenize(u8, puzzle, "\n");
+    var grid = std.ArrayList(std.ArrayList(Node)).init(allocator);
+    var Sx: u8 = undefined;
+    var Sy: u8 = undefined;
+    var Ex: u8 = undefined;
+    var Ey: u8 = undefined;
+    // process input
+    var y: u8 = 0;
+    var line = it.next() orelse unreachable;
+    const width = line.len;
+    while (true) : (line = it.next() orelse break) {
+        var l = try grid.addOne();
+        l.* = try std.ArrayList(Node).initCapacity(allocator, width);
+        var x: u8 = 0;
+        while (x < line.len) : (x += 1) {
+            var n = l.*.addOneAssumeCapacity();
+            n.*.x = x;
+            n.*.y = y;
+            n.*.cost = null;
+            n.*.value = switch (line[x]) {
+                'S' => blk: {
+                    Sx = x;
+                    Sy = y;
+                    n.*.cost = 0;
+                    break :blk 'a';
+                },
+                'E' => blk: {
+                    Ex = x;
+                    Ey = y;
+                    break :blk 'z';
+                },
+                else => line[x],
+            };
+        }
+        y += 1;
+    }
+    const height = grid.items.len;
+    // find shortest path
+    var nq = std.PriorityQueue(*Node, void, lesserThan).init(allocator, {});
+    try nq.add(&grid.items[Sy].items[Sx]);
+    while (true) {
+        var n = nq.remove();
+        if (n.x == Ex and n.y == Ey) {
+            return n.cost.?;
+        }
+        if (n.x > 0) {
+            try grid.items[n.y].items[n.x - 1].evalAndAdd(n, &nq);
+        }
+        if (n.x < width - 1) {
+            try grid.items[n.y].items[n.x + 1].evalAndAdd(n, &nq);
+        }
+        if (n.y > 0) {
+            try grid.items[n.y - 1].items[n.x].evalAndAdd(n, &nq);
+        }
+        if (n.y < height - 1) {
+            try grid.items[n.y + 1].items[n.x].evalAndAdd(n, &nq);
+        }
+    }
+}
diff --git a/2022/12-hill-climbing-algorithm/input b/2022/12-hill-climbing-algorithm/input
new file mode 100644
index 0000000..0ae755d
--- /dev/null
+++ b/2022/12-hill-climbing-algorithm/input
@@ -0,0 +1,41 @@
+abccccaaacaccccaaaaacccccccaaccccccccaaaaaaccccccaaaaaccccccccccaaaaaaaaacccccccaaaaaaaaaaaaaaccaaaaaccccccccccccaccacccccccccccccccccccccccccccccccccccccccaaaaaa
+abccaacaaaaaccaaaaacccccaaaaaccccccccaaaaaaccccccaaaaaacccccccccaaaaaaaaaaaaacccaaaaaaaaaaaaaaaaaaaaaccccccccccccaaaacccccccccccccccccccccccccccccccccccccccaaaaaa
+abccaaaaaaaaccaaaaaacccccaaaaaccccccaaaaaaaacccccaaaaaaccccccccccaaaaaaaaaaaacccaaaaaacaaaaaacaaaaaaaaccccccccccaaaaacccccaccccccccccccccccccaaacccccccccccccaaaaa
+abcccaaaaaccccccaaaacccccaaaaacccccaaaaaaaaaaccccaaaaaacccccccccaaaaaaaaaaaaaacaaaaaaaaaaaaaacaaaaaaaaccccccccccaaaaaacccaaacccccccccccccccccaaaccccccccccccccaaaa
+abaaacaaaaacccccacccccccaaaaaccccccaaaaaaaaaaccccccaaaccccccccccaaaaaaaaacaaaaaaaaaaaaaaaaaaacccaaacaccaaaccccccaaaaaaaacaaacccccccccccaaccccaaacccccccccccccccaac
+abaaacaacaaaaccccccccccccccaaccccccacaaaaacccccaacccccccccccccccaaaacaaaaaaaaaacccaacccaaacaacccaaccccaaaaccccccccaacaaaaaaaaaaccccccccaaaaccaaaccccccccccccccaaac
+abaaccaaccaaacacccccccccccccccccccccccaaaacccaaaaaaccaaaccccccccccaacaaaaaaaaaacccaaccccccccccccccccccaaaaccccccccccccaaaaaaaaaccccccciiiiiaaaaacccccccccccccccccc
+abaaccccaaaaaaaacccccccccccccccccccccccaaccccaaaaaaccaaaaaccccacccaaccaaacaaaaacccccccccccccccaacccccccaaaccccccccccccccaaaaacccccccciiiiiiiiaaaaaccccccaaaccccccc
+abaaacccaaaaaaaacccccccccccccccccccccccccccccaaaaaacaaaaaccccaaaaaaaccaaccaaacccccccaaaaacacccaaccccccccccaacccccccccccaaaaaaccccccciiiiiiiiijjaaaaaccccaaacaccccc
+abaaaccccaaaaaaccccccccccccccccccccaaccccccccaaaaaccaaaaacccccaaaaaaaaccccccccccccccaaaaaaaaaaaaccccccccccaaacaaccccccaaaaaaaccccccciiinnnnoijjjjjjjjjjaaaaaaacccc
+abccccccccaaaaacccccaacccccccccccaaaacccccccccaaaacccaaaaaccccaaaaaaaaacccccccccccccaaaaaaaaaaaaaaccccccccaaaaaacccaacaaacaaacccccchhinnnnnoojjjjjjjjjkkaaaaaacccc
+abcccccccaaaaaacaaacaacccccccccccaaaaaaccccccccccccccaacccccccaaaaaaaaacaaccccccccccaaaaaaaaaaaaaaacccccaaaaaaacccaaaaccccccacaaccchhinnnnnoooojjjjjjkkkkaaaaccccc
+abaacccaccaaaccccaaaaaccccccccccccaaaaccccccccccccccccccccccccaaaaaaaacaaaaaaaccccccaaaaaaaaaaaaaaacccccaaaaaaacccaaaaccccaaacaaachhhnnntttuooooooooppkkkaaaaccccc
+abaacccaaaaaaaccccaaaaaacccccccccaaaaaccccccccccccccccccccccccaaaaaaacccaaaaacccccccccaaacaaaaaaaaccccccccaaaaacccaaaacccccaaaaacchhhnnnttttuooooooppppkkkaaaccccc
+abaacccaaaaaaccccaaaaaaacccccccccaacaaccccccccccccccccccccccaaaccaaaccaaaaaaacccccccccccccaaaaaaaccccccaacaacaaacccccccccccaaaaaahhhhnntttttuuouuuuupppkkkcccccccc
+abaaaacaaaaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaacccaaacaaaaaaaaccccccccccccaccaaaccccccaaacaaccccccccccccccaaaaaahhhhnnntttxxxuuuuuuupppkkkcccccccc
+abaaaacaaaaaaaaaaacaaacccaaacccccccccccccccccccccacccccccccaaaacccccccaaaaaaaaccccccccccccccccaaacccccaaacaaacccccccccccccaaaaaahhhhmnnttxxxxuuyuuuuuppkkkcccccccc
+abaaaccaaaaaaaaccccaaaccccaaaccacccccccccccaaaaaaaaccccccccaaaacccccccccaaacaacccccccccccccccccccccaaaaaaaaaacccccacccccccaacaghhhmmmmtttxxxxxxyyyuupppkkccccccccc
+abaaccaaaaaaaccccccccccccaaaaaaaacccccccccccaaaaaaccccccccccccccccccccccaaccccccaacccccccccccccccccaaaaaaaaacccccaaccccccccccagggmmmmttttxxxxxyyyyvvppkkkccccccccc
+abaacccaccaaacccccccccccaaaaaaaaccccccccccccaaaaaaccccccccccccccccccccccccccaaacaaaccccccccccccccccccaaaaaccccaaaaacaacccccccgggmmmmttttxxxxxyyyyvvpppiiiccccccccc
+SbaaaaaccccaaccccccccccaaaaaaaaacacccccccccaaaaaaaacccccccccccccccaacccccccccaaaaaccccccccccaaaacccccaaaaaacccaaaaaaaaccaaaccgggmmmsssxxxEzzzzyyvvvpppiiiccccccccc
+abaaaaaccccccccccccccccaaaaaaaaaaaaaaaaaccaaaaaaaaaacccccccccccaaaaacccccccccaaaaaaaccccccccaaaaaccccaaaaaaaccccaaaaacccaaaaagggmmmsssxxxxxyyyyyyvvqqqiiiccccccccc
+abaaaaacccccccccccccccccaaaaaaaacaaaaaacccaaaaaaaaaaccccccccccccaaaaacccccccaaaaaaaacccccccaaaaaaccccaaacaaacccaaaaacccaaaaaagggmmmssswwwwwyyyyyyyvvqqqiiicccccccc
+abaaaaccccccccccccccccccccaaaaaaaaaaaaacccacacaaacccccccccccccccaaaaacccccccaaaaaaaacccccccaaaaaaccccacccccccccaacaaaccaaaaaagggmmmsssswwwwyyyyyyyvvvqqiiicccccccc
+abaaaaacccccccccccccccccccaacccaaaaaaaaaccccccaaaccccccccccccccaaaaaccccccccaacaaacccccccccaaaaaacccccccccccccccccaaccccaaaaagggmmmmssssswwyywwvvvvvvqqiiicccccccc
+abaaaaaccccccccccccccccccaaacccaaaaaaaaaacccccaaaccccccaacccccccccaaccaaccccccaaaacaccccaacccaacccccccccccccccccccccccccaaaaccggglllllssswwwywwwvvvvqqqiiicccccccc
+abaccccccccccccccccccccccccccccaaaaaaaaaaccccaaaacccaaaacccccccccccccaaaccccccaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccffffllllsswwwwwwrrqvqqqqiiicccccccc
+abccccccccccccccccccccccccccccccccaaacacaccccaaaacccaaaaaacccccccccaaaaaaaaccccaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccfffflllssrwwwwrrrqqqqqqjjicccccccc
+abcccccccaaaccccccccaaccccccccccccaaacccccccccaaaccccaaaaacccccccccaaaaaaaaccaaaaaaacaaaaaaacccccccccccccccccccccccccccccccccccccfffflllrrwwwrrrrqqqqjjjjjcccccccc
+abaaaccaaaaacccccccaaacaaccccccccccaacccccccccccccccaaaaacccccccccccaaaaaacccaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccccccccccffffllrrrrrrrkjjjjjjjjjcccaccccc
+abaaaccaaaaaacccccccaaaaacaacaaccccccccccccccccccccccccaacccccccccccaaaaaacccaaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccccccfffllrrrrrrkkjjjjjjjcccccaccccc
+abaaaccaaaaaacccccaaaaaaccaaaaacccccccccccccccccccccccccccccccccccccaaaaaacccccaaacaaaaaaacccccccccccccccccccccccccccccccccccccccccfffllkkrrrkkkjjddcccccccaaacccc
+abaaaccaaaaaccccccaaaaaaaacaaaaaccccccccccccccccccccccccccccccccccccaaacaacccccaaaccccccaaaaccccaaaccccccccccccccccaaaccccccccccccccfeekkkkkkkkkdddddccccaaaaacccc
+abaaacccaaaaccccccaacaaaaaaaaaaaccccccccccccccccccccccccccccccccccccccaacaacccccccccccccccaaccccaaaacccccccccccccccaaaacccccccccccccceeekkkkkkdddddddcccaaacaccccc
+abaccccccccccccccccccaacccaaaaccccccccccccccccccccccccccccaaccaaccaacccaaaaccccccccccccaaaaaaaacaaaacccccccccccccccaaaacccaaaaacccccceeeekkkkdddddaaccccaacccccccc
+abccccccccccccccccccaaccccccaaccccccccccccaaacccccccccccccaaaaaaccaaaacaaaaacccccccccccaaaaaaaacaaaccccccccccccccccaaaacccaaaaaccccccceeeeeeedddcacacccccccccccccc
+abccccccccccccccccccccccccccccccccccccccccaaaacaacccccccccaaaaacccaaaaaaaaaaccccccccccccaaaaaacccccccccccccccccccccccccccaaaaaacccccccaeeeeeeddcccccccccccccccaaac
+abccccccccccccccccccccccccccccccccccccccccaaaaaaacccccccccaaaaaaccaaaaaaaacaccccccaaacaaaaaaaacccccccccccccccccccccccccccaaaaaacccccccccceeeeaaccccccccccccccccaaa
+abcccccccccccccccccccccccccccccccccccccccccaaaaaaccccccccaaaaaaaaccaaaaaaaccccccccaaaaaaaaaaaacccccccccccccccccccccccccccaaaaaacccccccccccccaaaccccccccccccccccaaa
+abccccccccccccccccccccccccccccccccccccccaaaaaaaaccccaaaccaaaaaaaacaaaaaaaaaacccccccaaaaaaaccaacccccccccccccccccccccccccccccaacccccccccccccccaaaccccccccccccccaaaaa
+abccccccccccccccccccccccccccccccccccccccaaaaaaaaacccaaaaccccaaccaaaaaaaaaaaaaccccaaaaaaaaaacccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccaaaaaa
diff --git a/2022/12-hill-climbing-algorithm/second.zig b/2022/12-hill-climbing-algorithm/second.zig
new file mode 100644
index 0000000..4340609
--- /dev/null
+++ b/2022/12-hill-climbing-algorithm/second.zig
@@ -0,0 +1,93 @@
+const std = @import("std");
+
+const example = @embedFile("example");
+const input = @embedFile("input");
+
+pub fn main() anyerror!void {
+    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
+    defer arena.deinit();
+    const allocator = arena.allocator();
+
+    try std.testing.expectEqual(try solve(example, allocator), 29);
+    const result = try solve(input, allocator);
+    try std.io.getStdOut().writer().print("{}\n", .{result});
+}
+
+const Node = struct {
+    x: u8,
+    y: u8,
+    cost: ?u64,
+    value: u8,
+    fn evalAndAdd(e: *Node, n: *Node, nq: *std.PriorityQueue(*Node, void, lesserThan)) !void {
+        if (e.cost == null and n.value <= e.value + 1) {
+            e.cost = n.cost.? + 1;
+            try nq.add(e);
+        }
+    }
+};
+
+fn lesserThan(context: void, a: *Node, b: *Node) std.math.Order {
+    _ = context;
+    return std.math.order(a.cost.?, b.cost.?);
+}
+
+fn solve(puzzle: []const u8, allocator: std.mem.Allocator) !u64 {
+    var it = std.mem.tokenize(u8, puzzle, "\n");
+    var grid = std.ArrayList(std.ArrayList(Node)).init(allocator);
+    var Sx: u8 = undefined;
+    var Sy: u8 = undefined;
+    var Ex: u8 = undefined;
+    var Ey: u8 = undefined;
+    // process input
+    var y: u8 = 0;
+    var line = it.next() orelse unreachable;
+    const width = line.len;
+    while (true) : (line = it.next() orelse break) {
+        var l = try grid.addOne();
+        l.* = try std.ArrayList(Node).initCapacity(allocator, width);
+        var x: u8 = 0;
+        while (x < line.len) : (x += 1) {
+            var n = l.*.addOneAssumeCapacity();
+            n.*.x = x;
+            n.*.y = y;
+            n.*.cost = null;
+            n.*.value = switch (line[x]) {
+                'S' => blk: {
+                    Sx = x;
+                    Sy = y;
+                    break :blk 'a';
+                },
+                'E' => blk: {
+                    Ex = x;
+                    Ey = y;
+                    n.*.cost = 0;
+                    break :blk 'z';
+                },
+                else => line[x],
+            };
+        }
+        y += 1;
+    }
+    const height = grid.items.len;
+    // find shortest path
+    var nq = std.PriorityQueue(*Node, void, lesserThan).init(allocator, {});
+    try nq.add(&grid.items[Ey].items[Ex]);
+    while (true) {
+        var n = nq.remove();
+        if (n.value == 'a') {
+            return n.cost.?;
+        }
+        if (n.x > 0) {
+            try grid.items[n.y].items[n.x - 1].evalAndAdd(n, &nq);
+        }
+        if (n.x < width - 1) {
+            try grid.items[n.y].items[n.x + 1].evalAndAdd(n, &nq);
+        }
+        if (n.y > 0) {
+            try grid.items[n.y - 1].items[n.x].evalAndAdd(n, &nq);
+        }
+        if (n.y < height - 1) {
+            try grid.items[n.y + 1].items[n.x].evalAndAdd(n, &nq);
+        }
+    }
+}