TweetFollow Us on Twitter

Mar 98 Challenge

Volume Number: 14 (1998)
Issue Number: 3
Column Tag: Programmer's Challenge

Programmer's Challenge

by Bob Boonstra, Westford, MA

Help Peter Get Home

Last summer, while he was on his way back to Perth from MacHack, Peter Lewis suggested a challenge based on airline schedules. His idea was to select the quickest route from an origin to a destination, given a schedule of flights between pairs of cities. This month's Challenge is based on Peter's suggestion, but embellished to capture the "probabilistic" nature of airline travel these days.

Your job is to write a routine FindQuickestRoute that will route Peter from his departureAirport to his arrivalAirport in as few simulated flight hours as possible. Peter's trip begins on startDay at startTime. He has a list of airports to which he can fly, and an airlineSchedule of flights between pairs of those airports. The airlineSchedule consists of a flightNumber that will take him from a fromAirport to a toAirport, nominally departing at a scheduledDepartureTime, and nominally taking nominalFlightDuration seconds to get there. The scheduledDepartureTime is expressed in the local time zone of the fromAirport, which is provided as a timeOffset from Universal Time associated with each of the airports. Some of the flights in the airlineSchedule operate only on particular days, described in the operatingDays associated with each flightNumber.

Each of the airports has a minConnectTime, which is the minimum amount of time following one's arrival at the airport before one can catch a connecting flight. This applies to the initial flight, which must be scheduled to leave at least minConnectTime after the startTime of Peter's adventure. Each subsequent connecting leg must also be scheduled to leave at least minConnectTime after the actual arrival time of the preceding leg.

Sounds simple enough so far, right? Except that airplanes seldom depart or arrive on time. So we have introduced a little randomness in our simulated airline operations. The actual departure time of each flight is modeled as a random variable with an exponential distribution, governed by the parameter lambdaDeparture. The duration of each flight is also modeled as an exponential distribution, governed by lambdaDuration. When you decide to take a flight, the callback routine myGetFlightTime will roll the exponential dice for you and return the number of minutes the flight actually took, measured from the scheduledDepartureTime, taking into account the departure delay and the duration delay. A few facts for those whose probability theory is a little rusty: an exponential distribution with parameter t has a probability density function of t*exp(-tx), an expected value of (1/t), and a variance of 1/t2.

The prototype for the code you should write is:

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

typedef char FlightNum[8],AirportName[64];

typedef enum {
 Sunday=0, Monday, Tuesday, Wednesday, Thursday, Friday, 
 Saturday} DayOfWeek;

typedef struct MyTime {
 long hour;   /* 0-23, 0==midnight */
 long min;    /* 0-59 */
} MyTime;

typedef struct {
 AirportName name;     /* airport name */
 MyTime timeOffset;    /* local time offset relative to Universal Time */
                       /* 0 == Greenwich, {-5,0}==Eastern Time, etc. */
 MyTime minConnectTime;/* minimum time to make a connection at this airport */
} Airport;

typedef struct {
 FlightNum flightNumber;
 AirportName fromAirport;
 AirportName toAirport;
 MyTime scheduledDepartureTime;  /* local departure time from fromAirport */
 MyTime nominalFlightDuration;   /* nominal flight duration */
 float lambdaDeparture;          /* parameter for actual flight departure
                                    (mins) */
 float lambdaDuration;           /* parameter for actual flight duration
                                    (mins) */
 Boolean operatingDays[7];       /* if operatingDays[d], flight valid on 
                                    day d */
} Flight;

typedef long (*GetFlightTime) (
      /* returns actual flight duration from scheduledDepartureTime in minutes */
 FlightNum flightNumber          /* flight number taken */
);

long FindQuickestRoute(          /* return travel time in seconds */
 AirportName departureAirport,   /* origin airport */
 AirportName arrivalAirport,     /* destination airport */
 DayOfWeek startDay,             /* day the adventure begins (local time) */
 MyTime startTime,               /* time the adventure begins (local time) */
 Airport airports[],             /* places to fly from/to */
 long numAirports,               /* number of entries in airports[] */
 Flight airlineSchedule[],       /* flights to choose from */
 long numFlights,                /* number of entries in airlineSchedule[] */
 GetFlightTime myGetFlightTime   /* callback that provides actual flight
                                    duration */
);

#if defined(__cplusplus)
}
#endif

My test code will keep track of the flights you choose in the myGetFlightTime routine. It will ensure that operatingDays and minConnectTime constraints are met, that the fromAirport for travel leg n+1 is the same as the toAirport for travel leg n, etc. Violations of these constraints will result in a 24 hour simulated time penalty.

Test cases will include several trials for each departure/arrival pair to average out randomness. The winner will be the solution that routes Peter to his destinations in the least amount of time, where time is calculated as cumulative simulated travel time plus a penalty of 1 simulated hour for every second of execution time required by your FindQuickestRoute solution.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. Thanks to Peter Lewis for inspiring this Challenge -- he wins two Challenge points for the suggestion.

Three Months Ago Winner

If the number of entries to the December Challenge is any indication, many Programmer's Challenge readers are also avid crossword puzzle-ists. Congratulations to Mat Hostetter (location unknown) for submitting the fastest of 14 entries Clueless Crosswords Challenge. The problem was to solve (or actually, to generate) a crossword puzzle given the pattern of open and blocked cells, along with a dictionary of words from which to choose. The dictionary contained up to ten extra words for each word in the crossword puzzle solution, making multiple solutions were possible.

The evaluation is based on the time required to solve each of five crossword puzzles three times, each time with the dictionary sorted differently. I used each puzzle three times because a number of contestants reported that execution time varied significantly depending on the sort order of the dictionary, a fact that was borne out in my tests. Some of the entries took two orders of magnitude more time to solve a puzzle for one sort order than for the same puzzle with a different sort order. The winning entry exhibited significantly less variability, ranging from a 4% difference for one crossword puzzle to a 63% difference for another puzzle.

Like many of the entries submitted, Mat's solution has a recursive component. To accommodate recursion, I gave each entry 512K of stack space.

The key to efficient solution of this Challenge was propagating the constraints imposed by puzzle squares where an "across" word intersected a "down" word. The style of crossword puzzle provided in the test code and used to evaluate this Challenge contained many blocks of cells that were 4x4 or larger, resulting in many such intersections. Mat uses a set of filter_for_length_N routines to efficiently propagate constraints imposed by the intersections. When reading the modestly commented code, pay particular attention to the create_placements routine used to identify possible word locations, and to the tighten_constraints routine used to eliminate conflicting word placements.

Five of the entries had not solved one or more test cases after ten minutes or more, exceeding my ability to wait for an answer. In these cases, a test time of 10 minutes was assessed.

The table below lists the total execution time in seconds for the fifteen test cases, code size, data size, and programming language for each entry. The number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges to date prior to this one. The entries marked with an asterisk are those which did not complete one or more test cases in the 10 minutes mentioned above.

Name                    Time   Code      Data  Language
Mat Hostetter           0.37  14196       200  C
Brad Smith              1.36   7532     61835  C
Tom Saxton (12)         1.42   4132         8  C
Jens Martin Bengaard    9.76   4108     16628  C++
Xan Gregg (114)        23.73   4536    224584  C
Randy Boring (73)      74.56   4260     35158  C
Ernst Munter (310)    107.81   5824     16460  C++
Sebastian Maurer (10) 389.23   3968       112  C++
Rainer Brockerhoff    606.03   4609    165577  C
(*) ACC Murphy (34)  2400.29   6528  10212602  Pascal
(*) Mike Miller      2433.70  10052       428  C++
(*) Eric Kenninga    5599.22   6076       188  C++
(*) Steve Wozniac    5925.92   2836        64  C
(*) H.L.             9000.00   6780      1732  C++

Top 20 Contestants

Here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated more than 10 points during that the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank  Name                Points
 1.   Munter, Ernst          200  
 2.   Boring, Randy           73
 3.   Cooper, Greg            61
 4.   Lewis, Peter            61
 5.   Mallett, Jeff           50
 6.   Nicolle, Ludovic        48
 7.   Murphy, ACC             34
 8.   Gregg, Xan              28
 9.   Antoniewicz, Andy       24
10.   Day, Mark               20
11.   Higgins, Charles        20
12.   Hostetter, Mat          20
13.   Studer, Thomas          20
14.   Gundrum, Eric           15
15.   Hart, Alan              14
16.   O'Connor, Turlough      14
17.   Picao, Miguel Cruz      14

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place  20 points            5th place  2 points
2nd place  10 points          finding bug  2 points
3rd place  7 points  suggesting Challenge  2 points
4th place  4 points

