This month’s Exercise was inspired by a program I recall from years ago called The Drunk and the Lamppost. It’s not the classic joke, but an examination of random movements and probability.

In the simulation, the lamppost was in the center of a grid. The drunk would wander randomly about the grid, similar to the problem presented in this month’s Exercise. The observation made as that eventually the drunk would return to the lamppost. This program is a proof of some higher math concept that’s beyond me, but the puzzle stuck in my brain.

Unlike the Drunk and the Lamppost example, the Wandering King tries to get off the grid. (When the drunk hit the edge of the grid, he changed directions.)

My original solution used a two-dimensional array to track the king’s movements. After toying with it a while, I discovered a better solution is to keep the king’s location in a structure and dispense with the game grid array. Here is the structure is used:

struct location {
    int x;
    int y;
};

With the structure mapping the king’s location, the array was no longer necessary. I could check the x and y members of the structure to update and confirm the king’s position. The grid can still be output without an array; all that’s needed is the king’s coordinates. Here’s the show_grid() function I wrote as part of my solution:

void show_grid(int t, struct location m)
{
    int x,y;

    if( t == 0 )
        puts("Start!");
    else
        printf("Turn %d:\n",t);

    for(x=0;x<SIZE;x++)
    {
        for(y=0;y<SIZE;y++)
        {
            if( x==m.x && y==m.y )
                printf(" X ");
            else
                printf(" . ");
        }
        putchar('\n');
    }
}

Argument t is the turn number and m is the king’s structure with x and y members. The SIZE constant expression is the grid’s dimensions, which is set to 9 in my solution. In the function, the x and y (row and column) variables are compared with their counterparts in the king’s m structure. When the king’s position matches, an X is output instead of a dot in the grid. No array is necessary.

A second function, direction(), returns the values -1, 0, or 1. This value is used in a while loop inside the main() function to change the king’s location. An if statement tests the updated location to see whether the king has wandered off the grid, with values of x or y less than 0 or greater than the SIZE constant.

Click here to view my full solution.

I hope that you enjoyed the Exercise and devised a clever solution. Remember, my solution isn’t the only or best one. Any programming puzzle can be solved in a number of interesting ways.