const std = @import("std");

const PATH = "input/day22.txt";
const Str = []const u8;

pub fn first(allocator: ?std.mem.Allocator) anyerror!usize {
    var game = try parseInput(allocator.?, @embedFile(PATH));
    defer {
        game.p1.deinit();
        game.p2.deinit();
    }

    try game.play();

    var sum: usize = 0;
    for (game.p1.items) |item, idx| {
        sum += (game.p1.items.len - idx) * item;
    }
    for (game.p2.items) |item, idx| {
        sum += (game.p2.items.len - idx) * item;
    }

    return sum;
}

pub fn second(allocator: ?std.mem.Allocator) anyerror!usize {
    const game = try parseInput(allocator.?, @embedFile(PATH));
    var rc = RecursiveCombat{
        .p1 = game.p1,
        .p2 = game.p2,
        .p1prev = Cache.init(allocator.?),
        .p2prev = Cache.init(allocator.?),
    };
    defer {
        rc.p1.deinit();
        rc.p2.deinit();
        rc.p1prev.deinit();
        rc.p2prev.deinit();
    }

    _ = try rc.play(allocator.?);

    var sum: usize = 0;
    for (rc.p1.items) |item, idx| {
        sum += (rc.p1.items.len - idx) * item;
    }
    for (rc.p2.items) |item, idx| {
        sum += (rc.p2.items.len - idx) * item;
    }

    return sum;
}

const CardType = u6;
const Game = struct {
    p1: std.ArrayList(CardType),
    p2: std.ArrayList(CardType),

    fn play(self: *@This()) anyerror!void {
        if (self.p1.items.len == 0 or self.p2.items.len == 0) {
            return;
        }

        const p1 = self.p1.orderedRemove(0);
        const p2 = self.p2.orderedRemove(0);

        if (p1 > p2) {
            try self.p1.append(p1);
            try self.p1.append(p2);
        } else {
            try self.p2.append(p2);
            try self.p2.append(p1);
        }

        try self.play();
    }
};

const Cache = std.ArrayList([]CardType);
const RecursiveCombat = struct {
    p1: std.ArrayList(CardType),
    p2: std.ArrayList(CardType),
    p1prev: Cache,
    p2prev: Cache,

    fn play(self: *@This(), allocator: std.mem.Allocator) anyerror!u1 {
        if (self.p2.items.len == 0) {
            return 0;
        }
        if (self.p1.items.len == 0) {
            return 1;
        }

        // Infinite check
        for (self.p1prev.items) |item| {
            if (std.mem.eql(CardType, item, self.p1.items)) return 0;
        }
        for (self.p2prev.items) |item| {
            if (std.mem.eql(CardType, item, self.p2.items)) return 0;
        }

        // Add current decks to previous decks
        const tmp1 = try self.p1.clone();
        const tmp2 = try self.p1.clone();
        defer tmp1.deinit();
        defer tmp2.deinit();
        try self.p1prev.append(tmp1.items);
        try self.p2prev.append(tmp2.items);

        // Start the round with drawing
        const p1 = self.p1.orderedRemove(0);
        const p2 = self.p2.orderedRemove(0);

        var winner: ?u1 = null;

        // Check recursion
        if (p1 <= self.p1.items.len and p2 <= self.p2.items.len) {
            var rc = RecursiveCombat{
                .p1 = try std.ArrayList(CardType).initCapacity(allocator, p1),
                .p2 = try std.ArrayList(CardType).initCapacity(allocator, p2),
                .p1prev = Cache.init(allocator),
                .p2prev = Cache.init(allocator),
            };
            defer {
                rc.p1.deinit();
                rc.p2.deinit();
                rc.p1prev.deinit();
                rc.p2prev.deinit();
            }
            rc.p1.appendSliceAssumeCapacity(self.p1.items[0..p1]);
            rc.p2.appendSliceAssumeCapacity(self.p2.items[0..p2]);

            winner = try rc.play(allocator);
        }

        // Without recursion winner is null, set it
        if (winner == null) {
            if (p1 > p2) winner = 0 else winner = 1;
        }

        if (winner.? == 0) {
            try self.p1.append(p1);
            try self.p1.append(p2);
        } else {
            try self.p2.append(p2);
            try self.p2.append(p1);
        }

        return try self.play(allocator);
    }
};

fn parseInput(allocator: std.mem.Allocator, input: Str) !Game {
    var ret = Game{
        .p1 = std.ArrayList(CardType).init(allocator),
        .p2 = std.ArrayList(CardType).init(allocator),
    };

    var lines = std.mem.split(u8, input, "\n");

    // Player 1
    while (lines.next()) |line| {
        if (line.len == 0) break;
        if (line[0] == 'P') continue;
        const num = try std.fmt.parseUnsigned(CardType, line, 10);
        try ret.p1.append(num);
    }

    // Player 2
    while (lines.next()) |line| {
        if (line.len == 0) break;
        if (line[0] == 'P') continue;
        const num = try std.fmt.parseUnsigned(CardType, line, 10);
        try ret.p2.append(num);
    }

    return ret;
}

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

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

const test_input =
    \\Player 1:
    \\9
    \\2
    \\6
    \\3
    \\1
    \\
    \\Player 2:
    \\5
    \\8
    \\4
    \\7
    \\10
;

const infinite_test =
    \\Player 1:
    \\43
    \\19
    \\
    \\Player 2:
    \\2
    \\29
    \\14
;