day3

1 files changed, 138 insertions, 0 deletions

diff --git a/day03/solution.zig b/day03/solution.zig
new file mode 100644
index 0000000..b98260a
--- /dev/null
+++ b/day03/solution.zig
@@ -0,0 +1,138 @@
+const std = @import("std");
+const print = std.debug.print;
+const assert = std.debug.assert;
+const ArrayList = std.ArrayList;
+const mem = std.mem;
+const isDigit = std.ascii.isDigit;
+const Self = @This();
+
+const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
+var gpa = std.heap.GeneralPurposeAllocator(.{}){};
+const allocator = gpa.allocator();
+const MapOfNumDesc = std.HashMap(NumDesc, void, NumDescCtx, 80);
+
+const NumDesc = struct {
+    i: u64,
+    left: u64,
+    right: u64,
+};
+
+const NumDescCtx = struct {
+    pub fn hash(self: @This(), K: NumDesc) u64 {
+        _ = self;
+        return K.left | (K.right << 32);
+    }
+
+    pub fn eql(self: @This(), K1: NumDesc, K2: NumDesc) bool {
+        _ = self;
+        // Checking .i and .left can uniquely identify the number in the grid
+        return K1.i == K2.i and K1.left == K2.left;
+    }
+};
+
+fn isSymbol(c: u8) bool {
+    return c != '.' and !std.ascii.isDigit(c);
+}
+
+fn isGear(c: u8) bool {
+    return c == '*';
+}
+
+fn getNumberAt(map: ArrayList([]const u8), i: u64, j: u64) NumDesc {
+    var left: u64 = j;
+    var right: u64 = j;
+
+    // Lookahead checking to avoid dropping below 0
+    while (left > 0 and
+        isDigit(map.items[i][left - 1])) : (left -= 1)
+    {}
+
+    while (right < map.items.len and
+        isDigit(map.items[i][right])) : (right += 1)
+    {}
+
+    return NumDesc{
+        .i = i,
+        .left = left,
+        .right = right,
+    };
+}
+
+// Evaluated numbers are managed by the caller for more flexibility.
+// P1: Each number is only evaluated once
+// P2: Each number may be evaluated an arbitrary number of times
+fn findAdjacent(map: ArrayList([]const u8), i: u64, j: u64, evaluated: *MapOfNumDesc) ArrayList(u64) {
+    var surroundNums = ArrayList(u64).init(allocator);
+
+    for (@max(i - 1, 0)..@min(i + 2, map.items.len)) |ai| {
+        for (@max(j - 1, 0)..@min(j + 2, map.items[0].len)) |aj| {
+            if (!isDigit(map.items[ai][aj])) {
+                continue;
+            }
+            const p = getNumberAt(map, ai, aj);
+            const s = map.items[p.i][p.left..p.right];
+            const n = std.fmt.parseInt(u64, s, 10) catch unreachable;
+
+            if (evaluated.contains(p)) {
+                continue;
+            }
+            evaluated.put(p, undefined) catch unreachable;
+            surroundNums.append(n) catch unreachable;
+        }
+    }
+
+    return surroundNums;
+}
+
+fn part1(map: ArrayList([]const u8)) void {
+    var ans: u64 = 0;
+    var evaluated = MapOfNumDesc.init(allocator);
+    defer evaluated.deinit();
+
+    for (map.items, 0..) |line, i| {
+        for (line, 0..) |c, j| {
+            if (isSymbol(c)) {
+                const adj = findAdjacent(map, i, j, &evaluated);
+
+                for (adj.items) |adj_num| {
+                    ans += adj_num;
+                }
+            }
+        }
+    }
+
+    print("{d}\n", .{ans});
+}
+
+fn part2(map: ArrayList([]const u8)) void {
+    var ans: u64 = 0;
+    var evaluated = MapOfNumDesc.init(allocator);
+    defer evaluated.deinit();
+
+    for (map.items, 0..) |line, i| {
+        for (line, 0..) |c, j| {
+            if (isGear(c)) {
+                const adj = findAdjacent(map, i, j, &evaluated);
+                evaluated.clearRetainingCapacity();
+
+                if (adj.items.len == 2) {
+                    ans += adj.items[0] * adj.items[1];
+                }
+            }
+        }
+    }
+
+    print("{d}\n", .{ans});
+}
+
+pub fn main() !void {
+    var splitLines = mem.splitScalar(u8, fin, '\n');
+    var lines = ArrayList([]const u8).init(allocator);
+
+    while (splitLines.next()) |line| {
+        try lines.append(line);
+    }
+
+    part1(lines);
+    part2(lines);
+}