CROZZLE Program entry descriptions

Beware of long mail .... but there ARE gems buried! Even if you don't study the whole thing, you might want to check out the first four or five writeups!

The attached mail is the collection of write-ups I received. As usual they are mostly unedited (only personal POTM-master insults were removed). Write-ups are provided in order of finish (more or less).


======================================= jigsaw =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
            jigsaw   212   280   646  794.83  GCC  Franz Korntner
=================
jigsaw was submitted by Franz Korntner at fkorntne@bazis.nl
=================

LS: A cell is a entry in the 20x20 grid

++ WHERE DID jigsaw begin - short words, complex meshes, corners, etc.??? Why?

Jigsaw mainly starts from the top-left corner and works it way down to the
bottom-right. New words a placed in such a fashion that they fit tightly
against the already placed words. Why? I've tried many other algorithms but 
it seems that they create 'islands' (an island is a large cluster of cells 
that cannot be filled with letters). The presence of islands use up valuable
grid space, thus  lowering the score. I've even tried island detection 
algorithms, but they cost too many CPU.

The placing of new words can create many new grids, too many to process
within the CPU time limit. To reduce calculation time, a selection must
be made of grids which are to be generated. Therefore, we can be very fussy
about which word will be placed where. It makes no sense to create a new 
grid that contains a pathological bad solution. New words are placed
in the following order:

  - Adjecent letters are handled specially. When adjecent letters are 
    found that do not belong to an already placed word, new grids are
    generated containing *ALL* word possabilities. These grids do not
    count against GRIDMAX (see below).

  - A word can *only* be placed if at least one letter of the word is
    already present in the grid, *AND* when newly placed letters will
    be adjecent to already existing letters, those letter pairs (or
    three-sums) must exist somewhere in the wordlist.

  For the nearest unprocessed letter located to the top-left corner:
  
  - If a word can be placed using the selected letter and the starting 
    letter of that word fits tightly to the words already placed (max.
    one free cell distance to an existing letter), then place that word.

  - If no words could be found, then try placing *one* word using the 
    selected letter in such a way that the first letter of the word 
    is located nearest to an existing letter. Only one word may be
    placed as there are many combinations possible, and jigsaw must
    be fussy.

  - If still no word has been found, mark the selected letter as
    unprocessable and find a new letter and 
    
  - Stop generating new grids when more than GRIDMAX grids have created.
    (unprocessed adjecent letter pairs are special and always processed).

++ HOW DID jigsaw try to maximize the number of words and intersections used?

Jigsaw's algorithm needs to know how good a grid is. Good means it is 
candidate to get a high final score. Jigsaw continues filling grids that
have high scores, and discards grids that have low scores. The scoring 
formula is:

  <#connectors> / <#letters>

This implies:

  - Many connectors good. If a word has more connectors it means that
    other words are occuping the nebouring space, thus more words will
    fit the grid.

  - Many letters bad. It's better to have two short words than one bad.

The number of words are not taken into account, as all score comparisons
are done with grids containg the same number of words. 

For comparison, I've tries some other formulas, but they didn't work
out for the better.

++ Did jigsaw iterate?  randomize?  attempt to improve it's first solution?

Jigsaw uses a non-exaustive width-first tree-search algorithm. The level
on which a node resides in the tree indicates the number of words placed. 
The root contains no words, all nodes on the first level contain 1 word, 
and so on.

The algorithm processes one level at a time, starting at the root. It takes 
NODEMAX (1500) nodes of a single level with the highest score, adds a word 
forming a new node of a next tree level. Once the level has been completed,
all nodes of the (old) level are deleted to free memory space. This implies
that there is no recallable history of how the grid was created. Duplicate 
grid detection is needed to compensate the lack of history. For example:

  ---f-
  your-
  -n-o-
  blank
  -y-t-

This grid can be created by placing (in sequence) "your front blank only"
or "your only blank front". If there wasn't duplicate detection, the tree
would contain many of these (duplicate) combinations, effectively reducing 
the algorithms outcome dramaticly.

++ How did jigsaw know it was done?

Simple, when no more words can be inserted into the grid.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

This scoring algorithm has one flaw. It tends to nonimate very tight grids 
for the first handful of words consisting mainly of short words. When the
grid is about half full, only larger words can be placed that are 
not so tight, but there are no shorter words available anymore. One solution
is to 'pollute' the levels with grids containing relatively bad scores in the
hope that they might work out better when the grid is starting to get full.

I've implemented poluting by giving NODEMAX a relatively low value of 1500.
A better method is to add a random value to the score, but I havn't had the
time to implement/test that.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

I like to play games (mahjongg, talisman, dragondice), but can't really
find play-pals as they prefer Magic cards.

