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 ( _____________________________________________________________________ __ / /\ 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 o f 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. =================================================================