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.
=================================================================