21b.c

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