aoc2023

day8.zig (6332B)

---

 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");