**Did you come here via search engine?**
Sorry, this webpage won't play Waldo's Nim
with you directly. This is the reference answer
to Exercise 5.4 in a free
on-line programming course.
(If you have a C compiler you can create your own
interactive game from this page, but we are focussed on
interesting algorithmic issues and provide no
aesthetic embellishments.)

Waldo's Nim is a game in the *Nim* or *Chomp*
family.
Start with twelve rows of twelve jelly beans each.
Two players alternate turns, removing (and eating) jelly beans.
Whoever eats the last jelly bean loses.

The only legal moves are *a*-by-*b* ``rectangles:''
You remove *b* beans from each of the *a* smallest (non-empty) rows.
The player can choose his own *a* and *b*, as long as both numbers
are positive, there are at least *a* non-empty rows, and at least
*b* beans in each non-empty row.

Solving this kind of game by brute force is quite straightforward:
work backwards, solving the simplest endings first.
One bit of information is retained in memory for each solved ending;
the bit tells you which player will win from that position.
A position will be described by the 12 integers *x1, x2, ..., x12*
denoting the number of beans in each of 12 rows;
it will be convenient to address these game values with C syntax like:

Posvalue[x1][x2][x3][x4][x5][x6][x7][x8][x9][x10][x11][x12]

Since each row can contain anywhere from 0 to 12 beans as the game progresses, a logical way to define the memory structure would be

This wastes 7 out of every 8 bits, and it would be nice to avoid that, but it's rather the least of our worries here. When I try to compile the above statement with FSF's C compiler I get:char Posvalue[13][13][13][13][13][13][13][13][13][13][13][13];

Yeah, it's pretty large; otherwise this would be an easy problem.bonzo.c:1: size of array `Posvalue' is too large

Compile the attached source code and the machine will play
Waldo's Nim with you.
(Reduce **WID** if your machine has a small memory.)
Do you see how I avoid the fixed array
with its preposterous memory requirement?
(Do you see that C's unique `*' and `[]' operators allow a
syntactic elegance unavailable to, say, Fortran?)
I don't blame you a bit if you decide this program is not a thing
of beauty, but how would *you* code it?

#define NROW 12 /* Don't change, without several other changes too */ #define WID 12 /* Reduce this dimension to reduce memory usage */ typedef unsigned short **********Node; main() { int psize[NROW+1], plast, numpile, numrem, i, j, moveno; unsigned short *winbits; Node Posvalue[WID+1], *grow[NROW-2], calloc(); #define INDX(i) \ (i > plast-1 ? 0 : psize[i+1] - (i >= plast-numpile ? numrem : 0)) #define NFOR(N) \ for (psize[N] = 0; \ psize[N] <= psize[N-1] \ && (N > NROW - 2 || N == NROW - 2 && \ (winbits = (unsigned short *)(*grow[N-1]++ \ = calloc(1, WID * sizeof (unsigned short)))) \ || (grow[N] = (Node *)(*grow[N-1]++ \ = calloc(1, ((unsigned)psize[N]+1) \ * sizeof (Node))))); psize[N]++, plast = N) #define WINNER (Posvalue \ [INDX(0)][INDX(1)][INDX(2)][INDX(3)][INDX(4)][INDX(5)] \ [INDX(6)][INDX(7)][INDX(8)][INDX(9)][INDX(10)] & 1 << INDX(11)) grow[0] = Posvalue; psize[0] = WID; plast = 0; /* * After the foregoing preliminaries, a brief nested * loop suffices to solve every position. */ NFOR(1) NFOR(2) NFOR(3) NFOR(4) NFOR(5) NFOR(6) NFOR(7) NFOR(8) NFOR(9) NFOR(10) NFOR(11) NFOR(12) { if (plast) { for (numpile = 1; numpile <= plast; numpile++) for (numrem = 1; numrem <= psize[plast]; numrem++) if (WINNER) goto contin_3; winbits[INDX(10)] |= 1 << INDX(11); contin_3: ; } } /* The winning strategies have all been found. * Now let's just play at top speed with whoever's * at the other end of sockets stdin and stdout. */ while (1) { for (j = 1; j < NROW+1; j++) psize[j] = WID; plast = NROW; for (moveno = 1; plast; moveno++) { for (i = 1; i <= plast; i++) printf("%s%2d%s", i == 1 ? " [" : "", psize[i], i == plast ? "] : \n" : " "); if (moveno & 1) while (1) { printf("Enter num piles and num beans per pile:\n"); scanf("%d %d", &numpile, &numrem); if (numpile >= 1 && numpile <= plast && numrem >= 1 && numrem <= psize[plast]) break; printf("Illegal move; try again.\n"); } else { for (numpile = 1; numpile <= plast; numpile++) for (numrem = 1; numrem <= psize[plast]; numrem++) if (WINNER) goto move; numpile = numrem = 1; move: printf("My move: %d piles and %d beans per pile.\n", numpile, numrem); } for (j = 0; j < NROW; j++) psize[j+1] = INDX(j); for (plast = j = 0; j < NROW; j++) if (psize[j+1]) ++plast; } printf("%s Win!!!\n", moveno & 1 ? "You" : "I"); printf("Let's play again\n"); } }

Go back to my home page.