Here is Mat's winning solution:

Crossword.c
© 1997 Mat Hostetter

#define kMaxSize 32
typedef char Puzzle[kMaxSize][kMaxSize];  /* referenced as [x][y] */

void Crossword(
 Puzzle thePuzzle,    /* return solved puzzle here */
 char *dictionary[],  /* array of words to choose from */
 long puzzleSize,    /* number of rows/cols in puzzle */
 long dictSize        /* number of words in dictionary */
);

/* Program begins here */

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Must be at least 32 bits, and ideally exactly 32 bits. */
typedef long letter_mask_t;

typedef struct {
 const char *original_word;
 unsigned char letter[1]; /* variable-sized array of values [1, 26]. */
} move_t;

/* Non-portable hack to compute size of above struct given how many
 * letters it has. It rounds up to sizeof(void *) to guarantee
 * alignment constraints are met. */
#define MOVE_SIZE(n)                  \
 (((sizeof(void *) + (n) + (sizeof(void *) - 1))    \
  / sizeof(void *))                  \
  * sizeof(void *))

#define NEXT_MOVE(m, n) ((move_t *) ((char *) (m) + (n)))

typedef enum {
 CYCLENESS_UNKNOWN,
 IN_CYCLE,
 NOT_IN_CYCLE
} cycleness_t;

typedef struct _placement_t {
 /* number of entries in `move' array. */
 long num_moves;

 /* If this == current_mark, this placement_t is "marked". We use
  * this for things like recursive searches. */
 unsigned long mark;

 /* Number of letters in each entry of the `move' array. */
 unsigned short letters_per_move;
 
 /* Byte size of each element in the `move' array. */
 unsigned short move_size;

 /* Where does this start? */
 unsigned short start_x, start_y;

 /* Direction this heads. */
 unsigned short dx, dy;

 /* Is this partition part of a cyclic dependency? */
 cycleness_t in_cycle;

 /* Totally done with this placement? */
 char done;

 /* Field temporarily used during recursion. */
 long depth;

 /* 1D index into the board where each letter is placed. */
 unsigned long where[kMaxSize]; 
 
 /* Other placements that intersect this one. */
 struct _placement_t *neighbor[kMaxSize + 1]; 
        /* NULL-terminated. */

 /* array of variable-size objects! Don't dereference this array normally. */
 move_t *move;
} placement_t;

/* No -1 so we can save room for NULL at the end. */
#define PLACEMENT_SIZE(n) \
    (sizeof(placement_t) + (n) * sizeof(move_t *))

filter_for_length_1
static void
filter_for_length_1(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(1));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(1));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   m = NEXT_MOVE(m, MOVE_SIZE(1));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
}

filter_for_length_2
static void
filter_for_length_2(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(2));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(2));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   m = NEXT_MOVE(m, MOVE_SIZE(2));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
}

filter_for_length_3
static void
filter_for_length_3(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(3));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(3));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   m = NEXT_MOVE(m, MOVE_SIZE(3));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
}

filter_for_length_4
static void
filter_for_length_4(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(4));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(4));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   m = NEXT_MOVE(m, MOVE_SIZE(4));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
}

filter_for_length_5
static void
filter_for_length_5(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(5));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(5));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   m = NEXT_MOVE(m, MOVE_SIZE(5));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
}

filter_for_length_6
static void
filter_for_length_6(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(6));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(6));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   m = NEXT_MOVE(m, MOVE_SIZE(6));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
}

filter_for_length_7
static void
filter_for_length_7(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 const letter_mask_t global_mask_6 = 
      letters_allowed[p->where[6]];
 letter_mask_t allowed_by_us_6 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(7));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))
    || !(global_mask_6 & (1 << m->letter[6]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(7));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   allowed_by_us_6 |= 1 << m->letter[6];
   m = NEXT_MOVE(m, MOVE_SIZE(7));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
 allowed_by_us[6] = allowed_by_us_6;
}

filter_for_length_8
static void
filter_for_length_8(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 const letter_mask_t global_mask_6 = 
      letters_allowed[p->where[6]];
 letter_mask_t allowed_by_us_6 = 0;
 const letter_mask_t global_mask_7 = 
      letters_allowed[p->where[7]];
 letter_mask_t allowed_by_us_7 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(8));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))
    || !(global_mask_6 & (1 << m->letter[6]))
    || !(global_mask_7 & (1 << m->letter[7]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(8));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   allowed_by_us_6 |= 1 << m->letter[6];
   allowed_by_us_7 |= 1 << m->letter[7];
   m = NEXT_MOVE(m, MOVE_SIZE(8));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
 allowed_by_us[6] = allowed_by_us_6;
 allowed_by_us[7] = allowed_by_us_7;
}

filter_for_length_9
static void
filter_for_length_9(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 const letter_mask_t global_mask_6 = 
      letters_allowed[p->where[6]];
 letter_mask_t allowed_by_us_6 = 0;
 const letter_mask_t global_mask_7 = 
      letters_allowed[p->where[7]];
 letter_mask_t allowed_by_us_7 = 0;
 const letter_mask_t global_mask_8 = 
      letters_allowed[p->where[8]];
 letter_mask_t allowed_by_us_8 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(9));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))
    || !(global_mask_6 & (1 << m->letter[6]))
    || !(global_mask_7 & (1 << m->letter[7]))
    || !(global_mask_8 & (1 << m->letter[8]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   void *copy3 = ((void **)last)[3];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   ((void **)m)[3] = copy3;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(9));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   allowed_by_us_6 |= 1 << m->letter[6];
   allowed_by_us_7 |= 1 << m->letter[7];
   allowed_by_us_8 |= 1 << m->letter[8];
   m = NEXT_MOVE(m, MOVE_SIZE(9));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
 allowed_by_us[6] = allowed_by_us_6;
 allowed_by_us[7] = allowed_by_us_7;
 allowed_by_us[8] = allowed_by_us_8;
}

filter_for_length_10
static void
filter_for_length_10(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 const letter_mask_t global_mask_6 = 
      letters_allowed[p->where[6]];
 letter_mask_t allowed_by_us_6 = 0;
 const letter_mask_t global_mask_7 = 
      letters_allowed[p->where[7]];
 letter_mask_t allowed_by_us_7 = 0;
 const letter_mask_t global_mask_8 = 
      letters_allowed[p->where[8]];
 letter_mask_t allowed_by_us_8 = 0;
 const letter_mask_t global_mask_9 = 
      letters_allowed[p->where[9]];
 letter_mask_t allowed_by_us_9 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(10));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))
    || !(global_mask_6 & (1 << m->letter[6]))
    || !(global_mask_7 & (1 << m->letter[7]))
    || !(global_mask_8 & (1 << m->letter[8]))
    || !(global_mask_9 & (1 << m->letter[9]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   void *copy3 = ((void **)last)[3];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   ((void **)m)[3] = copy3;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(10));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   allowed_by_us_6 |= 1 << m->letter[6];
   allowed_by_us_7 |= 1 << m->letter[7];
   allowed_by_us_8 |= 1 << m->letter[8];
   allowed_by_us_9 |= 1 << m->letter[9];
   m = NEXT_MOVE(m, MOVE_SIZE(10));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
 allowed_by_us[6] = allowed_by_us_6;
 allowed_by_us[7] = allowed_by_us_7;
 allowed_by_us[8] = allowed_by_us_8;
 allowed_by_us[9] = allowed_by_us_9;
}


filter_for_length_11
static void
filter_for_length_11(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 const letter_mask_t global_mask_6 = 
      letters_allowed[p->where[6]];
 letter_mask_t allowed_by_us_6 = 0;
 const letter_mask_t global_mask_7 = 
      letters_allowed[p->where[7]];
 letter_mask_t allowed_by_us_7 = 0;
 const letter_mask_t global_mask_8 = 
      letters_allowed[p->where[8]];
 letter_mask_t allowed_by_us_8 = 0;
 const letter_mask_t global_mask_9 = 
      letters_allowed[p->where[9]];
 letter_mask_t allowed_by_us_9 = 0;
 const letter_mask_t global_mask_10 = 
      letters_allowed[p->where[10]];
 letter_mask_t allowed_by_us_10 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(11));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))
    || !(global_mask_6 & (1 << m->letter[6]))
    || !(global_mask_7 & (1 << m->letter[7]))
    || !(global_mask_8 & (1 << m->letter[8]))
    || !(global_mask_9 & (1 << m->letter[9]))
    || !(global_mask_10 & (1 << m->letter[10]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   void *copy3 = ((void **)last)[3];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   ((void **)m)[3] = copy3;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(11));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   allowed_by_us_6 |= 1 << m->letter[6];
   allowed_by_us_7 |= 1 << m->letter[7];
   allowed_by_us_8 |= 1 << m->letter[8];
   allowed_by_us_9 |= 1 << m->letter[9];
   allowed_by_us_10 |= 1 << m->letter[10];
   m = NEXT_MOVE(m, MOVE_SIZE(11));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
 allowed_by_us[6] = allowed_by_us_6;
 allowed_by_us[7] = allowed_by_us_7;
 allowed_by_us[8] = allowed_by_us_8;
 allowed_by_us[9] = allowed_by_us_9;
 allowed_by_us[10] = allowed_by_us_10;
}

