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

// Links in this list are arranges in a circle
const RingLink = struct {
    data: u32,
    next: *RingLink,
    const Self = @This();

    pub fn insertNext(self: *Self, link: *RingLink) void {
        link.next = self.next;
        self.next = link;
    }

    pub fn popNext(self: *Self) !*Self {
        const nlink = self.next;
        if (nlink == self) return error.EmptyRingList;
        self.next = nlink.next;
        return nlink;
    }

    pub fn length(self: *Self) usize {
        var count: usize = 1;
        var link = self.next;
        while (link != self) : (link = link.next) {
            count += 1;
        }
        return count;
    }

    pub fn advance(self: *Self, count: usize) *RingLink {
        var link = self;
        var counter: usize = 0;
        while (counter < count) : (link = link.next) {
            counter += 1;
        }
        return link;
    }
};

fn printLinks(start: *RingLink, end: *RingLink, skipfirst: bool) void {
    var link = start;
    var b = skipfirst;
    while (b or link != end) : (link = link.next) {
        b = false;
        aoc.debugfmt("{} ", .{link.data});
    }
}

fn parseInput(input: []const u8, lookup: []RingLink, list: *?*RingLink) !u32 {
    var max: u32 = 0;
    var link: *RingLink = undefined;
    for (input) |c, i| {
        if (c == '\n') break;
        const v = try std.fmt.parseInt(u32, input[i .. i + 1], 10);
        if (v > max) max = v;
        if (list.* == null) {
            list.* = &lookup[v];
            link = list.*.?;
            link.next = link;
        } else {
            link.insertNext(&lookup[v]);
            link = link.next;
        }
    }
    return max;
}

fn doRound(list: *RingLink, len: u32, lookup: []RingLink, current: **RingLink, max: u32, round: usize) !void {
    _ = list;
    var target = (current.*.data + max - 2) % max + 1;
    var k: usize = 0;
    var check = current.*.next;
    while (k < 9) : (k += 1) {
        if (check.data == target)
            target = (target + max - 2) % max + 1;

        check = if (k % 3 == 0) current.*.next else check.next;
    }
    var closest = &lookup[target];

    if (aoc.debug) {
        aoc.debugfmt("\n-- move {} --\ncups:", .{round});

        if (aoc.debuglvl == 1) {
            var start = current.*.advance(len - ((round - 1) % len));
            var link = start;
            while (true) {
                if (link == current.*) {
                    aoc.debugfmt(" ({})", .{link.data});
                } else {
                    aoc.debugfmt("  {} ", .{link.data});
                }
                link = link.next;
                if (link == start) break;
            }
            aoc.debugfmt("\n", .{});
        } else {
            aoc.debugfmt("\n{} {} {}\n", .{ current.*.data, target, closest.data });
            aoc.debugfmt(".. ", .{});
            printLinks(current.*, current.*.next.next.next.next, false);
            aoc.debugfmt("..\n.. ", .{});
            printLinks(closest, closest.next.next.next.next, false);
            aoc.debugfmt("..\n", .{});
        }
    }

    var i: usize = 0;
    while (i < 3) : (i += 1) {
        const poplink = try current.*.popNext();
        closest.insertNext(poplink);
        closest = poplink;
    }

    current.* = current.*.next;
}

fn createLookup(allocator: std.mem.Allocator, len: usize) ![]RingLink {
    var lookup = try allocator.alloc(RingLink, len + 1);
    errdefer allocator.free(lookup);

    var i: usize = 1;
    while (i <= len) : (i += 1) {
        lookup[i] = RingLink{ .data = @intCast(u32, i), .next = undefined };
    }

    return lookup;
}

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

    var lookup = try createLookup(allocator, 9);
    defer allocator.free(lookup);

    var list: ?*RingLink = null;
    const max = try parseInput(input, lookup, &list);
    if (list == null) return aoc.Error.InvalidInput;
    const real_len = @intCast(u32, list.?.length());

    var round: usize = 0;
    var current = list.?;
    while (round < 100) : (round += 1) {
        try doRound(list.?, real_len, lookup, &current, max, round + 1);
    }

    var start = &lookup[1];
    var link = start.next;

    var parts = std.ArrayList(u8).init(allocator);
    defer parts.deinit();
    while (link != start) : (link = link.next) {
        try parts.append('0' + @intCast(u8, link.data));
    }

    return try std.fmt.allocPrint(allocator, "{s}", .{parts.items});
}

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

    var lookup = try createLookup(allocator, 1000000);
    defer allocator.free(lookup);

    var list: ?*RingLink = null;
    _ = try parseInput(input, lookup, &list);
    if (list == null) return aoc.Error.InvalidInput;
    const real_len = list.?.length();

    var end = list.?.advance(real_len - 1);
    var i = real_len + 1;
    while (i <= 1000000) : (i += 1) {
        end.insertNext(&lookup[i]);
        end = end.next;
    }

    var round: usize = 0;
    var current = list.?;
    while (round < 10000000) : (round += 1) {
        if (round % 1000000 == 0) aoc.debugfmt(".", .{});
        try doRound(list.?, 1000000, lookup, &current, 1000000, round + 1);
    }
    aoc.debugfmt("\n", .{});

    var link = (&lookup[1]).next;

    const a = @intCast(u64, link.data);
    const b = @intCast(u64, link.next.data);
    aoc.debugfmt("{} * {} = {}\n", .{ a, b, a * b });

    return try std.fmt.allocPrint(allocator, "{}", .{a * b});
}

pub const main = aoc.main(part1, part2, .{ "97245386", "156180332979" });