Skip to content

Instantly share code, notes, and snippets.

@ficusk

ficusk/war.c

Created October 5, 2019 00:23
Show Gist options
  • Save ficusk/5e1c344cac3ad0a4a9d6036afd4a7696 to your computer and use it in GitHub Desktop.
Save ficusk/5e1c344cac3ad0a4a9d6036afd4a7696 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
war.c
// -rw-r--r--@ 1 ficus 1876110778 5344 Oct 8 2004 war.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>
typedef struct _card card;
#define min(a,b) ((a)<(b)?(a):(b))
#define PLUS_B 0
struct _card {
int value;
card *next;
};
typedef struct {
card *top;
card *bottom;
int count;
} deck;
deck deck_a;
deck deck_b;
deck spoils;
#define SUIT_SHIFT 8
#define RANK_MASK 0xff
char card_names[] = { '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A' };
char suit_names[] = { 'c', 'd', 'h', 's' };
void
dump(deck *d)
{
card *c;
for (c = d->top; c != NULL; c = c->next) {
printf("%c%c, ", card_names[(c->value & RANK_MASK)], suit_names[c->value >> SUIT_SHIFT]);
}
printf("\n");
}
void
_shuffle(int *values, int count)
{
int i, ii;
for (ii = 0; ii < 5; ii++) {
for (i = 0; i < count; i++) {
int s = values[i];
int p = rand() % count;
values[i] = values[p];
values[p] = s;
}
}
}
void
shuffle(deck *d)
{
int *ii = (int *)malloc(sizeof(int) * d->count);
card *c;
int i = 0;
for (c = d->top; c != NULL; c = c->next) {
ii[i++] = c->value;
}
_shuffle(ii, i);
i = 0;
for (c = d->top; c != NULL; c = c->next) {
c->value = ii[i++];
}
}
void
add_top(deck *d, int v)
{
card *c = (card *)malloc(sizeof(card));
c->value = v;
c->next = d->top;
d->top = c;
if (d->bottom == NULL)
d->bottom = c;
d->count++;
}
void
add_bottom(deck *d, int v)
{
card *c = (card *)malloc(sizeof(card));
c->value = v;
c->next = NULL;
if (d->bottom != NULL) {
d->bottom->next = c;
}
d->bottom = c;
if (d->top == NULL)
d->top = c;
d->count++;
}
int
pick_top(deck *d)
{
card *pick;
int v;
if (d->top == NULL)
return -1;
pick = d->top;
d->top = d->top->next;
if (d->top == NULL)
d->bottom = NULL;
v = pick->value;
free(pick);
d->count--;
return v;
}
void
init_decks()
{
int i, ii;
int init[52];
for (ii = 0; ii < 4; ii++) {
for (i = 0; i < 13; i++) {
init[(ii*13)+i] = i | (ii << SUIT_SHIFT);
}
}
_shuffle(init, 52);
deck_a.top = NULL;
deck_b.top = NULL;
deck_a.bottom = NULL;
deck_b.bottom = NULL;
deck_a.count = 0;
deck_b.count = 0;
for (i = 0; i < 26; i++) {
add_top(&deck_a, init[i]);
}
for (i = 26; i < 52; i++) {
add_top(&deck_b, init[i]);
}
}
void
cleanup_decks()
{
while (pick_top(&deck_a) != -1);
while (pick_top(&deck_b) != -1);
while (pick_top(&spoils) != -1);
}
void push_spoils(deck *d)
{
int v;
shuffle(&spoils);
while ((v = pick_top(&spoils)) != -1)
add_bottom(d, v);
}
int pop(deck *d)
{
int v = pick_top(d);
add_top(&spoils, v);
return v;
}
#define A_WINS 1
#define B_WINS 2
#define pop_a() pop(&deck_a)
#define pop_b() pop(&deck_b)
int findstuck_orig[52];
int findstuck[52];
int
play1(int *_moves)
{
int moves = 0;
for (;;) {
int a = pop(&deck_a);
int b = pop(&deck_b)+PLUS_B;
while (min(12, (a & RANK_MASK)) == min(12, (b & RANK_MASK))) {
//printf("WAR\n");
switch(deck_a.count) {
default:
case 4:
a = pop_a();
case 3:
a = pop_a();
case 2:
a = pop_a();
case 1:
a = pop_a();
case 0:
}
//printf("A (%d) risks: "); dump(&spoils);
switch(deck_b.count) {
default:
case 4:
b = pop_b()+PLUS_B;
case 3:
b = pop_b()+PLUS_B;
case 2:
b = pop_b()+PLUS_B;
case 1:
b = pop_b()+PLUS_B;
case 0:
}
//printf("B (%d) risks: ", b); dump(&spoils);
}
if ((a & RANK_MASK) == 12 && (b & RANK_MASK) == 0) {
push_spoils(&deck_b);
/*
} else if ((a & RANK_MASK == 0 && (b & RANK_MASK) == 12) {
push_spoils(&deck_a);
*/
} else if (min(12, (a & RANK_MASK)) > min(12, (b & RANK_MASK))) {
push_spoils(&deck_a);
} else {
push_spoils(&deck_b);
}
moves++;
#if 0
if (++moves >= 10000) {
if (moves == 10000) {
card *c;
int iii = 0;
for (c = deck_a.top; c != NULL; c = c->next) {
findstuck_orig[iii++] = c->value;
}
for (c = deck_b.top; c != NULL; c = c->next) {
findstuck_orig[iii++] = c->value;
}
printf("A:"); dump(&deck_a);
printf("B:"); dump(&deck_b);
} else {
card *c;
int iii = 0;
for (c = deck_a.top; c != NULL; c = c->next) {
findstuck[iii++] = c->value;
}
for (c = deck_b.top; c != NULL; c = c->next) {
findstuck[iii++] = c->value;
}
if (memcmp(findstuck, findstuck_orig, sizeof(findstuck)) == 0) {
printf("LOOP at 10000 and %d!\n", moves);
printf("A:"); dump(&deck_a);
printf("B:"); dump(&deck_b);
exit(1);
}
}
}
#endif
if (deck_a.count == 0) {
//printf("A wins\n");
*_moves = moves;
return A_WINS;
} else if (deck_b.count == 0) {
//printf("B wins\n");
*_moves = moves;
return B_WINS;
}
}
}
int
main()
{
int a_wins = 0, b_wins = 0, total = 0;
struct timeval tv;
int moves;
long long move_log = 0;
gettimeofday(&tv, 0);
srand(tv.tv_sec * tv.tv_usec);
while (1) {
int result;
init_decks();
result = play1(&moves);
cleanup_decks();
if (result == A_WINS) {
//printf("A wins in %d moves\n", moves);
a_wins++;
} else {
//printf("B wins in %d moves\n", moves);
b_wins++;
}
total++;
move_log += moves;
if ((total % 1000) == 0) {
printf("a: %d (%.2f%%), b: %d (%.2f%%) (avg moves %.2f)\n",
a_wins, ((double)a_wins) / (double)total,
b_wins, ((double)b_wins) / (double)total,
(double)move_log / (double)total);
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment