21b.c

   1 #include <stdio.h>
   2 #include <stdbool.h>
   3 #include <uthash.h>
   4 #include <limits.h>
   5
   6 struct result { unsigned long p1wins; unsigned long p2wins; };
   7 struct player { int pos; int score; };
   8 struct cache {
   9         struct key { bool p1turn; struct player p1; struct player p2; } key;
  10         struct result res;
  11         UT_hash_handle hh;
  12 };
  13
  14 struct player move (struct player p, int steps)
  15 {
  16         p.pos = (p.pos+steps)%10;
  17         if (p.pos == 0)
  18                 p.pos = 10;
  19         p.score += p.pos;
  20         return p;
  21 }
  22
  23 struct cache *cache = NULL;
  24
  25 struct result playd (bool p1turn, struct player p1, struct player p2);
  26 struct result play(bool p1turn, struct player p1, struct player p2)
  27 {
  28         struct cache *e;
  29         struct key p;
  30         memset(&p, 0, sizeof(p));
  31         p = (struct key){.p1turn=p1turn, .p1=p1, .p2=p2};
  32         HASH_FIND(hh, cache, &p, sizeof(struct key), e);
  33         if (e == NULL) {
  34                 struct result r = playd(p1turn, p1, p2);
  35                 e = calloc(1, sizeof(struct cache));
  36                 *e = (struct cache){.key=p, .res=r};
  37                 HASH_ADD(hh, cache, key, sizeof(struct key), e);
  38                 return r;
  39         } else {
  40                 return e->res;
  41         }
  42 }
  43
  44 void add_result(struct result *l, struct result r)
  45 {
  46         l->p1wins += r.p1wins;
  47         l->p2wins += r.p2wins;
  48 }
  49
  50 struct result playd (bool p1turn, struct player p1, struct player p2)
  51 {
  52         struct result r = {.p1wins=0, .p2wins=0};
  53         if (p1.score >= 21) {
  54                 r.p1wins++;
  55         } else if (p2.score >= 21) {
  56                 r.p2wins++;
  57         } else if (p1turn) {
  58                 for (int i = 1; i<=3; i++)
  59                         for (int j = 1; j<=3; j++)
  60                                 for (int k = 1; k<=3; k++)
  61                                         add_result(&r, play(!p1turn, move(p1, i+j+k), p2));
  62         } else {
  63                 for (int i = 1; i<=3; i++)
  64                         for (int j = 1; j<=3; j++)
  65                                 for (int k = 1; k<=3; k++)
  66                                         add_result(&r, play(!p1turn, p1, move(p2, i+j+k)));
  67         }
  68         return r;
  69 }
  70
  71 int main()
  72 {
  73         struct player p1 = {.score=0}, p2 = {.score=0};
  74         if (2 != scanf(
  75                         "Player 1 starting position: %d\n"
  76                         "Player 2 starting position: %d\n", &p1.pos, &p2.pos))
  77                 return 1;
  78
  79         struct result r = play(true, p1, p2);
  80         printf("%lu\n", r.p1wins > r.p2wins ? r.p1wins : r.p2wins);
  81 }