filter_for_length_12
static void
filter_for_length_12(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 const letter_mask_t global_mask_6 = 
      letters_allowed[p->where[6]];
 letter_mask_t allowed_by_us_6 = 0;
 const letter_mask_t global_mask_7 = 
      letters_allowed[p->where[7]];
 letter_mask_t allowed_by_us_7 = 0;
 const letter_mask_t global_mask_8 = 
      letters_allowed[p->where[8]];
 letter_mask_t allowed_by_us_8 = 0;
 const letter_mask_t global_mask_9 = 
      letters_allowed[p->where[9]];
 letter_mask_t allowed_by_us_9 = 0;
 const letter_mask_t global_mask_10 = 
      letters_allowed[p->where[10]];
 letter_mask_t allowed_by_us_10 = 0;
 const letter_mask_t global_mask_11 = 
      letters_allowed[p->where[11]];
 letter_mask_t allowed_by_us_11 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(12));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))
    || !(global_mask_6 & (1 << m->letter[6]))
    || !(global_mask_7 & (1 << m->letter[7]))
    || !(global_mask_8 & (1 << m->letter[8]))
    || !(global_mask_9 & (1 << m->letter[9]))
    || !(global_mask_10 & (1 << m->letter[10]))
    || !(global_mask_11 & (1 << m->letter[11]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   void *copy3 = ((void **)last)[3];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   ((void **)m)[3] = copy3;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(12));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   allowed_by_us_6 |= 1 << m->letter[6];
   allowed_by_us_7 |= 1 << m->letter[7];
   allowed_by_us_8 |= 1 << m->letter[8];
   allowed_by_us_9 |= 1 << m->letter[9];
   allowed_by_us_10 |= 1 << m->letter[10];
   allowed_by_us_11 |= 1 << m->letter[11];
   m = NEXT_MOVE(m, MOVE_SIZE(12));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
 allowed_by_us[6] = allowed_by_us_6;
 allowed_by_us[7] = allowed_by_us_7;
 allowed_by_us[8] = allowed_by_us_8;
 allowed_by_us[9] = allowed_by_us_9;
 allowed_by_us[10] = allowed_by_us_10;
 allowed_by_us[11] = allowed_by_us_11;
}

filter_for_length_13
static void
filter_for_length_13(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 const letter_mask_t global_mask_6 = 
      letters_allowed[p->where[6]];
 letter_mask_t allowed_by_us_6 = 0;
 const letter_mask_t global_mask_7 = 
      letters_allowed[p->where[7]];
 letter_mask_t allowed_by_us_7 = 0;
 const letter_mask_t global_mask_8 = 
      letters_allowed[p->where[8]];
 letter_mask_t allowed_by_us_8 = 0;
 const letter_mask_t global_mask_9 = 
      letters_allowed[p->where[9]];
 letter_mask_t allowed_by_us_9 = 0;
 const letter_mask_t global_mask_10 = 
      letters_allowed[p->where[10]];
 letter_mask_t allowed_by_us_10 = 0;
 const letter_mask_t global_mask_11 = 
      letters_allowed[p->where[11]];
 letter_mask_t allowed_by_us_11 = 0;
 const letter_mask_t global_mask_12 = 
      letters_allowed[p->where[12]];
 letter_mask_t allowed_by_us_12 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(13));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))
    || !(global_mask_6 & (1 << m->letter[6]))
    || !(global_mask_7 & (1 << m->letter[7]))
    || !(global_mask_8 & (1 << m->letter[8]))
    || !(global_mask_9 & (1 << m->letter[9]))
    || !(global_mask_10 & (1 << m->letter[10]))
    || !(global_mask_11 & (1 << m->letter[11]))
    || !(global_mask_12 & (1 << m->letter[12]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   void *copy3 = ((void **)last)[3];
   void *copy4 = ((void **)last)[4];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   ((void **)m)[3] = copy3;
   ((void **)m)[4] = copy4;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(13));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   allowed_by_us_6 |= 1 << m->letter[6];
   allowed_by_us_7 |= 1 << m->letter[7];
   allowed_by_us_8 |= 1 << m->letter[8];
   allowed_by_us_9 |= 1 << m->letter[9];
   allowed_by_us_10 |= 1 << m->letter[10];
   allowed_by_us_11 |= 1 << m->letter[11];
   allowed_by_us_12 |= 1 << m->letter[12];
   m = NEXT_MOVE(m, MOVE_SIZE(13));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
 allowed_by_us[6] = allowed_by_us_6;
 allowed_by_us[7] = allowed_by_us_7;
 allowed_by_us[8] = allowed_by_us_8;
 allowed_by_us[9] = allowed_by_us_9;
 allowed_by_us[10] = allowed_by_us_10;
 allowed_by_us[11] = allowed_by_us_11;
 allowed_by_us[12] = allowed_by_us_12;
}

filter_for_length_14
static void
filter_for_length_14(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 const letter_mask_t global_mask_6 = 
      letters_allowed[p->where[6]];
 letter_mask_t allowed_by_us_6 = 0;
 const letter_mask_t global_mask_7 = 
      letters_allowed[p->where[7]];
 letter_mask_t allowed_by_us_7 = 0;
 const letter_mask_t global_mask_8 = 
      letters_allowed[p->where[8]];
 letter_mask_t allowed_by_us_8 = 0;
 const letter_mask_t global_mask_9 = 
      letters_allowed[p->where[9]];
 letter_mask_t allowed_by_us_9 = 0;
 const letter_mask_t global_mask_10 = 
      letters_allowed[p->where[10]];
 letter_mask_t allowed_by_us_10 = 0;
 const letter_mask_t global_mask_11 = 
      letters_allowed[p->where[11]];
 letter_mask_t allowed_by_us_11 = 0;
 const letter_mask_t global_mask_12 = 
      letters_allowed[p->where[12]];
 letter_mask_t allowed_by_us_12 = 0;
 const letter_mask_t global_mask_13 = 
      letters_allowed[p->where[13]];
 letter_mask_t allowed_by_us_13 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(14));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))
    || !(global_mask_6 & (1 << m->letter[6]))
    || !(global_mask_7 & (1 << m->letter[7]))
    || !(global_mask_8 & (1 << m->letter[8]))
    || !(global_mask_9 & (1 << m->letter[9]))
    || !(global_mask_10 & (1 << m->letter[10]))
    || !(global_mask_11 & (1 << m->letter[11]))
    || !(global_mask_12 & (1 << m->letter[12]))
    || !(global_mask_13 & (1 << m->letter[13]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   void *copy3 = ((void **)last)[3];
   void *copy4 = ((void **)last)[4];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   ((void **)m)[3] = copy3;
   ((void **)m)[4] = copy4;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(14));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   allowed_by_us_6 |= 1 << m->letter[6];
   allowed_by_us_7 |= 1 << m->letter[7];
   allowed_by_us_8 |= 1 << m->letter[8];
   allowed_by_us_9 |= 1 << m->letter[9];
   allowed_by_us_10 |= 1 << m->letter[10];
   allowed_by_us_11 |= 1 << m->letter[11];
   allowed_by_us_12 |= 1 << m->letter[12];
   allowed_by_us_13 |= 1 << m->letter[13];
   m = NEXT_MOVE(m, MOVE_SIZE(14));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
 allowed_by_us[6] = allowed_by_us_6;
 allowed_by_us[7] = allowed_by_us_7;
 allowed_by_us[8] = allowed_by_us_8;
 allowed_by_us[9] = allowed_by_us_9;
 allowed_by_us[10] = allowed_by_us_10;
 allowed_by_us[11] = allowed_by_us_11;
 allowed_by_us[12] = allowed_by_us_12;
 allowed_by_us[13] = allowed_by_us_13;
}

