January 2000 Programmer's Challenge

Peg Triangles

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Saturday, 1 January 2000

Welcome to the New Year! If you’re not one of those people who quibble about whether the new century starts in 2000 or 2001, welcome also to a new century and a new millennium! As I write this, I can’t be certain whether the doomsday predictions will turn out to have had any validity, but I’m betting that as you read this, the lights will be on, the telephones will work, the ATMs might be occasionally short of cash, the grocery stores will be replenishing their canned goods, and the pundits will be questioning what the fuss was all about. (At least this is my prediction for the so-called First World — I’m not close enough to the situation in the rest of the world to be as confident.) Of course, as someone whose Real Job included making certain that this transition to January was as boring as any other, I know that there was a lot of hard work invested in ensuring that life went on in the IT world.

But I’m betting that most of you are ready and able to take on this month’s Programmer’s Challenge. Especially since most of you are presumably Mac users, who didn’t (or don’t) have to go through the complicated process of remediating their Monopoly-OS machine so that it would continue to function. We’re going to make the Challenge a little simpler this month, in hopes of encouraging some new participants to take a shot at making the Top Five.

#if defined(__cplusplus)
extern "C" {
#endif

typedef struct TrianglePegPosition {
  short row;  /* 0..numberOfRows-1 */
  short col;  /* -row, -row+2, ..., +row */
} TrianglePegPosition;

typedef struct PegJump {
  TrianglePegPosition from;
  TrianglePegPosition to;
      // must satisfy
      //    (((to.row == from.row) && (to.col == from.col +- 4) && 
      //      ((from.row, from.col +-2) occupied))  ||
      //     ((to.row == from.row +- 2) && (to.col == from.col +- 2) &&      //      ((from.row +- 1, from.col +-1) occupied)) )
} PegJump;

short /* number of moves */ SolvePegTriangle (
  short triangleSize,    /* number of rows in triangle to solve */
  short numInitialPegs,  /* number of pegs in starting puzzle position */
  TrianglePegPosition initialPegPositions[],
        /* peg locations in starting puzzle position */
  PegJump pegJumps[]
        /* return peg moves that solve the puzzle here, in sequence */
);

#if defined(__cplusplus)
}
#endif