commit dce8c1112bee0915f35ef256ae875ca220e9f854
parent 1492327fa770491b679fb1554d77c308bad0f2b9
Author: Louis Burda <quent.burda@gmail.com>
Date: Tue, 22 Dec 2020 13:36:18 +0100
added day22
Diffstat:
6 files changed, 677 insertions(+), 0 deletions(-)
diff --git a/src/day22/input b/src/day22/input
@@ -0,0 +1,53 @@
+Player 1:
+3
+42
+4
+25
+14
+36
+32
+18
+33
+10
+35
+50
+16
+31
+34
+46
+9
+6
+41
+7
+15
+45
+30
+27
+49
+
+Player 2:
+8
+11
+47
+21
+17
+39
+29
+43
+23
+28
+13
+22
+5
+20
+44
+38
+26
+37
+2
+24
+48
+12
+19
+1
+40
diff --git a/src/day22/input-test b/src/day22/input-test
@@ -0,0 +1,13 @@
+Player 1:
+9
+2
+6
+3
+1
+
+Player 2:
+5
+8
+4
+7
+10
diff --git a/src/day22/input-test2 b/src/day22/input-test2
@@ -0,0 +1,8 @@
+Player 1:
+43
+19
+
+Player 2:
+2
+29
+14
diff --git a/src/day22/main.zig b/src/day22/main.zig
@@ -0,0 +1,180 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Player = enum { P1, P2 };
+const GameResult = struct {
+ score: u64, winner: Player
+};
+
+fn parseInput(input: []u8, decks: [2]*std.ArrayList(u32)) !void {
+ var partit = std.mem.split(input, "\n\n");
+ var decknum: u32 = 0;
+ while (partit.next()) |part| : (decknum += 1) {
+ if (decknum == 2) break;
+ var lineit = std.mem.tokenize(part, "\n");
+ _ = lineit.next();
+ while (lineit.next()) |line| {
+ try decks[decknum].append(try std.fmt.parseInt(u32, line, 10));
+ }
+ }
+ if (decknum < 2) return aoc.Error.InvalidInput;
+}
+
+fn printDeck(deck: *std.ArrayList(u32)) void {
+ for (deck.items) |v, i| {
+ if (i > 0) std.debug.print(", ", .{});
+ std.debug.print("{}", .{v});
+ }
+}
+
+fn printRoundInfo(roundnum: u32, decks: [2]*std.ArrayList(u32)) void {
+ std.debug.print("\n-- ROUND {} --\n", .{roundnum});
+ std.debug.print("Player 1's deck: ", .{});
+ printDeck(decks[0]);
+ std.debug.print("\nPlayer 2's deck: ", .{});
+ printDeck(decks[1]);
+ std.debug.print("\n", .{});
+}
+
+fn printPickedCards(card1: u32, card2: u32) void {
+ std.debug.print("Player 1 plays: {}\n", .{card1});
+ std.debug.print("Player 2 plays: {}\n", .{card2});
+}
+
+fn calcScore(deck: *std.ArrayList(u32)) u64 {
+ var score: u64 = 0;
+ for (deck.items) |v, i| {
+ score += v * (deck.items.len - i);
+ }
+ return score;
+}
+
+fn copyList(allocator: *std.mem.Allocator, list: []u32) !std.ArrayList(u32) {
+ var newlist = std.ArrayList(u32).init(allocator);
+ errdefer newlist.deinit();
+
+ for (list) |v| {
+ try newlist.append(v);
+ }
+
+ return newlist;
+}
+
+fn part1Round(
+ allocator: *std.mem.Allocator,
+ roundnum: u32,
+ decks: [2]*std.ArrayList(u32),
+) anyerror!void {
+ if (aoc.debug) printRoundInfo(roundnum, decks);
+ const card1: u32 = decks[0].orderedRemove(0);
+ const card2: u32 = decks[1].orderedRemove(0);
+ if (aoc.debug) printPickedCards(card1, card2);
+ if (card1 > card2) {
+ if (aoc.debug) std.debug.print("Player1 wins\n", .{});
+ try decks[0].append(card1);
+ try decks[0].append(card2);
+ } else if (card2 > card1) {
+ if (aoc.debug) std.debug.print("Player2 wins\n", .{});
+ try decks[1].append(card2);
+ try decks[1].append(card1);
+ } else return aoc.Error.InvalidInput;
+}
+
+fn part2Round(
+ allocator: *std.mem.Allocator,
+ roundnum: u32,
+ decks: [2]*std.ArrayList(u32),
+) anyerror!void {
+ if (aoc.debug) printRoundInfo(roundnum, decks);
+ const card1: u32 = decks[0].orderedRemove(0);
+ const card2: u32 = decks[1].orderedRemove(0);
+ if (aoc.debug) printPickedCards(card1, card2);
+
+ var winner = @intToEnum(Player, @boolToInt(card2 > card1));
+ if (card1 <= decks[0].items.len and card2 <= decks[1].items.len) {
+ if (aoc.debug) std.debug.print("\nStarting subgame..\n", .{});
+ var tmp_deck1 = try copyList(allocator, decks[0].items[0..card1]);
+ defer tmp_deck1.deinit();
+
+ var tmp_deck2 = try copyList(allocator, decks[1].items[0..card2]);
+ defer tmp_deck2.deinit();
+
+ const result = try playGame(allocator, [2]*std.ArrayList(u32){ &tmp_deck1, &tmp_deck2 }, part2Round);
+ winner = result.winner;
+ if (aoc.debug) {
+ const wp: u32 = if (winner == Player.P1) 1 else 2;
+ std.debug.print("Player{} wins the subgame\n...anyway, back to previous game\n\n", .{wp});
+ }
+ }
+
+ if (winner == Player.P1) {
+ if (aoc.debug) std.debug.print("Player1 wins the round\n", .{});
+ try decks[0].append(card1);
+ try decks[0].append(card2);
+ } else if (winner == Player.P2) {
+ if (aoc.debug) std.debug.print("Player2 wins the round\n", .{});
+ try decks[1].append(card2);
+ try decks[1].append(card1);
+ } else return aoc.Error.InvalidInput;
+}
+
+fn playGame(
+ allocator: *std.mem.Allocator,
+ decks: [2]*std.ArrayList(u32),
+ roundFunc: fn (
+ alloc: *std.mem.Allocator,
+ num: u32,
+ decks: [2]*std.ArrayList(u32),
+ ) anyerror!void,
+) !GameResult {
+ var ctxstack = std.ArrayList(u64).init(allocator);
+ defer ctxstack.deinit();
+
+ var roundnum: u32 = 1;
+ while (decks[0].items.len > 0 and decks[1].items.len > 0) : (roundnum += 1) {
+ try roundFunc(allocator, roundnum, decks);
+
+ var hash: u64 = calcScore(decks[0]) + 100000 * calcScore(decks[1]);
+ if (std.mem.indexOfScalar(u64, ctxstack.items, hash) != null) {
+ return GameResult{ .score = calcScore(decks[0]), .winner = Player.P1 };
+ }
+
+ try ctxstack.append(hash);
+ }
+
+ var nonempty = if (decks[0].items.len != 0) decks[0] else decks[1];
+ return GameResult{
+ .score = calcScore(nonempty),
+ .winner = if (nonempty == decks[0]) Player.P1 else Player.P2,
+ };
+}
+
+fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
+ var deck1 = std.ArrayList(u32).init(allocator);
+ defer deck1.deinit();
+
+ var deck2 = std.ArrayList(u32).init(allocator);
+ defer deck2.deinit();
+
+ const decks = [2]*std.ArrayList(u32){ &deck1, &deck2 };
+ try parseInput(input, decks);
+
+ const result = try playGame(allocator, decks, part1Round);
+ std.debug.print("{}\n", .{result.score});
+}
+
+fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
+ var deck1 = std.ArrayList(u32).init(allocator);
+ defer deck1.deinit();
+
+ var deck2 = std.ArrayList(u32).init(allocator);
+ defer deck2.deinit();
+
+ const decks = [2]*std.ArrayList(u32){ &deck1, &deck2 };
+ try parseInput(input, decks);
+
+ const result = try playGame(allocator, decks, part2Round);
+ std.debug.print("{}\n", .{result.score});
+}
+
+pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day22/part1 b/src/day22/part1
@@ -0,0 +1,123 @@
+--- Day 22: Crab Combat ---
+
+It only takes a few hours of sailing the ocean on a raft for boredom to sink in. Fortunately, you
+brought a small deck of space cards! You'd like to play a game of [1m[37mCombat[0m, and there's
+even an opponent available: a small crab that climbed aboard your raft before you left.
+
+Fortunately, it doesn't take long to teach the crab the rules.
+
+Before the game starts, split the cards so each player has their own deck (your puzzle input). Then,
+the game consists of a series of [1m[37mrounds[0m: both players draw their top card, and the
+player with the higher-valued card wins the round. The winner keeps both cards, placing them on the
+bottom of their own deck so that the winner's card is above the other card. If this causes a player
+to have all of the cards, they win, and the game ends.
+
+For example, consider the following starting decks:
+
+Player 1:
+9
+2
+6
+3
+1
+
+Player 2:
+5
+8
+4
+7
+10
+
+This arrangement means that player 1's deck contains 5 cards, with 9 on top and 1 on the bottom;
+player 2's deck also contains 5 cards, with 5 on top and 10 on the bottom.
+
+The first round begins with both players drawing the top card of their decks: 9 and 5. Player 1 has
+the higher card, so both cards move to the bottom of player 1's deck such that 9 is above 5. In
+total, it takes 29 rounds before a player has all of the cards:
+
+-- Round 1 --
+Player 1's deck: 9, 2, 6, 3, 1
+Player 2's deck: 5, 8, 4, 7, 10
+Player 1 plays: 9
+Player 2 plays: 5
+Player 1 wins the round!
+
+-- Round 2 --
+Player 1's deck: 2, 6, 3, 1, 9, 5
+Player 2's deck: 8, 4, 7, 10
+Player 1 plays: 2
+Player 2 plays: 8
+Player 2 wins the round!
+
+-- Round 3 --
+Player 1's deck: 6, 3, 1, 9, 5
+Player 2's deck: 4, 7, 10, 8, 2
+Player 1 plays: 6
+Player 2 plays: 4
+Player 1 wins the round!
+
+-- Round 4 --
+Player 1's deck: 3, 1, 9, 5, 6, 4
+Player 2's deck: 7, 10, 8, 2
+Player 1 plays: 3
+Player 2 plays: 7
+Player 2 wins the round!
+
+-- Round 5 --
+Player 1's deck: 1, 9, 5, 6, 4
+Player 2's deck: 10, 8, 2, 7, 3
+Player 1 plays: 1
+Player 2 plays: 10
+Player 2 wins the round!
+
+...several more rounds pass...
+
+-- Round 27 --
+Player 1's deck: 5, 4, 1
+Player 2's deck: 8, 9, 7, 3, 2, 10, 6
+Player 1 plays: 5
+Player 2 plays: 8
+Player 2 wins the round!
+
+-- Round 28 --
+Player 1's deck: 4, 1
+Player 2's deck: 9, 7, 3, 2, 10, 6, 8, 5
+Player 1 plays: 4
+Player 2 plays: 9
+Player 2 wins the round!
+
+-- Round 29 --
+Player 1's deck: 1
+Player 2's deck: 7, 3, 2, 10, 6, 8, 5, 9, 4
+Player 1 plays: 1
+Player 2 plays: 7
+Player 2 wins the round!
+
+
+== Post-game results ==
+Player 1's deck:
+Player 2's deck: 3, 2, 10, 6, 8, 5, 9, 4, 7, 1
+
+Once the game ends, you can calculate the winning player's [1m[37mscore[0m. The bottom card in
+their deck is worth the value of the card multiplied by 1, the second-from-the-bottom card is worth
+the value of the card multiplied by 2, and so on. With 10 cards, the top card is worth the value on
+the card multiplied by 10. In this example, the winning player's score is:
+
+ 3 * 10
++ 2 * 9
++ 10 * 8
++ 6 * 7
++ 8 * 6
++ 5 * 5
++ 9 * 4
++ 4 * 3
++ 7 * 2
++ 1 * 1
+= 306
+
+So, once the game ends, the winning player's score is [1m[37m306[0m.
+
+Play the small crab in a game of Combat using the two decks you just dealt. [1m[37mWhat is the
+winning player's score?[0m
+
+
diff --git a/src/day22/part2 b/src/day22/part2
@@ -0,0 +1,300 @@
+--- Part Two ---
+
+You lost to the small crab! Fortunately, crabs aren't very good at recursion. To defend your honor
+as a Raft Captain, you challenge the small crab to a game of [1m[37mRecursive Combat[0m.
+
+Recursive Combat still starts by splitting the cards into two decks (you offer to play with the same
+starting decks as before - it's only fair). Then, the game consists of a series of
+[1m[37mrounds[0m with a few changes:
+
+
+ - Before either player deals a card, if there was a previous round in this game that had exactly
+the same cards in the same order in the same players' decks, the [1m[37mgame[0m instantly ends in
+a win for player 1. Previous rounds from other games are not considered. (This prevents infinite
+games of Recursive Combat, which everyone agrees is a bad idea.)
+ - Otherwise, this round's cards must be in a new configuration; the players begin the round by each
+drawing the top card of their deck as normal.
+ - If both players have at least as many cards remaining in their deck as the value of the card they
+just drew, the winner of the round is determined by playing a new game of Recursive Combat (see
+below).
+ - Otherwise, at least one player must not have enough cards left in their deck to recurse; the
+winner of the round is the player with the higher-value card.
+
+
+As in regular Combat, the winner of the round (even if they won the round by winning a sub-game)
+takes the two cards dealt at the beginning of the round and places them on the bottom of their own
+deck (again so that the winner's card is above the other card). Note that the winner's card might be
+[1m[37mthe lower-valued of the two cards[0m if they won the round due to winning a sub-game. If
+collecting cards by winning the round causes a player to have all of the cards, they win, and the
+game ends.
+
+Here is an example of a small game that would loop forever without the infinite game prevention
+rule:
+
+Player 1:
+43
+19
+
+Player 2:
+2
+29
+14
+
+During a round of Recursive Combat, if both players have at least as many cards in their own decks
+as the number on the card they just dealt, the winner of the round is determined by recursing into a
+sub-game of Recursive Combat. (For example, if player 1 draws the 3 card, and player 2 draws the 7
+card, this would occur if player 1 has at least 3 cards left and player 2 has at least 7 cards left,
+not counting the 3 and 7 cards that were drawn.)
+
+To play a sub-game of Recursive Combat, each player creates a new deck by making a [1m[37mcopy[0m
+of the next cards in their deck (the quantity of cards copied is equal to the number on the card
+they drew to trigger the sub-game). During this sub-game, the game that triggered it is on hold and
+completely unaffected; no cards are removed from players' decks to form the sub-game. (For example,
+if player 1 drew the 3 card, their deck in the sub-game would be [1m[37mcopies[0m of the next
+three cards in their deck.)
+
+Here is a complete example of gameplay, where Game 1 is the primary game of Recursive Combat:
+
+=== Game 1 ===
+
+-- Round 1 (Game 1) --
+Player 1's deck: 9, 2, 6, 3, 1
+Player 2's deck: 5, 8, 4, 7, 10
+Player 1 plays: 9
+Player 2 plays: 5
+Player 1 wins round 1 of game 1!
+
+-- Round 2 (Game 1) --
+Player 1's deck: 2, 6, 3, 1, 9, 5
+Player 2's deck: 8, 4, 7, 10
+Player 1 plays: 2
+Player 2 plays: 8
+Player 2 wins round 2 of game 1!
+
+-- Round 3 (Game 1) --
+Player 1's deck: 6, 3, 1, 9, 5
+Player 2's deck: 4, 7, 10, 8, 2
+Player 1 plays: 6
+Player 2 plays: 4
+Player 1 wins round 3 of game 1!
+
+-- Round 4 (Game 1) --
+Player 1's deck: 3, 1, 9, 5, 6, 4
+Player 2's deck: 7, 10, 8, 2
+Player 1 plays: 3
+Player 2 plays: 7
+Player 2 wins round 4 of game 1!
+
+-- Round 5 (Game 1) --
+Player 1's deck: 1, 9, 5, 6, 4
+Player 2's deck: 10, 8, 2, 7, 3
+Player 1 plays: 1
+Player 2 plays: 10
+Player 2 wins round 5 of game 1!
+
+-- Round 6 (Game 1) --
+Player 1's deck: 9, 5, 6, 4
+Player 2's deck: 8, 2, 7, 3, 10, 1
+Player 1 plays: 9
+Player 2 plays: 8
+Player 1 wins round 6 of game 1!
+
+-- Round 7 (Game 1) --
+Player 1's deck: 5, 6, 4, 9, 8
+Player 2's deck: 2, 7, 3, 10, 1
+Player 1 plays: 5
+Player 2 plays: 2
+Player 1 wins round 7 of game 1!
+
+-- Round 8 (Game 1) --
+Player 1's deck: 6, 4, 9, 8, 5, 2
+Player 2's deck: 7, 3, 10, 1
+Player 1 plays: 6
+Player 2 plays: 7
+Player 2 wins round 8 of game 1!
+
+-- Round 9 (Game 1) --
+Player 1's deck: 4, 9, 8, 5, 2
+Player 2's deck: 3, 10, 1, 7, 6
+Player 1 plays: 4
+Player 2 plays: 3
+Playing a sub-game to determine the winner...
+
+=== Game 2 ===
+
+-- Round 1 (Game 2) --
+Player 1's deck: 9, 8, 5, 2
+Player 2's deck: 10, 1, 7
+Player 1 plays: 9
+Player 2 plays: 10
+Player 2 wins round 1 of game 2!
+
+-- Round 2 (Game 2) --
+Player 1's deck: 8, 5, 2
+Player 2's deck: 1, 7, 10, 9
+Player 1 plays: 8
+Player 2 plays: 1
+Player 1 wins round 2 of game 2!
+
+-- Round 3 (Game 2) --
+Player 1's deck: 5, 2, 8, 1
+Player 2's deck: 7, 10, 9
+Player 1 plays: 5
+Player 2 plays: 7
+Player 2 wins round 3 of game 2!
+
+-- Round 4 (Game 2) --
+Player 1's deck: 2, 8, 1
+Player 2's deck: 10, 9, 7, 5
+Player 1 plays: 2
+Player 2 plays: 10
+Player 2 wins round 4 of game 2!
+
+-- Round 5 (Game 2) --
+Player 1's deck: 8, 1
+Player 2's deck: 9, 7, 5, 10, 2
+Player 1 plays: 8
+Player 2 plays: 9
+Player 2 wins round 5 of game 2!
+
+-- Round 6 (Game 2) --
+Player 1's deck: 1
+Player 2's deck: 7, 5, 10, 2, 9, 8
+Player 1 plays: 1
+Player 2 plays: 7
+Player 2 wins round 6 of game 2!
+The winner of game 2 is player 2!
+
+...anyway, back to game 1.
+Player 2 wins round 9 of game 1!
+
+-- Round 10 (Game 1) --
+Player 1's deck: 9, 8, 5, 2
+Player 2's deck: 10, 1, 7, 6, 3, 4
+Player 1 plays: 9
+Player 2 plays: 10
+Player 2 wins round 10 of game 1!
+
+-- Round 11 (Game 1) --
+Player 1's deck: 8, 5, 2
+Player 2's deck: 1, 7, 6, 3, 4, 10, 9
+Player 1 plays: 8
+Player 2 plays: 1
+Player 1 wins round 11 of game 1!
+
+-- Round 12 (Game 1) --
+Player 1's deck: 5, 2, 8, 1
+Player 2's deck: 7, 6, 3, 4, 10, 9
+Player 1 plays: 5
+Player 2 plays: 7
+Player 2 wins round 12 of game 1!
+
+-- Round 13 (Game 1) --
+Player 1's deck: 2, 8, 1
+Player 2's deck: 6, 3, 4, 10, 9, 7, 5
+Player 1 plays: 2
+Player 2 plays: 6
+Playing a sub-game to determine the winner...
+
+=== Game 3 ===
+
+-- Round 1 (Game 3) --
+Player 1's deck: 8, 1
+Player 2's deck: 3, 4, 10, 9, 7, 5
+Player 1 plays: 8
+Player 2 plays: 3
+Player 1 wins round 1 of game 3!
+
+-- Round 2 (Game 3) --
+Player 1's deck: 1, 8, 3
+Player 2's deck: 4, 10, 9, 7, 5
+Player 1 plays: 1
+Player 2 plays: 4
+Playing a sub-game to determine the winner...
+
+=== Game 4 ===
+
+-- Round 1 (Game 4) --
+Player 1's deck: 8
+Player 2's deck: 10, 9, 7, 5
+Player 1 plays: 8
+Player 2 plays: 10
+Player 2 wins round 1 of game 4!
+The winner of game 4 is player 2!
+
+...anyway, back to game 3.
+Player 2 wins round 2 of game 3!
+
+-- Round 3 (Game 3) --
+Player 1's deck: 8, 3
+Player 2's deck: 10, 9, 7, 5, 4, 1
+Player 1 plays: 8
+Player 2 plays: 10
+Player 2 wins round 3 of game 3!
+
+-- Round 4 (Game 3) --
+Player 1's deck: 3
+Player 2's deck: 9, 7, 5, 4, 1, 10, 8
+Player 1 plays: 3
+Player 2 plays: 9
+Player 2 wins round 4 of game 3!
+The winner of game 3 is player 2!
+
+...anyway, back to game 1.
+Player 2 wins round 13 of game 1!
+
+-- Round 14 (Game 1) --
+Player 1's deck: 8, 1
+Player 2's deck: 3, 4, 10, 9, 7, 5, 6, 2
+Player 1 plays: 8
+Player 2 plays: 3
+Player 1 wins round 14 of game 1!
+
+-- Round 15 (Game 1) --
+Player 1's deck: 1, 8, 3
+Player 2's deck: 4, 10, 9, 7, 5, 6, 2
+Player 1 plays: 1
+Player 2 plays: 4
+Playing a sub-game to determine the winner...
+
+=== Game 5 ===
+
+-- Round 1 (Game 5) --
+Player 1's deck: 8
+Player 2's deck: 10, 9, 7, 5
+Player 1 plays: 8
+Player 2 plays: 10
+Player 2 wins round 1 of game 5!
+The winner of game 5 is player 2!
+
+...anyway, back to game 1.
+Player 2 wins round 15 of game 1!
+
+-- Round 16 (Game 1) --
+Player 1's deck: 8, 3
+Player 2's deck: 10, 9, 7, 5, 6, 2, 4, 1
+Player 1 plays: 8
+Player 2 plays: 10
+Player 2 wins round 16 of game 1!
+
+-- Round 17 (Game 1) --
+Player 1's deck: 3
+Player 2's deck: 9, 7, 5, 6, 2, 4, 1, 10, 8
+Player 1 plays: 3
+Player 2 plays: 9
+Player 2 wins round 17 of game 1!
+The winner of game 1 is player 2!
+
+
+== Post-game results ==
+Player 1's deck:
+Player 2's deck: 7, 5, 6, 2, 4, 1, 10, 8, 9, 3
+
+After the game, the winning player's score is calculated from the cards they have in their original
+deck using the same rules as regular Combat. In the above game, the winning player's score is
+[1m[37m291[0m.
+
+Defend your honor as Raft Captain by playing the small crab in a game of Recursive Combat using the
+same two decks as before. [1m[37mWhat is the winning player's score?[0m
+
+