filter_for_length_15
static void
filter_for_length_15(placement_t *p, 
      letter_mask_t *letters_allowed,
      letter_mask_t *allowed_by_us)
{
 move_t *m, *last;
 const letter_mask_t global_mask_0 = 
      letters_allowed[p->where[0]];
 letter_mask_t allowed_by_us_0 = 0;
 const letter_mask_t global_mask_1 = 
      letters_allowed[p->where[1]];
 letter_mask_t allowed_by_us_1 = 0;
 const letter_mask_t global_mask_2 = 
      letters_allowed[p->where[2]];
 letter_mask_t allowed_by_us_2 = 0;
 const letter_mask_t global_mask_3 = 
      letters_allowed[p->where[3]];
 letter_mask_t allowed_by_us_3 = 0;
 const letter_mask_t global_mask_4 = 
      letters_allowed[p->where[4]];
 letter_mask_t allowed_by_us_4 = 0;
 const letter_mask_t global_mask_5 = 
      letters_allowed[p->where[5]];
 letter_mask_t allowed_by_us_5 = 0;
 const letter_mask_t global_mask_6 = 
      letters_allowed[p->where[6]];
 letter_mask_t allowed_by_us_6 = 0;
 const letter_mask_t global_mask_7 = 
      letters_allowed[p->where[7]];
 letter_mask_t allowed_by_us_7 = 0;
 const letter_mask_t global_mask_8 = 
      letters_allowed[p->where[8]];
 letter_mask_t allowed_by_us_8 = 0;
 const letter_mask_t global_mask_9 = 
      letters_allowed[p->where[9]];
 letter_mask_t allowed_by_us_9 = 0;
 const letter_mask_t global_mask_10 = 
      letters_allowed[p->where[10]];
 letter_mask_t allowed_by_us_10 = 0;
 const letter_mask_t global_mask_11 = 
      letters_allowed[p->where[11]];
 letter_mask_t allowed_by_us_11 = 0;
 const letter_mask_t global_mask_12 = 
      letters_allowed[p->where[12]];
 letter_mask_t allowed_by_us_12 = 0;
 const letter_mask_t global_mask_13 = 
      letters_allowed[p->where[13]];
 letter_mask_t allowed_by_us_13 = 0;
 const letter_mask_t global_mask_14 = 
      letters_allowed[p->where[14]];
 letter_mask_t allowed_by_us_14 = 0;
 last = (move_t *) ((char *) p->move + 
      (p->num_moves - 1) * MOVE_SIZE(15));
 for (m = p->move; m->original_word != NULL; )
 {
  if (  !(global_mask_0 & (1 << m->letter[0]))
    || !(global_mask_1 & (1 << m->letter[1]))
    || !(global_mask_2 & (1 << m->letter[2]))
    || !(global_mask_3 & (1 << m->letter[3]))
    || !(global_mask_4 & (1 << m->letter[4]))
    || !(global_mask_5 & (1 << m->letter[5]))
    || !(global_mask_6 & (1 << m->letter[6]))
    || !(global_mask_7 & (1 << m->letter[7]))
    || !(global_mask_8 & (1 << m->letter[8]))
    || !(global_mask_9 & (1 << m->letter[9]))
    || !(global_mask_10 & (1 << m->letter[10]))
    || !(global_mask_11 & (1 << m->letter[11]))
    || !(global_mask_12 & (1 << m->letter[12]))
    || !(global_mask_13 & (1 << m->letter[13]))
    || !(global_mask_14 & (1 << m->letter[14]))) {
   void *copy0 = ((void **)last)[0];
   void *copy1 = ((void **)last)[1];
   void *copy2 = ((void **)last)[2];
   void *copy3 = ((void **)last)[3];
   void *copy4 = ((void **)last)[4];
   ((void **)m)[0] = copy0;
   ((void **)m)[1] = copy1;
   ((void **)m)[2] = copy2;
   ((void **)m)[3] = copy3;
   ((void **)m)[4] = copy4;
   last->original_word = NULL;
   --p->num_moves;
   last = NEXT_MOVE(last, -MOVE_SIZE(15));
  } else {
   allowed_by_us_0 |= 1 << m->letter[0];
   allowed_by_us_1 |= 1 << m->letter[1];
   allowed_by_us_2 |= 1 << m->letter[2];
   allowed_by_us_3 |= 1 << m->letter[3];
   allowed_by_us_4 |= 1 << m->letter[4];
   allowed_by_us_5 |= 1 << m->letter[5];
   allowed_by_us_6 |= 1 << m->letter[6];
   allowed_by_us_7 |= 1 << m->letter[7];
   allowed_by_us_8 |= 1 << m->letter[8];
   allowed_by_us_9 |= 1 << m->letter[9];
   allowed_by_us_10 |= 1 << m->letter[10];
   allowed_by_us_11 |= 1 << m->letter[11];
   allowed_by_us_12 |= 1 << m->letter[12];
   allowed_by_us_13 |= 1 << m->letter[13];
   allowed_by_us_14 |= 1 << m->letter[14];
   m = NEXT_MOVE(m, MOVE_SIZE(15));
  }
 }
 allowed_by_us[0] = allowed_by_us_0;
 allowed_by_us[1] = allowed_by_us_1;
 allowed_by_us[2] = allowed_by_us_2;
 allowed_by_us[3] = allowed_by_us_3;
 allowed_by_us[4] = allowed_by_us_4;
 allowed_by_us[5] = allowed_by_us_5;
 allowed_by_us[6] = allowed_by_us_6;
 allowed_by_us[7] = allowed_by_us_7;
 allowed_by_us[8] = allowed_by_us_8;
 allowed_by_us[9] = allowed_by_us_9;
 allowed_by_us[10] = allowed_by_us_10;
 allowed_by_us[11] = allowed_by_us_11;
 allowed_by_us[12] = allowed_by_us_12;
 allowed_by_us[13] = allowed_by_us_13;
 allowed_by_us[14] = allowed_by_us_14;
}

typedef filter_func_t
typedef void (*filter_func_t)(placement_t *, 
      letter_mask_t *, letter_mask_t *);
static const filter_func_t filter_func[16] = { 0,
 filter_for_length_1,
 filter_for_length_2,
 filter_for_length_3,
 filter_for_length_4,
 filter_for_length_5,
 filter_for_length_6,
 filter_for_length_7,
 filter_for_length_8,
 filter_for_length_9,
 filter_for_length_10,
 filter_for_length_11,
 filter_for_length_12,
 filter_for_length_13,
 filter_for_length_14,
 filter_for_length_15,
};


/* Assorted constants, in an enum so debugger knows about them. */
enum {
 /* Bit mask indicating all letters. */
 ALL_LETTERS = (1 << 26) - 1,

 /* Bit mask indicating "this square is not an intersection point
  * so ignore it". */
 NOT_INTERSECTION_POINT = 0x7FFFFFFF,

 /* Empty square in the puzzle. */
 EMPTY_SQUARE = 0
};

static unsigned long current_mark = 1;

#define set_placement_mark(p)   ((p)->mark = current_mark)
#define clear_placement_mark(p)  ((p)->mark = current_mark - 1)
#define placement_is_marked(p)  ((p)->mark == current_mark)
#define clear_all_placement_marks() (++current_mark)


count_num_placements
/* Returns the total number of placements in the puzzle. */
static long
count_num_placements(Puzzle puzzle, long puzzle_size)
{
 long x, y, num_placements = 0;

 /* Horizontal placements. */
 for (y = 0; y < puzzle_size; y++)
  for (x = 0; x < puzzle_size - 1; x++)
   if (puzzle[x][y] == EMPTY_SQUARE && 
              puzzle[x + 1][y] == EMPTY_SQUARE)
    {
     ++num_placements;
     for (x++; x < puzzle_size && 
                        puzzle[x][y] == EMPTY_SQUARE; x++)
      ;
    }

 /* Vertical placements. */
 for (x = 0; x < puzzle_size; x++)
  for (y = 0; y < puzzle_size - 1; y++)
   if (puzzle[x][y] == EMPTY_SQUARE && 
              puzzle[x][y + 1] == EMPTY_SQUARE)
    {
     ++num_placements;
     for (y++; y < puzzle_size && 
                        puzzle[x][y] == EMPTY_SQUARE; y++)
      ;
    }

 return num_placements;
}