I really love POTM as there's a lot of feedback, something I can't say 
for IOCCC. I had a very nifty one-liner (mastermind solver) but I haven't 
a clue were it got placed :-( Pity as I like to pat my ego.

 
=================================================================

======================================= crossroads =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
        crossroads   210   251   664 1746.12    C  =Stan Peijffers
=================
crossroads was submitted by Stan Peijffers at speijffe@hvssa01.ns-nl.att.com
=================
++ WHERE DID crossroads begin 

A "move" consists in putting one or more interconnected words on the board.
Whether a move is better than another is based on an evaluation function.
The evaluation function takes into account the following :

+ the number of words placed (largest factor),
+ for each word :
  - a precalculated value for the word which depends on the number of
    occurrences of each letter totaled over all words in the list,
    (avoids placement of words which are hard to interconnect with)

  - the length of the word, where 4 is the optimal length :
    (longer words are increasingly non-interesting because
     they take up too much space. shorter words are increasingly
     non-interesting because they do not generate enough connecting
     points, and can more easily be added toward the end when the board gets
     full).

  - the number of squares on the board that become unplayable as a result 
    of putting the word on the board (normally this is 2)
    (this favors words that terminate on the edges, 
     and words that terminate close
     to where previous words have terminated -> compactness)

  - the number of intersections created (low factor however)

The move generator tries to put as many words as possible on the board
(see evaluation function) in one move. To make sure that only valid
combinations are generated a (recursive) check-function is embedded.
The move generator is general-purpose (no special cases for corners, 
intersections, etc), powerful (any combination of horizontal and vertical
words can be found) and fast (about 2/3 secs to fill an empty board).

The move generator is called repeatedly until the board is full. 
Each call to the move generator is in fact a recursive call with a look-ahead
of one.


OK. So now we have filled up the board (after 2/3 secs of CPU).
This may be a good first attempt but should be improved.

++ HOW DID crossroads try to maximize 

It does not attempt to maximize the number of intersections. It only attempts
to maximize the number of words.

++ Did crossroads iterate?  randomize?  attempt to improve it's first solution?

The rest of the 10 minutes worth of CPU is spent in trying to improve
the solution. This is done by removing words from the solution and trying
a different solution. 

Removal of words should be such that all the remaining words stay
interconnected. This can be achieved by considering the words on the board
as a graph 
(where the words are the nodes of the graph, and the interconnections between
2 words are the edges of the graph).

From graph theory we know that there exists an O(n+e) time algorithm to
compute the "articulation points" of a graph. These are the nodes (words)
that leave 2 (or more) subgraphs when removed from the graph.

This algorithm is used to decide which word (together with one of the
subgraphs) should be removed.

Articulation points are not exercized as they are detected by the
algorithm : in stead 3 consecutive scans are made over all articulation points :
in a first scan only those articulation points are exercized that 
remove many words (more than 2/3 of all the words). In a second scan
medium sized changes are considered, and in a final scan only small
changes are considered (a few words). [Not unlike simulated annealing].

Clearly : everytime a new solution is found which improves upon the previous 
best, this solution is now taken as a new starting point.

This algorithm typically still does not use up all of the
alloted 10 minutes : an initial solution 
+ 3 scans of all articulation points on average uses 30 secs.
Therefore the above algorithm is repeated with an empty board again and 
placing a different first word on the board.

++ How did crossroads know it was done?

When all words have been put on the grid, or when 10 minutes were used up
whichever comes first.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

I have put some ad-hoc code at the beginning of the algorithm to cater for
tests that can generate a fully intermeshed raster of words 
(say 40 words of 20 letters each) and some variants thereof
(since you never know what the POTM-master may throw at you).

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

Lucent Technologies, International 5ESS SW development, Hilversum NL

=================================================================

======================================= crucigramista =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
     crucigramista   207   255   643 1799.33  GCC  =Andre' Wilhelmus

=================
crucigramista was submitted by Andre' Wilhelmus at 
			hvgtw!hvscg01!awilhelm@attmail.att.com
=================
++ WHERE DID crucigramista begin 
The first attempt starts with the shortest word in the upper left corner.
Following attempts will cycle through the words and fields on the board.

++ HOW DID crucigramista try to maximize 
It keeps a list of untried occupied fields which could be crossed and
tries to fit short words first.  If a word fits it is placed on the board.
If a word is placed next to another word, it maintains a list of fields
which must be resolved first and goes recursive to try to
fit other words on those fields.

++ Did crucigramista iterate?  randomize?  attempt to improve
At the end, words which cross another word once are removed and replaced
to see if more words can be fitted.

++ How did crucigramista know it was done?
After trying to replace the last single word it saves the best solution,
empties the board and starts all over again until time runs out.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

++ COMPANY?          Lucent Technologies
LOCATION?         Hilversum, The Netherlands
JOB?              maintaining programs for the factory in Huizen
DO FOR FUN?       playing the adventure game Monkey Island 2 on my Mac
INNERMOST SECRET? bishoujo senshi... ^_^
POTM IDEAS?       nope

=================================================================

======================================= knuppel =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
           knuppel   201   227   613 1777.48  G++  P.Frants S.Pieterse

=================
knuppel was submitted by P.Frants S.Pieterse at spieters@cs.vu.nl
=================
++ WHERE DID knuppel begin - short words, complex meshes, corners, etc.??? Why?

We started out by throwing away the longest 50% of the words. This
speeds up the program enormously. It is clear that short words take less
space in the puzzle.

The next step was to place words in the puzzle one by one using
appropriate heuristics. Words placed on the borders or with many crosses
were considered better than others.


++ HOW DID knuppel try to maximize the number of words and intersections used?
This was achieved using appropriate heuristics


++ Did knuppel iterate?  randomize?  attempt to improve it's first solution?
Yes, yes, yes :-)


++ How did knuppel know it was done?
alarm(592)


++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
First make a prototype to get acquainted with the problem. Next leave
the POTM alone for about two weeks and throw away the prototype. NOW you
are ready to write a killer program. Well almost, don't forget to
optimize the hell out of your code!


++ COMPANY?  LOCATION?	JOB?	DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
We are both CS-students at Vrije Universiteit Amsterdam and like solving
these POTM-style problems. Also we promise to win the next POTM :)
Damn! That was our innermost secret!

=================================================================

======================================= Crozzodile =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
        Crozzodile   200   253   615 1112.07  GCC  =Chad Hurwitz

=================
Crozzodile was submitted by Chad Hurwitz at churritz@cts.com
=================
++ WHERE DID Crozzodile begin

a random word placed randomly.

++ HOW DID Crozzodile try to maximize

after the first random word it tried to choose words that scored well.  and
the scoring involved shortness of word, adjacency to puzzle edges, and
count of additional words necessary to be placed for this word to be placed.

++ Did Crozzodile iterate?  randomize?  attempt to improve it's first solution?

yes, yes, yes.  my improvement algorithm wasn't very productive though.

++ How did Crozzodile know it was done?

time limit.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

well, if you're unwashed (and you don't mind washing), then wash.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

vaxa, usa, well if you insist, mountains, yes, chessers (mix of checkers chess).

=================================================================

======================================= Wordsworth =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
        Wordsworth   198   235   607 1788.40    C  Davor Slamnig

=================
Wordsworth was submitted by Davor Slamnig at slama.pub.hr!slama@ig2.att.att.com
=================

++ WHERE DID Wordsworth begin 
++ HOW DID Wordsworth try to maximize the number of words 
++ Did Wordsworth iterate?  randomize?  attempt to improve it's first solution?
++ How did Wordsworth know it was done?

Wordsworth uses a simple engine which examines a set of words S1 already
on the grid and crosses the words with others, which comprise the set
S2. Then S2 becomes S1, etc.

Initially, set S1 is one short word placed somewhere.
Then the algorithm is looped until no more words can be added.

This simple scheme is embellished by constructing "clusters" of 4 words,
each of which intersects two other words, e.g.:

            c
           bake
          sit
           t

(I was working on the construction of bigger clusters with words
overlapping over a larger area, but I simply ran out of stamina).

By feeding it permuted input data, this engine constructs as many
crosswords as it can in the time given, and outputs the best one.

The permutation goes like this: First randomize the input word-list, then
sort it according to word-length. This forces the use of shorter words,
and still produces a significant number of different orderings.
(The actual implementation is a bit more complicated, since I use
various indexing schemes).

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?

Freelance contractor / Zagreb, Croatia / Application designer /
Play guitar / Debugging 3rd party software takes longer than writing
it yourself

=================================================================

======================================= sswordpu =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
          sswordpu   192   204   587 1799.94    C  Bob Ashenfelter
=================
sswordpu was submitted by Bob Ashenfelter at ash@hotsoup.att.com
=================

++ WHERE DID sswordpu begin - short words, complex meshes, corners, etc.??? Why?

Short words, usually, but not the very shortest because these are some-
times generated incidentally while fitting in subsequent words and I
didn't want to use them up.  Usually start at a random point, but some-
times in the upper-left corner.  Why?  Because I couldn't think of any-
thing better.

