const std = @import("std");
const aoc = @import("aoc");

fn gcd(a: u64, b: u64) u64 {
    var ac = a;
    var bc = b;
    while (true) {
        if (ac > bc) {
            ac = ac % bc;
            if (ac == 0) return bc;
        } else {
            bc = bc % ac;
            if (bc == 0) return ac;
        }
    }
}

fn lcm(a: u64, b: u64) u64 {
    return @divExact(a * b, gcd(a, b));
}

fn waittime(start: u32, busid: u32) u32 {
    return (busid - (start % busid)) % busid;
}

fn printRegion(buses: []u32, start: u64, end: u64) void {
    aoc.debugfmt("          ", .{});
    for (buses) |bus| {
        aoc.debugfmt(" {:^5}", .{bus});
    }
    aoc.debugfmt("\n", .{});

    var i = start;
    while (i < end) : (i += 1) {
        aoc.debugfmt("{:<10}", .{i});
        for (buses) |bus| {
            var c: u8 = '.';
            if (bus > 0 and i % bus == 0) c = 'D';
            aoc.debugfmt("   {c}  ", .{c});
        }
        aoc.debugfmt("\n", .{});
    }
    aoc.debugfmt("\n", .{});
}

fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
    _ = args;

    var lineit = std.mem.tokenize(u8, input, "\n");
    var start = try std.fmt.parseInt(u32, lineit.next().?, 10);

    var bestbus: ?u32 = null;
    var busit = std.mem.tokenize(u8, lineit.next().?, ",");
    while (busit.next()) |bus| {
        if (bus[0] == 'x') continue;
        const val = try std.fmt.parseInt(u32, bus, 10);
        if (bestbus == null or waittime(start, val) < waittime(start, bestbus.?)) {
            bestbus = val;
        }
    }

    const answer = bestbus.? * waittime(start, bestbus.?);

    return try std.fmt.allocPrint(allocator, "{d}", .{answer});
}

fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
    _ = args;

    var lineit = std.mem.tokenize(u8, input, "\n");
    _ = try std.fmt.parseInt(u32, lineit.next().?, 10);

    var busses = std.ArrayList(u32).init(allocator);
    defer busses.deinit();

    var busit = std.mem.tokenize(u8, lineit.next().?, ",");

    const first = try std.fmt.parseInt(u32, busit.next().?, 10);
    try busses.append(first);

    var offset: u64 = 0;
    var cycle: u64 = first;
    var delay: u32 = 1;
    while (busit.next()) |bus| : (delay += 1) {
        if (bus[0] == 'x') {
            try busses.append(0);
            continue;
        }
        const val = try std.fmt.parseInt(u32, bus, 10);
        try busses.append(val);

        var mult: u64 = @divFloor(offset + delay, val);
        if ((offset + delay) % val != 0) mult += 1;
        while ((mult * val - offset - delay) % cycle != 0) {
            mult += std.math.max(1, @divFloor(cycle - (mult * val - offset - delay) % cycle, val));
        }
        offset = mult * val - delay;

        cycle = lcm(cycle, val);
        if (aoc.debug) {
            printRegion(busses.items, offset, offset + delay + 1);
            printRegion(busses.items, offset + cycle, offset + cycle + delay + 1);
            aoc.debugfmt("{}\n", .{offset});
        }
    }

    printRegion(busses.items, offset, offset + busses.items.len);

    return try std.fmt.allocPrint(allocator, "{}", .{offset});
}

pub const main = aoc.main(part1, part2, .{ "6568", "554865447501099" });