identify_placements
static placement_t *
identify_placements(Puzzle puzzle, long puzzle_size, 
      long *num_placements_ptr,
      placement_t *square_to_placement[kMaxSize][kMaxSize][2],
      char interesting_length[kMaxSize + 1])
{
 /* Create an empty map from squares to the placements that intersect. */
 long x, y, num_placements;
 placement_t *p, *placement;

 num_placements = count_num_placements(puzzle, puzzle_size);
 p = placement = (placement_t *) calloc(num_placements, 
                                        sizeof p[0]);
 /* Find all horizontal placements. */
 for (y = 0; y < puzzle_size; y++)
  for (x = 0; x < puzzle_size - 1; x++)
   if (puzzle[x][y] == EMPTY_SQUARE && 
              puzzle[x + 1][y] == EMPTY_SQUARE)
    {
     const long start_x = x;
     p->start_x = x;
     p->start_y = y;
     p->dx = 1;
     p->dy = 0;
     for (; x < puzzle_size && 
                        puzzle[x][y] == EMPTY_SQUARE; x++)
      square_to_placement[x][y][0] = p;
     ++p;
     interesting_length[x - start_x] = 1;
    }

 /* Find all vertical placements. */
 for (x = 0; x < puzzle_size; x++)
  for (y = 0; y < puzzle_size - 1; y++)
   if (puzzle[x][y] == EMPTY_SQUARE && 
              puzzle[x][y + 1] == EMPTY_SQUARE)
    {
     const long start_y = y;
     p->start_x = x;
     p->start_y = y;
     p->dx = 0;
     p->dy = 1;
          for (; y < puzzle_size && puzzle[x][y] ==
               EMPTY_SQUARE; 
                        y++)
      square_to_placement[x][y][1] = p;
     ++p;
     interesting_length[y - start_y] = 1;
    }
 /* assert(p == &placement[num_placements]); */

 *num_placements_ptr = num_placements;
 return placement;
}

intersect_placement_with_global_mask
/* Takes the list of moves allowed by a placement and uses that set
 * to tighten what's globally allowed for the squares it intersects.
 * "Marks" any placements whose word lists are changed as a result. */
static void
intersect_placement_with_global_mask(const placement_t *p,
      letter_mask_t *global_mask)
{
 const unsigned long move_size = p->move_size;
 int i;

 for (i = p->letters_per_move - 1; i >= 0; i--)
  {
   move_t *m;
   letter_mask_t mask = 0, g;

   /* Figure out the union of all letters valid for each square. */
   for (m = p->move; m->original_word != NULL; 
                m = NEXT_MOVE(m, move_size))
    mask |= 1 << m->letter[i];

   g = global_mask[p->where[i]];
   if ((g & mask) != g)
    {
     /* Mark this neighbor as being in need of further refinement,
      * since we have just disallowed some of his moves. */
     set_placement_mark(p->neighbor[i]);

     /* Note the new, tighter restriction on this square. */
     global_mask[p->where[i]] = g & mask;
    }
  }
}

create_ascii_to_letter
/* Creates an array mapping ASCII letter values to numbers 0-25. */
static void
create_ascii_to_letter(unsigned char ascii_to_letter[256])
{
 int let;
 memset(ascii_to_letter, 0, 256);
 for (let = 0; let < 26; let++)
  ascii_to_letter['a' + let] = 
          ascii_to_letter['A' + let] = let;
}

partition_words_by_length
static void
partition_words_by_length(char *dictionary[], long dict_size,
      const char interesting_length[kMaxSize + 1],
      const char **words_of_length[kMaxSize + 1],
      long num_words_of_length[kMaxSize + 1],
      void **mem_to_free_on_cleanup)
{
 long num_words_left[kMaxSize + 1], num_useful_words, 
          i, j, w, k;
 const char **r;
 void *raw_words_mem;
 
 /* Figure out how many words there are of each length. */
 for (i = 0; i <= kMaxSize; i++)
  num_words_of_length[i] = 0;
 num_useful_words = 0;
 for (w = 0; w < dict_size; w++)
  {
   size_t len = strlen(dictionary[w]);
   if (len <= kMaxSize && interesting_length[len])
    {
     ++num_words_of_length[len];
     ++num_useful_words;
    }
  }

 /* Allocate room for a pointer vector for each word length.
  * We'll just put all of the pointer vectors together into
  * one big block of memory, separated by a NULL pointer. */
 raw_words_mem = 
      malloc((num_useful_words + kMaxSize + 1) * sizeof r[0]);
 r = (const char **) raw_words_mem;
 for (k = 0; k <= kMaxSize; k++)
  {
   const long num_words_of_this_length = 
            num_words_of_length[k];
   words_of_length[k] = r;
   r[num_words_of_this_length] = NULL;
   r += num_words_of_this_length + 1;
           /* leave room for terminating NULL */
  }

 /* Note the words of each length. */
 memcpy(num_words_left, num_words_of_length, 
        sizeof num_words_left);
 for (j = 0; j < dict_size; j++)
  {
   size_t len = strlen(dictionary[j]);
   if (len <= kMaxSize && interesting_length[len])
    words_of_length[len][--num_words_left[len]] = 
                  dictionary[j];
  }

 /* Report the block of memory to free when done. */
 *mem_to_free_on_cleanup = raw_words_mem;
}

tighten_constraints
static int
tighten_constraints(placement_t *placement, long num_placements,
      letter_mask_t *letters_allowed, int do_acyclic)
{
 placement_t **orig_stack, **stack, *p;
 long n;

 stack = orig_stack = malloc((num_placements + 1) * 
        sizeof orig_stack[0]);
 *stack++ = NULL;

 /* On entry, we've marked every placement that needs to be explored
  * further, so push those on the stack. */
 for (n = num_placements - 1; n >= 0; n--)
  {
   placement_t *t = &placement[n];
   if (placement_is_marked(t))
    *stack++ = t;
  }

 while ((p = *--stack) != NULL)
  {
   letter_mask_t allowed_by_us[kMaxSize];
   long i;
   
   if (p->done || 
              (!do_acyclic && p->in_cycle == NOT_IN_CYCLE))
    continue;

   if (p->letters_per_move < 
                  sizeof filter_func / sizeof filter_func[0])
    (*filter_func[p->letters_per_move])(p, 
                      letters_allowed, allowed_by_us);
   else
    {
     letter_mask_t global_mask[kMaxSize];
     long i, move_size;
     move_t *m, *last;
    
     move_size = p->move_size;
     memset(allowed_by_us, 0, sizeof allowed_by_us);
    
     /* For speed, stash globally allowed letters in linear array. */
     for (i = 0; i < p->letters_per_move; i++)
      global_mask[i] = letters_allowed[p->where[i]];
    
     /* Loop through all words here, discarding illegal words and
      * accruing a new union mask. */
     last = (move_t *) ((char *) p->move + 
                  (p->num_moves - 1) * p->move_size);
     for (m = p->move; m->original_word != NULL; )
      {
       long j;
     
       /* See if word is legal. */
       for (j = p->letters_per_move - 1; j >= 0; j--)
        if (!(global_mask[j] & (1 << m->letter[j])))
         break;
       
       if (j < 0)
        {
         /* It's legal. Note the possible letters and move on. */
        long k;
        for (k = p->letters_per_move - 1; k >= 0; k--)
          allowed_by_us[k] |= 1 << m->letter[k];
         m = NEXT_MOVE(m, move_size);
        }
       else
        {
         /* It's illegal. Delete this move by replacing it with
          * the last move in the list. Profiling shows this is
          * a hotspot, so inline a memcpy using our knowledge
          * about what moves look like. */
         char *from, *to;
         long ctr;
         from = (char *) last;
         to = (char *) m;
         for (ctr = move_size; 
                          (ctr -= sizeof(void *)) >= 0; )
          *(void **)(to + ctr) = 
                                *(void **)(from + ctr);
         
         last->original_word = NULL;
         --p->num_moves;
         last = NEXT_MOVE(last, -move_size);
        }
      }
    }

   if (p->num_moves == 0)
    {
     /* No moves --> no solution. Quit now! */
     free(orig_stack);
     return 0;
    }

   /* Propagate our constraints to the global grid. If we actually
    * change anything, note that we need to recompute the valid
    * words list for whomever intersects the newly tightened square. */
   for (i = p->letters_per_move - 1; i >= 0; i--)
    {
     letter_mask_t g = letters_allowed[p->where[i]];
     if ((g & allowed_by_us[i]) != g)
      {
       placement_t *nbr;
       letters_allowed[p->where[i]] = 
                      g & allowed_by_us[i];
       nbr = p->neighbor[i];
       if (!placement_is_marked(nbr))
        {
         *stack++ = nbr;
         set_placement_mark(nbr);
        }
      }
    }

   clear_placement_mark(p);
  }

 free(orig_stack);
 return 1;
}

