Entry Summaries
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).
BOGGLE INVERSE Program entry descriptions
Even if you don't study the whole thing, you might
want to check out the first four or five writeups!
If you need even more detail - contact the authors - not ME!!!
=Fred
============== 1 ====================== SnakePit =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
SnakePit 352 81 c Tim Ruhl 601.35
=================
SnakePit submitted by Tim Ruhl at tim@cs.vu.nl
=================
++ Please summarize the algorithm used by SnakePit
Image a pit full with snakes doing the things that causes new
snakes.... That's basically the algorithm that I've used. The program
has two major components: an efficient evaluation function and a
genetic algorithm. The evaluation function computes the score of a
given solution. Every possible letter sequence (i.e, snake, so to
speak) in a solution is tried, as long as the letter sequence is a
prefix of any of the words given in the input. For efficiency, a word
prefix table is computed in advance that tells whether a given string
is such a prefix. Whenever a complete word is found, the score for
that solution is updated.
The genetic algorithm maintains a set of 300 solutions. In each
iteration, a new set of 300 solutions is generated. A new solution is
generated by selecting two old solutions, and copy each letter from
one of these two old solutions (selected randomly). The algorithm that
picks the two solutions uses the score of all current solutions to
make a weighted random selection, so it prefers better solutions, but
does not exclude bad ones. Also, sometimes it tries to place a new
word in the solution. However, no check is made whether this new word
overwrites its own letters.
To stop the program, I installed a signal handler that catches
SIGALRM, and set an alarm to go off after 590 seconds.
++ If I had it to do all over - here's what I would try ....
I would have liked to change the algorithm that places a random word
in the solution. Randomly placing a 25 letter word on a 5x5 board such
that the letters connect and do not overwrite each other, however, is
not as trivial as it first seemed.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I am a PhD student at the Vrije Universiteit Amsterdam, and I'm
currently writing my dissertation.
=================================================================
============== 2 ====================== Shake_Rattle_Roll =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Shake_Rattle_Roll 333 78 c Hal Burch 636.70
=================
Shake_Rattle_Roll submitted by Hal Burch at hburch@cs.cmu.edu
=================
++ Please summarize the algorithm used by Shake_Rattle_Roll
To start, try to pack words together. Do this greedily, choosing
the longest word that adds the most number of letters. Because of
time constraints, only search for the absolute best layout for short
words. Once this no longer gives any new letters, fill in the rest,
trying to maximize the pairings and triplets that are created with
respect to the word list.
From this starting board, make alterations to improve the board.
Basically, allow any one character change, and a subset of the
two character changes. If none of these work, try a couple random
three point charges (with the letter frequency based on the original
word list).
Once none of these give a better board, with a random chance related
to how good this board is compared to the best I've found thus far,
shake up the board a little bit and restart the process.
++ Did you iterate the process? randomize? keep track of time?
I iterated the above process until I ran out of time (well, close to
it). The "seed word" (the first word to be laid down) was selected
randomly, giving a wide variaty of choices.
++ If I had it to do all over - here's what I would try ....
Coming up with the original layout is a bit of a hack. It should
really be improved. In addition, swaps seem to be a fairly common
helpful thing to do, but I couldn't get it done in such a way that
it seemed to help.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a first year computer science graduate student at Carnegie Mellon
University.
=================================================================
============== 3 ====================== bogged_down =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
bogged_down 325 72 C Martin Weiss 583.49
=================
bogged_down submitted by Martin Weiss at mcw@pacbell.net
=================
++ Please summarize the algorithm used by bogged_down
Rather than try to actually fold words into the grid I did
an iterative process starting with a random grid:
- randomly place letters in a 5x5 grid
- iterate until no more improvements are possible as follows:
- for all possible neighboring squares, swap the neighbors
that would result in the best score
- for all possible squares and all possible letters change
the square/letter comination that results in the best score
- continue until there is 10 seconds left
- the iteration process requires an enormous amout of grid scoring
which I speed up by placing all words (and word fragments) in
a hash for quick lookup - the scoring algorithm is designed to
score not only full words but fragments of words as well
++ Did you iterate the process? randomize? keep track of time?
- I use an iterative process
- Randomization is only used to start off a grid, I don't use
randomization to choose possible words ... too hit and miss
- I only look at real time ... I could of looked at sys+user time
but I wasn't really interested in getting the best score ... I
just wanted to see if my iterative strategy had any merit.
++ If I had it to do all over - here's what I would try ....
- I didn't get to spend much time on this ... maybe 2/3 of a day.
If I had more time I would:
- prune words from the list that contained rare (and potentially
square-wasting letters)
- use sys+user timing
- preset some center squares and only iterate the perimter squares
- bribe Fred Hicinbothem to get the word list ahead of time !!!
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM
IDEAS?
- I am a consultant currently working at JavaSoft (Sun Microsystems)
in Cupertino, CA
- I am a Software Engineer (what a surprise)
- Internet Chess, Orienteering and POTM eat up my nonexistent
free time
- I am way too boring to have innermost secrets
- POTM idea:
- Write a program to transfer Bill Gate's stock to my account!
=================================================================
============== 4 ====================== Intelligent_Brute_Force =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Intelligent_Brute_Force 299 71 gc Dan Gehlhaar 595.50
=================
Intelligent_Brute_Force submitted by Dan Gehlhaar at gehlhaar@agouron.com
=================
++ Please summarize the algorithm used by Intelligent_Brute_Force
There are three components to my solution:
1) Intelligent detection of word associations
2) Stochastic generation of a "decent" solution
3) Stochastic optimization of that solution
(1) Word associations are determined by finding the best alignment
between a word and all words of that length or less. The best
alignment is defined by that one which has the most letters
overlapping. If the difference between the word length of the
shorter word and the best score is less than a given cutoff
(I used three), the shorter word is considered a "child" of the
longer word.
(2) My generation algorithm is quite straightforward. I randomize the
word order of the dictionary. Taking words one at a time, I attempt
to place it into the square, using all possible starting places.
The placement algorithm is a recursive one with lookahead, with
preference being given to placements that use existing letters in
the square. If a word is able to be placed, I choose the starting
place that minimizes the usage of new spaces.
If the word that was successfully placed has any children, I attempt
to place them immediately thereafter.
(3) The optimization function is based on ideas given to me by Neal
Palmer, who will probably *still* out-score me despite my best
efforts. I take the current best solution, randomly blank out
one to five places on the board, and try to re-place the dictionary.
Believe it or not it works. Rather well, I might add. I didn't
think of it myself because it was too simple.
++ Did you iterate the process? randomize? keep track of time?
I generate a gahungus (<-- that's a technical term for "large") number of
possible solutions. The initial discovery phase is set to twenty seconds.
The optimization phase is set to end when there hasn't been any further
improvement for 25 seconds. After that, I start over. I average 10-12
rounds in 10 minutes, which says that most of my optimization happens
early in the game. A typical run with the sample dictionary evaluates
several tens of thousands of possible solutions per round (on my computer,
at least).
In order to assure as much coverage of the search space as possible, I
randomize basically everything:
- The order of the words in the dictionary (for each solution)
- The direction order in the recursive search
- Which equi-scoring placement to keep for a given word
- How many blank spaces to insert during optimization
- Which spaces to blank out
I also profiled the bajeezus out of my solution, so that I could sample
as much of the space as possible.
++ If I had it to do all over - here's what I would try ....
A few things:
- More intelligent ordering of the words before trying to place them.
In particular, try to stay away from words with many instances of
the same letter.
- A more deterministic optimization. Unfortunately, although it's
straightforward to try all of the one- and two-point blanking (a
total of 325 possibilities), the three-, four-, and five-point
optimizations have a tremendously huge number of possibilities.
I didn't try to spend the time to find the best balance.
++ COMPANY?
Agouron Pharmaceuticals, Inc.
LOCATION?
San Diego, CA
JOB?
Methods development for computational drug design
DO FOR FUN?
Karate, playing in the ocean, dance (no, I don't surf)
INNERMOST SECRET?
That I don't have enough of them.
POTM IDEAS?
=================================================================
============== 5 ====================== dawkins_dichotomy =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
dawkins_dichotomy 288 67 c John Williams 724.46
=================
dawkins_dichotomy submitted by John Williams at jwill@chromatic.com
=================
++ Please summarize the algorithm used by dawkins_dichotomy
The algorithm was pretty simple: Start off with a random configuration, then
one by one look for replacements that make improvements to the potential
score. Do this enough times, and you find one that is not so bad.
++ Did you iterate the process? randomize? keep track of time?
Yes, I iterate the basic algorithm many times, stopping when I run out
of time.
++ If I had it to do all over - here's what I would try ....
Possibly a simpler evaluation, less randomization, more lookahead. I
briefly entertained a heuristic based optimal solution with no randomization,
but I've been burned by the these approaches in the past on large
system tests.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Chromatic Research, Inc.
Sunnyvale, CA
MTS VLSI Design Verification
I like reading, playing bridge, playing guitar.
=================================================================
============== 6 ====================== HobBoglin =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
HobBoglin 287 63 JAVA Ted Alper 584.78
=================
HobBoglin submitted by Ted Alper at alper@turing.stanford.edu
=================
++ Please summarize the algorithm used by HobBoglin
nothing special -- it starts from the center of the board and works
its way out in a spiral. at each position it tries to find the letter
to maximize the number of words, or substrings of words (weighted
by length & how many words they are in) that are formed.
when its finished, it goes back and tries replacing letters
to see if later changes made initial guesses obsolete.
aside from some pathological cases, it will converge to a local maximum,
where any single letter can't be improved. but this is still not very good.
++ Did you iterate the process? randomize? keep track of time?
yes, iterate; no, randomize; yes keep track of time. But it's
messy to get the CPU time from within a java program (though I did
figure out a way to do it at least on one Linux machine --
entering this contest was really to motivate me to learn java), so
I wound up just using real clock time.
it didn't matter much on my machine, but of course it might on yours.
++ If I had it to do all over - here's what I would try ....
Lots of things -- I chose this method because I could see a way to
quickly implement it. I can think of other approaches that
might work better -- rather than assigning letters to positions,
one could assign positions to letters -- make a graph of
the most common letters and try to wedge it into a grid.
With a *little* more time, I might try to modify my weights
for substrings to make better choices -- or try to recognize which
words are blatantly incompatible with the letters I have already
placed and ignore their substrings in selecting remaining letters.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
EPGY, Education Program for Gifted Youth at Stanford University.
We produce and supervise computer-based courses in math and science
for talented pre-college students who are advanced beyond the courses
available to them at their own schools. Our students run our
software at their homes/schools, and we monitor
them via email/phone/conferencing software.
Fun: My son has had chicken pox the last few days, so there hasn't
been much time for fun, or anything else and I'm too tired to remember
if I ever did anything fun. I'm currently head coach of the
San Francisco Bay Area ARML team, a high school all-star math
team that competes in a national contest each spring (1996
national champions!).
Innermost secret: I loathe Halloween -- for the last 3 hours,
strangers have been knocking on our door, oblivious to the sign
about Chicken pox. My little son is frightened of all these
strangers and has been whimpering. We'd have to turn out all
the lights and hide to get them to stop.
=================================================================
============== 7 ====================== boondoggle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
boondoggle 281 68 C John Sichi 618.68
=================
boondoggle submitted by John Sichi at jsichi@broadbase.com
=================
++ Please summarize the algorithm used by boondoggle
boondoggle transforms the wordlist into a trie for fast searching and
then builds a simple Markov model for the frequencies of various
letters and their proximities to each other. This is used to generate
random boards which compete in a primitive genetic algorithm. Some
caching is done to avoid spending too much time computing conditional
probabilities.
++ Did you iterate the process? randomize? keep track of time?
Yes, yes, no. Keeping track of time would have been beneficial for
varying the genetic algorithm paramters (how many mutations, matings,
etc.) as the run proceeded, but I didn't get that far.
++ If I had it to do all over - here's what I would try ....
I would try to do a 3rd or 4th order Markov model, because going from 0
to 1 and 1 to 2 were both big improvements.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Same as last time.
=================================================================
============== 8 ====================== xyzzy =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
xyzzy 274 67 c Clark Kent 656.43
=================
xyzzy submitted by Clark Kent at fah@potm.ffast.att.com
=================
++ Please summarize the algorithm used by xyzzy
The input wordlist is analyzed to find the most common pairs and
most common triplets ... then this information is used to fill
in the center 9 positions in the following way:
_ _ _ _ _ This is how the four most common center
_ 0 a 1 _ letters in the top 20 triplets
_ d x b _ are used to seed the square.
_ 3 c 2 _ (0 is the most common, then 1, etc.)
_ _ _ _ _
Next I fill in the center spot (x) by looking for the letter that is
most often found between the four already inserted ...
Finally, fill in the a, b, c, d spots by examining which letters create
the most common pairs. Avoiding duplication of letters just for the
heck of it ... so NOW I've got the center 9 locked in ... next I
tackle the corner squares as follows: I forbid the use of the two
adjacent squares to a corner - and then try each of the 26 letters
in turn and save the one that would yield the largest potential score
if unfilled in squares were wildcards ... duplication is allowed!
(So the corners are picked based on beginning and ending letters.)
A _ _ B The corners are picked one at a
x x x _ time by tring all 26 letters and
_ x x x _ disallowing the use of the two
_ x x x _ adjacent postions. Evaluations are
C _ _ _ D based on scoring against the wordlist.
And finally, I try each of the 26 letters in the remaining spots and
save the one which results in the highest score against the wordlist.
++ Did you iterate the process? randomize? keep track of time?
No iteration except as above. no randomization. no timekeeping.
++ If I had it to do all over - here's what I would try ....
I'd copy the winning program and submit it myself ... I really wanna
win one of these things someday!!!
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T in West Long Branch New Jersey pays my salary for being a
development planner ... for fun I run the POTM ... oops, that was
my secret too ... =Fred
=================================================================
============== 9 ====================== Boggle_Brain =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Boggle_Brain 258 69 gC Dave Mathews 543.52
=================
Boggle_Brain submitted by Dave Mathews at dhm@rpa.net
=================
++ Please summarize the algorithm used by Boggle_Brain
At first, Boggle brain starts with an empty board and fills in one letter
position at a time. Positions are filled in with the optimal letter as
determined by a scoring routine. Once a position is filled, it is set.
Then, other passes, allow one letter to change at a time if it
improves the score.
++ Did you iterate the process? randomize? keep track of time?
The process is iterated. Not randomized. Time is not tracked.
++ If I had it to do all over - here's what I would try ....
If I had more computational try, I would write a genetic algorithm
to mutate the board to a more optimal configuration.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a graduate student in Chemistry at the University of Rochester.
=================================================================
============== 10 ====================== glegob =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
glegob 256 56 gC Kaj Telenar 570.53
glegob submitted by Kaj Telenar at kaj@turningpoint.com
=================
++ Please summarize the algorithm used by glegob
Make an initial board by randomly choosing letters that could go
next to the letter to the left. loop through each board location
and change that letter. Keep the better board and continue with the
loop. If any of the letters helped, do the loop again.
Do the whole process again until I run out of time.
++ Did you iterate the process? randomize? keep track of time?
++ History: Or, why is it so lame?
I've looked at a few of the potms in the past, but never sat down and
actually wrote one. Usually because I was too busy at work and didn't want
to be anywhere near a computer on the weekends. But this time I mentioned
the potm to a friend of mine while we were playing Robo-Rally (great
game!). Two days later I get an email from him saying he wrote it and it
got 45 using a genetic algorithm.
I started off by figuring I could simply look at how often pairs or triples
of letters showed up, make a few boards based on that information. i.e. put
letters next to each other that had more pairs. By itself this wasn't too
good. On the test list, my best results were in the high teens.
Based on my friends two minute explanation of genetic algorithms, I threw
one together. The resulting boards weren't that great.
When I kept the best 200 of 400 boards, it got quite a bit better, but
still only in the low thirties.
So I went out on the net to learn about genetic algorithms, and wrote
another version where I tried mutating a random square. I kept the best out
of the original and the mutant. This was very promising! My score was in
the forties. Starting with random squares didn't work as well as starting
with my "pairs" boards.
The literature said that allowing a mutant to stick around could end up
with a better result after a while, but that seemed to require sorting the
whole list and it was more effective to simply try a few more combinations.
Sticking with the mutation concept, I designed a tree where each node has
26 children, one for each letter in the alphabet. I assumed there would be
too much overhead if I stored the path of every mutation, so I changed the
algorithm to check every single cell mutation for each board. Then I took
the best mutation, stored that path and tried all mutation of it.
This gave acceptable results, and they seemed slightly better than the
previous version. Getting tired of trying all these different algorithms, I
finally settled down to optimizing the app.
Instead of reading the whole file of words every time I checked a board, I
read the whole thing into an internal buffer. That made no difference. And
I suddenly realized that this version was horrendous with large files. So I
used the same 26-way tree to store all the words. This was much better! Now
the 1000 word file was only 5 times slower than the 50 word file, instead
of 20 times slower.
I still wasn't happy with the algorithm, but I'd killed too much time
already, so I sent it in. :-)
++ If I had it to do all over - here's what I would try ....
1. I would try to figure out the speed differential between the POTM
machine and mine and only run it for the equivilant number of cycles...
2. I thought of an algorithm that would maximize the number of possible
word possibilities as I created the initial board and should make use of
every spot on the board. Unfortunately I couldn't figure out a good way of
storing the state information at various locations so I could iterate
through the possibilities at each step. I also got too busy again...
++ COMPANY? Turning Point Software
LOCATION? Boston area
JOB? Write shrink-wrapped Windows apps.
DO FOR FUN? Read, go to open houses, hike, host Babylon 5 parties, ski,
play board games.
INNERMOST SECRET? Don't you wish you knew!
=================================================================
============== 11 ====================== sue =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
sue 256 62 gC Ian Redfern 798.27
=================
sue submitted by Ian Redfern at RedfernI@logica.com
=================
++ Please summarize the algorithm used by sue
sue uses a fast non-recursive scoring algorithm. It keeps a list of its
five best scoring games, and each turn attempts to insert a random word
into each of them; it then keeps the best five. After the score of the
best of the five has stabilised for long enough, it starts again from
scratch.
++ Did you iterate the process? randomize? keep track of time?
Yes, yes and yes.
++ If I had it to do all over - here's what I would try ....
A more intelligent word inserter that was able to insert long words more
reliably. I gave up on breeding between games as the results were poor.
Making more use of letter pair frequencies - I tried it for random game
generation but it was too slow.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Logica, London, communications consultant, I spent 3 years doing a PhD
on algebraic group theory with state machines, so it seemed like a fun
challenge, null, null.
=================================================================
============== 12 ====================== Philantha_Boggle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Philantha_Boggle 252 61 c Benny Liaw 165.05
=================
Philantha_Boggle submitted by Benny Liaw at bennyl@texascom.co.id
=================
++ Please summarize the algorithm used by Philantha_Boggle
Philantha_Boggle use a heuristic algorithm. It is not a brute force
algorithm, nor backtracking algorithm.
At first, the system will scan the input file, and generate
a histogram table. For every word, it tally the occurence of
any sub-words found in the word. For example, for the word ABCD
it will increase the counter for A, B, C, D, AB, BC, CD, ABC, BCD, ABCD.
It will then determine a single letter to be put in the board, one at a
time, until the board is completely filled. The decision about which
letter to put and where it is placed, is calculated using a heuristic
function h(l,x,y).
I iterate through all the blank position (x,y), and iterate through all
letter (l) found in the histogram of one letter histogram, calculate the
score using for the heuristic function.
I will then choose the combination (l,x,y) with the highest score to be
placed in the board.
The heuristic function will the histogram table to calculate the score.
The system will generate all possible sub-word that can be found in the
board by placing (l,x,y), and sum the tallies (the number of occurence)
the sub-words to the score.
I use some parameters in the heuristic function so that the longer the
sub-word the higher the score will be, and if the sub-word is a full
word (the word in input file) the score will be higher.
In the second revision I changed the structure of the histogram table to
speed-up the process.
It was unsorted link list, and I changed it to be sorted, index by the
length of the sub-word and the first letter of the sub-word.
++ Did you iterate the process? randomize? keep track of time?
I use iteration to generate the result, but I do not try all of the
possibilities.
I do not randomize.
I do not keep track of the time.
++ If I had it to do all over - here's what I would try ....
If I had it to do all over I would try:
- to use a hash table store the histogram table to make the searching
faster.
- to use two level in heuristic function, so that it would give better
solution.
++ COMPANY? LOCATION?
I work in PT. Texascom Hitek System,
which is located in Jakarta, Indonesia.
JOB?
I am a Lotus Notes Consultant.
DO FOR FUN?
I like to explore new things, play guitar, listen music, watch movie,
browse the internet.
INNERMOST SECRET?
I don't think I will tell anyone :-p
=================================================================
============== 13 ====================== Boogie_Woogie_Boggle_Boy =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Boogie_Woogie_Boggle_Boy 231 56 gc Ken Bateman 151.24
=================
Boogie_Woogie_Boggle_Boy submitted by Ken Bateman at kbateman@esinet.net
=================
++ Please summarize the algorithm used by Boogie_Woogie_Boggle_Boy
Dirt simple. It is a basic greedy algorithm:
Start off with a random board. Score it. Make a few changes to the
board (swap two letters, change a letter). If the changed board has a
worse score than the previous board, then throw the new changes away.
Do this over and over again until the ten minutes are up.
There are a couple of enhancements, though. I use a different scoring
algorithm when the wordlist is large (state-machine based rather than
word-search based). The idea is basically the same.
Sometimes this algorithm does well, sometimes it stinks. It depends on
the random numbers coming from rand() that are used by the mutation
code.
I wrote a script to run my program repeatedly over a weekend, and the
best board was this one which scores 77:
HMTHW
ATEOP
TNSRV
KEDIF
SWLGN
SINGLE THAT PROVIDES THE FILE NAME WORDLIST LETTER AND LIST WORDS
PRESENT A KEWL POTM THANKS
++ Did you iterate the process? randomize? keep track of time?
It's just that mutate-and-score loop, bailing out after 10 minutes. Not
much to it.
The mutations are randomized.
++ If I had it to do all over - here's what I would try ....
For starters, I wouldn't put a canned initial board state in there. I
hope I didn't discourage anybody from improving their program. The
board scoring 77 was extraordinary, which was one of hundreds of results
I got on a weekend run. On my P133 I typically get scores of 45-55
after 10 minutes, and the POTM machine seems to be slower than mine.
It seems that an algorithm that starts from the wordlist and contrives a
good board should do better than my dumb greedy algorithm. If I were to
rewrite it, I probably would create a program that picks a reasonable
subset of the wordlist, makes a graph of the subset words with the nodes
being letters and the arcs between consecutive letters in the words,
then somehow fit the graph into a boggle board as best it can. This
could be done at least a few dozen times within the ten minutes.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a system test engineer for GE Fanuc Automation in Charlottesville, VA.
I really wish the POTM-master would start turning on the optimization
flags for the code. I don't understand why optimization is not used.
=================================================================
============== 14 ====================== Boggler =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Boggler 228 59 gC Keith Smith 591.60
=================
Boggler submitted by Keith Smith at fqhj@cyber-dyne.com
=================
Please excuse the attempt at grammar and spelling, I am rather
pressed for time and did definately want to respond to your
questionaire. Let me open with I enjoy the concept and the
way you are administering the POTM. Please Keep up the good work!
++ Please summarize the algorithm used by Boggler
The plan was simple originally, just make a recursive call (Boggle)
that would take a board and find all words on the wordlist. Of
course I sorted it first to simplify the process. Board construction
was done by concatenating random words from the Wordlist until the
board was full and then reversing rows 2 and 4 to
make the string continuous.
The results were ok, but certainly not impressive so I went
back to the drawing board.
I kept the Boggle Routine and turned to the task of building a
better board. I eventually decided to use 'natural selection'.
Starting the board as AAAAAAAAAAAAAAAAAAAAAAAAA and randomly
changing a single letter, and taking the better result, old or
new with ties retaining the changes and keeping the new board.
This routine worked surprisingly well, especially on the longer
lists I tested on.
On a lark I experimented with enlarging the "random" area, trying
1x1, 2x2 and 3x3. evaluating all permutations(2, 16, 512) of
New and old letters.
Of those runs the 2x2 worked best, allowing more mutation while
only requiring 16 valuations of the grid to check all permutations.
Once a 2x2 square was evaluated and the best retained the Timecheck
either terminated with an answer or selected
another 2x2 grid from the 5x5 and started again.
When time expired I re-evaluated the BestBoard and voila!
I eventually made a Found word array to paralell the Worllist and
just used 0/1 flags
to indicate found words. improved the speed a bit but faster is faster.
++ Did you iterate the process? randomize? keep track of time?
I used standard timing routines and stopped checking with 10
seconds to go, ample time for a final re-eval and output.
++ If I had it to do all over - here's what I would try ....
If I had more time I would try using weighted random letters based
on letter frequency in the wordlist. and Or construction of a
board by packing words in. My gut feeling is that a packing routine
will win this POTM, but my attempts have been less than successful.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I own my own Publishing Company, Datasmith Pub., Inc.
I live is Eugene/Springfiled Oregon, Home of the University of Oregon.
How 'bout them Ducks!
As for Job, they run the gamut, CC&BW is probably most accurate.
Programming, chess(both postal and OTB), and any form of competitive gaming.
I also have an interest in gyroscopes.
POTM Ideas, that's a toughie, I'd like to see some
variation of the "prisoners dilemma" type head to head AI.
Answers are easy, It's coming up with questions that is hard :)
=================================================================
============== 15 ====================== Mifflin =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Mifflin 225 58 PERL Jon Howell 575.58
=================
Mifflin submitted by Jon Howell at jonh@cs.dartmouth.edu
=================
++ Please summarize the algorithm used by Mifflin
Mifflin uses a genetic algorithm to get a decent starting board.
The genetic algorithm starts with random boards, combines boards
by selecting each tile randomly from one of two randomly chosen
parents, and then selects the top n% of the new boards to live
to the next generation.
Once it has a seeded board with at least a few words on it, it
uses hill-climbing to improve it. It picks the tile whose absence
damages the board's score least, and replaces it with the letter
that improves it most.
If it has hill-climbed for a while with no improvement, it runs
a few more rounds of the genetic algorithm to shuffle things up
in hopes of hopping out of a local maximum to find a better hill
to climb.
++ Did you iterate the process? randomize? keep track of time?
Yes, yes, and yes. Time was pretty crude -- I called a checkTime()
function every iteration (each genetic generation and hill iteration),
and when time is up, it just prints out what it's got.
++ If I had it to do all over - here's what I would try ....
I think this problem really called for a more deterministic approach.
I would probably try to organize the dictionary as a graph with
edges representing some edit distance between the words (giving me
an idea how much one word can "recycle" another), then look for
dense clusters (good recycling values), and then attempt to pack
those words onto a board starting with words from the "middle"
of the cluster, using some sort of backtracking so I could try
more than one solution (in case my edit distance heuristic or packer
got stuck with boards that don't pack well).
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Dartmouth College. Hanover NH. grad student.
Build things out of wood. It wouldn't be a secret, then, would it? No.
=================================================================
============== 16 ====================== igglobe =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
igglobe 223 57 C Paul Nelson 16.82
Sorry ... no description available for igglobe
=================================================================
============== 17 ====================== O_Boggle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
O_Boggle 222 55 c K.Williams J.Riedl 595.22
Sorry ... no description available for O_Boggle
=================================================================
============== 18 ====================== another =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
another 220 56 gc Bernard Hatt 578.92
=================
another submitted by Bernard Hatt at bmh@arkady.demon.co.uk
=================
++ Please summarize the algorithm used by another
A simple(ish) to start with a random(ish) grid and write words
from the wordlist into the grid, disturbing as few as possible
of the existing words, evaluating the score and keeping a copy
of the best grid found.
++ Did you iterate the process? randomize? keep track of time?
The program re-sorts the word list used according to different
criteria, which I have attempted to arange in order of usefulness.
++ If I had it to do all over - here's what I would try ....
I feel there is a better solution involving generating a tree
structure of the words, and fitting the higher scoring nodes into
the grid, but I could never get it to work (This was what I tried
first, but gave up and made 'another' attempt).
++ COMPANY?
I currently work for UniSoft Ltd., a company which (mainly) develops
standards testing software.
++ LOCATION?
My job is in central London, I live 15-20 miles outside London
in Hemel Hempstead.
++ JOB?
Software Engineer.
++ DO FOR FUN?
Food, drink, music, computers.
++ INNERMOST SECRET?
If I said it wouldn't be a secret.
++ POTM IDEAS?
How about a competion based on (lowest) execution time for a task?
=================================================================
============== 19 ====================== gobble =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
gobble 217 55 c John Feiler 29.88
=================
gobble submitted by John Feiler at jjfeiler@relief.com
=================
++ Please summarize the algorithm used by gobble
analyze words
pick words we're going to try
put them in a grid, and swap pairs of letters to get best solution
++ Did you iterate the process? randomize? keep track of time?
the swapping iterates, the rest just plugs along.....
++ If I had it to do all over - here's what I would try ....
Java. This will be the last program of more than 10 lines that I write in
plain C. I would prefer Objective-C, but that isn't one of the language
options.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Did it for fun, but got frustrated with the language before I got a chance
to try all of my ideas, and sorta quit working on it.
=================================================================
============== 20 ====================== just_random_252_modran_tsuj =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
just_random_252_modran_tsuj 216 51 C Neal Palmer 594.94
=================
just_random_252_modran_tsuj submitted by Neal Palmer at neal@us.extern.ucsd.edu
=================
++ Please summarize the algorithm used by just_random_252_modran_tsuj
The program has two parts to it:
1) choosing some starting "squares"
2) optimizing those "squares"
implementation:
1) given N words in the wordlist, create N "squares", where the square
consists of 25 letters in an S pattern:
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
For the Nth "square" start with the Nth word in the list and write it
in the square in the order of the numbers, and when the Nth word is
finished, write the N+1th word at the next successive position.
And also create 1 special square that has the following properties. The
same S pattern of writing words. The first word to be written into the
square is the word that by itself gives the highest score per positions
used. The second then has the highest additional score, and so on.
Then score all of the above squares and choose the best 10 of them. And
proceed with those onto the optimization part.
2) optimization.
For each of the 10 squares, incremental optimizations are performed.
First ALL unnecessary letters are "removed" from the square by first
removing each letter one at a time, and checking to see if the score of
the "square" was lowered. When a letter is removed I replace it with a
"wildcard" character.
Then the iterative process of choosing the best letter(s) to replace the
"wildcards" is run.
And finally I go through the square and replace sets of 1,2,3,4...
letters with wildcards, and after each replacement of a set of letters, I
attempt to replace the wildcards with the best letters to give the highest
score, and if the score has improved or is the same, then I keep the new
square. When I replace a group of 2+ letters, I do it in three patterns: S
pattern, 90 degrees S pattern, and chess-knight pattern. I have found
that runs of letters longer than about 5 never helps the score of the
square.
++ Did you iterate the process? randomize? keep track of time?
Iterated.
did no randomization.
kept track of time, and quit about 5-6 seconds early.
++ If I had it to do all over - here's what I would try ....
I would find a reasonable way to test more starting "squares".
Instead of replacing squares with "wildcards" (or in addition to it), I
would attempt to "drag/swap" characters around the square to try to get
new words.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
The Dini Group - digital hardware design consulting organization
La Jolla, California (a part of San Diego on the coast with good
snorkeling and scuba)
I design FPGA, board schematics, and firmware.
I enter programming contests just for the fun of it.
innermost secret: tutoring students in college for programming classes
helps more than you can imagine.
POTM ideas:
1) something like the "board game" "Black Box"
2) 2-player board game "Stratego"
3) packing a "rectangular" paper bag of groceries (all boxes, or
all spheres)
4) something that is three-dimensional
isn't it strange what people do at 2:15 in the morning when they can't sleep?
=================================================================
============== 21 ====================== Snoopy =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Snoopy 215 54 C Don Kirkby 600.35
Snoopy submitted by Don Kirkby at DKirkby@Sierrasys.com
=================
++ Please summarize the algorithm used by Snoopy
I start with a random square, look for partial words and try to
complete them. I have a heuristic function that counts partial words. If
a change in the square improves the heuristic or the score, I keep it.
If nothing improves for a while, then I just complete words at random
and ignore the heuristic for a while. After 10 minutes, I print out the
best solution I found.
++ Did you iterate the process? randomize? keep track of time?
The direction I extended the words was random.
++ If I had it to do all over - here's what I would try ....
Perhaps a less random technique. Actually do some analysis and
try to fold the words on their common letters. Of course, the reason I
didn't do it that way this time was that I couldn't think of a practical
way to do it.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM
IDEAS?
Innermost secret: Snoopy is a beagle. I play Ultimate Frisbee
for fun. This summer, Vancouver, B.C. hosted the World Ultimate Club
Championships and I was one of the organizers. Play Ultimate!
Thanks, Fred. Keep doing that thing you do.
=================================================================
============== 22 ====================== oonD =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
oonD 207 49 c Bob Ashenfelter 555.15
=================
oonD submitted by Bob Ashenfelter at ash@att.com
=================
++ Please summarize the algorithm used by oonD
Words are picked at random from the word list and inserted in the
square starting at upper left and zig-zagging down to lower right.
When the square is filled, its score is evaluated. This is cont-
inued until the time limit (555 seconds) is reached and then the
best-scoring square is output.
This isn't a very clever algorithm and I don't expect it to do very
well--probably in the middle of the pack. Most of the effort went
into evaluating the score, searching for each letter of each word
in the list using a recursive routine.
++ Did you iterate the process? randomize? keep track of time?
Yes, yes, and yes.
++ If I had it to do all over - here's what I would try ....
Unfortunately, I no longer feel the compulsion to put in the long
hours that it takes to develop a competitive POTM entry. You can
interpret that to mean that I currently have a more challenging and
satisfying job than I had a couple of years ago when my POTM efforts
scored near the top. As a result of not putting in the time, I don't
have any well thought-out answers to this question.
Obviously, I need a better way to generate trial squares, preferably
several ways. Also, I need ways of incrementally improving existing
solutions. It would also help to have an efficient algorithm for
evaluating squares; I think my current program spends almost all its
time doing this.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Tyco Submarine Systems, Ltd. Retired from AT&T.
Holmdel, N.J., U.S.A.
Electro-optical system and circuit design.
Bicycling, sailing, grow orchids, travel. (Recently got back from
three weeks cycling in Greece.)
No way...
No new ideas.
=================================================================
============== 23 ====================== BogOfWords =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
BogOfWords 195 49 c Gerhard Lutz 570.11
=================
BogOfWords submitted by Gerhard Lutz at glutz@acm.org
=================
++ Please summarize the algorithm used by BogOfWords
- Look only for words with less than 14 letters
- Count letters and letter pairs from all input words
- Random initialization of board with counting heuristic
- Try to find better solutions till time limit is reached
- Save the ten best solutions that were found
- Try to combine the best solutions
++ Did you iterate the process? randomize? keep track of time?
- Random process like a generic algorithm
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Gerhard Lutz
Student in computer science, University of Ulm, Germany
ACM Contest Secretary of South Western European Programming Contest 1997
look at http://www.informatik.uni-ulm.de/acm/
(we still look for European teams)
=================================================================
============== 24 ====================== HMSBoggle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
HMSBoggle 189 44 c Randy Saint 720.10
=================
HMSBoggle submitted by Randy Saint at saint@phoenix.net
=================
++ Please summarize the algorithm used by HMSBoggle
HMSBoggle creates a set of empty boggle boards, then places one word on
each one. It saves the top 10% of those, judged by most words & least
characters. It copys those 10% to fill out the set, then repeats the
process by adding words one at a time and saving the best 10% of the
boards. Once the board is full, it saves the best one.
++ Did you iterate the process? randomize? keep track of time?
This process is repeated until time runs out, or 100 boards are tested,
whichever comes first.
The word list is randomized each time to spice things up a little.
++ If I had it to do all over - here's what I would try ....
I started working on another algorithm, but couldn't complete it in time
for the contest. I generated a list of letters with up to 8 "links" to
other letters. Then I would place all the words on this list. Next, I
would try to map that list onto the 5x5 boggle board. It was this last
part that I could never get working.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work for Lockheed Martin at NASA, JSC, Houston. I recently (1 year ago)
got promoted to a management position, which is great, but they don't let
me do any coding. This contest is my "outlet" for my programming urges.
In case anyone was wondering about the name, when I started this program, I
used a more "Genetic Algorithm" type algorithm, which brought about ideas
of Darwin. Darwin's ship was the HMS Beagle.
=================================================================
============== 25 ====================== WordSoup =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
WordSoup 188 42 C Giorgio Difalco 312.34
=================
WordSoup submitted by Giorgio Difalco at G.Difalco@agora.stm.it
=================
++ Please summarize the algorithm used by WordSoup
I first discard all words longer than 11, for performance reasons.
Then I choose the first word, among those having 3 to 6 letters, as the one
with the best average letter frequency (i.e. the number of occurrences of
each letter in the complete words set divided by the number of letters).
Then I put the chosen word into the square by evaluating its best
positioning, with the algorithm at point 5 below.
After the first word is put down, all subsequent moves are made by
iterating the following steps:
1) all words are weighted basing on their best matching over the square,
i.e. by finding just one positioning with the maximum possible number of
reused letters.
2) since words have different lengths, the evaluator takes into account
the length too, by applying a formula like
coeff*#reused - length
After many tests, I fixed the coefficient to 2.
3) the best N words (after tests, I determined N=7) are then exhaustively
analyzed for finding each word's best positioning
4) each position is evaluated first by calculating how many words in the
N-set can still be put down after the under examination one is put (this
is a quite coarse evaluator, but it proved efficacious)
5) as a better evaluator, all couples of adjacent letters in the square
are determined and, for each, the number of occurrences of the couple
in the word set is computed.
6) As the last evaluator, the number of couples in the square
that have no occurrences in the word set are counted.
7) the move with maximum value at points 4 and 5 and minimum value
at point 6 is done.
For the sake of performances, the positioning of each word is computed by
first fixing then maximum number of possible pivots (letters already in the
square), and trying all possible positions for all other letters, then
decreasing the number of pivots if no positioning is found.
++ Did you iterate the process? randomize? keep track of time?
I thought of iterating the process by backtracking some moves and trying
alternative choices, but it turned to be too expensive in terms of
execution time.
There is no randomization anywhere.
I did not track time, because I do not like it. Unfortunately, time reports
from Fred showed that my notebook is about 10 times faster than Fred's
machine, so my estimates for a large word set (that my program can
process in about 40 seconds) are not reliable...
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Company: I.S. & O.
Location: Rome, Italy
Job: Consultant, System Architect
Fun: reading, computers, ski, physics, mathematics, sf
Secrets: ...
POTM ideas: reverse LifeGame (find a configuration that produces
a given next configuration, according to the Life Game
rules, by J.H.Conway).
=================================================================
============== 26 ====================== It_came_from_the_boggle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
It_came_from_the_boggle 187 48 c Mike Liddell 645.19
=================
It_came_from_the_boggle submitted by Mike Liddell at mjl@students.cs.mu.oz.au
=================
++ Please summarize the algorithm used by It_came_from_the_boggle
A hand-tuned genetic algorithm is the basic approach
++ Did you iterate the process? randomize? keep track of time?
I run up to 50 independent trials (time permitting) and keep the best.
1) Preprocessing: find character frequencies, single letter words and
two-character prefixes for all words. A hash table is built to
speed up the scoring of grids. Some long words are split to try
and aid their matching
2) The genetic algorithm
I start with a randomized population of 500 grids
At each step I score the grids keep the best 90 and a random
set of 10 to make a breeding population of 100. These are then
mated to make a new population of 500. The crossovers are on a
character-by-character basis.
The genetic algorithm runs until the top score has been stable for
20 iterations.
Because of the need to score many thousands of grids during a run, I
have tried to optimize the scoring routines somewhat. Some attempts
have been made to make the basic genetic algorithm more amenable to
the particular problem, but many trial optimizations where found not
to help. eg selecting a critical subset of the word-list to improve
speed just results in lower scores.
++ If I had it to do all over - here's what I would try ....
I would like to have a method which attempts to get the long words. If I
maintained my basic approach then it may be possible to improve the
starting population. eg rather than random grids, try to force a few long
words in and then run the genetic stuff in the hope that the long words
will remain.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
4th year undergraduate--Computer Engineering and Computer Science
University of Melbourne
Favourite stufff---small hacky programs (POTM, POTM, POTM)!!
graphics, games
Outside of computers --- sport, music, computers.
Now, back to my 4th year project.
_____________________________________________________________________
__
/ /\ Mike Liddell
/ / \ 4th Year Computer Engineering / Computer Science
/ / /\ \ Melbourne University
/ / /\ \ \ mjl@students.cs.mu.oz.AU
/ /_/__\ \ \
/________\ \ \ "Nothing cures insomnia like the realisation
\___________\/ thats its time to get up"
_____________________________________________________________________
=================================================================
============== 27 ====================== BogglePlayingChicken =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
BogglePlayingChicken 186 44 PERL Brian Raiter 618.32
=================
BogglePlayingChicken submitted by Brian Raiter at breadbox@muppetlabs.com
=================
++ Please summarize the algorithm used by BogglePlayingChicken
The program is a basically a patchwork of various searches and
simplifying mechanisms.
At the heart of it is a process that attempts to fit a subset of words
into an empty Boggle board using the minimum number of cells. In other
words, it fails if it can't be done without duplicating a letter.
This is done by treating the Boggle board as a graph. (Graph as in
graph theory, with vertices and edges.) Given a set of words, it
constructs a graph for it that assumes that every occurrence of the
letter A (for example) can be represented by the same vertex.
(Excepting of course the case when A appears more than once in a
single word.) The reason for this assumption is to narrow the problem
space to something approachable. It slashes off a lot of
possibilities, but hopefully the program will catch most of them later
on. Anyway, once the set of words is in a graph, the program computes
how many immediate neighbors each vertex has, and how many 1-away
neighbors, and so on. It then compares these numbers with the vertices
of the Boggle board, and generates a list of where each vertex would
"best" fit, roughly. This list then guides it as it does a
straightforward search for a possible mapping of letters onto the
Boggle board. Every time it puts down a letter, it computes how that
decision constrains the possibilities for every other letter. If it
becomes impossible to place a letter, it backtracks. Eventually it
either finds a mapping or runs out of possibilities.
Of course, this part can take a very short time, or it can take well
over ten minutes. However, it's not infrequent that when a board does
have a possible mapping, it is found rather quickly. So this function
is usually only run for a limited number of iterations. If it reaches
that limit, it quits and returns the best partial mapping it had at
the time.
So, what the program does at first is grab random subsets of the
wordlist and tries to quickly find mappings for them. Every time it
succeeds in finding one, it stashes it in a list which is sorted by
"density", i.e., the number of points per letter on the board. The
random subset chooser keeps track of successful mappings, and weights
its choices so that those words will be more likely to be chosen
together in the future. This phase of the program runs for five
minutes, just grabbing subsets of the wordlist and trying to place
them on a board. Every time it succeeds, it increases the size of the
subsets it uses next time.
Then, the program stops and takes a look at the saved list of
half-filled in boards. It throws away all but the "densest" boards on
the list, and then proceeds to try to cram more words into the
remaining space on each board. It does this in three different
ways. The first attack starts with the longest words first (i.e., the
ones with the most points), and works down to the shortest. For each
word, if it can be added to the board, it puts it in the first place
it finds. The second attack does the same thing, but the order of the
words it tries to fit in is chosen using the weightings accumulated in
the previous phase by the random subset chooser. The third attack
tries to be more complete - it considers all possible positions of
every word that can fit on the board, and follows out the branching
choices. This one can obviously run for a very long time, so it is
only used when there are no "lumps" of empty cells on the board - that
is, when the empty cells are relatively spread out from each other.
In the case of a maximum-sized wordlist, the program will probably run
out of time while doing the above. If it finishes this examination of
the boards, however, it then goes back to the first part, looking for
sets of words that can be fit on a board compactly. This time around,
it tries to choose sets of words that will be at least as "dense" as
the best density achieve the first time around, since a less dense
group is unlikely to yield anything that wind up scoring more points
than what the program already has. As soon as it finds one, it
then jumps back into trying to squeeze more words in. This
back-and-forth process is repeated until time runs out.
++ Did you iterate the process? randomize? keep track of time?
Yes, yes, and yes. The latter especially - all of the "cramming"
functions check the current time inside their innermost loop.
++ If I had it to do all over - here's what I would try ....
Too numerous to mention. I had lots of ideas that I didn't have time
to work out the details for. I wrote most of the program I submitted
in the last two weeks before the deadline. (And I spent most of the
two months before that scratching my head and drawing funny diagrams
in my notebook.)
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Currently unemployed, and in Seattle. For fun I like to hack on
problems like this one.
Innermost secret? It's so deep down in there even I don't know what it is.
=================================================================
============== 28 ====================== werdnerd =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
werdnerd 184 47 c Michael Pantiuk 432.72
=================
werdnerd submitted by Michael Pantiuk at mpanti1@gl.umbc.edu
=================
++ Please summarize the algorithm used by werdnerd
sort of a random use-what-I can approach.
++ Did you iterate the process? randomize? keep track of time?
process was an iterated randomness... didn't consider
time at all..
++ If I had it to do all over - here's what I would try ....
drop out of school so that I could have more time to
work on the problem.... as it stood, I only was able to
submit my first try.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Grad Student, Mechanical Engineering, University of Md. Balt. Co... I have
no life, so I don't do anything for fun. (except of course, POTM, and
that only half-assed!)
=================================================================
============== 29 ====================== GobbleSquares =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
GobbleSquares 182 49 C Joe Vollbrecht 699.85
=================
GobbleSquares submitted by Joe Vollbrecht at vollbrec@GEMINI.kc63.att.com
=================
++ Please summarize the algorithm used by GobbleSquares
At start up, determine what words are contained in other words to
potentially reduce search time. Load words into the square
left-right-left, and then search for all words not initially loaded.
++ Did you iterate the process? randomize? keep track of time?
I loaded random words into the square, except that if a long word
contained a short word, I wouldn't put the short word in separately. I
kept track of time, checking every 1500 squares searched.
++ If I had it to do all over - here's what I would try ....
I would have added different square loading algorithms, and planned to
implement something to improve the search speed.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T. Kansas City. Programmer. Sing and chase children. It hasn't been
revealed to me yet.
=================================================================
============== 30 ====================== Refrigerator =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Refrigerator 181 59 c Franz Mauch 570.10
=================
Refrigerator submitted by Franz Mauch at Franz.Mauch@uni-konstanz.de
=================
++ Please summarize the algorithm used by Refrigerator
Many tables are tested, from one table to the next some modification is
made, and if one gets a better score the new table is used. Actually
sometimes the new table is also accepted if one gets a smaller score -
randomly and with a small probability. The latter is done in the sense of
a method named simulated annealing (therefore the name).
++ Did you iterate the process? randomize? keep track of time?
Which process? All is randomized. Keeping track of time is done.
++ If I had it to do all over - here's what I would try ....
First the same...
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
University of Constance, Department of Mathematics and Computer Science,
a small assistence job, looking for a full job. I've done it for fun.
No secret at all.
=================================================================
============== 31 ====================== Fear =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Fear 177 41 c Kyle Larsen 590.01
=================
Fear submitted by Kyle Larsen at kylel@microsoft.com
=================
++ Please summarize the algorithm used by Fear
Pick a random word. Place the word on the board in a random way. Pick
the next word and continue. If I can not place any of the remaining
words, start over. This program is simple enough and produces
reasonable answers.
The first optimization was to pick words that are more similiar to the
words already in the puzzle and/or more similiar to the words present in
the best known answer so far. The next was to prefer to place words on
top of squares that were already occupied instead of using up the blank
squares. The third optimization was to use only the upper 6 squares for
the first letter of the first word since the board is symetrical. The
last was to limit the exhausive search required during the attempt to
place a word on the current board, and consider it failed after a
certain number of attempts to prevent working too hard on a word that
will simply never fit.
++ Did you iterate the process? randomize? keep track of time?
Fear simply keeps starting over and trying at random until it comes up
with a better answer. Fear isn't really random. It uses a function and
look up table which I wrote along with the rest of the program when I
was feeling creative in the midst of much emotion for the love of my
life, Tyler. I consider the program more art than science.
++ If I had it to do all over - here's what I would try ....
I have it to do all over again every day. I wouldn't have it any other
way.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM
IDEAS?
I am a Software Design Engineer at Microsoft. I enjoy barefoot
water-skiing. I am free of secrets, and full of mystery.
=================================================================
============== 32 ====================== HICINBOGGLE =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
HICINBOGGLE 176 43 gC Michael Strauch 74.53
=================
HICINBOGGLE submitted by Michael Strauch at michael.strauch@cww.de
=================
++ Please summarize the algorithm used by HICINBOGGLE
Hicinboggle uses a simple greedy algorithm by inserting one word after
another into the 5x5-square. The square is empty at the beginning, i. e.
it contains no letter at all (I use a "?" to show that a field of the
square is empty). To chose the next word to be inserted, it
tests all words if and where they can be inserted, and tries to find
the one word which gives the highest "relative" score. I define
"relative Score" as the quotient "score/(number of non-empty fields)".
++ Did you iterate the process? randomize? keep track of time?
My first idea was to remove and insert words randomly after the "greedy"
search and to improve my solution, but I encountered a lot of problems
in the "greedy" search I had to overcome, so I had no time at the end of
the contest to implement this idea. The main problem was that my depth
search (which I use to test if a word can be inserted anywhere into the
square) sometimes needs immense time to find that a word cannot be
inserted. This situation occurs mostly if I try to insert a word that
has slightly more characters than the square has "?"-fields.
++ If I had it to do all over - here's what I would try ....
Perhaps I would try to enter the problem from another side, trying to
insert letters instead of words, or setting up a complete
branch-and-bound algorithm.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Do for Fun: POTM (what else?)
=================================================================
============== 33 ====================== Noise =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Noise 173 41 c Justin Legakis 106.59
=================
Noise submitted by Justin Legakis at legakis@mit.edu
=================
++ Please summarize the algorithm used by Noise
Noise placed words, in a random order, starting at random locations, and
stepping in random directions -- over and over again, keeping track of the
best arrangement.
++ Did you iterate the process? randomize? keep track of time?
Didn't look at the time. Only itereated a fixed number of times, which
ended up taking about 100 seconds. Should have used that time code to
take advantage of my whole 10 minutes...
++ If I had it to do all over - here's what I would try ....
Better search tree. Looking at histograms of letters to pick good words,
and to prune out problem words.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Graduate student in the computer graphics group in the laboratory for
computer science at MIT.
=================================================================
============== 34 ====================== Bogeyman =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Bogeyman 172 43 gC Markus Sabadello 590.04
Sorry ... no description available for Bogeyman
=================================================================
============== 35 ====================== perloined-letters =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
perloined-letters 169 40 PERL John Linderman 424.23
=================
perloined-letters submitted by John Linderman at jpl@research.att.com
=================
++ Please summarize the algorithm used by perloined-letters
Preprocess wordlist to build array of letter pair frequencies
Seed board with word having good letter-pair score
Try all words in existing board
Favor placement that creates high-frequency pairs
Add word that brings in most letters using fewest blank squares
Stop when no new word fits or time is tight
Keep track of best board, report it when time expires
++ Did you iterate the process? randomize? keep track of time?
No randomness, strictly iterative, usually run till time expires
Iterate over several seed words -- if possible, in several positions
For large wordlists, restrict to about 45 words over reduced alphabet
++ If I had it to do all over - here's what I would try ....
Perl was great for finding good (and really bad) algorithms
If maximal score was all that mattered, I'd recode in C
I wish I could have some of those nice fall weekends back :-)
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
AT&T Research Florham Park, NJ Hacker
Potm, books, outdoors, classical music, draught beer
Evolution has over-rated size (guess who's short?)
The potm is in good hands
=================================================================
============== 36 ====================== Mind_Boggling =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Mind_Boggling 164 46 C Darren Davis 605.60
=================
Mind_Boggling submitted by Darren Davis at jpdavis@webspan.net
=================
++ Please summarize the algorithm used by Mind_Boggling
The algorithm that Mind_Boggling used was to randomly select the words
from the wordlist, and put them together in the random order picked.
Then, the resulting string is placed into the grid using 11 predefined
patterns (and going backwards with those patterns; flips & rotations
don't affect letters touching each other, so they just add work). It
would then search through the grid for any additional words that
happened to be in there. If the score achieved was greater than the
best score so far, it would save it separately. It would keep this up
for 595 seconds. Then it would change only one position to all other
characters (testing 650 more possibilities). And that was all that
there was to it.
++ Did you iterate the process? randomize? keep track of time?
See above.
++ If I had it to do all over - here's what I would try ....
Take the largest words and try to fit it into the middle of the grid.
Then take successively smaller words and try to fit them as compactly as
possible overlapping as many letters as possible until you couldn't do
it any more. And then try it again, but with some random aspect
different. Keep that up until time is up.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM
IDEAS?
I'm a Junior at Marlboro High School in Marlboro, New Jersey.
POTM IDEAS: I only have one idea, and it is to allow programs to be
done in:
PPPPPP AAAAAA SSSSSS CCCCCC AAAAAA L !! !!
P P A A S C A A L !! !!
PPPPPP AAAAAA SSSSSS C AAAAAA L !! !!
P A A S C A A L !! !!
P A A S C A A L
P A A SSSSSS CCCCCC A A LLLLLL !! !!
=================================================================
============== 37 ====================== BoggleLava =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
BoggleLava 161 43 JAVA Gilbert Wellisch 439.79
=================
BoggleLava submitted by Gilbert Wellisch at gilbertw@utw.com
=================
++ Please summarize the algorithm used by BoggleLava
BoggleLava makes use of Java's multithreading. It starts two threads
that solve the problem two different ways. One thread randomly inserts
words that are not already in the puzzle. The other thread randomly inserts
letters based on the frequency of the letters in the word list. After the
changes, each thread then compares its new score with the old, undoing the
changes if no progress was made. As the program exits, the main thread
compares the results from both and picks the best one.
++ Did you iterate the process? randomize? keep track of time?
The threads both approach the problem using randomization. The main
thread keeps track of the time and terminates the solver threads before the
time limit expires.
++ If I had it to do all over - here's what I would try ....
The methods I used were heuristic. I would try to create a more
procedual method.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I work for Mervyn's Utah Distribution Center as a Network Technician.
=================================================================
============== 38 ====================== Coin_Toss =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Coin_Toss 156 41 c Corey Anderson 658.74
=================
Coin_Toss submitted by Corey Anderson at corin@cs.washington.edu
=================
++ Please summarize the algorithm used by Coin_Toss
I generate a list of words whose letter-length is 25 (or fewer but pretty
close). Then I wrap those words around the boggle grid, and check my
score. I have several ways to wrap words on the grid, about half of which
are motivated by Celtic knots(!). An explanation of that in a nutshell:
Celtic knots are drawn on an offset grid, where the string can go
diagonally (usually) or horizontally and vertically (if constrained). The
Celtic knot idea let me come up with several unique wrapping methods that
worked well.
++ Did you iterate the process? randomize? keep track of time?
I randomly generated the string of words, and then exhaustively tried all
the different ways of putting that string on the board. I have about a
dozen board orderings hard-coded in the code, so exhaustively is kind of
an overstatement.
A better method, which I never got to try, would have been to randomly
generate different legal board orderings. I think that this might have
been more optimal, just because it isn't impaired by my lack of
imagination at compile time.
I always run for about nine and a half minutes, using the timeofday()
function to know when it's time to quit.
++ If I had it to do all over - here's what I would try ....
I think that random searches are kinda neat, but really slow. Given the
chance, I would have liked to try to find a constructive way of building
an optimal or near-optimal board word by word. Or, maybe even a hybrid of
these two ideas: build board fragments, then glue them together randomly.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm a 2nd year grad student at the University of Washington in Seattle.
I'm presently working in the AI group, doing research in planning
algorithms. I'm also a contract software engineer for Cirrus Logic, Inc.
My claim to fame with them is that I wrote the XFree86 driver for the
Laguna family of chips. Between classes, I entertain myself by playing
bridge with my other CSE grad and ugrad friends.
I think that we should have another head-to-head POTM. Or what about a
multi-player POTM? Like a 4-way conquer-the-universe game, where entries
can either cooperate or ignore each other, at their own choosing.
=================================================================
============== 39 ====================== arcboggle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
arcboggle 154 44 c Gerry Sullivan 399.95
=================
arcboggle submitted by Gerry Sullivan at sullivan@arete.com
=================
++ Please summarize the algorithm used by arcboggle
1 - Read in word list
2 - Choose letters to fill boggle grid using weighted letter usage
3 - Break grid into 3 rings, filling most used letters nearest center
4 - Rotate 3 rings, keeping grid with maximum score
++ Did you iterate the process? randomize? keep track of time?
- A very simple iteration scheme was used due to time constaints
(mine really, not the POTM limit of 600s)
- Did not keep track of time
++ If I had it to do all over - here's what I would try ....
- Steps 1 & 2 worked great on both the test and final grids
- I would work out a scheme which made use of looking at
n-letter subwords to find better cube placement
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
- I work at a small oceanographic research company called
Arete Associates located in Sherman Oaks, CA --
in the San Fernando Valley (the Valley) north of LA.
Our (fairly primitive) web site is www.arete.com.
- I work as a Staff Scientist -- putting together computer
simulations and doing data analysis.
- Fun -- I have a 7 month old at home -- don't remember
what I did for fun
- Innermost Secret -- I was the fifth Beatle... and the twelth man
=================================================================
============== 40 ====================== hack-n-pack =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
hack-n-pack 147 48 c John Lauro 20.00
=================
hack-n-pack submitted by John Lauro at jlauro@umich.edu
=================
++ Please summarize the algorithm used by hack-n-pack
*Very* rough summary:
1. Read in the word list, and ignore words I'm too lazy to deal with.
Words with 2 letters the same, and stuff like that.
2. Chop up the word set into 2 character strings.
3. Combine word set into larger strings if possible. IE:
AB, BC, and CA would combine to ABC.
4. If any 5 letter chains we then have to drop something as there is no
way to fit a 5 letter chain.
5. Try to fit all the chains. If a problem occurs then either drop a
word or a letter from the selection and redo step 2 with smaller word
set. When dropping letters/words, try to optimize based on
statistics of letters and words...
6. After first pass, repeat with other passes on remaining words.
++ Did you iterate the process? randomize? keep track of time?
I ignored time. Used a word list over 20,000 long for my testing.
++ If I had it to do all over - here's what I would try ....
One thing that bugs me, is if I feed back my answer as the new word
list I typically don't get the same thing back...
I would also try to come up with some mathimatical way of generating
the best answer in a reasonable amount of time (some sort of shortest
distance mapping problem), but I'm not that good at that sort of
thing... I would at least do a minimal support for words with
2 letters the same.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Company: University of Michigan - Flint
Location: Owosso, MI (Me), Flint, MI (work)
Job: System Administrator III
Do for fun: Play multi-player computer network games against friends.
Innermost secret: Now, it wouldn't be a secret if I told you, would it?
=================================================================
============== 41 ====================== something_clever_please =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
something_clever_please 133 36 c David Wales 599.02
=================
something_clever_please submitted by David Wales at david.wales@waii.com
=================
++ Please summarize the algorithm used by something_clever_please
Decide on a set of words such that each letter, or group of letters,
in a word is used in at least one other word in the set. Give a score
to each letter = the sum of lengths of all words possibly using that
letter. Produce a score for each word = sum of letter scores for all
letters in the word.
Order all the words according to word score, how many unique letters
there are in the word, length.
Start loop until timeout, build a square, compare the winning criteria
for the generated square with the best so far. Keep the best. Every so
often regenerate the word list. This is done by taking the first word
in the list that was NOT in the latest square, and promoting it to the
top of the list. Every so often reset the word list to the
original. Every so often rejiggle the neighbour order - the search
order for considering neighbours of a cell in the square.
A square is built by a brute force method. In order, take the words
from the list and attempt to 1) find them in the square 2) put them in
the square. Make a recursive call to the routine for putting a letter,
iterating over all neighbours of a successfully placed letter, will
guarantee to find or place a word if it is possible.
Other fiddly things to help with speed.
++ If I had it to do all over - here's what I would try ....
Instead of a brute force method, pack all words into a connected mesh,
words added to a mesh a letter at a time, if the letter is in the mesh
and has not been used already in this word then re-use the letter,
else use another letter of the same value make links between adjacent
letters in a word. Then a second phase would be to pack this mesh into
a 5X5 square. At least then I could guarantee that all neighbours (or
links) in the mesh are valid, the work would then be done in the
packing phase. However I had started with a brute force method, it was
taking too much of my time already!
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Western Geophysical, Software Engineer,
cycling/programming/travel/things chinese
=================================================================
============== 42 ====================== GobbleBoggle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
GobbleBoggle 126 38 c Nathan Carlson 300.79
=================
GobbleBoggle submitted by Nathan Carlson at n.carlson@lmco.com
=================
++ Please summarize the algorithm used by GobbleBoggle
Essentially a random-recursive algorithm. There are a small number of
factors which, when taken together, determine the boggle board with the
best possible score for a given wordlist. Basically, I started with a
recursive routine that randomly placed the words in the order given in
the grid. I then added some routines to order the word list so as to
minimize execution time and maximize (at least as far as possible
with this approach) the number of words that could be added to the grid.
Of course, this doesn't work very well on long words, so a very simple
algorithm is used for those.
++ Did you iterate the process? randomize? keep track of time?
Random and recursive, and then to maximize on the capability of the
algorithm, I did multiple runs until time ran out, taking the best of
all the generated grids.
++ If I had it to do all over - here's what I would try ....
Something a little less complex! I didn't spend a lot of time on
design, just said: this ought to work.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Lockheed Martin Federal Systems, Gaithersburg, MD; Don't have time for
fun! If I come up with any great POTM ideas, I'll let you know
(I really liked the last one- June 97 POTM? The game idea...)
=================================================================
============== 43 ====================== Bungle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Bungle 120 36 c Davor Slamnig 591.07
=================
Bungle submitted by Davor Slamnig at slamnig@fa2.so-net.or.jp
=================
++ Please summarize the algorithm used by Bungle
++ Did you iterate the process? randomize? keep track of time?
Bungle uses a not-completely-random algorithm to generate results, bungling
it again and again until time runs out. I'll post a more detailed
description if I make top 10, which I won't according to the system test
results.
++ If I had it to do all over - here's what I would try ....
Well, I had a vague idea about creating a multidimensional space where all
the words are connected by all of the constituent letters, and then
projecting the resulting object onto a two-dimesional grid... Never could
figure out how to actually do it.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
At present I work for TechnoCraft (Japan) via the net - I'm living in
Zagreb, Croatia. We're making automated "screen-sensitive" multilingual
dictionaries for Windows. I'm a C/C++ programmer, also a guitar player,
composer, writer (lit.).
My innermost secret is always trying to follow my desires, expecting
something worthwhile at the other end no matter how trivial or megalomanic
the desires themselves seem to be.
Slama
=================================================================
============== 44 ====================== boggoblin =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
boggoblin 107 30 gC Dave Krofssik 588.09
=================
boggoblin submitted by Dave Krofssik aat davek@soft-tek.com
=================
++ Please summarize the algorithm used by boggoblin
The word list was randomized and then each word was attempted one by one.
The CBoggle class kept track of board positions. A word was placed
randomly on the board, a letter at a time in only valid positions,
until the full word was on the board. The word then tried different
positions to find one that had the most coverage with previous words
(leaving the most squares open for future words).
Each word list was given up to one minute to find a series of words
with the best score (so that at least 10 random word lists were tried).
This was to prevent a single long word from taking up all the time.
++ If I had it to do all over - here's what I would try ....
I might try to find the longest common string in the list of words
and build around that iteratively.
=================================================================
============== 45 ====================== salad =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
salad 98 33 C Arthur Zogla 224.00
=================
salad submitted by Arthur Zogla at fix.lv!uvsk@kcig2.att.att.com
=================
++ Please summarize the algorithm used by salad
++ Did you iterate the process? randomize? keep track of time?
To solve the problem we have to fill the square 5*5 with letters by the help of
following algorithm.We choose each position of the square and fill them with
letters A..Z so that we get a square where there are as much words from the
given set as possible. There are 25 positions and 26 letters, thet makes
25*26=650 operations to solve the problem. But the most of the time my
program spends to find the words in the square. It is possible to change the
order we fill the square, but the best till now is: from left to right and
from up to bottom.There was no Random in my solution.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I'm in grade 11, Ugale Secondary School, Latvia.
=================================================================
============== 46 ====================== INDIAN_MAGIC =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
INDIAN_MAGIC 88 22 c Ramkumar Srinivasan 206.99
=================
INDIAN_MAGIC submitted by Ramkumar Srinivasan at rsrini@iiap.ernet.in
=================
++ Please summarize the algorithm used by INDIAN_MAGIC
Simple! just find out the words with the maximum number of sub-words
and print out the square.
++ Did you iterate the process? randomize? keep track of time?
No : My program takes 3800 seconds (1 Hr aprox.) to give out the output.
I wont be surprised to receive an award from Fred for the slowest entry :-)
++ If I had it to do all over - here's what I would try ....
No.. No.. No.. I would never do it all over again.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I am 18 years old. I am a student of BE (Electronics & Comm.).
I like reading about Neural networks & AI.
=================================================================
============== 47 ====================== Bozo_TM_Billion_Monkey =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Bozo_TM_Billion_Monkey 88 28 c Shawn Smith 591.01
=================
Bozo_TM_Billion_Monkey submitted by Shawn Smith at
smiths2zzyy@worldnet.att.net
=================
++ Please summarize the algorithm used by Bozo_TM_Billion_Monkey
Bozo_TM_Billion_Monkey (I would have preferred Bozo (TM) Billion Monkey for
a name, but wasn't sure if the parens would be legal for the name) does
pretty much what the name implies. It tries to pretend there are a billion
monkeys typing away at a billion typewriters for a billion years (I
know--too conservative) to get the correct board. It does this by
generating random boards, checking each against the wordlist that it read
in, and storing the best Boggle board it finds until the 10 minutes are up.
The only tricky (and slow) thing about the program is that it uses
a recursive algorithm to check each word. The standard maze finder
Backtracking algorithm is used for the word check. Also, because it was
written before the answer about no repeating words was placed in the FAQ,
it does make certain that the wordlist I check against only has each word
once.
++ Did you iterate the process? randomize? keep track of time?
The program was iterative in the sense that each board was generated one
after the other, completely independently. Also, each word is looked up in
the board, one after the other.
Yes, it did randomize, every board creation.
Yes, after each board was checked, it checked the time for 9min 50sec. and
printed the best board found at that point.
++ If I had it to do all over - here's what I would try ....
to get a life, by not spending so much time in front of the computer or
television. Oh--you meant for this problem. Well, perhaps try building
some sort of graph that would track which letters were the best placed in
which locations in the board, by knowing how many different adjacent
letters were indicated.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
TRW Environmental Safety Systems, in Las Vegas, Nevada. I'm a computer
programmer, maintaining Ingres databases and developing applications for
the Project Control group. (translation: I generate status reports.)
For fun I ride my bicycle (not very well), bowl (again, not very well), and
catch a few of my favorite programs (only broadcast TV because I'm too
cheap to buy cable.)
My innermost secret is something I did fourteen years ago in high
school.
=================================================================
============== 48 ====================== pzsolt =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
pzsolt 81 16 c Peter Zsolt 3.20
=================
pzsolt submitted by Peter Zsolt at pzsolt@augusta.inf.elte.hu
=================
++ Please summarize the algorithm used by pzsolt
I gave a value for all the words in the list, which was the number
of the letters from the word plus the lenghts of the words which
were part of this.
eg. BCD 3
ABCDEF 6 + 3 + 3 = 12
DEF 3
Then I tried to put some words into the 5x5 place in the fallowing
letter order:
12345
A9876
BCDEF
KJIHG
LMNOP
getting the highest sum of the values used.
++ Did you iterate the process? randomize? keep track of time?
?
no.
no.
++ If I had it to do all over - here's what I would try ....
If I would have a better idea except trying all the possibilities,
I would have done it that way.
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
None.
Budapest, Hungary
I'm a student at a university.
-
-
I will think about it.
=================================================================
============== 49 ====================== Bognalramus =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Bognalramus 37 18 c Rex Jolliff .48
=================
Bognalramus submitted by Rex Jolliff at rex@lvcablemodem.com
=================
++ Please summarize the algorithm used by Bognalramus
Bognalramus chose a subset of the complete set of words by
counting unique letters and rejecting words that certainly
would not fit on the boggle board, it sorted this set of words
by adding the inverted frequency of each letter up and ordered
the list by this value. then it started placing each word from
the list into the board trying to reuse as many letters as it could.
This was the simple solution I came up with while I was working
on the cool solution that I never finished. Usually, I just work
on the cool solution and never finish it, but this time I decided
I would at least get something in.
++ Did you iterate the process? randomize? keep track of time?
No, it made one attempt to fill the board with words from the list.
++ If I had it to do all over - here's what I would try ....
>
the graph one of 6 classifications based onthe six positional
classes in the boggle board, the classes are differentiated
by the degree of the node and the degree of the
adjacent nodes. Once the wordlist had been traversed and
all words placed into the graph, then the graph would be fitted into
the boggle board. I just couldnt think of a good way to pick
words to be placed into the graph, it seems like a revenge of
the knapsack.
++ COMPANY?
TRW- Environmental safety systems. we make the world safe
for nuclear waste.
LOCATION?
Fabulous Las Vegas
JOB?
Oddly enough, I write programs for them too.
DO FOR FUN?
Frontal Lobotomies
INNERMOST SECRET?
Scott McCord
=================================================================
============== 50 ====================== zigzaggle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
zigzaggle 25 2 sh Hans-Joachim Gurt 1.58
=================
zigzaggle submitted by Hans-Joachim Gurt at gurt@nacamar.net
=================
++ Please summarize the algorithm used by zigzaggle
Very simple: select the longest words from the list,
until we have enough letters.
Then the letters are filled into the boggle-square
in a zig-zag fashion.
With any decent wordlist, this should always yield 25 points.
(Worst case would be a list with all words 13 chars long :-)
++ Did you iterate the process? randomize? keep track of time?
No need for this simple program.
++ If I had it to do all over - here's what I would try ....
I could not come up with clever algorithm,
and a brief look into the sources for boggle
convinced me, that I didn't want to re-engineer that one.
So I only did the minimal work to 'solve' the problem.
There are a few obvious things to enhance my simple
solution, but that would not help much (maybe 30+ points),
and would take at least another two hours, so I decided
to leave it as-is.
++ COMPANY? LOCATION? JOB?
NACAMAR Data Communications, a german internet-provider.
Network Administration, e.g. domains and IP-space.
DO FOR FUN?
SF, Fantay, RPG, board+computer games (mainly adventures
and economic/tactial/strategic ones, like Civ, MOO, XCOM,
VgaPlanets, Stars!)
Some 'bits' of MUDs and Quake now and then (some collegues
next door run evermore.de, quakeforum.de and splatterfest).
Surfing the net, some 'bits' of programming 'now and then',
and sometime I even go out the door and have a beer :-)
INNERMOST SECRET?
:->
POTM IDEAS?
No interesting problems yet, sorry.
But I keep an eye on it...
=================================================================
============== 51 ====================== Boogle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Boogle 25 6 JAVA K. Raja 5.80
Sorry ... no description available for Boogle
=================================================================
============== 52 ====================== elggob =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
elggob 3 3 gc Bill Wendling .17
=================
elggob submitted by Bill Wendling at wendling@ncsa.uiuc.edu
=================
++ Please summarize the algorithm used by elggob
Well, I tried a heuristic algorithm which calculated which was the most
likely letter to come after a letter. It then tried to build a board
using that information. It was ill-conceived and didn't work.
++ Did you iterate the process? randomize? keep track of time?
I kept track of none of these things. Given the same words it would
produce the same board.
++ If I had it to do all over - here's what I would try ....
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
=================================================================
============== 53 ====================== Last =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
Last 0 0 c Paul Banta .09
Sorry ... no description available for Last
=================================================================
============== 54 ====================== BOGGLE^-1 =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
BOGGLE^-1 0 0 c Mark Masten 0
=================
BOGGLE^-1 submitted by Mark Masten at masten@voicenet.com
=================
++ Please summarize the algorithm used by BOGGLE^-1
I approached the problem using a type of genetic algorithm.
First, the program generates some squares using randomly generated letters
(selected from only letters contained in any of the words; no attempt was
made to favor frequently used letters).
Then, it keeps going though all the squares repeatedly until time is up,
doing the following each time:
1. "Mutate" a square by changing one or more of its letters
2. Compute the score of the new square
3. If the new square has a higher score than the old one,
then add it to the population of squares (and keep the old one)
4. If it has been too long since the old square produced an
improvement, then remove it from the square population
When time is almost up, it prints out the square that had the highest
score and prints out the words it found for that square.
I tried to speed up steps 1 and 2 as much as possible, so that the program
would have more time to keep trying for improvement.
After experimenting with several different ways to mutate squares (see
below), this approach quickly yielded scores consistently in the 50s,
and once in a while in the 60s (using the test list). After four runs
(after the contest ended) with the final wordlist, the scores ranged
from 315 to 412 (but I should point out that I don't know how much slower
it might have run on the POTM's machine, so this might not neccessarily be
a good indication of the program's strength).
No attempt was made to make mutated squares (in step 1) by somehow
combining several different squares together into one (I do not think
that sounds like a promising approach to finding better squares).
An approach which I think seems promising that I didn't have enough time
to test out is having the program favor words which it judges to have
a higher probability of being able to fit into a high-scoring square (for
example, not spending time trying to use words like EXTRAORDINAIRE).
A mutation approach which I didn't have time to try is to find partial
sequences of letters of scoring words in a square, and attempting to
complete those words. Besides sounding very hard to code, it seems to
me that this approach might slow the program considerably (reducing the
number of mutations possible), and therefore might actually be worse.
A mutation method I thought worked surprisingly well was simply placing a
single random letter on the square. It didn't do very well by itself, but
it helped when used as an occaisonal alternative to a different method.
A mutation method I predicted to work well but which was not too
impressive was to create a massive table of up to 8-position sequences of
(X, Y) coordinates, and use it to place words quickly in a square
without constantly randomly computing the next coordinate of a sequence
and making sure it was within the square.
++ Did you iterate the process? randomize? keep track of time?
Yes Yes Yes
++ Biggest obstacles?
1. Porting problems
2. My favorite baseball team making it to the World Series (and winning)
3. About one week before the end of the contest, my former University
cut off access to my account, which I was using because it was Unix and
much faster than my ISP's system. Fortunately I periodically got
copies of it, but I still lost over a week's work at a time I seriously
needed to be resolving porting problems.
++ If I had it to do all over - here's what I would try ....
1. I would go with basically the same idea overall.
2. Experimenting with not trying to place longer words.
3. Getting to the least fun part (resolving porting problems) sooner.
4. Testing with larger lists, and more lists.
5. Running my computer overnight on several days trying different
combinations of mutation approaches.
++ LOCATION? JOB? DO FOR FUN? ETC.
I am a computer programmer from Pennsylvania who couldn't get enough of
programming at the office, so I did this in my spare time for fun :)
=================================================================
============== 55 ====================== LegoMyBoggle =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
LegoMyBoggle 0 0 C Eric Sinzinger .18
Sorry ... no description available for LegoMyBoggle
=================================================================
============== 56 ====================== BogglesTheMind =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
BogglesTheMind 0 0 gC Mike Goldshteyn 19
Sorry ... no description available for BogglesTheMind
=================================================================
============== 57 ====================== SidewaysTurkey =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
SidewaysTurkey 0 0 C Sam Wilson .10
=================
SidewaysTurkey submitted by Sam Wilson at samw@crss.esy.com
=================
++ Please summarize the algorithm used by SidewaysTurkey
No algorithm at all. I submitted an initial entry which produced a hand-created
solution to the system test list of words. I never had time to produce a real
solution to a general list.
++ Did you iterate the process? randomize? keep track of time?
Nope.
++ If I had it to do all over - here's what I would try ....
Anything...
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
Raytheon E-Systems
Garland, TX
Software Engineer
=================================================================
============== 58 ====================== retrevnIelggoB =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
retrevnIelggoB -148 1 gc Stephane Moreau .48
Sorry ... no description available for retrevnIelggoB
=================================================================
============== 59 ====================== BOGG_GGOB =============
=================================================================
ENTRY SCORE WORDS LANG Programmer - time (sec)
------------------ ----- ----- ---- -------------------------
BOGG_GGOB -4024 42 C Juan Leni 597.28
=================
BOGG_GGOB submitted by Juan Leni at jleni@impsat1.com.a
=================
++ Please summarize the algorithm used by BOGG_GGOB
In order to solve the problem I used a genetic algorithm.
Obviously, I had a problem with the part of the program that
calculates the score of certain square. Sadfully I had some
problems with my computer the last days and couldn't fix
the problem before Friday...
++ Did you iterate the process? randomize? keep track of time?
I kept track of time and as genetic algorithm need I used
random numbers too.
++ If I had it to do all over - here's what I would try ....
If I had to do it over again I would have test the program better and
assured my computer wouldn't fail during the last days..
++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS?
I study Industrial Engineering at a local university (Argentina) and did
this just for fun. This was the first time I participate and I'll try to do
it again.
=================================================================