Subversion Repositories wimsdev

Rev

Rev 8893 | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. /*2010-08-20
  2.  
  3. Modify the output to wims
  4. Rename it in crossword.c
  5. Bernadette Perrin-Riou
  6. bpr@math.u-psud.fr
  7.  
  8. */
  9.  
  10. /*  POTM ENTRY: jigsaw                                          */
  11. /*  Your Name:  Franz Korntner                                  */
  12. /*  Your email: fkorntne@hiscom.nl                              */
  13. /*              korntner@xs4all.nl                              */
  14. /*  To:         enter@potm.ffast.att.com                        */
  15. /*  Subject:    C R O Z Z L E                                   */
  16.  
  17. /*
  18. **  Hello Fred. This is my entry with some additional comments and
  19. **  some modifications to make it more portable. I haven't changed
  20. **  the algorithm in any way whatsoever.
  21. **  Because the source will be made available to the public, I've
  22. **  included a copyright message to state that the source is free
  23. **  and not public-domain. I'm sure thats alright with you.
  24. */
  25.  
  26. /*
  27.    jigsaw, to create crossword puzzle grids
  28.    Copyright 1996 Franz Korntner <fkorntne@hiscom.nl> <korntner@xs4all.nl>
  29.  
  30. This program is free software; you can redistribute it and/or modify
  31. it under the terms of the GNU General Public License as published by
  32. the Free Software Foundation; either version 2 of the License, or
  33. (at your option) any later version.
  34.  
  35. This program is distributed in the hope that it will be useful,
  36. but WITHOUT ANY WARRANTY; without even the implied warranty of
  37. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  38. GNU General Public License for more details.
  39.  
  40. You should have received a copy of the GNU General Public License
  41. along with this program; if not, write to the Free Software
  42. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  43. */
  44.  
  45. /*
  46. **  *** For your pleasure only ***
  47. **
  48. **  The code can produce symmetrical grids by setting the macro
  49. **  SYMMETRICAL to 1. Sadly enough not as many words will fit
  50. **  into a symmetrical grid than into a non-symmetrical grid,
  51. **  so NODEMAX must be increased (say with 1000) to get better results.
  52. */
  53.  
  54. /* Configuring parameters */
  55.  
  56. #define TIMEMAX         (10*60-15)      /* 10 minute limit              */
  57. #define DEBUG           0               /* 0=Off 1=On 2=Verbose         */
  58. #define NODEMAX         1500            /* 500=Fast 1500=Normal         */
  59. #define SYMMETRICAL     0               /* 0=No 1=Yes                   */
  60. #define MALLOC_BROKEN   1               /* 0=No 1=Yes (See below)       */
  61. #define WIMS 1
  62. /*
  63. ** It seems that malloc() under Linux is broken. I could only allocate
  64. ** a couple of thousand nodes before my program crashed. A solution was to
  65. ** allocate a BIG chunk of memory and split it up manually. This way about
  66. ** 10500 nodes could be allocated.
  67. */
  68.  
  69. /* Start of program */
  70.  
  71. #include <stdio.h>
  72. #include <stdlib.h>
  73. #include <string.h>
  74. #include <ctype.h>
  75. #include <unistd.h>
  76. #include <sys/times.h>
  77.  
  78. #if defined(__alpha__)
  79. #ifndef __GNUC__
  80. #error I want GCC !!!
  81. #endif
  82. typedef          int int8   __attribute__ ((mode (QI)));
  83. typedef unsigned int uint8  __attribute__ ((mode (QI)));
  84. typedef          int int16  __attribute__ ((mode (HI)));
  85. typedef unsigned int uint16 __attribute__ ((mode (HI)));
  86. typedef          int int32  __attribute__ ((mode (SI)));
  87. typedef unsigned int uint32 __attribute__ ((mode (SI)));
  88. #else
  89. /* It seems that your Sparc-GCC doesn't support the above :-(( */
  90. typedef          char  int8;
  91. typedef unsigned char  uint8;
  92. typedef          short int16;
  93. typedef unsigned short uint16;
  94. typedef          long  int32;
  95. typedef unsigned long  uint32;
  96. #endif
  97.  
  98. #define GRIDMAX 22                      /* Size of grid incl. border    */
  99. #define LINKMAX 4096                    /* # links                      */
  100. #define WORDMAX 256                     /* # words                      */
  101. #define WORDLENMAX 32                   /* # length of word             */
  102. #define ADJMAX 128                      /* # unaccounted adjacent chars */
  103. #define SCOREMAX 1000                   /* Spead for hashing            */
  104.  
  105. #define BASE ('a'-1)                    /* Word conversion              */
  106. #define STAR   (28)                     /* Word delimiters              */
  107. #define FREE   (31)                     /* Unoccupied grid cell         */
  108. #define TODOH 1                         /* Hint: Hor. word can be here  */
  109. #define TODOV 2                         /* Hint: Ver. word can be here  */
  110. #define BORDER 4                        /* Cell is grid border          */
  111.  
  112. #define ISSTAR(C)   ((C)==STAR)         /* Test the above               */
  113. #define ISFREE(C)   ((C)==FREE)
  114. #define ISCHAR(C)   ((C)< STAR)
  115. #define ISBORDER(C) ((C)&BORDER)
  116.  
  117. #define BITSET(M,B) ((M).s[(B)>>3] |=  (1<<((B)&7))) /* BitSet          */
  118. #define BITCLR(M,B) ((M).s[(B)>>3] &= ~(1<<((B)&7))) /*   manipulation  */
  119. #define INSET(M,B)  ((M).s[(B)>>3] &   (1<<((B)&7)))
  120.  
  121. typedef struct {                        /* Bitset containing 256 bits   */
  122.   uint8 s[32];
  123. } SET;
  124.  
  125. typedef struct node {
  126.   struct node   *next;                  /*                              */
  127.   int           seqnr;                  /* For diagnostics              */
  128.   SET           words;                  /* Summary of placed words      */
  129.   int           numword,numchar,numconn;/* Statistics                   */
  130.   uint32        hash;                   /* Duplicate detection          */
  131.   int           firstlevel, lastlevel;  /* Grids hotspot                */
  132.   float         score;                  /* Will it survive?             */
  133.   int8          symdir;                 /* Force symmetry               */
  134.   int16         symxy;                  /*                              */
  135.   int16         symlen;                 /*                              */
  136.   int           numadj;                 /* # unprocessed char pairs     */
  137.   int8          adjdir[ADJMAX];         /* Pair's direction             */
  138.   int16         adjxy[ADJMAX];          /* Pair's location              */
  139.   int16         adjl[ADJMAX];           /* Pair's wordlist              */
  140.   uint8         grid[GRIDMAX*GRIDMAX];  /* *THE* grid                   */
  141.   uint8         attr[GRIDMAX*GRIDMAX];  /* Grid hints                   */
  142. } node;
  143.  
  144. struct link {
  145.   int16         next;
  146.   int16         w;                              /* What's the word      */
  147.   int16         ofs;                            /* Were's in the word   */
  148. };
  149.  
  150.  
  151. /* The external word list */
  152. uint8           wordbase[WORDMAX][WORDLENMAX];  /* Converted wordlist   */
  153. int             wlen[WORDMAX];                  /* Length of words      */
  154. int             numword;                        /* How many             */
  155. char            *wordfname = "wordlist";        /* Where are they found */
  156.  
  157. /* Where are 1,2,3 long character combinations */
  158. int16           links1[32];                     /* 1-char wordlist      */
  159. int16           links2[32][32];                 /* 2-char wordlist      */
  160. int16           links3[32][32][32];             /* 3-char wordlist      */
  161. struct link     linkdat[LINKMAX];               /* Body above wordlist  */
  162. int             numlinkdat;                     /* How many             */
  163.  
  164. /* Hotspot pre-calculations */
  165. int16           xy2level[GRIDMAX*GRIDMAX];      /* distance 0,0 to x,y  */
  166. int16           level2xy[GRIDMAX*2];            /* inverse              */
  167.  
  168. /* Node administration */
  169. node            *freenode;                      /* Don't malloc() too much */
  170. int             numnode, realnumnode;           /* Statistics           */
  171. node            solution;                       /* What are we doing?   */
  172. node            *scores[SCOREMAX];              /* Speed up hashing     */
  173.  
  174. /* Diagnostics */
  175. int             seqnr;
  176. int             hashtst, hashhit;
  177. int             nummalloc;
  178. int             numscan;
  179. int             flg_dump;
  180.  
  181. /* What's left */
  182. int             clktck;                         /* Timing portability   */
  183.  
  184. /* Forward declartions */
  185. char *elapsedstr(void);
  186.  
  188. /*
  189. ** Display the grid. Show disgnostics info in verbose mode
  190. */
  191.  
  192. void dump_grid (node *d)
  193. {
  194. int x, y;
  195.  
  196. #if DEBUG==2
  197.  int attr, cnt;
  198.   /* Double check the number of words */
  199.   cnt = 0;
  200.   for (x=GRIDMAX*GRIDMAX-1; x>=0; x--)
  201.     if (ISCHAR(d->grid[x])) {
  202.       if (!ISCHAR(d->grid[x-1]) && ISCHAR(d->grid[x+1])) cnt++;
  203.       if (!ISCHAR(d->grid[x-GRIDMAX]) && ISCHAR(d->grid[x+GRIDMAX])) cnt++;
  204.     }
  205.   printf("%s seqnr:%d level:%d/%d score:%f numword:%d/%d numchar:%d numconn:%d\n",
  206.          elapsedstr(), d->seqnr, d->firstlevel, d->lastlevel, d->score, d->numword,
  207.          cnt, d->numchar, d->numconn);
  208. #endif
  209.  
  210. #if DEBUG==2
  211.   /* Show grid as I would like to see it */
  212.   for (y=0; y<GRIDMAX; y++) {
  213.     for (x=0; x<GRIDMAX; x++) {
  214.       attr = d->attr[x+y*GRIDMAX]&(TODOH|TODOV);
  215.       if (attr==(TODOH|TODOV))
  216.         printf("B");
  217.       else if (attr==TODOH)
  218.         printf("H");
  219.       else if (attr==TODOV)
  220.         printf("V");
  221.       else
  222.         printf(".");
  223.     }
  224.     printf (" ");
  225.     for (x=0; x<GRIDMAX; x++)
  226.       if (ISSTAR(d->grid[x+y*GRIDMAX]))
  227.         printf("*");
  228.       else if (ISFREE(d->grid[x+y*GRIDMAX]))
  229.         printf(".");
  230.       else if (ISCHAR(d->grid[x+y*GRIDMAX]))
  231.         printf ("%c", d->grid[x+y*GRIDMAX]+BASE);
  232.       else
  233.         printf("0x%02x", d->grid[x+y*GRIDMAX]);
  234. #else
  235. # if WIMS==1
  236.   int sizex, sizey ; sizex=0 ;  sizey=0;
  237.       for (y=1; y<GRIDMAX; y++) {
  238.        for (x=1; x<GRIDMAX; x++) {
  239.          if (ISCHAR(d->grid[x+y*GRIDMAX])) { if (x > sizex) sizex = x ; }
  240.        }
  241.       }
  242.       for (x=1; x<GRIDMAX-1; x++) {
  243.        for (y=1; y<GRIDMAX-1; y++) {
  244.          if (ISCHAR(d->grid[x+y*GRIDMAX])) { if (y > sizey) sizey = y ; }
  245.        }
  246.       }
  247.       for (y=1; y<sizey+1; y++) {
  248.        for (x=1; x<sizex+1; x++) {
  249.         if (!ISCHAR(d->grid[x+y*GRIDMAX]) && x <sizex ){ printf(",");}
  250.         else {
  251.         if (ISCHAR(d->grid[x+y*GRIDMAX])){
  252.          printf ("%c", d->grid[x+y*GRIDMAX]+BASE);
  253.          if (x <sizex) printf(",") ;
  254.         }
  255.        }
  256.       }
  257.      printf("\n");
  258.    }
  259. #else
  260.    /* Show grid as Fred would like to see it */
  261.   for (y=1; y<GRIDMAX-1; y++) {
  262.     for (x=1; x<GRIDMAX-1; x++)
  263.       if (ISCHAR(d->grid[x+y*GRIDMAX]))
  264.         printf ("%c", d->grid[x+y*GRIDMAX]+BASE);
  265.       else
  266.         printf("-");
  267. #endif
  268. #endif
  269.  
  270.  
  271.   /* For diagnostics */
  272.   fflush (stdout);
  273. }
  274.  
  275. int elapsedtime (void)
  276. {
  277. int seconds;
  278. static struct tms TMS;
  279.  
  280.   times(&TMS);
  281.  
  282.   /* add the elapsed system and user times                        */
  283.   /* calculation comes out to the nearest second - rounded down   */
  284.   seconds = (TMS.tms_stime + TMS.tms_utime)/clktck;
  285.   if (seconds < 1) seconds=1;
  286.   if (seconds >= TIMEMAX) {
  287.     /* PRINT OUT YOUR SOLUTION BEFORE YOU GO! */
  288.     /*
  289.     ** HELP, the algorithm must compleet well under 10 minutes.
  290.     */
  291.     dump_grid (&solution);
  292.     exit(0);
  293.   }
  294.   return seconds;
  295. }
  296.  
  297. /*
  298. ** Elapsed time for diagnostics
  299. */
  300. char *elapsedstr(void)
  301. {
  302. static char line[40];
  303. int seconds;
  304.  
  305.   seconds = elapsedtime();
  306.   sprintf(line, "%02d:%02d", seconds/60, seconds%60);
  307.   return line;
  308. }
  309.  
  311. /*
  312. ** Get a node, reusing free'ed nodes.
  313. */
  314.  
  315. node *mallocnode (void)
  316. {
  317. node *d;
  318.  
  319.   d = freenode;
  320.   if (d == NULL) {
  321.     d = (node*) malloc (sizeof(node));
  322.     nummalloc++;
  323.   } else
  324.     freenode = d->next;
  325.  
  326.   if (d == NULL) {
  327.     fprintf (stderr, "Out of memory after %d nodes (%lo bytes)\n", nummalloc, (long)nummalloc*sizeof(node));
  328.     dump_grid (&solution);
  329.     exit(0);
  330.   }
  331.  
  332.   return d;
  333. }
  334.  
  335. void add_node (node *d)
  336. {
  337. int i;
  338. node **prev, *next;
  339.  
  340.   /* Evaluate grids score */
  341.   d->score = (float)d->numconn/d->numchar;
  342.  
  343.   /* Insert grid into sorted list, eliminating duplicates */
  344.   i = d->score*(SCOREMAX-1);
  345.   if (i<0) i=0;
  346.   if (i>=SCOREMAX) i=SCOREMAX-1;
  347.   prev = &scores[i];
  348.   next = scores[i];
  349.   for (;;) {
  350.     if (next == NULL) break;
  351.     if (d->score > next->score) break;
  352.     if (d->score == next->score && d->hash >= next->hash) break;
  353.     prev = &next->next;
  354.     next = next->next;
  355.   }
  356.  
  357.   /* Test if entry is duplicate */
  358.   while (next && d->score == next->score && d->hash == next->hash) {
  359.     hashtst++;
  360.     if (memcmp(d->grid, next->grid, sizeof(d->grid)) == 0) {
  361.       d->next = freenode;
  362.       freenode = d;
  363.       return;
  364.     }
  365.     hashhit++;
  366.     prev = &next->next;
  367.     next = next->next;
  368.   }
  369.  
  370.   /* Diagnostics */
  371.   if (flg_dump > 1)
  372.     dump_grid (d);
  373.  
  374.   /* Enter grid into list */
  375.   d->seqnr = seqnr++;
  376.   d->next = next;
  377.   (*prev) = d;
  378.   if (d->numadj == 0)
  379.     numnode++;
  380.   realnumnode++;
  381. }
  382.  
  384. /*
  385. ** The next two routines test if a given word can be placed in the grid.
  386. ** If a new character will be adjacent to an existing character, check
  387. ** if the newly formed character pair exist in the wordlist (it doesn't
  388. ** matter where).
  389. */
  390.  
  391. int test_hword (node *d, int xybase, int word)
  392. {
  393. uint8 *p, *grid;
  394. int l;
  395.  
  396.   /* Some basic tests */
  397.   if (xybase < 0 || xybase+wlen[word] >= GRIDMAX*GRIDMAX+1) return 0;
  398.  
  399. #if SYMMETRICAL
  400.   /* How about star's */
  401.   if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-xybase]))
  402.     return 0;
  403.   if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-(xybase+wlen[word]-1)]))
  404.     return 0;
  405. #endif
  406.  
  407.   /* Will new characters create conflicts */
  408.   for (grid=d->grid+xybase,p=wordbase[word]; *p; grid++,p++) {
  409.     if (*grid == *p)
  410.       continue; /* Char already there */
  411.     if (!ISFREE(*grid))
  412.       return 0; /* Char placement conflict */
  413.     if (ISSTAR(*p))
  414.       continue; /* Skip stars */
  415.     if (!ISCHAR(grid[-GRIDMAX]) && !ISCHAR(grid[+GRIDMAX]))
  416.       continue; /* No adjacent chars */
  417.  
  418.     if (ISFREE(grid[-GRIDMAX]))
  419.       l = links2[*p][grid[+GRIDMAX]];
  420.     else if (ISFREE(grid[+GRIDMAX]))
  421.       l = links2[grid[-GRIDMAX]][*p];
  422.     else
  423.       l = links3[grid[-GRIDMAX]][*p][grid[+GRIDMAX]];
  424.     if (l == 0)
  425.       return 0;
  426.   }
  427.  
  428.   /* Word can be placed */
  429.   return 1;
  430. }
  431.  
  432. int test_vword (node *d, int xybase, int word)
  433. {
  434. uint8 *p, *grid;
  435. int l;
  436.  
  437.   /* Some basic tests */
  438.   if (xybase < 0 || xybase+wlen[word]*GRIDMAX >= GRIDMAX*GRIDMAX+GRIDMAX) return 0;
  439.  
  440. #if SYMMETRICAL
  441.   /* How about star's */
  442.   if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-xybase]))
  443.     return 0;
  444.   if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-(xybase+wlen[word]*GRIDMAX-GRIDMAX)]))
  445.     return 0;
  446. #endif
  447.  
  448.   /* Will new characters create conflicts */
  449.   for (grid=d->grid+xybase,p=wordbase[word]; *p; grid+=GRIDMAX,p++) {
  450.     if (*grid == *p)
  451.       continue; /* Char already there */
  452.     if (!ISFREE(*grid))
  453.       return 0; /* Char placement conflict */
  454.     if (ISSTAR(*p))
  455.       continue; /* Skip stars */
  456.     if (!ISCHAR(grid[-1]) && !ISCHAR(grid[+1]))
  457.       continue; /* No adjacent characters */
  458.  
  459.     if (ISFREE(grid[-1]))
  460.       l = links2[*p][grid[+1]];
  461.     else if (ISFREE(grid[+1]))
  462.       l = links2[grid[-1]][*p];
  463.     else
  464.       l = links3[grid[-1]][*p][grid[+1]];
  465.     if (l == 0)
  466.       return 0;
  467.   }
  468.  
  469.   /* Word can be placed */
  470.   return 1;
  471. }
  472.  
  474. /*
  475. ** The next two routines will place a given word in the grid. These routines
  476. ** also performs several sanity checks to make sure the new grid is worth
  477. ** it to continue with. If a newly placed character is adjacent to an
  478. ** existing character, then that pair must be part of a word that can
  479. ** be physically placed. If multiple character pairs exist, then no check
  480. ** is done to determine if those words (of which the pairs are part) can
  481. ** be adjacent. That is done later as these grids are not counted against
  482. ** NODEMAX.
  483. */
  484.  
  485. int place_hword (node *data, int xybase, int word)
  486. {
  487. node *d=data;
  488. uint8 *p, *grid, *attr;
  489. int i, l, xy;
  490. int newnumadj;
  491. struct link *ld;
  492.  
  493.   /* Can word be placed */
  494.   if (INSET(d->words, word)) return 0;
  495.   if (xybase < 0 || xybase+wlen[word] >= GRIDMAX*GRIDMAX+1) return 0;
  496.  
  497. #if SYMMETRICAL
  498.   /* How about star's */
  499.   if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-xybase]))
  500.     return 0;
  501.   if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-(xybase+wlen[word]-1)]))
  502.     return 0;
  503. #endif
  504.  
  505.   /* check character environment */
  506.   newnumadj = d->numadj;
  507.   for (xy=xybase,grid=d->grid+xy,p=wordbase[word]; *p; grid++,xy++,p++) {
  508.     if (*grid == *p)
  509.       continue; /* Char already there */
  510.     if (!ISFREE(*grid))
  511.       return 0; /* Char placement conflict */
  512.     if (ISSTAR(*p))
  513.       continue; /* Skip stars */
  514.     if (!ISCHAR(grid[-GRIDMAX]) && !ISCHAR(grid[+GRIDMAX]))
  515.       continue; /* No adjacent chars */
  516.  
  517.     if (ISFREE(grid[-GRIDMAX])) {
  518.       d->adjxy [newnumadj] = xy;
  519.       d->adjl  [newnumadj] = links2[*p][grid[+GRIDMAX]];
  520.     } else if (ISFREE(grid[+GRIDMAX])) {
  521.       d->adjxy [newnumadj] = xy-GRIDMAX;
  522.       d->adjl  [newnumadj] = links2[grid[-GRIDMAX]][*p];
  523.     } else {
  524.       d->adjxy [newnumadj] = xy-GRIDMAX;
  525.       d->adjl  [newnumadj] = links3[grid[-GRIDMAX]][*p][grid[+GRIDMAX]];
  526.     }
  527.     if (d->adjl[newnumadj] == 0 || newnumadj == ADJMAX-1)
  528.       return 0;
  529.     d->adjdir[newnumadj++] = 'V';
  530.   }
  531.  
  532.   /* Test if new adj's really exist */
  533.   for (i=d->numadj; i<newnumadj; i++) {
  534.     for (l=d->adjl[i]; l; l=ld->next) {
  535.       ld = &linkdat[l];
  536.       if (test_vword (d, d->adjxy[i]+ld->ofs*GRIDMAX, ld->w))
  537.         break;
  538.     }
  539.     if (l == 0) return 0;
  540.     d->adjl[i] = l;
  541.   }
  542.  
  543.   /* Get a new grid */
  544.   d = mallocnode();
  545.   memcpy (d, data, sizeof(node));
  546.  
  547.   /* Place word */
  548.   BITSET(d->words, word);
  549.   d->numword++;
  550.   d->numadj = newnumadj;
  551.   for (xy=xybase,grid=d->grid+xy,attr=d->attr+xy,p=wordbase[word];
  552.        *p;
  553.        grid++,attr++,xy++,p++) {
  554.     if (!ISSTAR(*p)) {
  555.       *attr &= ~TODOH;
  556.  
  557.       /* Remove character pair hints that are part of the new word */
  558.       for (i=0; i<d->numadj; i++)
  559.         if (d->adjdir[i] == 'H' && d->adjxy[i] == xy) {
  560.           d->adjdir[i] = d->adjdir[--d->numadj];
  561.           d->adjxy [i] = d->adjxy [  d->numadj];
  562.           d->adjl  [i] = d->adjl  [  d->numadj];
  563.           break; /* There can be only one */
  564.         }
  565.  
  566.       /* Place character */
  567.       if (ISFREE(*grid)) {
  568.         d->hash += (123456+xy)*(123456-*p); /* Neat, isn't it? */
  569.         *attr |= TODOV;
  570.         d->numchar++;
  571.       } else {
  572.         d->numconn++;
  573.      }
  574.     }
  575.     *grid = *p;
  576.   }
  577.  
  578.   /* Update hotspot */
  579.   if (xy2level[xy-1] > d->lastlevel)
  580.     d->lastlevel = xy2level[xy-1];
  581.  
  582. #if SYMMETRICAL
  583.   /* Don't forget the symmetry */
  584.   if (d->symdir == 0) {
  585.     d->symdir = 'H';
  586.     d->symxy  = GRIDMAX*GRIDMAX-1-(xybase+wlen[word]-1);
  587.     d->symlen = wlen[word];
  588.   } else
  589.     d->symdir = 0;
  590. #endif
  591.  
  592.   /* Save grid */
  593.   add_node (d);
  594.   return 1;
  595. }
  596.  
  597. int place_vword (node *data, int xybase, int word)
  598. {
  599. node *d=data;
  600. uint8 *p, *grid, *attr;
  601. int i, xy, l;
  602. int newnumadj;
  603. struct link *ld;
  604.  
  605.   /* Some basic tests */
  606.   if (INSET(d->words, word)) return 0;
  607.   if (xybase < 0 || xybase+wlen[word]*GRIDMAX >= GRIDMAX*GRIDMAX+GRIDMAX) return 0;
  608.  
  609. #if SYMMETRICAL
  610.   /* How about star's */
  611.   if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-xybase]))
  612.     return 0;
  613.   if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-(xybase+wlen[word]*GRIDMAX-GRIDMAX)]))
  614.     return 0;
  615. #endif
  616.  
  617.   /* Check character environment */
  618.   newnumadj = d->numadj;
  619.   for (xy=xybase,grid=d->grid+xy,p=wordbase[word]; *p; grid+=GRIDMAX,xy+=GRIDMAX,p++) {
  620.     if (*grid == *p)
  621.       continue; /* Char already there */
  622.     if (!ISFREE(*grid))
  623.       return 0; /* Char placement conflict */
  624.     if (ISSTAR(*p))
  625.       continue; /* Skip stars */
  626.     if (!ISCHAR(grid[-1]) && !ISCHAR(grid[+1]))
  627.       continue; /* No adjacent chars */
  628.  
  629.     if (ISFREE(grid[-1])) {
  630.       d->adjxy [newnumadj] = xy;
  631.       d->adjl  [newnumadj] = links2[*p][grid[+1]];
  632.     } else if (ISFREE(grid[+1])) {
  633.       d->adjxy [newnumadj] = xy-1;
  634.       d->adjl  [newnumadj] = links2[grid[-1]][*p];
  635.     } else {
  636.       d->adjxy [newnumadj] = xy-1;
  637.       d->adjl  [newnumadj] = links3[grid[-1]][*p][grid[+1]];
  638.     }
  639.     if (d->adjl[newnumadj] == 0 || newnumadj == ADJMAX-1)
  640.       return 0;
  641.     d->adjdir[newnumadj++] = 'H';
  642.   }
  643.  
  644.   /* Test if new adj's really exist */
  645.   for (i=d->numadj; i<newnumadj; i++) {
  646.     for (l=d->adjl[i]; l; l=ld->next) {
  647.       ld = &linkdat[l];
  648.       if (test_hword (d, d->adjxy[i]+ld->ofs, ld->w))
  649.         break;
  650.     }
  651.     if (l == 0) return 0;
  652.     d->adjl[i] = l;
  653.   }
  654.  
  655.   /* Get a new grid */
  656.   d = mallocnode();
  657.   memcpy (d, data, sizeof(node));
  658.  
  659.   /* Place word */
  660.   BITSET(d->words, word);
  661.   d->numword++;
  662.   d->numadj = newnumadj;
  663.   for (xy=xybase,grid=d->grid+xy,attr=d->attr+xy,p=wordbase[word];
  664.        *p;
  665.        grid+=GRIDMAX,attr+=GRIDMAX,xy+=GRIDMAX,p++) {
  666.     if (!ISSTAR(*p)) {
  667.       *attr &= ~TODOV;
  668.  
  669.       /* Remove character pair hints that are part of the new word */
  670.       for (i=0; i<d->numadj; i++)
  671.         if (d->adjdir[i] == 'V' && d->adjxy[i] == xy) {
  672.           d->adjdir[i] = d->adjdir[--d->numadj];
  673.           d->adjxy [i] = d->adjxy [  d->numadj];
  674.           d->adjl  [i] = d->adjl  [  d->numadj];
  675.           break; /* There can be only one */
  676.         }
  677.  
  678.       /* Place character */
  679.       if (ISFREE(*grid)) {
  680.         *attr |= TODOH;
  681.         d->hash += (123456+xy)*(123456-*p); /* Neat, isn't it? */
  682.         d->numchar++;
  683.       } else {
  684.         d->numconn++;
  685.       }
  686.     }
  687.     *grid = *p;
  688.   }
  689.  
  690.   /* Update hotspot */
  691.   if (xy2level[xy-GRIDMAX] > d->lastlevel)
  692.     d->lastlevel = xy2level[xy-GRIDMAX];
  693.  
  694. #if SYMMETRICAL
  695.   /* Don't forget the symmetry */
  696.   if (d->symdir == 0) {
  697.     d->symdir = 'V';
  698.     d->symxy  = GRIDMAX*GRIDMAX-1-(xybase+wlen[word]*GRIDMAX-GRIDMAX);
  699.     d->symlen = wlen[word];
  700.   } else
  701.     d->symdir = 0;
  702. #endif
  703.  
  704.   /* Save grid */
  705.   add_node (d);
  706.   return 1;
  707. }
  708.  
  710. /*
  711. ** Scan a grid and place a word. To supress an exponential growth of
  712. ** generated grids, we can be very fussy when chosing which word to
  713. ** place. I have chosen to fill the grid from top-left to bottom-right
  714. ** making sure the newly placed words fit tightly to the already placed
  715. ** words. If this is not possible, then I choose just one word such that
  716. ** the first letter is nearest to the start of the hotspot regeon.
  717. ** This sounds easy but it took me quite some time to figure it out.
  718. */
  719.  
  720. void scan_grid (node *d)
  721. {
  722. uint8 *grid, *attr;
  723. int xy, l, cnt, tstxy, level;
  724. struct link *ld;
  725. int hasplace, hasfree;
  726.  
  727. #if SYMMETRICAL
  728.   int w ;
  729.   /* Don't forget the symmetry */
  730.   if (d->symdir == 'H') {
  731.     for (w=numword-1; w>=0; w--)
  732.       if (!INSET(d->words, w) && wlen[w] == d->symlen)
  733.         place_hword (d, d->symxy, w);
  734.     return;
  735.   }
  736.   if (d->symdir == 'V') {
  737.     for (w=numword-1; w>=0; w--)
  738.       if (!INSET(d->words, w) && wlen[w] == d->symlen)
  739.         place_vword (d, d->symxy, w);
  740.     return;
  741.   }
  742. #endif
  743.  
  744.   /* locate unaccounted adjacent cells */
  745.   if (d->numadj > 0) {
  746.     xy  = d->adjxy[--d->numadj];
  747.     if (d->adjdir[d->numadj] == 'H') {
  748.       for (l=d->adjl[d->numadj]; l; l=ld->next) {
  749.         ld = &linkdat[l];
  750.         place_hword (d, xy+ld->ofs, ld->w);
  751.       }
  752.     } else {
  753.       for (l=d->adjl[d->numadj]; l; l=ld->next) {
  754.         ld = &linkdat[l];
  755.         place_vword (d, xy+ld->ofs*GRIDMAX, ld->w);
  756.       }
  757.     }
  758.     return;
  759.   }
  760.  
  761.   /* Nominate grid for final result */
  762.   if (d->numword > solution.numword)
  763.     memcpy (&solution, d, sizeof(node));
  764.  
  765.   /* Sweep grid from top-left to bottom-right corner */
  766.   for (level=d->firstlevel; level<=d->lastlevel&&level<=GRIDMAX*2-4; level++) {
  767.  
  768. #if !SYMMETRICAL
  769.     /* Locate 'tight' words */
  770.     hasplace = 0;
  771.     for (xy=level2xy[level],grid=d->grid+xy,attr=d->attr+xy;
  772.          !ISBORDER(*attr);
  773.          xy+=GRIDMAX-1,grid+=GRIDMAX-1,attr+=GRIDMAX-1) {
  774.       if (*attr&TODOH) {
  775.         for (l=links1[*grid]; l; l=ld->next) {
  776.           ld = &linkdat[l];
  777.           tstxy = xy+ld->ofs;
  778.           if (xy2level[tstxy] == d->firstlevel)
  779.             hasplace += place_hword (d, tstxy, ld->w);
  780.         }
  781.       }
  782.       if (*attr&TODOV) {
  783.         for (l=links1[*grid]; l; l=ld->next) {
  784.           ld = &linkdat[l];
  785.           tstxy = xy+ld->ofs*GRIDMAX;
  786.           if (xy2level[tstxy] == d->firstlevel)
  787.             hasplace += place_vword (d, tstxy, ld->w);
  788.         }
  789.       }
  790.       if (hasplace)
  791.         return;
  792.     }
  793. #endif
  794.  
  795.     /* Locate 'adjacent' word */
  796.     hasplace = 0;
  797.     for (xy=level2xy[level],grid=d->grid+xy,attr=d->attr+xy;
  798.          !ISBORDER(*attr);
  799.          xy+=GRIDMAX-1,grid+=GRIDMAX-1,attr+=GRIDMAX-1) {
  800.       if (*attr&TODOH) {
  801.         for (l=links1[*grid]; l; l=ld->next) {
  802.           ld = &linkdat[l];
  803.           tstxy = xy+ld->ofs;
  804.           if (ISSTAR(d->grid[tstxy]))
  805.             hasplace += place_hword (d, tstxy, ld->w);
  806. #if SYMMETRICAL
  807.           if (ISSTAR(d->grid[GRIDMAX*GRIDMAX-1-(tstxy+wlen[ld->w]-1)]))
  808.             hasplace += place_hword (d, tstxy, ld->w);
  809. #endif
  810.         }
  811.       }
  812.       if (*attr&TODOV) {
  813.         for (l=links1[*grid]; l; l=ld->next) {
  814.           ld = &linkdat[l];
  815.           tstxy = xy+ld->ofs*GRIDMAX;
  816.           if (ISSTAR(d->grid[tstxy]))
  817.             hasplace += place_vword (d, tstxy, ld->w);
  818. #if SYMMETRICAL
  819.           if (ISSTAR(d->grid[GRIDMAX*GRIDMAX-1-(tstxy+wlen[ld->w]*GRIDMAX-GRIDMAX)]))
  820.             hasplace += place_vword (d, tstxy, ld->w);
  821. #endif
  822.         }
  823.       }
  824.       if (hasplace)
  825.         return;
  826.     }
  827.  
  828.     /* Locate word fragments (just one word please) */
  829.     hasplace = 0;
  830.     hasfree = 0;
  831.     for (xy=level2xy[level],grid=d->grid+xy,attr=d->attr+xy;
  832.          !ISBORDER(*attr);
  833.          xy+=GRIDMAX-1,grid+=GRIDMAX-1,attr+=GRIDMAX-1) {
  834.       if (ISFREE(*grid))
  835.         hasfree = 1;
  836.       if (*attr&TODOH) {
  837.         cnt = 0;
  838.         for (l=links1[*grid]; l; l=ld->next) {
  839.           ld = &linkdat[l];
  840.           tstxy = xy+ld->ofs;
  841.           if (!ISSTAR(d->grid[tstxy]))
  842.             cnt += place_hword (d, tstxy, ld->w);
  843. #if !SYMMETRICAL
  844.           if (cnt != 0)
  845.             break;
  846. #endif
  847.         }
  848.         if (cnt == 0) {
  849.           /* Speed things up (Not 100% correct, but it's fast) */
  850.           *attr &= ~TODOH;
  851.           grid[-1] = STAR;
  852.           grid[+1] = STAR;
  853. #if SYMMETRICAL
  854.           if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-(xy-1)])) return; /* Arghh */
  855.           d->grid[GRIDMAX*GRIDMAX-1-(xy-1)] = STAR;
  856.           if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-(xy+1)])) return; /* Arghh */
  857.           d->grid[GRIDMAX*GRIDMAX-1-(xy+1)] = STAR;
  858. #endif
  859.         }
  860.         hasplace += cnt;
  861.       }
  862.       if (*attr&TODOV) {
  863.         cnt = 0;
  864.         for (l=links1[*grid]; l; l=ld->next) {
  865.           ld = &linkdat[l];
  866.           tstxy = xy+ld->ofs*GRIDMAX;
  867.           if (!ISSTAR(d->grid[tstxy]))
  868.             cnt += place_vword (d, tstxy, ld->w);
  869. #if !SYMMETRICAL
  870.           if (cnt != 0)
  871.             break;
  872. #endif
  873.         }
  874.         if (cnt == 0) {
  875.           /* Speed things up (Not 100% correct, but it's fast) */
  876.           *attr &= ~TODOV;
  877.           grid[-GRIDMAX] = STAR;
  878.           grid[+GRIDMAX] = STAR;
  879. #if SYMMETRICAL
  880.           if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-(xy-GRIDMAX)])) return; /* Arghh */
  881.           d->grid[GRIDMAX*GRIDMAX-1-(xy-GRIDMAX)] = STAR;
  882.           if (ISCHAR(d->grid[GRIDMAX*GRIDMAX-1-(xy+GRIDMAX)])) return; /* Arghh */
  883.           d->grid[GRIDMAX*GRIDMAX-1-(xy+GRIDMAX)] = STAR;
  884. #endif
  885.         }
  886.         hasplace += cnt;
  887.       }
  888.       if (hasplace)
  889.         return;
  890.     }
  891.  
  892.     /* Update hotspot */
  893.     if (!hasfree)
  894.       d->firstlevel = level+1;
  895.   }
  896. }
  897.  
  898. void kick_ass (void)
  899. {
  900. node *d, *todonode;
  901. int i;
  902.  
  903.   for (;;) {
  904.     /* setup up some debugging statistics */
  905.     realnumnode = numnode = numscan = 0;
  906.     hashtst = hashhit = 0;
  907.  
  908.     /* gather all nodes into a single list with highest score first */
  909.     d=todonode = NULL;
  910.     for (i=SCOREMAX-1; i>=0; i--)
  911.       if (scores[i]) {
  912.         if (todonode == NULL)
  913.           d=todonode=scores[i];
  914.         else
  915.           d->next = scores[i];
  916.         while (d->next) d=d->next;
  917.         scores[i] = NULL;
  918.       }
  919.  
  920.     /* Ok babe, lets go!!! */
  921.     while (todonode) {
  922.       d = todonode;
  923.       todonode = d->next;
  924.       if (d->numadj > 0 || numnode<NODEMAX) {
  925.         if (d->numadj == 0) numscan++;
  926.         scan_grid (d);
  927.       }
  928.       d->next = freenode;
  929.       freenode = d;
  930.     }
  931.  
  932.     /* Test for timeouts */
  933.     elapsedtime();
  934.  
  935. #if DEBUG
  936.     fprintf(stderr, "%s word:%2d score:%f level:%2d/%2d node:%4d/%4d/%4d hash:%3d/%3d\n",
  937.             elapsedstr(), solution.numword, solution.score,
  938.             solution.firstlevel, solution.lastlevel, numscan, numnode,
  939.             realnumnode, hashtst, hashhit);
  940.     if (flg_dump) dump_grid (&solution);
  941. #endif
  942.  
  943.     /* Ass kicked? */
  944.     if (realnumnode == 0)
  945.       break;
  946.   }
  947. }
  948.  
  950. void load_words (void)
  951. {
  952. char line[80], c;
  953. FILE *f;
  954. int i, w, done;
  955. uint8 *p;
  956.  
  957.   /* Open file and load the words and check if they are valid */
  958.   f = fopen (wordfname, "r");
  959.   if (!f) {
  960.     fprintf (stderr, "Cannot open %s\n", wordfname);
  961.     exit (1);
  962.   }
  963.   for (numword=0;;) {
  964.     /* Read line */
  965.     if(fgets (line, sizeof(line), f)==NULL || feof(f))
  966.       break;
  967.     /* Copy the word */
  968.     i = 0;
  969.     wordbase[numword][i++] = STAR;
  970.     for (;isalpha(c=line[i-1]);i++)
  971.       wordbase[numword][i] = isupper(c) ? tolower(c)-BASE : c-BASE;
  972.     wordbase[numword][i++] = STAR;
  973.     wordbase[numword][i] = 0;
  974.     wlen[numword] = i;
  975.     if (i > WORDLENMAX-2) {
  976.       fprintf(stderr, "Word too long\n");
  977.       exit(0);
  978.     }
  979.     if (i > 2){
  980.       if (numword == WORDMAX-1) {
  981.         fprintf(stderr, "Too many words\n");
  982.         exit(0);
  983.       } else {
  984.         numword++;}
  985.      }
  986.   }
  987.   fclose (f);
  988.  
  989. #if DEBUG
  990.   fprintf(stderr, "%s Loaded %d words\n", elapsedstr(), numword);
  991. #endif
  992.  
  993.   /*
  994.   ** Calculate links. These are indexes on the wordlist which are used
  995.   ** to quickly locate 1,2,3 long letter sequences within the words.
  996.   */
  997.   numlinkdat=1;
  998.   memset (links1, 0, sizeof(links1));
  999.   memset (links2, 0, sizeof(links2));
  1000.   memset (links3, 0, sizeof(links3));
  1001.   for (i=0,done=0; !done && i<WORDLENMAX; i++) {
  1002.     done = 1;
  1003.     for (w=numword-1; w>=0; w--) {
  1004.       p = wordbase[w];
  1005.       if (i>=0 && i<=wlen[w]-3) {
  1006.         /* With delimiters */
  1007.         linkdat[numlinkdat].w = w;
  1008.         linkdat[numlinkdat].ofs = -i;
  1009.         linkdat[numlinkdat].next = links3[p[i+0]][p[i+1]][p[i+2]];
  1010.         links3[p[i+0]][p[i+1]][p[i+2]] = numlinkdat++;
  1011.         done = 0;
  1012.       }
  1013.       if (i>=0 && i<=wlen[w]-2) {
  1014.         /* With delimiters */
  1015.         linkdat[numlinkdat].w = w;
  1016.         linkdat[numlinkdat].ofs = -i;
  1017.         linkdat[numlinkdat].next = links2[p[i+0]][p[i+1]];
  1018.         links2[p[i+0]][p[i+1]] = numlinkdat++;
  1019.         done = 0;
  1020.       }
  1021.       if (i>0 && i<=wlen[w]-2) {
  1022.         /* Without delimiters */
  1023.         linkdat[numlinkdat].w = w;
  1024.         linkdat[numlinkdat].ofs = -i;
  1025.         linkdat[numlinkdat].next = links1[p[i]];
  1026.         links1[p[i]] = numlinkdat++;
  1027.         done = 0;
  1028.       }
  1029.     }
  1030.   }
  1031.  
  1032. #if DEBUG
  1033.   fprintf(stderr, "%s Found %d links\n", elapsedstr(), numlinkdat);
  1034. #endif
  1035. }
  1036.  
  1037. int main (int argc, char **argv)
  1038. {
  1039. node *d;
  1040. int x, y, i, w;
  1041.  
  1042. #if DEBUG
  1043.   fprintf(stderr, "sizeof(node)=%d\n", sizeof(node));
  1044. #endif
  1045.  
  1046.   /* simple arguments */
  1047.   for (i=1; i<argc; i++) {
  1048.     if (argv[i][0] != '-')
  1049.       wordfname = argv[i];
  1050.     else {
  1051.       switch (argv[i][1]) {
  1052.         case 'd':
  1053.           flg_dump++; /* Diagnostics */
  1054.           break;
  1055.       }
  1056.     }
  1057.   }
  1058.  
  1059.   /* In case we run out of memory, sigh */
  1060.   fflush (stderr);
  1061.   fflush (stdout);
  1062.  
  1063.   /* Load the database */
  1064.   clktck = sysconf(_SC_CLK_TCK);
  1065.   load_words();
  1066.  
  1067.   /* init grid administration */
  1068.   freenode = NULL;
  1069. #if MALLOC_BROKEN
  1070.   nummalloc = 6000;
  1071.   d=malloc (nummalloc*sizeof(node));
  1072.   if (d == NULL)
  1073.     nummalloc = 0;
  1074.   else
  1075.     for(i=0; i<nummalloc; i++) {
  1076.       d[i].next = freenode;
  1077.       freenode = d+i;
  1078.     }
  1079. #endif
  1080.  
  1081.   /* Do some hotspot pre-calculations */
  1082.   for (i=GRIDMAX*GRIDMAX-1; i>=0; i--)
  1083.     xy2level[i] = (i%GRIDMAX)+(i/GRIDMAX);
  1084.   for (i=0; i<GRIDMAX*2; i++) {
  1085.     if (i<GRIDMAX) {
  1086.       level2xy[i] = i+GRIDMAX-1;
  1087.     } else {
  1088.       level2xy[i] = GRIDMAX*GRIDMAX-(GRIDMAX*2-3-i)*GRIDMAX-2;
  1089.     }
  1090.   }
  1091.  
  1092.   /* create an initial grid */
  1093.   d = (node*) calloc(1, sizeof(node));
  1094.   for (y=GRIDMAX-1; y>=0; y--)
  1095.     for (x=GRIDMAX-1; x>=0; x--) {
  1096.       d->grid[x+y*GRIDMAX] = STAR;
  1097.       d->attr[x+y*GRIDMAX] = BORDER;
  1098.     }
  1099.   for (y=GRIDMAX-2; y>0; y--)
  1100.     for (x=GRIDMAX-2; x>0; x--) {
  1101.       d->grid[x+y*GRIDMAX] = FREE;
  1102.       d->attr[x+y*GRIDMAX] = 0;
  1103.     }
  1104.  
  1105.   /* Place all the words for starters */
  1106. #if SYMMETRICAL
  1107.   /* work from the middle out */
  1108.   for (w=numword-1; w>=0; w--)
  1109.     if (wlen[w]>=5) {
  1110.       d->hash = 0;
  1111.       place_hword (d, (GRIDMAX/2+2-wlen[w])+(GRIDMAX/2)*GRIDMAX, w);
  1112.     }
  1113. #else
  1114.   /* work from top-left to bottom-right */
  1115.   for (w=numword-1; w>=0; w--) {
  1116.     d->firstlevel = 2;
  1117.     place_hword (d, 0+1*GRIDMAX, w);
  1118.   }
  1119. #endif
  1120.   d->next = freenode;
  1121.   freenode = d;
  1122.  
  1123.   /* Here we go */
  1124.   kick_ass();
  1125.   dump_grid (&solution);
  1126.  
  1127.   exit(0);
  1128. }
  1129.