6 struct result
{ unsigned long p1wins
; unsigned long p2wins
; };
7 struct player
{ int pos
; int score
; };
9 struct key
{ bool p1turn
; struct player p1
; struct player p2
; } key
;
14 struct player
move (struct player p
, int steps
)
16 p
.pos
= (p
.pos
+steps
)%10;
23 struct cache
*cache
= NULL
;
25 struct result
playd (bool p1turn
, struct player p1
, struct player p2
);
26 struct result
play(bool p1turn
, struct player p1
, struct player p2
)
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
);
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
);
44 void add_result(struct result
*l
, struct result r
)
46 l
->p1wins
+= r
.p1wins
;
47 l
->p2wins
+= r
.p2wins
;
50 struct result
playd (bool p1turn
, struct player p1
, struct player p2
)
52 struct result r
= {.p1wins
=0, .p2wins
=0};
55 } else if (p2
.score
>= 21) {
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
));
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
)));
73 struct player p1
= {.score
=0}, p2
= {.score
=0};
75 "Player 1 starting position: %d\n"
76 "Player 2 starting position: %d\n", &p1
.pos
, &p2
.pos
))
79 struct result r
= play(true, p1
, p2
);
80 printf("%lu\n", r
.p1wins
> r
.p2wins
? r
.p1wins
: r
.p2wins
);