place_word
static void
place_word(Puzzle puzzle, int x, int y, int dx, int dy, 
          const char *word)
{
 for (; *word; word++)
  {
   puzzle[x][y] = *word;
   x += dx;
   y += dy;
  }
}

place_move
static void
place_move(Puzzle puzzle, placement_t *p, move_t *m)
{
 place_word(puzzle, p->start_x, p->start_y, 
            p->dx, p->dy, m->original_word);
}

solve_trivial_placements
/* Go ahead and fill in every placement where there's only one choice. */
static void
solve_trivial_placements(Puzzle puzzle, placement_t *placement,
        long num_placements)
{
 long i;

 /* Go ahead and make any move where there's only one choice. */
 for (i = 0; i < num_placements; i++)
  {
   placement_t *p = &placement[i];
   if (p->num_moves == 1)
    {
     place_move(puzzle, p, &p->move[0]);
     free(placement[i].move);
     placement[i].move = NULL;
     p->num_moves = 0;
     p->done = 1;
    }
  }
}

create_placements
static placement_t *
create_placements(Puzzle puzzle, long puzzle_size,
      char *dictionary[], long dict_size,
      letter_mask_t letters_allowed[kMaxSize * kMaxSize],
      long *letters_allowed_size_ptr,
      long *num_placements_ptr)
{
 /* Do we care about words of length n? */
 char interesting_length[kMaxSize + 1];
 long n, num_placements;
 placement_t *placement;
 const char **words_of_length[kMaxSize + 1];
 long num_words_of_length[kMaxSize + 1];
 move_t **hash_table = NULL;
 unsigned long max_hash_table_size = 0;
 void *mem_to_free;

 /* Maps [A-Za-z] to the numbers 1-26, zero for all others. */
 unsigned char ascii_to_letter[256];

 /* Maps intersection squares to unique contiguous numbers.
  * Undefined garbage for non-intersection squares. */
 unsigned long square_to_packed_linear[kMaxSize][kMaxSize];
 unsigned long num_packed_linears = 0;

 /* Gives us the up to two placements that intersect the given square. */
 placement_t *square_to_placement[kMaxSize][kMaxSize][2];

 /* Initialize assorted arrays. */
 memset(square_to_placement, 0, sizeof square_to_placement);
 memset(interesting_length, 0, sizeof interesting_length);

 create_ascii_to_letter(ascii_to_letter);

 /* Create all of the placement structs, etc. */
 placement = identify_placements(puzzle, puzzle_size, 
      &num_placements, square_to_placement, interesting_length);

 /* Figure out all of the words of the various lengths we want. */
 partition_words_by_length(dictionary, dict_size, 
      interesting_length, words_of_length, num_words_of_length,
      &mem_to_free);

 /* Loop through each partition and set up its neighbors and move list,
  * and reflect our move list on the global state. */
 for (n = 0; n < num_placements; n++)
  {
   placement_t *t = &placement[n];
   long num_intersect_squares = 0;
   long x, y, dx, dy, length;
   letter_mask_t mask[kMaxSize];

   /* If anyone marked us as needing further refinement, clear it
    * since we're going to do that refinement now. */
   clear_placement_mark(t);

   dx = t->dx;
   dy = t->dy;

   for (x = t->start_x, y = t->start_y, length = 0;
      x < puzzle_size && y < puzzle_size && 
                      puzzle[x][y] == EMPTY_SQUARE;
      x += dx, y += dy, length++)
    {
     placement_t *p0 = square_to_placement[x][y][0];
     placement_t *nbr;

     /* default to all letters being allowed for this square. */
     mask[length] = NOT_INTERSECTION_POINT;

     if (p0 != NULL && p0 != t)
      nbr = p0;
     else
      {
       placement_t *p1 = square_to_placement[x][y][1];
       if (p1 != NULL && p1 != t)
        nbr = p1;
       else
        nbr = NULL;
      }
     if (nbr != NULL)
      {
       /* If we are the first partition to visit this intersect
        * point (i.e. this neighbor hasn't been processed) then
        * add this square to the global list of interesting
        * squares. */
       if (nbr->letters_per_move != 0)
        mask[length] = 
                  letters_allowed
                  [square_to_packed_linear[x][y]];
       else
        {
          mask[length] = ALL_LETTERS;
         letters_allowed[num_packed_linears] = 
                            ALL_LETTERS;
         square_to_packed_linear[x][y] = 
                            num_packed_linears++;
        }

       /* We intersected some other placement here. This means we
        * care about this square. */
       t->neighbor[num_intersect_squares] = nbr;
       t->where[num_intersect_squares] = 
                      square_to_packed_linear[x][y];
       num_intersect_squares++;
      }
    }

   t->letters_per_move = num_intersect_squares;
   t->move_size = MOVE_SIZE(num_intersect_squares);

   if (t->letters_per_move == 0)
    {
     /* Plug in anything that fits. */
     if (num_words_of_length[length] == 0)
      {
       /* No solution! */
       goto done;
      }
     place_word(puzzle, t->start_x, t->start_y, 
                  t->dx, t->dy, words_of_length[length][0]);
     t->done = 1;
     t->num_moves = 0;
     t->move = NULL;
     continue;
    }

   /* Create all the moves for this placement. */
     t->move = (move_t *) malloc((num_words_of_length[length]+1)
                 * MOVE_SIZE(length));

   {
    const char **w;
    move_t *m = t->move;
    unsigned long hash_table_size;

    hash_table_size = num_words_of_length[length] * 3 + 16;
    if (hash_table_size > max_hash_table_size)
     {
      free(hash_table);
      max_hash_table_size = hash_table_size;
      hash_table = calloc(max_hash_table_size, 
                    sizeof hash_table[0]);
     }
    else
     memset(hash_table, 0, hash_table_size * 
                    sizeof hash_table[0]);

    for (w = words_of_length[length]; *w; w++)
     {
      const char *s = *w;
      unsigned long hash;
      long ix, out;

      hash = 1;
      for (ix = out = 0; s[ix] != '\0'; ix++)
       if (mask[ix] != NOT_INTERSECTION_POINT)
        {
         int letter = 
                    ascii_to_letter[(unsigned char) s[ix]];
         if ((mask[ix] & (1 << letter)) == 0)
          break;
         hash = (hash * 26) + letter;
         m->letter[out++] = letter;
        }

      /* If we made it all the way to the end without failing,
       * then add this word to the list. */
      if (s[ix] == '\0')
       {
        const move_t *test_move;
        long j;

        hash %= hash_table_size;

       while ((test_move = hash_table[hash]) != NULL)
        {
        for (j = t->letters_per_move - 1; j>=0; j--)
          if (test_move->letter[j] != m->letter[j])
            break;
          if (j < 0)
           break;
          if (++hash >= hash_table_size)
           hash -= hash_table_size;
         }
        if (test_move == NULL)
         {
          hash_table[hash] = m;
          m->original_word = *w;
          ++t->num_moves;
          m = NEXT_MOVE(m, t->move_size);
         }
       }
     }

    /* Terminate our list with a NULL pointer. */
    m->original_word = NULL;
   }

   /* Compute global implications of the legal words here. */
   intersect_placement_with_global_mask(t, letters_allowed);
  }

 solve_trivial_placements(puzzle, placement, num_placements);

done:
 /* We don't need this memory any more, so free it. */
 free(hash_table);
 free(mem_to_free);

 /* Recursively propagate around constraints. */
 tighten_constraints(placement, num_placements, 
          letters_allowed, 1);

 *letters_allowed_size_ptr = num_packed_linears;
 *num_placements_ptr = num_placements;
 return placement;
}

partition_aux
/* Recursive helper function for `partition_and_mark_cycles'. */
static long
partition_aux(placement_t *p, placement_t ***partition, 
      placement_t *parent, long depth)
{
 placement_t **nbrs, *nbr;
 long retval = depth;

 /* Add this placement to our partition. */
 set_placement_mark(p);
 p->depth = depth;
 p->in_cycle = NOT_IN_CYCLE;
 if (!p->done)
  {
   **partition = p;
   ++*partition;

   for (nbrs = p->neighbor; (nbr = *nbrs) != NULL; nbrs++)
    {
     long x;
     
     if (nbr == parent)
      continue;
     
     if (placement_is_marked(nbr))
      x = nbr->depth;
     else
      x = partition_aux(nbr, partition, p, depth + 1);
     if (x <= retval)
      {
       p->in_cycle = IN_CYCLE;
       retval = x;
      }
    }
  }

 return (p->in_cycle == IN_CYCLE) ? retval : 10000000;
}