++ HOW DID sswordpu try to maximize the number of words and intersections used?

Multiple solutions and pick the best one.

++ Did sswordpu iterate?  randomize?  attempt to improve it's first solution?

All of the above.

++ How did sswordpu know it was done?

Time limit.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

Well, this appears to be the appropriate heading for a description of
how it all works.  For this program description, I will take a bottom-up
approach.

The heart of the program is a routine called addwd(i,j) which attempts to
add a crossword to the grid at location (i,j) which presumably already
contains a letter, but not a connector.  The first thing is to decide
whether the crossword goes across or down.  Then it searches through
all available words and, for each word, all letters in the word.  When
it finds a letter that matches the letter at (i,j) it checks whether
the word can be used as a crossword.  The ends are checked to see that
it doesn't run into something previously in the grid or off the edge of
the grid.  Each letter of the possible crossword is then checked.  If it
matches a previous letter in its position in the grid, all is well.  If
there is a mismatch then that word at that position doesn't work.  If
there is a space in the grid at the position of the letter being examined,
then there are several possibilities:  (1) spaces on both sides of the
space; (2) a single letter on either side of the space, a space on the
other; (3) a single letter on both sides of the space, (4) a pre-existing
word ends on one side with a space or single letter on the other side;
(5) pre-existing words end on both sides.  Of these, (1) is OK.  (2) and
(3) will create an additional 2- or 3-letter word (I call it a double-
crossword) which is OK if that word is available, NG if not.  (4) will
add to the pre-existing word which would be OK if the augmented word is
available, but I was too lazy to implement this since it would require
returning the previous pre-existing word to the available word list (but
only potentially, since the crossword being examined may not pan out at
other letters), so (4) is considered NG.  (5) will bridge two words into
one and this is probably not a good idea in any case, not to mention the
horrendous complications in implementing it.  After all letters of the
potential crossword have been approved, it is accepted as a candidate and
the search goes on.  After all positions for all available words have
been searched, the best candidate (i.e. most words added to the grid),
if any, is chosen and added to the grid and the crossword and all double-
crosswords are removed from the list of available words.

