const std = @import("std");

const INPUT = "394618527";
const Str = []const u8;

pub fn first(allocator: ?std.mem.Allocator) anyerror!usize {
    var cc = try CrabCups(u4, 9).init(allocator.?);
    defer {
        cc.cups.deinit();
    }
    try cc.parse(INPUT);

    // std.debug.print("{any}\n", .{cc.cups.items});

    var round: usize = 0;
    while (round < 100) : (round += 1) {
        // std.debug.print("{d} {any}\n", .{ cc.current, cc.cups.items });
        try cc.move();
    }

    var ret: usize = 0;

    var idx: usize = 0;
    var next: usize = 0;
    while (idx < 8) : (idx += 1) {
        ret += (cc.cups.items[next] + 1) *
            try std.math.powi(usize, 10, cc.cups.items.len - idx - 2);
        next = cc.cups.items[next];
    }

    return ret;
}

pub fn second(allocator: ?std.mem.Allocator) anyerror!usize {
    const ARRAY_SIZE = 1_000_000;
    const input = INPUT;
    var cc = try CrabCups(u20, ARRAY_SIZE).init(allocator.?);
    defer {
        cc.cups.deinit();
    }
    try cc.parse(input);

    // fill up the array
    var item: u20 = input.len;
    while (item < ARRAY_SIZE) : (item += 1) {
        cc.cups.items[item] = item + 1;
    }

    // fill up fixes...
    const tmp = (try std.fmt.parseUnsigned(usize, input[input.len - 1 ..], 10)) - 1;
    // last item should point to first
    cc.cups.items[cc.cups.items.len - 1] = cc.current;
    // parsed last item should point to first item in fill up
    cc.cups.items[tmp] = input.len;

    var round: usize = 0;
    while (round < 10_000_000) : (round += 1) {
        try cc.move();
    }

    var ret: usize = 0;
    const cup1 = cc.cups.items[0];
    const cup2 = cc.cups.items[cup1];
    ret = cup1 + 1;
    ret *= cup2 + 1;

    return ret;
}

fn CrabCups(comptime CupType: anytype, comptime SIZE: usize) type {
    const Cups = std.ArrayList(CupType);

    return struct {
        cups: Cups = undefined,
        current: CupType = undefined,

        allocator: std.mem.Allocator,

        fn init(allocator: std.mem.Allocator) !@This() {
            return @This(){
                .cups = try std.ArrayList(CupType).initCapacity(allocator, SIZE),
                .allocator = allocator,
            };
        }

        // cup_label points to next cup
        fn parse(self: *@This(), input: Str) !void {
            var array = try self.cups.addManyAsArray(SIZE);
            var prev: CupType = undefined;
            for (input) |_, idx| {
                const cup_label = (try std.fmt.parseUnsigned(CupType, input[idx .. idx + 1], 10)) - 1;
                if (idx == 0) self.current = cup_label;
                if (idx != 0) array[prev] = cup_label;
                if (idx == input.len - 1) array[cup_label] = self.current;
                prev = cup_label;
            }
        }

        fn move(self: *@This()) !void {
            // std.debug.print("current: {d}\n", .{self.current + 1});

            const cup1 = self.cups.items[self.current];
            const cup2 = self.cups.items[cup1];
            const cup3 = self.cups.items[cup2];

            // std.debug.print("pick up: {d} {d} {d}\n", .{ cup1 + 1, cup2 + 1, cup3 + 1 });

            const destination = blk: {
                var dest: CupType = self.current;
                while (true) {
                    if (dest != 0) dest -= 1 else dest = SIZE - 1;
                    if (dest != self.current and dest != cup1 and dest != cup2 and dest != cup3) {
                        break;
                    }
                }
                break :blk dest;
            };
            // std.debug.print("destination: {}\n", .{destination + 1});

            // 1. point current to item after cup3
            self.cups.items[self.current] = self.cups.items[cup3];
            // 2. point cup3 to destination's next
            self.cups.items[cup3] = self.cups.items[destination];
            // 3. point destination to cup1
            self.cups.items[destination] = cup1;

            // update current
            self.current = self.cups.items[self.current];
        }
    };
}

test "day23a" {
    try std.testing.expectEqual(@as(usize, 78569234), try first(std.testing.allocator));
}

test "day23b" {
    try std.testing.expectEqual(@as(usize, 565615814504), try second(std.testing.allocator));
}

const test_input = "389125467";