From 86994bfea30b6ccde76d61ff661bfe5f1d11415d Mon Sep 17 00:00:00 2001
From: Brendan Hansen <brendan.f.hansen@gmail.com>
Date: Tue, 22 Dec 2020 10:18:19 -0600
Subject: [PATCH] added day 22

---
 day22.onyx      | 161 ++++++++++++++++++++++++++++++++++++++++++++++++
 input/day22.txt |  53 ++++++++++++++++
 2 files changed, 214 insertions(+)
 create mode 100644 day22.onyx
 create mode 100644 input/day22.txt

diff --git a/day22.onyx b/day22.onyx
new file mode 100644
index 0000000..a706afe
--- /dev/null
+++ b/day22.onyx
@@ -0,0 +1,161 @@
+#include_file "core/std/wasi"
+
+use package core
+use package core.string.reader as reader
+
+key_arena : alloc.arena.ArenaState;
+key_alloc : Allocator;
+
+score_player :: proc (p: ^[..] u32) -> u32 {
+    count := 0;
+    mul := p.count;
+    for c: *p {
+        count += c * mul;
+        mul -= 1;
+    }
+    return count;
+}
+
+combat :: proc (player1: ^[..] u32, player2: ^[..] u32) -> u32 {
+    while player1.count > 0 && player2.count > 0 {
+        p1 := player1.data[0];
+        p2 := player2.data[0];
+        array.delete(player1, 0);
+        array.delete(player2, 0);
+
+        if p1 > p2 {
+            array.push(player1, p1);
+            array.push(player1, p2);
+        } else {
+            array.push(player2, p2);
+            array.push(player2, p1);
+        }
+    }
+
+    if player1.count > 0 do return score_player(player1);
+    return score_player(player2);
+}
+
+// Encodes a hand state such as:
+//   P1: 4 5 2 8
+//   P2: 1 3 9 7
+// into:
+//   4,5,2,8,|1,3,9,7,
+// Larger numbers are encoded in base 64.
+encode_hands :: proc (alloc: Allocator, p1: ^[..] u32, p2: ^[..] u32) -> str {
+    use package core.string.builder as b
+
+    builder := b.make(200, alloc);
+    for n: *p1 {
+        b.add_i64(^builder, ~~n, 64);
+        b.add_str(^builder, ",");
+    }
+    b.add_str(^builder, "|");
+    for n: *p2 {
+        b.add_i64(^builder, ~~n, 64);
+        b.add_str(^builder, ",");
+    }
+
+    return b.to_str(^builder);
+}
+
+recursive_combat :: proc (player1: ^[..] u32, player2: ^[..] u32) -> u32 {
+    hand_seen : map.Map(str, bool);
+    map.init(^hand_seen, 31);
+    defer map.free(^hand_seen);
+
+    while player1.count > 0 && player2.count > 0 {
+        enc_hand := encode_hands(key_alloc, player1, player2);
+        if map.has(^hand_seen, enc_hand) do return 1;
+        map.put(^hand_seen, enc_hand, true);
+
+        p1 := player1.data[0];
+        p2 := player2.data[0];
+        array.delete(player1, 0);
+        array.delete(player2, 0);
+
+        round_win := 0;
+
+        if player1.count >= p1 && player2.count >= p2 {
+            p1_copy := array.copy_range(player1, 0 .. p1);
+            p2_copy := array.copy_range(player2, 0 .. p2);
+            defer array.free(^p1_copy);
+            defer array.free(^p2_copy);
+
+            round_win = recursive_combat(^p1_copy, ^p2_copy);
+        } else {
+            if p1 > p2 do round_win = 1;
+            else       do round_win = 2;
+        }
+
+        if round_win == 1 {
+            array.push(player1, p1);
+            array.push(player1, p2);
+        } else {
+            array.push(player2, p2);
+            array.push(player2, p1);
+        }
+    }
+
+    if player1.count == 0 do return 2;
+    return 1;
+}
+
+main :: proc (args: [] cstr) {
+    contents := file.get_contents("input/day22.txt");
+    defer string.free(contents);
+
+    file := reader.make(contents);
+
+    player1: [..] u32;
+    player2: [..] u32;
+    array.init(^player1);
+    array.init(^player2);
+    defer array.free(^player1);
+    defer array.free(^player2);
+
+    reader.advance_line(^file); // 'Player 1:'
+    while *file.data != #char "\n" {
+        card := reader.read_u32(^file);
+        array.push(^player1, card);
+
+        reader.advance_line(^file);
+    }
+
+    reader.advance_line(^file); // '\n'
+    reader.advance_line(^file); // 'Player 2:'
+    while !reader.empty(^file) {
+        card := reader.read_u32(^file);
+        array.push(^player2, card);
+
+        reader.advance_line(^file);
+    }
+
+    {
+        player1_copy := array.copy(^player1);
+        player2_copy := array.copy(^player2);
+        defer array.free(^player1_copy);
+        defer array.free(^player2_copy);
+
+        combat_score := combat(^player1_copy, ^player2_copy);
+        printf("Answer: %i\n", combat_score);
+    }
+
+    {
+        key_arena = alloc.arena.make(context.allocator, 1 << 12);
+        key_alloc = alloc.arena.make_allocator(^key_arena);
+
+        player1_copy := array.copy(^player1);
+        player2_copy := array.copy(^player2);
+        defer array.free(^player1_copy);
+        defer array.free(^player2_copy);
+
+        winner := recursive_combat(^player1_copy, ^player2_copy);
+
+        score : u32;
+        if winner == 1 do score = score_player(^player1_copy);
+        if winner == 2 do score = score_player(^player2_copy);
+
+        printf("Recursive answer: %i\n", score);
+    }
+}
diff --git a/input/day22.txt b/input/day22.txt
new file mode 100644
index 0000000..3870b02
--- /dev/null
+++ b/input/day22.txt
@@ -0,0 +1,53 @@
+Player 1:
+44
+24
+36
+6
+27
+46
+33
+45
+47
+41
+15
+23
+40
+38
+43
+42
+25
+5
+30
+35
+34
+13
+29
+1
+50
+
+Player 2:
+32
+28
+4
+12
+9
+21
+48
+18
+31
+39
+20
+16
+3
+37
+49
+7
+17
+22
+8
+26
+2
+14
+11
+19
+10
-- 
2.25.1