As you can tell, this is an excessively complicated routine!  (If you can
understand the above paragraph, my hat's off to you.)  But as the heart
of the program, it is where the game is won or lost.  Probably it was a
mistake not to try to implement possibility (4) despite the daunting add-
itional complications.

Now things get easier.  The routine addwd(i,j) is used by two higher-level
routines, addrnd() and addall().  In either case, there is a list of
possible positions in the grid to use addwd(i,j).  Routine addrnd() keeps
picking from the list randomly until some number of choices result in no
successful crossword being added.  Routine addall() just goes through
the whole list.  Of course, whenever a crossword is added to the grid,
the list gets longer.  Either of these routines will take a partially
completed grid and add words to it until they run out of steam.

Routines addrnd() and addall() are used by several solver routines, each
of which starts from scratch and generates a possible solution grid.
Solve0() picks a random word and places it in a random spot in a blank
grid and them calls addall() to add as many other words as it can.
Solve1() is similar except it first calls addrnd() and then addall().
Solve2() is similar except the first word is placed in an even-numbered
row and addrnd() only adds 4-letter words and only in even-numbered rows
and columns; then addall() is called several times with successively
larger and smaller words allowed and all positions allowed.  The idea is
to fill the grid up with short words before considering the long ones,
hopefully getting more words in.  Solve3() starts off by trying to place
only 3-letter words in a special lattice that is optimum for 3-letter
words; then, like solve2() it allows ever more words in all positions.
Solve4() is like solve2() without the initial restrictions to even-numbered
rows and columns.  Solve5() is more complicated.  It starts with an 8x8
grid, generates a number of solutions, and chooses the best.  It then
expands to 12x12 and adds words to the best solution for the smaller size.
Again, it does this a number of times and chooses the best.  This is
repeated for 16x16 and finally for 20x20.

Finally, we have come to the top.  Main() starts by reading in the wordlist
and computing the word lengths.  It then sorts the wordlist, first by
length, and then alphabetically.  I can't remember why I did this but I
don't make any use of it and the wordlist is immediately scrambled by
the solvers, never to be re-sorted again.  Then it enters an endless loop
which calls each of the solvers in turn.  If any solution is better than
the previous best then that solution is saved as the best.  Actually, on
the very last day, I found that there is a bug somewhere that results in
an occasional invalid grid for a certain class of wordlists.  Not having
the time to fix the problem, I grafted in a routine, chkgrid(), from the
program I wrote at the very beginning to grade solutions and check them
for validity.  So a "better" solution is only saved if it passes checks
for words being in the wordlist, words not repeated, and a completely
connected solution.  As it turned out, Fred didn't challenge us with such
a wordlist.  Oh yes, the endless loop really isn't endless; at various
points in the program the clock is polled and when the 10 minutes are up,
the best solution is printed.

Most of the time, for most wordlists, solve5() ends up computing the best
solution.  However, because of the use of random choices, any of the them
is capable of coming up with the best.  For a wordlist containing only
three-letter words, solve3() usually comes up with a significantly better
solution.  I was hoping this would give me an edge if Fred used such a
wordlist.  In fact, I rather expected he would; why else would he have
left them out of the system test wordlist?  But, once again, he put his
energies into choosing clever sources for his test inputs rather than
making the test inputs themselves clever.  In the end the winning programs
were sufficiently better than sswordpu that an all-three-letter input
would not have made up the difference.


++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

Lucent Technologies, soon to transfer back to AT&T.  (Just got word that
it was signed while writing this blurb.)

Holdmel, N.J., U.S.A.  (Will have to move some day--no longer an AT&T
location.)

Circuit design.  (So why am I going back to AT&T?  Submarine Systems.)

Bicycling (new bike has been ordered), sailing (got rid of the boat...),
grow orchids (big new one recently acquired, small lady-slipper in bloom
on my desk), travel.

No way...

See questionnaire for previous POTM.

=================================================================

======================================= Binky =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
             Binky   189   201   596  180.13  GCC  Robert Rounthwaite

	Sorry ... no description available for Binky

=================================================================

======================================= Gak =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
               Gak   188   218   559 1787.23  G++  Justin Legakis

=================
Gak was submitted by Justin Legakis at legakis@cs.ucdavis.edu
=================

++ WHERE DID Gak begin

Gak begins by trying to fit the words into "clumps", groups of words
that fit together to form a solid rectangular block of letters.  Such
clumps cannot be found by solvers that attempt to place words one at
a time.  Gak then treats the clumps as a single unit that can be placed
onto the board.

++ HOW DID Gak try to maximize the number of words and intersections used?

Gak only uses 2-6 letter words.  The upper limit of 6 was chosen based on
experimentation.  Searching for clumps of words with a solid rectangle of
letters in the middle increases the number of intersections.

++ Did Gak iterate?  randomize?  attempt to improve it's first solution?

Gak starts with a clump/word in a random place, and repeatedly tries to
add clumps/words to the board.  Rather than tring to juggle words around
on the board, Gak tries to fill the board as fast as it can so it can
start over and make as many attempts as possible.  Between each attempt,
the list of clumps and words is randomized.

++ How did Gak know it was done?

When the time is up.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

Gak was able to find the clumps of words quickly by putting all the words
into a series of lists.  For example, a list of words is generated for all
words that have an 'r' as their first letter, or a 'u' as thier third letter,
or an 'i' as their second to last letter.  Gak stores the placed horizontal
and vertical words separately in order to more efficiently determine if a
given word will fit.


++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

I'm finishing my undergraduate degree in computer science at UC Davis,
and am trying to decide where to go for graduate school.

I'd like to try a puzzle where the programs compete against each other,
like Numbers Game, Boxing Match, or Chomp.
=================================================================

======================================= DontCrossMe =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
       DontCrossMe   185   182   586 1698.50  G++  Mike Goldshteyn

	Sorry ... no description available for DontCrossMe

=================================================================

======================================= theos_cross =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
       theos_cross   173   183   540 1457.99  GCC  Theo Sprokholt
=================
theos_cross was submitted by Theo Sprokholt at tsprokho@intgp1.att.com
=================
++ WHERE DID theos_cross begin 

First it sorted approximately 100 shortest words out of the list, since
it appeared that the longest words almost never showed up in the final result.
The program does a few trials with different orders of the words:
- short words first
- long words first
- lengths 5,6,7..20,2,3,4
- lengths 4,5,6,7..20,3,2
It starts at the left top corner, placing one word horizontally, and then
one word vertically. The first eight words are placed with the only
restriction of having only one cross. Every next word is tried with the
requirement of 4 crosses. If that does not succeed, 3, 2, or 1 cross is
allowed. This is repeated until all words are tried to fit in.

++ HOW DID theos_cross try to maximize 

The number of crosses are set to a minimum value while trying to place a word.
When no word can make it with this requirement, the level is lowered until
at least 1.

++ Did theos_cross iterate?  randomize?  

The best solution is stored. After every new trial, it is verified if that
solution is better, if so, that one was stored as best one.

There was some postprocessing done by removing the 2, 3 and 4 letter words
that had only one cross. These words were tried to fit at different locations.
Maybe that results in new gaps for other words.

++ How did theos_cross know it was done?

It did a fixed number of trials with the words sorted in different orders.
It tried to do as much as possible in the 10 minutes. It uses a unix signal
after 9:55 minutes to show the best found solution.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

Throw away all the longest words, they only consume a lot of space but
don't contribute to the word count.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

Theo Sprokholt
Lucent Technologies, Hilversum, the Netherlands.
Software development engineer for 5ESS software and firmware for peripherals.
=================================================================

======================================= 2RoadsCroz =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
        2RoadsCroz   173   177   571 1504.98    C  Gary Gressel
=================
2RoadsCroz was submitted by Gary Gressel at ggressel@attmail.com
=================
++ WHERE DID 2RoadsCroz begin 
It reorganized the word list into a variety of orders (short, long, common
letters, etc.) and then tried starting with different words in each of the
lists in different spots on the board.

++ HOW DID 2RoadsCroz try to maximize 
The code worked its way through different word sorts and starting positions
for the first word for the first 5 minutes.  After 5 minutes the program 
looked at its best word sort order and tried numerous additional combinations
for that wordlist.  At just before 10 minutes, the program produced its
best result.  The functions which handled complex meshes never got completed
due to work actually expecting me to spend time on their projects instead of
my own!

++ Did 2RoadsCroz iterate?  randomize?  attempt to improve it's first solution?
After 5 minutes it attempted to improve on the best solution at that time.
I didn't use random generation--didn't want to realize that the program 
_could_ have won had the random generator been different.

++ How did 2RoadsCroz know it was done?
Generally speaking a time limit.  There were a set number of combinations it
would try, but as long as the word list was of any significant size, the
time limit would be reached first.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
Nothing much has changed other than my company...I now work for "The New
AT&T" instead of just AT&T.  Btw, have we filed for that with the FCC yet?
I'm a Programmer/Security/Disaster Recovery/Administrator for AT&T in 
Kansas City, MO.  Oh, and am getting married June 1st; just as work 
distracted me the last 2 months of this contest, that marriage thing will
do it for the next POTM; hope you can get the puzzle out soon!  
=================================================================

======================================= CrossIt =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
           CrossIt   173   171   590 1642.85    C  Dennis Brooks

=================
CrossIt was submitted by Dennis Brooks at dab@aloft.att.com
=================
++ WHERE DID CrossIt begin

It begins with the "best" words. Each word receives a figure of merit based
on the frequency of use of each letter in the entire word list and normalized
to the length of the word. The normalization removes any bias pertaining to
word length. The "best" word is the word with the highest figure of merit and
is placed horizontally in the center of the grid. The next "best" word is
placed vertically; if a connector letter can be found. The building continues
with horizontal and then vertical placements.

++ HOW DID CrossIt try to maximize the number of words and intersections used?

Only the number of words was maximized. This was done using iteration. The
puzzle is actually done 80 times using 80 different "fudge factors". The
"fudge factor" derates long words. A "fudge factor" of 0% does not derate
long words. A "fudge factor" of 100% derates the longest word such that
its' figure of merit is 0 and it will become the last word to try and be
placed. Fudge factors from 20% to 100% were used.

++ Did CrossIt iterate?  randomize?  attempt to improve it's first solution?

It iterates using 80 different "fudge factors".

++ How did CrossIt know it was done?

After completing all 80 (actually 81) tries, the one with the most number
of words, highest number of connectors, and highest number of overall
letters was outputted.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

++ COMPANY?  Lucent Technologies.
++ LOCATION? 1247 S. Cedar Crest Blvd.  Allentown, Pa.
++ JOB?      Circuit designer of DSP Integrated Circuits.
++ DO FOR FUN?  Write computer programs.
++ INNERMOST SECRET?
++ POTM IDEAS?  Keep up the good work. Your promptness, thoroughness, and
                sense of humor are what make it fun to compete.



=================================================================

======================================= alphaCross =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
        alphaCross   170   202   640  678.19  C++  Glenn Bradford
=================
alphaCross was submitted by Glenn Bradford at jupiter!gmb@ffast.ffast.att.com
=================

++ WHERE DID alphaCross begin?

In a corner. At first I tried centering the first two crossed words in the
middle of the grid, but I found that the final solns had holes in the hard
to get corners. So I figured to start in one corner, and at least nail one
of them. It seemed to give better scores.

++ HOW DID alphaCross try to maximize 

When presented with a letter on the board that I wanted to cross with a word,
I searched through all the available words with that letter and for those
that fit, I scored each on how many intersections they made. The word making
the most intersections won the spot.

I didn't do a great job maximizing words. For example, I didn't attempt to
fit smaller words first. I experimented with this but it tended to choke
the solution. A smarter way, perhaps, judging from the finals lists, would
have been to "prefer" smaller words, or at least stay away from the longest
ones, but I didn't do this. I had "wissenschaftliches" in the german soln!
My results were near the top in letters used, for this reason.

++ Did alphaCross iterate?  randomize?  attempt to improve it's first solution?

I put every word in a corner and crossed it with every other word that
would fit it in the corner square. I did this for all four corners. Then I
recursively, in a depth first manner, placed words in a long string,
alternating between crosswise and downward words until no more words could
fit. Words running in the same direction were always separated by at least
one blank square, which I called 'the non-packed scheme'. I scored the grid
and saved the best running soln.

++ How did alphaCross know it was done?

When it had tried all solns starting with every pair of words connected in all
four corners.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

Advice: Don't participate in a POTM if you know you are going to have a
baby anytime before the deadline.

One trick I used was to denote '#' as a black square (like on a real
crossword puzzle) internally.

At some point I decided to try to place words side-by-side, like in a real
crossword puzzle. I strongly suspected that Fred would choose a real
crossword puzzle soln. for the finals (which he didn't!), and while I didn't
imagine my program could recreate it all, I was going to try to recreate part
of it. So I abandoned the "corner" method above and tried a two phase attack.
First, start the grid with a partial soln. with about 10-20 words packed closely
together, with as many intersections as possible. Second, use the standard
non-packed algorithm to finish the puzzle. Packing was hard, but on the night
of the deadline, I thought I had it mostly working. The system test file made
it dump core, though, and I wasted most of the night trying to
debug it, to no avail. For other test files I made up, it worked OK. I took a
chance. I was extremely tired. I mailed Fred a version that had no output.
I had commented out the print routine by mistake just before I mailed it!
He was nice enough to use my last version, which is just as well.

When I got the finals lists the next day, I ran my packed version program
and got slightly better results, but the german list, with all its long
words, could not be packed well and my program ran for a long time, over
an hour, trying to pack it. I didn't have time to put in an alarm to tell
my program its time was up.

As an example of packing, here is the output from the packing phase on
the worldnet list:
--------------------
--------------------
--------------------
--------------------
--------------------
------s-------------
------e----s--------
------r----e--------
------v--p-l--------
------i-truly-------
------choose--------
------e--very-------
------s--i-security-
---------d--top-----
---------e---n------
---------r---n------
---------s---e------
-------------c------
-------------t------
--------------------
number of words = 13  number of conns = 20  number of letrs = 47

And the final solution after the second phase:
-p--bringing-with-s-
-how-------o-a----i-
-o-information--p-n-
-n-loo-----n-through
-e-l-r-using--i-r-l-
--r-b-s-a---together
-we-o-e-m--s--h-a---
--att-r-e-key--bbn-f
its-have-p-l----l--i
n-o---i-truly-them-n
t-n---choose-----and
risks-e--very----t--
o---easy-i-security-
d-a-e--o-d--top--e-t
u-c-k-buyers-n-worth
c-c-e-a--r---n-e---e
their-close-set--way
i-s-s-k-u----c-n-h--
o-s-----traditional-
n----------o--t--t--
number of words = 63  number of conns = 75  number of letrs = 223

It did only 2 words better than my totally unpacked soln.

++ COMPANY? Lucent
LOCATION? Red Hill
JOB? Software Developer, TDIL Operations System
DO FOR FUN? tennis, racquetball, woodworking
INNERMOST SECRET? fib to my wife so I can work on POTM
POTM IDEAS? some kind of packing problem?

=================================================================

======================================= WordMatrix =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
        WordMatrix   170   173   578 1794.57    C  Annemarie Kram
=================
WordMatrix was submitted by Annemarie Kram at akram@xs4all.nl
=================
++ WHERE DID WordMatrix begin 

Shortest word, with most used letters, every possible place. Why not?

++ HOW DID WordMatrix try to maximize 

Not

++ Did WordMatrix iterate?  randomize? 

generate all.

++ How did WordMatrix know it was done?

All solutions tested or time.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
None, Delft, Nurse, Yes, Just Guess, {Integer arithmetic, knapsack, 
	balistics, go, 4-in-a-row, nesting)




=================================================================

======================================= nonplussed =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
        nonplussed   168   175   532   71.44    C  Greg Marston

	Sorry ... no description available for nonplussed

=================================================================

======================================= Crozzilla =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
         Crozzilla   167   182   557  112.34  C++  James Rothenberger

	Sorry ... no description available for Crozzilla

=================================================================

======================================= mash =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
              mash   163   170   597 1651.39    C  Dave Lynch
=================
mash was submitted by Dave Lynch at dfl@esun.att.com
=================
++ WHERE DID mash begin - short words, complex meshes, corners, etc.??? Why?

Started with a randomly sorted list of words greater than 2 letters,
using only alternate rows and columns.  First word was placed randomly.
When there were no more opportunities, I also considered the 2-letter
words and all rows and columns.

++ HOW DID mash try to maximize the number of words and intersections used?

Brute force and repeated trials.

++ Did mash iterate?  randomize?  attempt to improve it's first solution?

Made repeated attempts with different list orderings and different
starting points, keeping the best solution.  Wanted to implement a
local search improvement scheme, but had to attend to other areas
of my life.

++ How did mash know it was done?

Out of time.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?

Last I heard, I'm in AT&T in Holmdel.

POTM IDEAS?
How to keep upper management from laying off, outsourcing, etc., so
many people.

=================================================================

======================================= santacroz =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
         santacroz   156   172   611   12.79    C  Ag Primatic

	Sorry ... no description available for santacroz

=================================================================

======================================= CrossEyed =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
         CrossEyed   147   151   606 1232.29  GCC  Randy Saint
=================
CrossEyed was submitted by Randy Saint at saint@phoenix.phoenix.net
=================
++ WHERE DID CrossEyed begin

First started with a sorted list based with most number of "popular" letters
	first.  Then tried random lists.

++ HOW DID CrossEyed try to maximize

Words were tried from the list, if they fit they were put on the board and
move on to the next word.

++ Did CrossEyed iterate?  randomize?  

Tried recursion, but it was too time consuming for little gain.  Used random 
beginning lists and stopped once it could not put any more words from the list
on the board.

++ How did CrossEyed know it was done?

Used a fixed number of random lists and tried starting with each.  Saved best 
solution.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

I submitted early with plans for improvements... I was glad I did.  I got too 
busy with other things and didn't get back to it.

++     COMPANY?  Loral
       LOCATION? Houston, TX
       JOB?    Systems Analyst
       DO FOR FUN?  Sling Code
       INNERMOST SECRET?  My boss thinks I use the internet to do
				"market research"
       POTM IDEAS?  I like the extra "awards" that are presented! Keep it up!
---
Randy & Marianne Saint
Houston, TX
saint@phoenix.phoenix.net
http://www.phoenix.net/~saint

=================================================================

======================================= lacrosse =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
          lacrosse   145   150   417 1795.53    C  Mark Schnitzius

	Sorry ... no description available for lacrosse

=================================================================

======================================= RedCrozzleDevils =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
  RedCrozzleDevils   144   144   483 1614.49  G++  Peter Conrad
=================
RedCrozzleDevils was submitted by Peter Conrad at conrad@unix-ag.uni-kl.de
=================
++ WHERE DID RedCrozzleDevils begin 

We use a function depending on the length of the word and the letters in
each word to determine the 'quality' of a word. Letters that appeared more
often in the wordlist were 'better' letters, words of (I think) 5 letters
have 'best' length. We choose one of the 'best' words in the list and place
it in the middle of our grid. Then we try to add more words in any
direction until the maximum size of the grid is reached.

++ HOW DID RedCrozzleDevils try to maximize 

After each step we try to place each of the remaining word in each place
of the grid. Every combination of the word/grid-position is assigned a
value depending on the 'quality' of the word and the number of intersections
caused by the word. We then choose one of the 'best' of these combinations.

++ Did RedCrozzleDevils iterate?  randomize?  

We use a non-deterministic approach. In each step we choose (more or less)
randomly a word to place, until no more words can be placed. So we find
a solution pretty quickly. We remember the best solution, and after
nearly ten minutes of computing time the best solution so far is printed
to stdout. So with a bit of luck we *could* have won... ;-)

++ How did RedCrozzleDevils know it was done?

See above, after a predetermined amount of time.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

*We* are a team, consisting of Nils Magnus, magnus@unix-ag.uni-kl.de, and
myself, conrad@unix-ag.uni-kl.de. Since we were both pretty busy during
the last months, our entry to this contest was more of the 'quick hack'
type. This may change in the future... :-)

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

