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 ;