From 2debf9a00ddabfd7a90952156745de87b0d7bdd0 Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Mon, 12 Dec 2022 15:14:12 +0100 Subject: 2022-12 in zig --- 2022/12-hill-climbing-algorithm/example | 5 ++ 2022/12-hill-climbing-algorithm/first.zig | 93 ++++++++++++++++++++++++++++++ 2022/12-hill-climbing-algorithm/input | 41 +++++++++++++ 2022/12-hill-climbing-algorithm/second.zig | 93 ++++++++++++++++++++++++++++++ 4 files changed, 232 insertions(+) create mode 100644 2022/12-hill-climbing-algorithm/example create mode 100644 2022/12-hill-climbing-algorithm/first.zig create mode 100644 2022/12-hill-climbing-algorithm/input create mode 100644 2022/12-hill-climbing-algorithm/second.zig 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); + } + } +} -- cgit v1.2.3