We're both students of CS at the Universitaet Kaiserslautern, Germany.
We've taken part in several other contests in the past, and we've always
had a lot of fun.

=================================================================

======================================= CUTE =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
              CUTE   143   144   566 1611.11    C  Corin Anderson
=================
CUTE was submitted by Corin Anderson at corin@cs.washington.edu
=================
++ WHERE DID CUTE begin - short words, complex meshes, corners, etc.??? Why?

CUTE (Crossword Utilization Transmogrifying Engine) begins with some word
at random dropped into the center of the board. From there, random words
were chosen and attempted to be placed at random positions.  Legal moves
were kept and illegal moves were discarded. 

I chose this strategy because it seemed like the easiest to program.  I
didn't have to perform any analysis of the input words and pay close
attention to how the board was being filled in.  I betted that fast and
furious would be just as effective as slow and sure.  Unfortunately, CUTE
failed on the fast part (lots of simple strcpy()s), so I couldn't try a
whole lot of possible word combinations. 

++ HOW DID CUTE try to maximize the number of words and intersections used?

CUTE really didn't pay attention to the number of words and intersections 
explicitly.  The basic algorithm was random sampling of the solution 
space and choosing the highest score.  Because the scoring function 
weighted more words higher than more intersections, CUTE followed these 
basic rules.

