diff options
Diffstat (limited to 'day8.zig')
| -rw-r--r-- | day8.zig | 208 |
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"); |