aoc2024: day 10

1 files changed, 123 insertions, 0 deletions

diff --git a/aoc24/src/day10.zig b/aoc24/src/day10.zig
new file mode 100644
index 0000000..3c63f1d
--- /dev/null
+++ b/aoc24/src/day10.zig
@@ -0,0 +1,123 @@
+const std = @import("std");
+
+const Input = [][]u4;
+
+const test_input =
+    \\89010123
+    \\78121874
+    \\87430965
+    \\96549874
+    \\45678903
+    \\32019012
+    \\01329801
+    \\10456732
+    \\
+;
+
+pub fn parse(allocator: std.mem.Allocator, data: []const u8) !Input {
+    var lines = std.mem.split(u8, data, "\n");
+    var rows = std.ArrayList([]u4).init(allocator);
+    while (lines.next()) |line| {
+        if (line.len == 0) break;
+        const row = try allocator.alloc(u4, line.len);
+        for (row, line) |*r, l| {
+            r.* = @intCast(l - '0');
+        }
+
+        try rows.append(row);
+    }
+    return rows.items;
+}
+
+test "part1" {
+    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
+    defer arena.deinit();
+
+    const output = try part1(arena.allocator(), try parse(arena.allocator(), test_input));
+    try std.testing.expectEqual(36, output);
+}
+
+pub fn part1(allocator: std.mem.Allocator, input: Input) !u32 {
+    const visited = try allocator.alloc([]u1, input.len);
+    for (visited) |*v| {
+        v.* = try allocator.alloc(u1, input[0].len);
+    }
+    var curr = std.ArrayList(@Vector(2, usize)).init(allocator);
+    var next = std.ArrayList(@Vector(2, usize)).init(allocator);
+
+    // for (input) |row| {
+    //     for (row) |cell| {
+    //         std.debug.print("{}", .{cell});
+    //     }
+    //     std.debug.print("\n", .{});
+    // }
+
+    var score: u32 = 0;
+    for (0.., input) |y, row| for (0.., row) |x, cell| {
+        if (cell != 0) continue;
+        for (visited) |v| @memset(v, 0);
+
+        curr.clearRetainingCapacity();
+        next.clearRetainingCapacity();
+        try curr.append(.{ x, y });
+        var height: u4 = 0;
+        while (curr.items.len > 0) {
+            for (curr.items) |pos| {
+                // std.debug.print("checking {}\n", .{pos});
+                if (height != input[pos[1]][pos[0]] or visited[pos[1]][pos[0]] == 1) continue;
+                visited[pos[1]][pos[0]] = 1;
+                if (height == 9) score += 1;
+                // left
+                if (pos[0] > 0) try next.append(.{ pos[0] - 1, pos[1] });
+                // up
+                if (pos[1] > 0) try next.append(.{ pos[0], pos[1] - 1 });
+                // right
+                if (pos[0] < input[0].len - 1) try next.append(.{ pos[0] + 1, pos[1] });
+                // down
+                if (pos[1] < input[0].len - 1) try next.append(.{ pos[0], pos[1] + 1 });
+            }
+            curr.clearRetainingCapacity();
+            std.mem.swap(@TypeOf(curr), &curr, &next);
+            height += 1;
+        }
+    };
+    return score;
+}
+
+test "part2" {
+    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
+    defer arena.deinit();
+
+    const output = try part2(arena.allocator(), try parse(arena.allocator(), test_input));
+    try std.testing.expectEqual(81, output);
+}
+
+pub fn part2(allocator: std.mem.Allocator, input: Input) !u32 {
+    var curr = std.ArrayList(@Vector(2, usize)).init(allocator);
+    var next = std.ArrayList(@Vector(2, usize)).init(allocator);
+
+    var score: u32 = 0;
+    for (0.., input) |y, row| for (0.., row) |x, cell| {
+        if (cell != 0) continue;
+
+        curr.clearRetainingCapacity();
+        next.clearRetainingCapacity();
+        try curr.append(.{ x, y });
+        var height: u4 = 0;
+        while (curr.items.len > 0) {
+            for (curr.items) |pos| {
+                if (height != input[pos[1]][pos[0]]) continue;
+                if (height == 9) score += 1;
+
+                if (pos[0] > 0) try next.append(.{ pos[0] - 1, pos[1] });
+                if (pos[1] > 0) try next.append(.{ pos[0], pos[1] - 1 });
+                if (pos[0] < input[0].len - 1) try next.append(.{ pos[0] + 1, pos[1] });
+                if (pos[1] < input[0].len - 1) try next.append(.{ pos[0], pos[1] + 1 });
+            }
+            curr.clearRetainingCapacity();
+            std.mem.swap(@TypeOf(curr), &curr, &next);
+            height += 1;
+        }
+    };
+    return score;
+}