++ Did CUTE iterate?  randomize?  attempt to improve it's first solution?

As hinted as earlier, CUTE would fill in a board as much as possible and 
compare its score to a known current best score.  If the current board's 
score exceeded the best score, CUTE replaced the best score (and its 
board) with the current.  Each board examined was generated by randomly 
selecting words and positions, as described earlier.  Each board was 
generated independently of previous boards.

++ How did CUTE know it was done?

CUTE had a little wrist watch that it checked frequently.  Once about 5 
and a half minutes elapsed, CUTE settled with the best-known-good board 
and quit.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

I'm presently an undergraduate at the University of Washington, and will
be a graduate student this fall here.  I take part in the POTM contest
because I really like doing programming contests and showing off my C 
skills.  Besides, it's a lot of fun!

=================================================================

======================================= SundayTimes =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
       SundayTimes   136   140   491   41.17  C++  Joe Eccles

=================
SundayTimes was submitted by Joe Eccles at mink!joe@ffast.ffast.att.com
=================
++ WHERE DID SundayTimes begin 

Started with longest words first. Just by experimentation, this usually
fared better then starting with long words first.

++ HOW DID SundayTimes try to maximize 

The version entered simply started trying to add words, shortest first, then
repeat the list until a traversal failed to add any new words to the board.
The first word was added to the center of a 40x40 board, and as any word was
added, the size of the board was shrunk to ensure that any new words added would
be within a 20x20 sub-board. This eliminated the decision of where on the board
the first word would go.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

AT&T, Middletown NJ

=================================================================

======================================= krozz-it =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
          krozz-it   132   138   400 1166.40    C  Jan Venema

	Sorry ... no description available for krozz-it

=================================================================

======================================= Cross-Stitch =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
      Cross-Stitch   129   188   427 1023.72    C  Alex Popiel
++ WHERE DID Cross-Stitch begin 

Cross-Stitch began by sorting the input words by length, and then building
huge tables of (a) lengths, (b) letter occurences, (c) two-letter combination
occurences, and (d) known impossible word adjacencies.  (The last table
there is a table of all words by all words by all offsets such that if
the first word may be laid parallel immediately above/left the second
word at the designated offset and still yield a legal grid, the table contains
a true value.)

After the tables are built, Cross-Stitch picks a word at random, placing
it in the center of an oversized grid (the grid is oversized and floating
boundaries are maintained so that there is no confusion about shifting
everything to the left one square or some such nonsense).  A second word
is picked, and laid below the first word.  Crossing words are chosen for
all places where two letters are adjacent, via depth first recursive
search until a legal grid is formed.  This legal grid is placed in a
priority queue of partial solutions, and the process is repeated a few
hundred times.

The top few entries of the priority queue are then improved upon, through
attempts to add words parallel to existing words (followed by cross-filling),
or words inserted perpendicular to existing words (again followed by cross-
filling).  The new solutions (which always have more words than the original)
are inserted into the priority queue.  If a solution cannot be improved,
it is compared to the best solution to date, possibly replacing it.
This process of incremental improvement is repeated until a magic number
of unimprovables have been encountered, at which time the entire queue
is deemed "stale" and wiped.  New grids are then generated as described
in the preceeding paragraph.

Cross-Stitch continues this cycle of iterative improvement until it
runs out of time, after which it prints out the best it has.

++ HOW DID Cross-Stitch try to maximize 

