add day 12

3 files changed, 168 insertions, 0 deletions

diff --git a/day_12.zig b/day_12.zig
new file mode 100644
index 0000000..57a69bb
--- /dev/null
+++ b/day_12.zig
@@ -0,0 +1,126 @@
+const std = @import("std");
+const Result = @import("util/aoc.zig").Result;
+
+const Point = struct { row: i32, col: i32, count: u16 = 0 };
+
+const Movements = [_]Point{
+    .{ .row = 0, .col = -1, .count = 0 },
+    .{ .row = -1, .col = 0, .count = 0 },
+    .{ .row = 1, .col = 0, .count = 0 },
+    .{ .row = 0, .col = 1, .count = 0 },
+};
+
+fn parse(allocator: std.mem.Allocator, input: []const u8) [][]u8 {
+    var grid = std.ArrayList([]u8).init(allocator);
+
+    var iter = std.mem.split(u8, input, "\n");
+    while (iter.next()) |line| {
+        var row = std.ArrayList(u8).initCapacity(allocator, line.len) catch unreachable;
+        for (line) |char| row.append(char) catch unreachable;
+        grid.append(row.toOwnedSlice() catch unreachable) catch unreachable;
+    }
+
+    return grid.toOwnedSlice() catch unreachable;
+}
+
+fn parse_free(allocator: std.mem.Allocator, grid: [][]u8) void {
+    for (grid) |row| allocator.free(row);
+    allocator.free(grid);
+}
+
+fn bfs(allocator: std.mem.Allocator, grid: [][]const u8, start: Point, end: Point) u16 {
+    var visited = std.AutoHashMap([2]i32, bool).init(allocator);
+    defer visited.deinit();
+    var queue = std.ArrayList(Point).init(allocator);
+    defer queue.deinit();
+
+    queue.append(start) catch unreachable;
+
+    while (queue.items.len > 0) {
+        const point = queue.orderedRemove(0);
+
+        if (visited.contains([_]i32{ point.row, point.col }))
+            continue;
+
+        if (point.row == end.row and point.col == end.col)
+            return point.count;
+
+        visited.put([_]i32{ point.row, point.col }, true) catch unreachable;
+
+        for (Movements) |m| {
+            const p = Point{
+                .row = point.row + m.row,
+                .col = point.col + m.col,
+                .count = point.count + 1,
+            };
+
+            if (!(p.row >= 0 and p.col >= 0 and p.row < grid.len and p.col < grid[0].len)) continue;
+            if (visited.contains([_]i32{ p.row, p.col })) continue;
+            if (grid[@intCast(usize, point.row)][@intCast(usize, point.col)] != 'S' and grid[@intCast(usize, p.row)][@intCast(usize, p.col)] != 'E')
+                if (grid[@intCast(usize, p.row)][@intCast(usize, p.col)] > (grid[@intCast(usize, point.row)][@intCast(usize, point.col)] + 1)) continue;
+
+            queue.append(p) catch unreachable;
+        }
+    }
+
+    return @intCast(u16, grid.len * grid[0].len);
+}
+
+pub fn puzzle_1(allocator: std.mem.Allocator, input: []const u8) Result {
+    const grid = parse(allocator, input);
+    defer parse_free(allocator, grid);
+
+    var start: ?Point = null;
+    var end: ?Point = null;
+
+    outLoop: for (grid) |row, x| {
+        for (row) |c, y| {
+            if (c == 'S') {
+                grid[x][y] = 'a';
+                start = Point{ .row = @intCast(i32, x), .col = @intCast(i32, y) };
+            }
+
+            if (c == 'E') {
+                grid[x][y] = 'z';
+                end = Point{ .row = @intCast(i32, x), .col = @intCast(i32, y) };
+            }
+
+            if (start != null and end != null)
+                break :outLoop;
+        }
+    }
+
+    return .{ .int = bfs(allocator, grid, start.?, end.?) };
+}
+
+pub fn puzzle_2(allocator: std.mem.Allocator, input: []const u8) Result {
+    const grid = parse(allocator, input);
+    defer parse_free(allocator, grid);
+
+    var start_points = std.ArrayList(Point).init(allocator);
+    defer start_points.deinit();
+
+    var distance = @intCast(u16, grid.len * grid[0].len);
+    var end: Point = undefined;
+
+    for (grid) |row, x| {
+        for (row) |c, y| {
+            if (c == 'a' or c == 'S') {
+                start_points.append(Point{ .row = @intCast(i32, x), .col = @intCast(i32, y) }) catch unreachable;
+            }
+
+            if (c == 'S') {
+                grid[x][y] = 'a';
+            }
+
+            if (c == 'E') {
+                grid[x][y] = 'z';
+                end = Point{ .row = @intCast(i32, x), .col = @intCast(i32, y) };
+            }
+        }
+    }
+
+    for (start_points.items) |start| distance = std.math.min(distance, bfs(allocator, grid, start, end));
+
+    return .{ .int = distance };
+}
diff --git a/inputs/day_12 b/inputs/day_12
new file mode 100644
index 0000000..c2ec0e6
--- /dev/null
+++ b/inputs/day_12
@@ -0,0 +1,41 @@
+abccccccccccccccccccccaaaaaaaacccccccccccccaacaaaaacccccccccccccccccccccaaaaaacccccaaaaaccccccccccccccccccccaaaccccccccccccccccccccccccccccccccccccccccccccccccccccccccccaaaa
+abcccccccccccccccccccaaaaaaaaacccccccccccccaaaaaaaaccccccccccccccaacccccaaaaaaaaaaaaaaaaccccccccccccccccccccaaaccccccccccccccccccccccccaccaccccccccccccccccccccccccccccaaaaaa
+abccccccccccccccccccaaaaaaaaaacccccaacccccccaaaaaccccccccccccccaaaaaacccaaaaaaaaaaaaaaaaccccccccccccccccccaacaaaaacccccccccccccccccccccaaaaccccccccccccccccccccccccccccaaaaaa
+abccccccccccaaacaaacaaacaaacccccacaaaccccccccaaaaacccccccccccccaaaaaacaaaaaaaaaaaaaaaaaaccccccccccccccccccaaaaaaaaccccccccccccccccccccaaaaaccccccccaaaccccaaaccccccccccaaacaa
+abccccccccaaaaaccaaaaaccaaaccccaaaaaaaacccccaaacaaccccccccccccccaaaaccaaaaaaaaccccaaaaaacccccccccccccccccccaaaaaccccccccccccccccccccccaaaaaacccccccaaaacccaaaccccccccccccccaa
+abccccccccaaaaaaccaaaaaaaaaaaccaaaaaaaaccccccaacccccccccccccccccaaaacaaaacaaaacccccaaacccccccaacaaccccccccccaaaaacccaaccccccccccccccccaaaaaaccccccccaaaaaaaacccccccccccccccaa
+abccccccccaaaaaaaaaaaaaaaaaaacccaaaaaaccccccccccccccccccccccccccaccaccccccaaaaaccccccccccccccaaaaacccccccccaaacaacaaaaaaccccccccccccccccaacccccccckkkkkkaaaaccccccccccccccccc
+abccccccccaaaaacaaaaaccaaaaaaaacaaaaaccccccccccccccccccccccccccccccccccccccaaaccccccccccccccccaaaaacccccccccaaccccaaaaaaccccccccccccccccccccccccckkkkkkklaaccccccccaacccccccc
+abccccccccaaaaacaacaaacaaaaaaaacaaaaaacccccccccccccccccccccaacccccccccccccccaaaccccccccccccccaaaaaacccccccccccccccaaaaaacccccccccccccccccccccccckkkkkkkklllccccccccccaaaacccc
+abcaaccccccccccccccaaaccaaaaaaaccccaaccccccccccccccccccaaccaacccccccccccccccccccaacccccccccccaaaacccccccccccccccccaaaaacccccccaaaacccccccccccccckkkoppppllllllccccccccaaccccc
+abcaacccccccccccccccccccaaaaaccccccccccccccccccccccccccaaaaaacccccccccccccccccaaaaaacccccccccccaaccccccccccccccccccaaaacccccccaaaaacccccccccccckkkooppppplllllllllccccdaccccc
+abaaaccccccaaacccccccccaaaaaaccccccccaaaccccccccccccccccaaaaaaacccccccccccccccaaaaaacccccccccccccccccccccccccccccccccccccccccaaaaaaccccccccccccjkoooopuppplllllllmmmddddacccc
+abaaaaaccccaaaaacccccccccccaaaaacccccaaaaccccccccccccccccaaaaaaccccccccccccccccaaaacccccccccccccccccaaaccccccccccccccccccccccaaaaaacccccccccccjjjooouuuuppppppqqmmmmmdddacccc
+abaaaaacccaaaaaacccaacaaacccaaaaaacccaaaacccccccccccccccaaaaaccccccccccaaccccccaaaaccccccaacccccacccaaccccccccccaacaaccccccccaaaaaacccaaaccccjjjjoouuuuuuppppqqqqqmmmdddacccc
+abaaccacccaaaaaacccaaaaaacccaaaaaacccaaacccccccccccccccaaaaaaccccccccaaaaaaccccaccacccccaaaacccaaaaaaaccccccccccaaaaaccccccccccaacacccaaccccjjjjooouuuxuuupppqqqqqmmmdddccccc
+abaaaccccccaaaaacccaaaaaacccaaaaaccccccccccccccccccccccccccaaccccccccaaaaaacccccccccccccaaaaccccaaaaaaaaccccccccaaaaaaccccccccccccaaaaaaacjjjjjoooouuxxxuuvvvvvvqqqmmdddccccc
+abaaaccccccaacaacccaaaaaaacccaaaaacccccccccccccccaaacccccccccccccccccaaaaaccccaaacccccccaaaaccccaaaaaaaaacccccccaaaaaaccccccccccccaaaaaacjjjjjoooouuuxxxuuvvvvvvqqqmmdddccccc
+abccccccccccccccccaaaaaaaacccaaaaacccccccccccccccaaaccccccccccccccccccaaaaacccaaacacccccccccccccaaaaaaaaacccccccaaaaaccccccaacccccaaaaaaajjjnoooottuuxxxxvyyyvvvqqmmmdddccccc
+abccccccccccccccccaaaaaaaacccccccccccccccccaaaaaaaaaccaaccccccccccccccaaaaacaacaaaaaccccccccccccaaaaaaaaccccccccccaaacccccaaaaccccaaaaaajjjnnnntttttxxxxyyyyyvvvqqmmmdddccccc
+abccccccaaaccccccccccaaacccaaccccccccccccccaaaaaaaaaaaaaaaccccccccaaacccccccaaaaaaaacccccccccccaaaaaaaaccccccccccccaacccccaaaaacacaaaaaaiiinnntttxxxxxxxyyyyyvvqqqmmdddcccccc
+SbccccccaaaaaccccccccaaccccaaaccccccccccccccaaaaaaaaaaaaaacccccccaaaaaaccccccaaaaaccccccccacccaaaccaaacccccccccaaacaaccaaaaaaaaaaaaaaaaaiiinnntttxxxEzzzzyyyvvqqqmmmeeecccccc
+abcccccaaaaaacccccccccccaaaaaaaaccccccccccccaaaaaaaaaaaaaccccccccaaaaaacccccccaaaaacccccccaacaaaccccaaacccccccccaaaaaccaaaaaaaaaacaccaaaiiinnntttxxxxxyyyyyvvvqqqnnneeecccccc
+abaacccaaaaaacccccccccccaaaaaaaaccccaaaccccaaaaaaaaaaaaaaacccccccaaaaaccccccccaacaaaaaccccaaaaacccccccccccccccccaaaaaaaccaaaaaacccccccaaiiinnnttttxxxxyyyyyyvvvrrnnneeecccccc
+abaaaaaaaaaaaccccccccccccaaaaaaccccaaaacccaaaaaaaaaaaaacaaccccccccaaaaacccccccaaccccaaaacccaaaaaacaacaaccccccccaaaaaaaaccaaaaaaccccccccciiiinnnttttxxwyywyyyyvvrrrnneeecccccc
+abaaaaacaacaaccccccccccccaaaaaaccccaaaacccaaacaaaacaaaccccccccccccaacaaccccaacccccaaaaaacaaaaaaaacaaaaacccccaaaaaaaaaaaccaaaaaacccccccccciiiinnnttttwwyywwywwwvrrrnneeecccccc
+abaaaacccccccccccccccccccaaaaaacccccaaacccccccaaacccacaaccccccccccccccccccaaccccccaaaaaccaaaaaaaaaaaaaccccccaaaaaaaaacccaaaaaaaacccccccccciiinnnnntswwywwwwwwwwrrrnnneecccccc
+abaaaaaccccccccccccccccccaacaaacccccccccccccccaacaaacaaacccccccccccccccaaaaacaaccccaaaaaccccaacccaaaaaacccccaaacaaaaaccccacccccccaaacccccciiiiinnmsswwwwwswwwwrrrrnnneecccccc
+abaaaaaaccaaaccccccccccccccccccccccccccccccccccccaaaaaaaccccccccaaaccccaaaaaaaaccccaaccaccccaacccccaaaaccaaaaaaaaaaccccccccccccccaaaaacccccciihmmmsswwwwssrrrrrrrrnnneecccccc
+abaaccaacaaaaccccccccccccccccccccccccccccccccccccaaaaaacccccccccaaaaaccccaaaaacccccccccccccccccccccacccccaaaaaaaaacccccccaaccaacaaaaacccccccchhhmmssswwsssrrrrrrrnnneeecccccc
+abaacccccaaaacccccccccccccccccccccccccccccccccccccaaaaaaaacccccaaaaaacccaaaaacccccccccccccccccccccccccccccaaaaaaaccccccccaaaaaacaaaaacccccccchhhmmssssssslllllllnnnnfeecccccc
+abccccccccaaacccccccccccccccaaccccccccccccccaaaccaaaaaaaaacccccaaaaaacccaacaaaccccccccccccccccccccccccaacccaaaaaaccccccccaaaaacccaaaaaccccccchhhmmmssssslllllllllnnfffeaacccc
+abcccccccccccccccccccccccacaaaccccccccccccccaaaaaaaaaaaaaaccaaccaaaaaccccccaaccaacccccccccccccccccccccaaaccaaaaaaacccccccaaaaaaccaaccccccccccchhhmmmmsmllllllllllfffffaaacccc
+abccccccccccccccccccccccaaaaaaaaccccccccccccaaaaaaacaaacaaaaaaccaaaaccccccccccaaaacccccccccccccccccaaaaaaaaaaacaaaccccccaaaaaaaacccccccccccccchhhmmmmmmlllggfffffffffaacccccc
+abccccccccccccccccccccccaaaaaaaaccccccccccccaaacccccaaacaaaaacccccccccccaaacccaaaacccccccccccccccccaaaaaaaaaacccccccccccaaaaaaaaccccccccccccccchhhmmmmmlggggffffffffaaacccccc
+abccccccccccccccccaaaacccaaaaaacccccccccccccccccccccaaacaaaaaaccccccccccaaacccaaaaccccccacccccccccccaaaaaacccccccccccccccccaacccaaccccccccccccchhhhgmgggggggffaccccccaacccccc
+abccccccccccccccccaaaacccaaaaacccccccccccccccccccccccccaaaaaaaacccccccccaaaaccaaacccccccaaacaaacccccaaaaaacccccccccccccccccaaccaaccccccccccccccchhhgggggggaaaaacccccccccccccc
+abccccccccccccccccaaaacccaaaaaaccccccccccccccccccccccccaaaaaaaaccccccccccaaaaaaaaaccccccaaaaaaacccccaaaaaaccccccccccccccccccaaaaacaaccccccccccccchggggggaacccccccccccccccccca
+abcccccccccccccccccaacccccccaaccccccccccccccccccccccccccccaacaccaaacccaacaaaaaaaacccccccaaaaaaccccccaaccaacaaaccacccccaaccccaaaaaaaaccccccccccccccccccaaaccccccccccccccccccca
+abcccccaaccccccccccccccccaaccccccccaacccccccccaaacccccccccaacaaaaaacccaaacaaaaaacccccccaaaaaaacccccccccccccaaaaaacccaaaaccccccaaaaaccccaaacccccccccccccaaccccccccccccccaaaaaa
+abccccaaaacccccccccccccccaaaacccaaaaccccccccccaaaacccccccccccaaaaaaccaaaaaaaaaacccccccaaaaaaaaaaccccccccccccaaaaacccaaaaaacccaaaaacccccaaaacccccccccccaaccccccccccccccccaaaaa
+abccccaaaacccccccccccccaaaaaacccaaaaaaccccccccaaaaccccccccccaaaaaaaacaaaaaaaaaaaaaccccaaaaaaaaaaccccccccccaaaaaaaacccaaaaccccaacaaaccccaaaacccccccccccccccccccccccccccccaaaaa
diff --git a/main.zig b/main.zig
index cb602a5..3459ba5 100644
--- a/main.zig
+++ b/main.zig
@@ -17,6 +17,7 @@ const t = [_]struct {
     .{ .day = @import("day_09.zig"), .input = @embedFile("inputs/day_09"), .expect = &[_]Result{ .{ .int = 6087 }, .{ .int = 2493 } } },
     .{ .day = @import("day_10.zig"), .input = @embedFile("inputs/day_10"), .expect = &[_]Result{ .{ .int = 14620 }, .{ .int = 4210 } } },
     .{ .day = @import("day_11.zig"), .input = @embedFile("inputs/day_11"), .expect = &[_]Result{ .{ .int = 108240 }, .{ .int = 25712998901 } } },
+    .{ .day = @import("day_12.zig"), .input = @embedFile("inputs/day_12"), .expect = &[_]Result{ .{ .int = 490 }, .{ .int = 488 } } },
 };
 
 pub fn main() !void {