Restructure repo and update solutions to zig 0.10.1HEADmaster

6 files changed, 678 insertions, 0 deletions

diff --git a/src/22/input b/src/22/input
new file mode 100644
index 0000000..cb0c4df
--- /dev/null
+++ b/src/22/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/22/input-test b/src/22/input-test
new file mode 100644
index 0000000..391cd24
--- /dev/null
+++ b/src/22/input-test
@@ -0,0 +1,13 @@
+Player 1:
+9
+2
+6
+3
+1
+
+Player 2:
+5
+8
+4
+7
+10
diff --git a/src/22/input-test2 b/src/22/input-test2
new file mode 100644
index 0000000..a29e13a
--- /dev/null
+++ b/src/22/input-test2
@@ -0,0 +1,8 @@
+Player 1:
+43
+19
+
+Player 2:
+2
+29
+14
diff --git a/src/22/main.zig b/src/22/main.zig
new file mode 100644
index 0000000..dc646b0
--- /dev/null
+++ b/src/22/main.zig
@@ -0,0 +1,181 @@
+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(u8, input, "\n\n");
+    var decknum: u32 = 0;
+    while (partit.next()) |part| : (decknum += 1) {
+        if (decknum == 2) break;
+        var lineit = std.mem.tokenize(u8, 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) aoc.debugfmt(", ", .{});
+        aoc.debugfmt("{}", .{v});
+    }
+}
+
+fn printRoundInfo(roundnum: u32, decks: [2]*std.ArrayList(u32)) void {
+    aoc.debugfmt("\n-- ROUND {} --\n", .{roundnum});
+    aoc.debugfmt("Player 1's deck: ", .{});
+    printDeck(decks[0]);
+    aoc.debugfmt("\nPlayer 2's deck: ", .{});
+    printDeck(decks[1]);
+    aoc.debugfmt("\n", .{});
+}
+
+fn printPickedCards(card1: u32, card2: u32) void {
+    aoc.debugfmt("Player 1 plays: {}\n", .{card1});
+    aoc.debugfmt("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 {
+    _ = allocator;
+    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) aoc.debugfmt("Player1 wins\n", .{});
+        try decks[0].append(card1);
+        try decks[0].append(card2);
+    } else if (card2 > card1) {
+        if (aoc.debug) aoc.debugfmt("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) aoc.debugfmt("\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;
+            aoc.debugfmt("Player{} wins the subgame\n...anyway, back to previous game\n\n", .{wp});
+        }
+    }
+
+    if (winner == Player.P1) {
+        if (aoc.debug) aoc.debugfmt("Player1 wins the round\n", .{});
+        try decks[0].append(card1);
+        try decks[0].append(card2);
+    } else if (winner == Player.P2) {
+        if (aoc.debug) aoc.debugfmt("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: *const 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) !?[]u8 {
+    _ = args;
+
+    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);
+
+    return try std.fmt.allocPrint(allocator, "{}", .{result.score});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+    _ = args;
+
+    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);
+
+    return try std.fmt.allocPrint(allocator, "{}", .{result.score});
+}
+
+pub const main = aoc.main(part1, part2, .{ "32272", "33206" });
diff --git a/src/22/part1 b/src/22/part1
new file mode 100644
index 0000000..56e6e13
--- /dev/null
+++ b/src/22/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 Combat, 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 rounds: 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 score. 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 306.
+
+Play the small crab in a game of Combat using the two decks you just dealt. What is the
+winning player's score?
+
+
diff --git a/src/22/part2 b/src/22/part2
new file mode 100644
index 0000000..4f85a8a
--- /dev/null
+++ b/src/22/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 Recursive Combat.
+
+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
+rounds 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 game 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
+the lower-valued of the two cards 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 copy
+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 copies 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
+291.
+
+Defend your honor as Raft Captain by playing the small crab in a game of Recursive Combat using the
+same two decks as before. What is the winning player's score?
+
+