Cross-Stitch miximized wordcount by heavy emphasis on complex meshes.
unforunately, I was unable to come up with an intelligent way of building
good meshes, so I relied on random chance.  This yielded decent solutions,
but not great ones.

++ Did Cross-Stitch iterate?  randomize?  

All of the above, at different levels.  It iterated through the improvement
cycle, which used randomization internally.

++ How did Cross-Stitch know it was done?

It knew any particular grid was done by being unable to add words to it.
It knew the run was done when time ran out.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

Cross-Stitch was an exploration into many ideas that did not work.
My first implementation used a fixed 20x20 grid to build stuff in;
this proved to be overly arbitrary, denying certain avenues of expansion
because all the free space was divided on opposite edges instead of being
on one side or other.  I tried a number of "intelligent" improvers, all
of which took too much time for results.  At one point, I was spending
over three minutes of runtime generating the (d) table (yielding more
early cutoffs in the improvers), but it turned out that the time was
better spent trying combinations.

Data structures were also very important; changing the storage methods
for various information yielded 20:1 speed improvements on a couple
occasions.

One of the traps I fell into was duplicate code.  Nearly all my improver
code is duplicated for each of horizontal and vertical alignments.  This
became a problem as I neared the 25K source limit.  The one benefit is
that the loops are optimized for each of the alignments, sometimes iterating
in row-major order, and sometimes in column-major.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

Company?  Please.  Location?  Initial meetings in public places.  Job?
He was persecuted by Yahweh.  Do for fun?  Sure.  Innermost secret?
Not here.  POTM ideas?  Gibberish generators.
=================================================================

======================================= manhattan =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
         manhattan   126   136   413 1141.31  GCC  Michael Strauch
=================
manhattan submitted by Michael Strauch at strauch.bbs@sx1.hrz.uni-dortmund.de
=================
++ WHERE DID manhattan begin 

Manhattan starts in the middle of the grid, inserting the first word from
the list with six characters (or less, if there is no such word). The idea
was to start with a short word (leaving much space for other words), but not
too short (to prevent being stuck at the beginning).

++ HOW DID manhattan try to maximize 

Manhattan does only try to maximize the number of words, it does not care
for the number of intersections.

++ Did manhattan iterate?  randomize?  attempt to improve it's first solution?

Manhattan uses two different strategies, one completely deterministic and
one random strategy.

(A) Remove one word from the current grid, make a depth search trying to
    insert at least two words (so you get at least one word more than before).
    If no such two words are found, reinsert the removed word, and repeat
    the same with the next word from the current grid.

(B) Remove up to 8 words randomly from the grid, then try to fill as many words
    as possible from the list of remaining words, starting with a randomly
    choosen one. Accept the resulting grid if it contains at least as many
    words as before, with a possible loss of up to four words. Do not accept
    the grid if the words in the resulting grid are not connected.
    
These two strategies are applied as follows:

(1) strategy A is used as long as the depth search works (increasing the number
    of words by one in each step)

(2) when (A) fails, strategy B is used up to ten times; do not apply strategy
    (B) any more if more words could be inserted than in step (1)

(3) if enough time is left, go to step (1)
    
One problem "Manhattan" had to deal with was: when is it allowed to insert
one word near to another word (so you need other words crossing the first
two ones)? So if this case occurs, manhattan makes a complete depth search 
to find out if there are enough other words in the list to fill the cross
points. This is the slowest part of the whole program, but I had no good
idea how to improve this.

++ How did manhattan know it was done?

Manhattan stops if the time is up. I should have better checked the time
more frequently. (sigh)

=================================================================

======================================= CrozzApp =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
          CrozzApp   120   128   381  552.08 JAVA  James Rothenberger
=================
CrozzApp was submitted by James Rothenberger at jar@rdga3.att.com
=================
++ WHERE DID CrozzApp begin 

In the center, just a best guess.  I didn't have time to try multiple solutions
for the first placement.

++ HOW DID CrozzApp try to maximize the number of words and intersections used?

I created many placement algorithms (27), ran all, kept track of the results
and spit out the best one as the answer. These algorithms included placement
towards edges, placement towards middle, probability of placement by letter
content, length, collisions with other words, gravity towards center of puzzle,
among others.

++ Did CrozzApp iterate?  randomize?  attempt to improve it's first solution?

It was more of a recursion than an iteration.  There was nothing random
about it.  It did not try to improve on a solution, just try a different
approach (certainly not the optimal solution).

++ How did CrozzApp know it was done?

It was done when it tried all possible strategies.  Completion time was not
an issue in the C++ program (ran in less than a minute).  JAVA program took
SUBSTANTIALLY longer to run, but I took a chance that it would finish in the
allotted time (no built-in timer).

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

This was great fun, hope to participate again!!

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

Software Developer
Lucent Technologies (Formerly AT&T)
Reading, PA

Do for fun?  Check my homepage!
Inside Lucent, AT&T - http://rdga3.att.com/~jar
Outside             - http://www.clever.net/bitwise/jar

=================================================================

======================================= WizardOfCrozz =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
     WizardOfCrozz   119   135   645  905.76  GCC  Chris Hendrie
=================
WizardOfCrozz was submitted by Chris Hendrie at cihendri@uwaterloo.ca
=================
++ WHERE DID WizardOfCrozz begin 

WizardOfCrozz employs a simple brute-force strategy, trying to use big
words with frequently-occuring letters first. It assembles a puzzle one
word at a time, depth first. (best I could do in the 8 hours before the
deadline...)

++ HOW DID WizardOfCrozz try to maximize 

See above.

++ Did WizardOfCrozz iterate?  randomize?  attempt to improve

It uses randomization to select which site to attempt to connect to next.
This improves things a bit.

++ How did WizardOfCrozz know it was done?

It keeps recursing, trying every possible 'simple' crossword puzzle, until
it runs out of time. Unfortunately, it doesn't seem to accomplish much
after the first 10 seconds or so.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

Next time I'm using C++ instead of C. Relentless optimization was the wrong
track: I would have been better off writing cleaner code and perfecting my
algorithm.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

I'm a second year Computer Science student at the University of Waterloo. I
am currently looking for a summer job. Fun? With final exams around the
corner?

Christopher Hendrie * Shad Valley 93A * IMO 94 * UW Comp.Sci 98
ACM ICPC 96 * http://www.undergrad.math.uwaterloo.ca/~cihendri/


=================================================================

======================================= mots =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
              mots   114   115   394   18.30    C  Ralph Meira

=================
mots was submitted by Ralph Meira at ralph.meira@sophia.attgis.com
=================
++ WHERE DID mots begin 

Mid-sized words (5 letters), then 4 & 6, then 7 & 3, .... and so on.
I used the concept of work area: words would be linked, and each time round, 
my program would calculate the potential work-area around the existing 
words:

e.g.: for a 3x3 Matrix with word "You" already in there.

 - - -
 - - -
 Y O U
 - - -
 - - -

