2 files changed, 107 insertions, 0 deletions
diff --git a/2021/day21/21.py b/2021/day21/21.py
new file mode 100644
index 0000000..8cd8307
--- /dev/null
+++ b/2021/day21/21.py
@@ -0,0 +1,52 @@
+
+die_val = 1
+rolls = 0
+def roll():
+    global die_val, rolls
+    x = die_val
+
+    die_val += 1
+    if die_val > 100:
+        die_val = 1
+
+    rolls += 1
+
+    return x
+
+
+class Player:
+    def __init__(self, pos):
+        self.pos = pos
+        self.score = 0
+
+    def move(self, roll):
+        self.pos += roll
+        while self.pos > 10:
+            self.pos -= 10
+
+    def take_turn(self):
+        r = sum([roll() for _ in range(0, 3)])
+        self.move(r)
+        self.score += self.pos
+
+    def __str__(self):
+        return "<Player pos=%d score=%d>" % (self.pos, self.score)
+
+inp = open("./input").read().split("\n")
+p1_start = int(inp[0].split(": ")[1])
+p2_start = int(inp[1].split(": ")[1])
+
+p1 = Player(p1_start)
+p2 = Player(p2_start)
+turn = p1
+while p1.score < 1000 and p2.score < 1000:
+    turn.take_turn()
+    if turn == p1:
+        turn = p2
+    else:
+        turn = p1
+
+ans = p1.score * rolls
+if p1.score >= 1000:
+    ans = p2.score * rolls
+print("Part 1: %d" % ans)
diff --git a/2021/day21/21b.py b/2021/day21/21b.py
new file mode 100644
index 0000000..3404c22
--- /dev/null
+++ b/2021/day21/21b.py
@@ -0,0 +1,55 @@
+from collections import defaultdict
+
+POSSIBLE_ROLLS = [a + b + c for a in range(1, 4) for b in range(1, 4) for c in range(1, 4)]
+
+def move(p, roll):
+    pos, score = p
+    pos += roll
+    while pos > 10:
+        pos -= 10
+
+    return (pos, score + pos)
+
+def won(p):
+    return p[1] >= 21
+
+P1_WON_KEY = (-1, -1, True)
+P2_WON_KEY = (-1, -1, False)
+
+def step_universes(d):
+    nxt = defaultdict(lambda: 0)
+    nxt[P1_WON_KEY] = d[P1_WON_KEY]
+    nxt[P2_WON_KEY] = d[P2_WON_KEY]
+    for ((p1, p2, p1_turn), count) in d.items():
+        if p1 == -1:
+            continue
+        elif won(p1):
+            nxt[P1_WON_KEY] += count
+            continue
+        elif won(p2):
+            nxt[P2_WON_KEY] += count
+            continue
+
+        for roll in POSSIBLE_ROLLS:
+            if p1_turn:
+                nxt[(move(p1, roll), p2, False)] += count
+            else:
+                nxt[(p1, move(p2, roll), True)] += count
+
+    return nxt
+
+inp = open("./input").read().split("\n")
+p1_start = int(inp[0].split(": ")[1])
+p2_start = int(inp[1].split(": ")[1])
+
+d = defaultdict(lambda: 0)
+d[((p1_start, 0), (p2_start, 0), True)] = 1
+d = step_universes(d)
+
+while len(d) > 2:
+    d = step_universes(d)
+
+w1 = d[P1_WON_KEY]
+w2 = d[P2_WON_KEY]
+print("Part 2: %d" % max([w1, w2]))
+