day 8 pt2

1 files changed, 208 insertions, 0 deletions

diff --git a/day8.zig b/day8.zig
new file mode 100644
index 0000000..831f751
--- /dev/null
+++ b/day8.zig
@@ -0,0 +1,208 @@
+const std = @import("std");
+pub const log_level: std.log.Level = .info;
+
+pub fn main() !void {
+    try std.fmt.format(std.io.getStdOut().writer(), "Day 8 pt1: {}\n", .{try solve_pt1(std.heap.page_allocator, puzzle_input)});
+    try std.fmt.format(std.io.getStdOut().writer(), "Day 8 pt2: {}\n", .{try solve_pt2(std.heap.page_allocator, puzzle_input)});
+}
+const NodeValue = struct {
+    left: []const u8,
+    right: []const u8,
+};
+
+fn solve_pt1(a: std.mem.Allocator, input: []const u8) !u64 {
+    var spl = std.mem.split(u8, input, "\n\n");
+    const instructions = spl.first();
+    const nodes_str = spl.next() orelse return error.NoNodes;
+    var spl2 = std.mem.split(u8, nodes_str, "\n");
+    var nodes = std.StringHashMap(NodeValue).init(a);
+    defer nodes.deinit();
+    while (spl2.next()) |node_line| {
+        var toks = std.mem.tokenize(u8, node_line, " (,)=");
+        const key = toks.next() orelse return error.NoKey;
+        const left = toks.next() orelse return error.NoLeft;
+        const right = toks.next() orelse return error.NoRight;
+        try nodes.putNoClobber(key, .{
+            .left = left,
+            .right = right,
+        });
+    }
+
+    var steps: u64 = 0;
+    var pos: []const u8 = "AAA";
+    while (!std.mem.eql(u8, pos, "ZZZ")) {
+        for (instructions) |inst| {
+            const node_value = nodes.get(pos).?;
+            pos = switch (inst) {
+                'R' => node_value.right,
+                'L' => node_value.left,
+                else => return error.InvalidDirection,
+            };
+            steps += 1;
+        }
+    }
+    return steps;
+}
+test "pt1" {
+    try std.testing.expectEqual(@as(u64, 6), try solve_pt1(std.testing.allocator, test_input));
+}
+const HistEntry = struct {
+    node: []const u8,
+    step: u64,
+};
+const Path = struct {
+    // current position
+    pos: []const u8,
+
+    // list of the _endpoints_ we have reached.
+    endpoints: std.ArrayList(HistEntry),
+
+    // at n*cycle + offset this path is finished where n is integer > 0
+    offset: ?u64 = null,
+    cycle: ?u64 = null,
+
+    fn init(a: std.mem.Allocator, start: []const u8) !Path {
+        return .{
+            .pos = start,
+            .endpoints = std.ArrayList(HistEntry).init(a),
+        };
+    }
+
+    fn visit(self: *Path, node: []const u8) void {
+        self.pos = node;
+    }
+
+    fn check(self: *Path, step: u64) !void {
+        if (self.cycle != null) return; // we already found the cycle for this one
+
+        if (self.pos[2] == 'Z') { // we hit an endpoint
+            for (self.endpoints.items) |hi| { // did we aleady hit this endpoint?
+                if (std.mem.eql(u8, hi.node, self.pos)) {
+                    self.offset = hi.step;
+                    self.cycle = step - hi.step;
+                    return;
+                }
+            }
+            try self.endpoints.append(.{ .node = self.pos, .step = step });
+        }
+    }
+};
+fn solve_pt2(a: std.mem.Allocator, input: []const u8) !u64 {
+    var spl = std.mem.split(u8, input, "\n\n");
+    const instructions = spl.first();
+    const nodes_str = spl.next() orelse return error.NoNodes;
+    var spl2 = std.mem.split(u8, nodes_str, "\n");
+    var nodes = std.StringHashMap(NodeValue).init(a);
+    defer nodes.deinit();
+    while (spl2.next()) |node_line| {
+        var toks = std.mem.tokenize(u8, node_line, " (,)=");
+        const key = toks.next() orelse return error.NoKey;
+        const left = toks.next() orelse return error.NoLeft;
+        const right = toks.next() orelse return error.NoRight;
+        try nodes.putNoClobber(key, .{
+            .left = left,
+            .right = right,
+        });
+    }
+
+    var pos: []Path = blk: {
+        var pl = std.ArrayList(Path).init(a);
+        defer pl.deinit();
+        var ki = nodes.keyIterator();
+        while (ki.next()) |k| {
+            if (k.*[2] == 'A') { // ends with an A
+                std.log.info("start pos {s}", .{k.*});
+                try pl.append(try Path.init(a, k.*));
+            }
+        }
+        break :blk try pl.toOwnedSlice();
+    };
+    defer a.free(pos);
+
+    var log = std.time.timestamp() + 10;
+
+    var steps: u64 = 0;
+    while (!ends(pos)) {
+        // > repeat the whole sequence of instructions as necessary
+        // always repeat the whole set
+        for (instructions) |inst| {
+            for (pos) |*p| {
+                const node_value = nodes.get(p.pos).?;
+                p.visit(switch (inst) {
+                    'R' => node_value.right,
+                    'L' => node_value.left,
+                    else => return error.InvalidDirection,
+                });
+            }
+        }
+        steps += instructions.len;
+
+        // logging...
+        const now = std.time.timestamp();
+        if (now > log) {
+            for (pos) |p| {
+                std.log.info("pos {s}", .{p.pos});
+            }
+            log = now + 10;
+        }
+
+        // now check for cycles
+        for (pos) |*p| {
+            try p.check(steps);
+        }
+        // now... check if we have detected a cycle on _all_ tracks
+        for (pos) |p| {
+            if (p.cycle == null) break;
+        } else {
+            std.log.info("all routes have cycled, using LCM", .{});
+            // great, so we haven't reached the end but we can probably calculate it.
+            var l = lcm(pos[0].cycle.?, pos[1].cycle.?);
+            for (pos[2..]) |p| {
+                l = lcm(l, p.cycle.?);
+            }
+            // so, this is our answer?
+            return l;
+        }
+    }
+    return steps;
+}
+
+fn ends(pos: []Path) bool {
+    for (pos) |p| {
+        if (p.pos[2] != 'Z') {
+            return false;
+        }
+    } else {
+        std.log.err("ends true", .{});
+        for (pos) |p| {
+            std.log.err("{s}", .{p.pos});
+        }
+        return true;
+    }
+}
+fn lcm(a: u64, b: u64) u64 {
+    return (a * b) / std.math.gcd(a, b);
+}
+test "pt2" {
+    try std.testing.expectEqual(@as(u64, 6), try solve_pt2(std.testing.allocator, test_input2));
+}
+const test_input =
+    \\LLR
+    \\
+    \\AAA = (BBB, BBB)
+    \\BBB = (AAA, ZZZ)
+    \\ZZZ = (ZZZ, ZZZ)
+;
+const test_input2 =
+    \\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)
+;
+const puzzle_input = @embedFile("day8.in");