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.tokenizeAny(u8, text, " =(),");

        return Rule{
            .key = hash(splitTokens.next().?),
            .left = hash(splitTokens.next().?),
            .right = hash(splitTokens.next().?),
        };
    }
};

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