++ HOW DID mots try to maximize the number of words and intersections used?

Mots did a histogram of letters used and then weighed the existing words 
sorting them first by size (as previously mentioned) and
then by the letter-weighting.

++ Did mots iterate?  randomize?  attempt to improve it's first solution?

Mots skipped words it could not fit in, but iterated back
once on those same words - just in case.

++ How did mots know it was done?

Once the program had executed the steps necessary ... that was it.
I just wanted to have an POTM-entry out there, and I was happy
to have one that did a reasonable job in less than 1 second
(at least on my machine).

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

It's been 2.5 years since I last did something in C,
so it was great fun !

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

NCR CORPORATION (formerly AT&T GIS)
SOPHIA-ANTIPOLIS
SOUTH OF FRANCE

FINANCIALS AND ORDER SYSTEMS SUPPORT
FOR EUROPE, MIDDLE EAST, AFRICA REGION.

I'M GETTING ALL MY TEAM TO ENTER THE NEXT POTM.
PLUS A FEW PEOPLE I KNOW AROUND THE GLOBE.

=================================================================

======================================= Crozzlometry =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
      Crozzlometry   108   113   532  387.82    C  Brace Stout

	Sorry ... no description available for Crozzlometry

=================================================================

======================================= Bhagvan =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
           Bhagvan   101   113   431 1204.23  G++  Bhagvan Konmadi
=================
Bhagvan was submitted by Bhagvan Konmadi at gt4501c@prism.gatech.edu
=================
++ WHERE DID Bhagvan begin 

Started off with long word , thought will get more connections,hence
more words.

++ HOW DID Bhagvan try to maximize 

try with a next long word.

++ Did Bhagvan iterate?  randomize?  attempt to improve it's first solution?

yes, iterate till you get maximum words

++ How did Bhagvan know it was done?

just a guess.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

bad guess , hence the result

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

Research Assistant,Georgia Tech,Industrial systems engineering
          do for fun.



=================================================================

======================================= crozzlectomy =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
      crozzlectomy    50    47   171 1781.69  KSH  =Fred Hicinbothem
=================
crozzlectomy was submitted by Fred Hicinbothem at fah@ffast.ffast.att.com
=================
++ WHERE DID crozzlectomy begin
upper left going across, then took the third letter and worked down, then took
the third letter and worked across, etc., etc. ... guarantees no conflicts
that way but makes for a real low score.

++ HOW DID crozzlectomy try to maximize 

It was tough enough just getting ANYTHING to work within the time constraints
when using a shell language (at least for ME!)

++ Did crozzlectomy iterate?  randomize? 
Ha!  The code WAS recursive though ... recursive shell functions ... imagine! 

++ How did crozzlectomy know it was done?
It was done when it reached the lower right hand corner or fell off the board!

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
Learn to program - giving up your day job helps as well ...

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?
AT&T (honest) in West Long Branch New Jersey USA ... I do software architecture
and requirements and proposals and stuff like that for a living, so the POTM
offers the opportunity to communicate with REAL programmers.
=================================================================

======================================= Croissant =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
         Croissant    26    23   164    0.45  C++  David Peterson
=================
Croissant was submitted by David Peterson at dpeterso@isd.net
=================
++ WHERE DID Croissant begin 

Center.  Allowed the greatest number of possible connections from the
highest scoring word alternating up and down.

++ HOW DID Croissant try to maximize the number of words and intersections used?

Used the letter frequency and letter count to sort the words.

++ Did Croissant iterate?  randomize? 

It did not.

++ How did Croissant know it was done?

It was done with the center word.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

C-Applied Systems, Inc.
L-Bloomington, MN
J-Senior Systems Analyst
D-Surf the Web
I-Hate Windows programming
P-Random walk through Dinky Town or Traveling Tony's Shortest Journey

=================================================================

======================================= Just_Becroz =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
       Just_Becroz     6     3    35    0.33    C  Scott Everett
=================
Just_Becroz was submitted by Scott Everett at severett@intgp1.att.com
=================
++ WHERE DID Just_Becroz begin 

The program created a sorted list of words. It placed the words 
sharing common letters with other words higher on the sorted list. 
This way, a word like "zzzz" would not be examined over a word like 
"the". Within this sort, words of equal value that were
shorter were placed above longer words.

++ HOW DID Just_Becroz try to maximize 

Insufficient time to work on the program due to job requirements.

++ Did Just_Becroz iterate?  randomize?  

See above

++ How did Just_Becroz know it was done?

It was planned to monitor time and end before time was up. Then it would
print best solution found.

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

The program knew that if a word was placed horizontally in the 3rd 
through 5th columns that only those columns should be examined for 
potential placement of vertical words. Thus, the entire puzzle did 
not have to be searched after each move.  Further, a look ahead of 
only one move was programmed and I was going to implement back-up moves.

In order to keep track of moves I kept a move list showing all moves 
made so that the moves could be popped off the stack if a dead end 
was reached. Before backing up from a dead end I save the current score 
of the puzzle and what it looked like.  That way, the most optimal solution 
is always known up to that point. If time would run out then I compare 
saved solution to current puzzle and print the one with the highest score.

Unfortunately, this last piece of the puzzle was never finished due 
to work load.

++ COMPANY?  LOCATION?  JOB?  DO FOR FUN?  INNERMOST SECRET?  POTM IDEAS?

Lucent Technologies. Indian Hill (Illinois). GlobeView ATM Development.
Ski, Water Ski, Tennis, Wind Surf, Read, ...
Love POTM puzzles

Develop programs that fight other programs (like two programs that take turns
making tic-tac-toe moves). The competition would take place on a 
tournament ladder system until a winner was found. It would not be 
tic-tac-toe, since too easy to deadlock and everyone knows how to do 
that one. Design a different type of competition.
=================================================================

======================================= one =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
               one     3     0    13    0.27  C++  Ionel Vasilescu

	Sorry ... no description available for one

=================================================================

======================================= hongtao =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
           hongtao     0     0     0    0.00  C++  Hongtao Gu

	Sorry ... no description available for hongtao

=================================================================

======================================= xid =============

=================================================================
             ENTRY  WORDS CONNS LETTR Seconds LANG  Programmer
               xid     0     0     0    0.00    C  Ken Weinert
=================
xid was submitted by Ken Weinert at kenw@ihs.com
=================
++ WHERE DID xid begin - short words, complex meshes, corners, etc.??? Why?
++ HOW DID xid try to maximize the number of words and intersections used?

     The intent was to start in the middle with the two longest words
and work my way down the list.

++ Did xid iterate?  randomize?  attempt to improve it's first solution?

     iterate over the sorted list, longest to shortest.

++ How did xid know it was done?

     no new "transactions"

++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?

     if I didn't have a real job or three, xid would have gone beyond
	the concept phase.

=================================================================












Make your own free website on Tripod.com