partition_and_mark_cycles
/* Store all non-solved placements reachable from root that are part of
 * some cycle into partition. */
static long
partition_and_mark_cycles(placement_t *root, 
      placement_t **partition)
{
 placement_t **end_partition, **in, **out, *p;

 /* Put everything in the partition into the array, and mark each
  * that's part of a cycle. */
 end_partition = partition;
 clear_all_placement_marks();
 partition_aux(root, &end_partition, NULL, 1);
 *end_partition = NULL;

 /* Remove everything that's not part of a cycle. */
 for (in = out = partition; (p = *in) != 0; in++)
  if (p->in_cycle == IN_CYCLE)
   *out++ = p;
 *out = NULL;

 return out - partition;
}

solve_partition
/* Tries to solve a partition. Returns true on success. */
static int
solve_partition(Puzzle puzzle, placement_t **partition, 
      long partition_size, letter_mask_t *letters_allowed, 
      long letters_allowed_size, placement_t *all_placements, 
      long all_placements_size, placement_t *start)
{
 placement_t *p, *most_popular;
 move_t **backup_move, *m;
 long *backup_num_moves, i;
 letter_mask_t *backup_letters_allowed;
 placement_t **new_partition;
 int success = 0;
 long bla_size;
 long move_size;

 /* Make a backup copy of our letters_allowed array. */
 bla_size = letters_allowed_size * 
          sizeof backup_letters_allowed[0];
 backup_letters_allowed = malloc(bla_size);
 memcpy(backup_letters_allowed, letters_allowed, bla_size);
 
 /* Make backup copies of our move lists. */
 backup_move = malloc(partition_size * sizeof backup_move[0]);
 backup_num_moves = 
      malloc(partition_size * sizeof backup_num_moves[0]);

 /* Allocate room to hold this. */
 new_partition = 
  malloc((all_placements_size + 1) * sizeof new_partition[0]);

 p = most_popular = NULL;
 
 for (i = 0; i < partition_size; i++)
  {
   placement_t *q = partition[i];
   long size;

   backup_num_moves[i] = q->num_moves;
   size = (q->num_moves + 1) * q->move_size;
   backup_move[i] = malloc(size);
   memcpy(backup_move[i], q->move, size);

   if (q == start)
    p = q;
   else if (most_popular == NULL
        || q->letters_per_move > 
                            most_popular->letters_per_move)
    most_popular = q;
  }

 if (p == NULL)
  p = most_popular;

 /* Hypothetically lay down this move. */
 move_size = p->move_size;
 for (m = p->move; m->original_word; 
              m = NEXT_MOVE(m, move_size))
  {
   long r;
   
   /* Actually lay this move down on the board. */
   place_move(puzzle, p, m);

   /* Remember that this placement is "done". */
   p->done = 1;

   /* Tighten grid and update all neighbors who may care. */
   clear_all_placement_marks();
   for (r = p->letters_per_move - 1; r >= 0; r--)
    {
     letter_mask_t g = letters_allowed[p->where[r]];
     letter_mask_t mask = 1 << m->letter[r];
     if (g != mask)
      {
       letters_allowed[p->where[r]] = mask;
       set_placement_mark(p->neighbor[r]);
      }
    }

   /* Propagate constraints and check for contradiction. */
   if (!tighten_constraints(all_placements, 
            all_placements_size, letters_allowed, 0))
    goto failed;
   
   {
    placement_t **nbrs, *nbr;

    /* No contradiction yet, so try our children. */
    for (nbrs = p->neighbor; (nbr = *nbrs) != 0; nbrs++)
    {
     long new_partition_size;
     new_partition_size = 
              partition_and_mark_cycles(nbr, new_partition);
     if (new_partition_size > 0 && 
                !solve_partition(puzzle, new_partition,
                      new_partition_size, letters_allowed, 
                      letters_allowed_size, all_placements, 
                      all_placements_size, nbr))
      goto failed;
    }
   }

   /* Woohoo! We did it! */
   success = 1;
   break;

   /* This didn't work, so restore state. */
  failed:
   p->done = 0;
   for (r = 0; r < partition_size; r++)
    {
     placement_t *q = partition[r];
     q->num_moves = backup_num_moves[r];
     /* FIXME - don't actually need to copy on the last pass...
      * just assign pointer to backup memory and free the bad copy. */
     memcpy(q->move, backup_move[r], 
                        (q->num_moves + 1) * q->move_size);
    }
   memcpy(letters_allowed, backup_letters_allowed,
       letters_allowed_size * sizeof letters_allowed[0]);
  }

 /* Housecleaning. */
 free(new_partition);
 free(backup_letters_allowed);
 for (i = 0; i < partition_size; i++)
  free(backup_move[i]);
 free(backup_num_moves);
 free(backup_move);

 return success;
}


solve_acyclic_aux
static void
solve_acyclic_aux(Puzzle puzzle, placement_t *p,
         letter_mask_t *letters_allowed)
{
 /* Find any legal move and make it. */
 move_t *m;
 long move_size, loop_start;

 if (p->done)
  return;
 
 move_size = p->move_size;
 loop_start = p->letters_per_move - 1;

 for (m = p->move; m->original_word; 
                  m = NEXT_MOVE(m, move_size))
  {
   long k;
   for (k = loop_start; k >= 0; k--)
    if (!(letters_allowed[p->where[k]] & 
                            (1 << m->letter[k])))
     break;
   if (k < 0)
    {
     long j;
     
     /* Make the move. */
     place_move(puzzle, p, m);
     
     /* Tighten up the board for everyone else. */
     for (j = loop_start; j >= 0; j--)
      letters_allowed[p->where[j]] = 1 << m->letter[j];

     p->done = 1;

     /* Flood out to our neighbors and do them too. */
     for (j = loop_start; j >= 0; j--)
      solve_acyclic_aux(puzzle, p->neighbor[j], 
                    letters_allowed);

     /* Stop looking for a word. */
     break;
    }
  }
}

solve_acyclic_stragglers
/* The main algorithm guarantees we solve things that are part of
 * cycles but not those things which are not part of cycles, because
 * they are utterly trivial given the information we've computed.
 * This solves those last acyclic pieces. */
static void
solve_acyclic_stragglers(Puzzle puzzle,
    placement_t *placement, long num_placements,
    letter_mask_t *letters_allowed)
{
 long i;
 for (i = 0; i < num_placements; i++)
  {
   placement_t *p = &placement[i];
   if (!p->done && p->num_moves > 0)
    solve_acyclic_aux(puzzle, p, letters_allowed);
  }
}


