add day 21

[advent21.git] / 21b.c

diff --git a/21b.c b/21b.c
new file mode 100644 (file)
index 0000000..96153cc
--- /dev/null
+++ b/21b.c
@@ -0,0 +1,81 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include <uthash.h>
+#include <limits.h>
+
+struct result { unsigned long p1wins; unsigned long p2wins; };
+struct player { int pos; int score; };
+struct cache {
+       struct key { bool p1turn; struct player p1; struct player p2; } key;
+       struct result res;
+       UT_hash_handle hh;
+};
+
+struct player move (struct player p, int steps)
+{
+       p.pos = (p.pos+steps)%10;
+       if (p.pos == 0)
+               p.pos = 10;
+       p.score += p.pos;
+       return p;
+}
+
+struct cache *cache = NULL;
+
+struct result playd (bool p1turn, struct player p1, struct player p2);
+struct result play(bool p1turn, struct player p1, struct player p2)
+{
+       struct cache *e;
+       struct key p;
+       memset(&p, 0, sizeof(p));
+       p = (struct key){.p1turn=p1turn, .p1=p1, .p2=p2};
+       HASH_FIND(hh, cache, &p, sizeof(struct key), e);
+       if (e == NULL) {
+               struct result r = playd(p1turn, p1, p2);
+               e = calloc(1, sizeof(struct cache));
+               *e = (struct cache){.key=p, .res=r};
+               HASH_ADD(hh, cache, key, sizeof(struct key), e);
+               return r;
+       } else {
+               return e->res;
+       }
+}
+
+void add_result(struct result *l, struct result r)
+{
+       l->p1wins += r.p1wins;
+       l->p2wins += r.p2wins;
+}
+
+struct result playd (bool p1turn, struct player p1, struct player p2)
+{
+       struct result r = {.p1wins=0, .p2wins=0};
+       if (p1.score >= 21) {
+               r.p1wins++;
+       } else if (p2.score >= 21) {
+               r.p2wins++;
+       } else if (p1turn) {
+               for (int i = 1; i<=3; i++)
+                       for (int j = 1; j<=3; j++)
+                               for (int k = 1; k<=3; k++)
+                                       add_result(&r, play(!p1turn, move(p1, i+j+k), p2));
+       } else {
+               for (int i = 1; i<=3; i++)
+                       for (int j = 1; j<=3; j++)
+                               for (int k = 1; k<=3; k++)
+                                       add_result(&r, play(!p1turn, p1, move(p2, i+j+k)));
+       }
+       return r;
+}
+
+int main()
+{
+       struct player p1 = {.score=0}, p2 = {.score=0};
+       if (2 != scanf(
+                       "Player 1 starting position: %d\n"
+                       "Player 2 starting position: %d\n", &p1.pos, &p2.pos))
+               return 1;
+
+       struct result r = play(true, p1, p2);
+       printf("%lu\n", r.p1wins > r.p2wins ? r.p1wins : r.p2wins);
+}