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
char Posvalue[13][13][13][13][13][13][13][13][13][13][13][13];
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:
bonzo.c:1: size of array `Posvalue' is too largeYeah, it's pretty large; otherwise this would be an easy problem.
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");
}
}