Crossword
void Crossword(
 Puzzle thePuzzle,    /* return solved puzzle here */
 char *dictionary[],  /* array of words to choose from */
 long puzzleSize,    /* number of rows/cols in puzzle */
 long dictSize        /* number of words in dictionary */
)
{
 letter_mask_t letters_allowed[kMaxSize * kMaxSize];
 long num_placements, i, letters_allowed_size;
 placement_t *placement, **partition;
 int success = 1;

 /* Create our placement structures. */
 placement = create_placements(thePuzzle, puzzleSize, 
      dictionary, dictSize, letters_allowed, 
      &letters_allowed_size, &num_placements);

 /* Find disjoint portions of the graph and solve them. */
 partition = malloc((num_placements + 1) * sizeof partition[0]);
 for (i = 0; i < num_placements; i++)
  {
   placement_t *p = &placement[i];
   if (p->num_moves > 0 && p->in_cycle == CYCLENESS_UNKNOWN)
    {
     long partition_size = 
                    partition_and_mark_cycles(p, partition);
     if (partition_size > 0)
      success &= solve_partition(thePuzzle, partition, 
                    partition_size, letters_allowed, 
                    letters_allowed_size, placement, 
                    num_placements, NULL);
    }
  }

 if (success)
  {
   /* Recompute all constraints for everyone not yet solved. */
   for (i = 0; i < num_placements; i++)
    set_placement_mark(&placement[i]);
   tighten_constraints(placement, num_placements, 
                letters_allowed, 1);
   
   /* Go through and solve them. */
   solve_acyclic_stragglers(thePuzzle, placement, 
                num_placements, letters_allowed);
  }
 
 /* House cleaning. */
 free(partition);
 for (i = 0; i < num_placements; i++)
  free(placement[i].move);
 free(placement);
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

SpamSieve 2.9.38 - Robust spam filter fo...
SpamSieve is a robust spam filter for major email clients that uses powerful Bayesian spam filtering. SpamSieve understands what your spam looks like in order to block it all, but also learns what... Read more
TeamViewer 15.0.8397 - Establish remote...
TeamViewer gives you remote control of any computer or Mac over the Internet within seconds or can be used for online meetings. Find out why more than 200 million users trust TeamViewer! Free for non... Read more
SteerMouse 5.4.3 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. SteerMouse can assign various functions to buttons that Apple's software does not allow, including double-clicks, modifier clicks,... Read more
Toast Titanium 18.2.1 - The ultimate med...
Roxio Toast Titanium, the leading DVD burner for Mac, makes burning even better, adding Roxio Secure Burn to protect your files on disc and USB in Mac- or Windows-compatible formats. Get more style... Read more
HoudahSpot 5.0.11 - Advanced file-search...
HoudahSpot is a versatile desktop search tool. Use HoudahSpot to locate hard-to-find files and keep frequently used files within reach. HoudahSpot will immediately feel familiar. It works just the... Read more
ClipGrab 3.8.6 - Download videos from Yo...
ClipGrab is a free downloader and converter for YouTube, Vimeo, Facebook and many other online video sites. It converts downloaded videos to MPEG4, MP3 or other formats in just one easy step Version... Read more
ExpanDrive 7.4.0 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
Adobe Dreamweaver CC 2020 20.0 - Build w...
Dreamweaver CC 2020 is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous Dreamweaver customer). Adobe Dreamweaver CC 2020 allows you to... Read more
Eye Candy 7.2.3.85 - 30 professional Pho...
Eye Candy renders realistic effects that are difficult or impossible to achieve in Photoshop alone, such as Fire, Chrome, and the new Lightning. Effects like Animal Fur, Smoke, and Reptile Skin are... Read more
Sparkle Pro 2.8.5 - Visual website creat...
Sparkle Pro will change your mind if you thought building websites wasn't for you. Sparkle is the intuitive site builder that lets you create sites for your online portfolio, team or band pages, or... Read more

Latest Forum Discussions

See All

Pre-register for Hello Kitty AR: Kawaii...
Hello Kitty — the cute cat that launched a multi-billion-pound franchise — has been brought to life… sort of. Sanrio has teamed up with the Bublar Group to create a new mobile game that uses AR tech to turn the real world into Hello Kitty’s... | Read more »
Gorgeous and tranquil puzzler Spring Fal...
One-man indie studio SPARSE//GameDev has now launched its tranquil puzzler, Spring Falls. It's described as "a peaceful puzzle game about water, erosion, and watching things grow". [Read more] | Read more »
Black Desert Mobile gets an official rel...
Pearl Abyss has just announced that its highly-anticipated MMO, Black Desert Mobile, will launch globally for iOS and Android on December 11th. [Read more] | Read more »
Another Eden receives new a episode, cha...
Another Eden, WFS' popular RPG, has received another update that brings new story content to the game alongside a few new heroes to discover. [Read more] | Read more »
Overdox guide - Tips and tricks for begi...
Overdox is a clever battle royale that changes things up by adding MOBA mechanics and melee combat to the mix. This new hybrid game can be quite a bit to take in at first, so we’ve put together a list of tips to help you get a leg up on the... | Read more »
Roterra Extreme - Great Escape is a pers...
Roterra Extreme – Great Escape has been described by developers Dig-It Games as a mini-sequel to their acclaimed title Roterra: Flip the Fairytale. It continues that game's tradition of messing with which way is up, tasking you with solving... | Read more »
Hearthstone: Battlegrounds open beta lau...
Remember earlier this year when auto battlers were the latest hotness? We had Auto Chess, DOTA Underlords, Chess Rush, and more all gunning for our attention. They all had their own reasons to play, but, at least from where I'm standing, most... | Read more »
The House of Da Vinci 2 gets a new gamep...
The House of Da Vinci launched all the way back in 2017. Now, developer Blue Brain Games is gearing up to deliver a second dose of The Room-inspired puzzling. Some fresh details have now emerged, alongside the game's first official trailer. [Read... | Read more »
Shoot 'em up action awaits in Battl...
BattleBrew Productions has just introduced another entry into its award winning, barrelpunk inspired, BattleSky Brigade series. Whilst its previous title BattleSky Brigade TapTap provided fans with idle town building gameplay, this time the... | Read more »
Arcade classic R-Type Dimensions EX blas...
If you're a long time fan of shmups and have been looking for something to play lately, Tozai Games may have just released an ideal game for you on iOS. R-Type Dimensions EX brings the first R-Type and its sequel to iOS devices. [Read more] | Read more »

Price Scanner via MacPrices.net

13″ 2.4GHz MacBook Pros available for up to $...
Apple has a full line of Certified Refurbished 2019 13″ 2.4GHz 4-Core Touch Bar MacBook Pros available starting at $1529 and up to $300 off MSRP. Apple’s one-year warranty is included, shipping is... Read more
New at T-Mobile: Switch to T-Mobile, and get...
T-Mobile is offering a free 64GB iPhone 8 for new customers who switch to T-Mobile and open a new line of service. Eligible trade-in required, and discount applied over a 24 month period. The fine... Read more
Xfinity Mobile’s Black Friday Apple savings:...
Take $250 off the purchase of any iPhone at Xfinity Mobile with a new line activation, and transfer of phone number to Xfinity Mobile, through December 8, 2019. This includes Apple’s new iPhone 11... Read more
2019 13″ 1.4GHz MacBook Pros available starti...
Apple has a full line of Certified Refurbished 2019 13″ 1.4GHz 4-Core Touch Bar MacBook Pros available starting at $1099 and up to $230 off MSRP. Apple’s one-year warranty is included, shipping is... Read more
Save up to $350 on a 21″ or 27″ iMac with the...
Apple has Certified Refurbished 2019 21″ & 27″ iMacs available starting at $929 and up to $350 off the cost of new models. Apple’s one-year warranty is standard, shipping is free, and each iMac... Read more
Early Holiday 2019 Sale: B&H again offers...
B&H Photo has 10.2″ iPads on sale again for $30 off Apple’s MSRP, starting at $299, as part of their early Holiday 2019 sale. Overnight shipping is free to many addresses in the US: – 10.2″ 32GB... Read more
Apple iMacs on sale today at B&H Photo fo...
B&H Photo has new 2019 21″ and 27″ 5K iMacs on stock today and on sale for up to $150 off Apple’s MSRP. Overnight shipping is free to many locations in the US. These are the same iMacs sold by... Read more
2018 4 and 6-Core Mac minis on sale today for...
Apple resellers are offering new 2018 4-Core and 6-Core Mac minis for $80-$100 off MSRP for a limited time. B&H Photo has the new 2018 4-Core and 6-Core Mac minis on sale for up to $100 off Apple... Read more
Early Holiday 2019 sale at B&H Photo: 12....
B&H Photo has new 12.9″ iPad Pros on sale for up to $120 off Apple’s MSRP as part of their early Holiday 2019 sale. Overnight shipping is free to many addresses in the US: – 12.9″ 64GB WiFi iPad... Read more
8-Core iMac Pro on sale today for $4499 at B...
B&H Photo has the base 8-Core 3.2GHz 32GB/1TB iMac Pro on sale today for $4499 — $500 off Apple’s MSRP. Shipping is free. Their price is the lowest available for a new iMac Pro from any Apple... Read more

Jobs Board

*Apple* Health Benefit Specialist - Call Cen...
Description ** Apple Health Benefit Specialist - Call Center (MAS 3/MACSC)** **Olympia, WA Multiple Positions** *The ideal candidate for this position will have Read more
Hair Stylist - *Apple* Blossom Mall - JCPen...
Hair Stylist - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job ID:1065040Salon Professionals Job Read more
*Apple* Mobility Pro - Best Buy (United Stat...
**747088BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Store NUmber or Department:** 000297-Reston-Store **Job Description:** At Best Read more
Nurse Practitioner - Field Based (San Bernard...
Nurse Practitioner - Field Based (San Bernardino, CA, Apple Valley, Hesperia) **Location:** **United States** **Requisition #:** PS30312 **Post Date:** Nov 11, 2019 Read more
Best Buy *Apple* Computing Master - Best Bu...
**747061BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Store NUmber or Department:** 000647-Kildeer-Store **Job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.