day8

4 files changed, 155 insertions, 0 deletions

diff --git a/day08/example1.txt b/day08/example1.txt
new file mode 100644
index 0000000..9029a1b
--- /dev/null
+++ b/day08/example1.txt
@@ -0,0 +1,9 @@
+RL
+
+AAA = (BBB, CCC)
+BBB = (DDD, EEE)
+CCC = (ZZZ, GGG)
+DDD = (DDD, DDD)
+EEE = (EEE, EEE)
+GGG = (GGG, GGG)
+ZZZ = (ZZZ, ZZZ)
diff --git a/day08/example2.txt b/day08/example2.txt
new file mode 100644
index 0000000..7d1b58d
--- /dev/null
+++ b/day08/example2.txt
@@ -0,0 +1,5 @@
+LLR
+
+AAA = (BBB, BBB)
+BBB = (AAA, ZZZ)
+ZZZ = (ZZZ, ZZZ)
diff --git a/day08/example3.txt b/day08/example3.txt
new file mode 100644
index 0000000..5b3fa58
--- /dev/null
+++ b/day08/example3.txt
@@ -0,0 +1,10 @@
+LR
+
+11A = (11B, XXX)
+11B = (XXX, 11Z)
+11Z = (11B, XXX)
+22A = (22B, XXX)
+22B = (22C, 22C)
+22C = (22Z, 22Z)
+22Z = (22B, 22B)
+XXX = (XXX, XXX)
diff --git a/day08/solution.zig b/day08/solution.zig
new file mode 100644
index 0000000..75e6e73
--- /dev/null
+++ b/day08/solution.zig
@@ -0,0 +1,131 @@
+const std = @import("std");
+const print = std.debug.print;
+const assert = std.debug.assert;
+const ArrayList = std.ArrayList;
+const HashMap = std.HashMap;
+const mem = std.mem;
+
+const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
+var gpa = std.heap.GeneralPurposeAllocator(.{}){};
+const allocator = gpa.allocator();
+
+const Rule = struct {
+    key: u32,
+    left: u32,
+    right: u32,
+
+    pub fn endsWith(key: u32, e: u8) bool {
+        return key & 0b1111_1111 == e;
+    }
+
+    pub fn hash(s: []const u8) u32 {
+        assert(s.len == 3);
+        return s[2] | (@as(u32, s[1]) << 8) | (@as(u32, s[0]) << 16);
+    }
+
+    pub fn init(text: []const u8) Rule {
+        var splitTokens = mem.splitAny(u8, text, " =(),");
+        var nonEmpty = [3]u32{ undefined, undefined, undefined };
+        var i: usize = 0;
+
+        while (splitTokens.next()) |tok| {
+            if (tok.len != 3) {
+                continue;
+            }
+            nonEmpty[i] = hash(tok);
+            i += 1;
+        }
+
+        assert(i == 3);
+
+        return Rule{
+            .key = nonEmpty[0],
+            .left = nonEmpty[1],
+            .right = nonEmpty[2],
+        };
+    }
+};
+
+const RuleCtx = struct {
+    pub fn hash(_: @This(), K: u32) u64 {
+        return K;
+    }
+
+    pub fn eql(_: @This(), K1: u32, K2: u32) bool {
+        return K1 == K2;
+    }
+};
+
+const RuleMap = HashMap(u32, Rule, RuleCtx, 80);
+
+fn evaluate(instructions: []const u8, rules: RuleMap, start: u32, isPart1: bool) u64 {
+    const zzz = Rule.hash("ZZZ");
+    var curr = start;
+    var steps: u64 = 0;
+
+    while (if (isPart1) (curr != zzz) else !Rule.endsWith(curr, 'Z')) : (steps += 1) {
+        const in = instructions[steps % instructions.len];
+
+        curr = switch (in) {
+            'L' => rules.get(curr).?.left,
+            'R' => rules.get(curr).?.right,
+            else => unreachable,
+        };
+    }
+
+    return steps;
+}
+
+pub fn part1(instructions: []const u8, rules: RuleMap) void {
+    const ans = evaluate(instructions, rules, Rule.hash("AAA"), true);
+
+    print("{d}\n", .{ans});
+}
+
+fn gcd(a_: u64, b_: u64) u64 {
+    var a = a_;
+    var b = b_;
+    while (a != b) {
+        if (a > b) {
+            a -= b;
+        } else {
+            b -= a;
+        }
+    }
+    return a;
+}
+
+fn lcm(a: u64, b: u64) u64 {
+    return a / gcd(a, b) * b;
+}
+
+pub fn part2(instructions: []const u8, rules: RuleMap) void {
+    var ans: u64 = 1;
+    var keyIt = rules.keyIterator();
+
+    while (keyIt.next()) |k| {
+        if (Rule.endsWith(k.*, 'A')) {
+            const steps = evaluate(instructions, rules, k.*, false);
+
+            ans = lcm(ans, steps);
+        }
+    }
+
+    print("{d}\n", .{ans});
+}
+
+pub fn main() !void {
+    var splitLines = mem.splitScalar(u8, fin, '\n');
+    var rules = RuleMap.init(allocator);
+
+    var instructions = splitLines.next().?;
+    _ = splitLines.next();
+
+    while (splitLines.next()) |line| {
+        const R = Rule.init(line);
+        try rules.put(R.key, R);
+    }
+
+    part1(instructions, rules);
+    part2(instructions, rules);
+}