CROZZLE Program entry descriptions Beware of long mail .... but there ARE gems buried! Even if you don't study the whole thing, you might want to check out the first four or five writeups! The attached mail is the collection of write-ups I received. As usual they are mostly unedited (only personal POTM-master insults were removed). Write-ups are provided in order of finish (more or less). _________________________________________________________________ ======================================= jigsaw ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer jigsaw 212 280 646 794.83 GCC Franz Korntner ================= jigsaw was submitted by Franz Korntner at fkorntne@bazis.nl ================= LS: A cell is a entry in the 20x20 grid ++ WHERE DID jigsaw begin - short words, complex meshes, corners, etc.??? Why? Jigsaw mainly starts from the top-left corner and works it way down to the bottom-right. New words a placed in such a fashion that they fit tightly against the already placed words. Why? I've tried many other algorithms but it seems that they create 'islands' (an island is a large cluster of cells that cannot be filled with letters). The presence of islands use up valuable grid space, thus lowering the score. I've even tried island detection algorithms, but they cost too many CPU. The placing of new words can create many new grids, too many to process within the CPU time limit. To reduce calculation time, a selection must be made of grids which are to be generated. Therefore, we can be very fussy about which word will be placed where. It makes no sense to create a new grid that contains a pathological bad solution. New words are placed in the following order: - Adjecent letters are handled specially. When adjecent letters are found that do not belong to an already placed word, new grids are generated containing *ALL* word possabilities. These grids do not count against GRIDMAX (see below). - A word can *only* be placed if at least one letter of the word is already present in the grid, *AND* when newly placed letters will be adjecent to already existing letters, those letter pairs (or three-sums) must exist somewhere in the wordlist. For the nearest unprocessed letter located to the top-left corner: - If a word can be placed using the selected letter and the starting letter of that word fits tightly to the words already placed (max. one free cell distance to an existing letter), then place that word. - If no words could be found, then try placing *one* word using the selected letter in such a way that the first letter of the word is located nearest to an existing letter. Only one word may be placed as there are many combinations possible, and jigsaw must be fussy. - If still no word has been found, mark the selected letter as unprocessable and find a new letter and - Stop generating new grids when more than GRIDMAX grids have created. (unprocessed adjecent letter pairs are special and always processed). ++ HOW DID jigsaw try to maximize the number of words and intersections used? Jigsaw's algorithm needs to know how good a grid is. Good means it is candidate to get a high final score. Jigsaw continues filling grids that have high scores, and discards grids that have low scores. The scoring formula is: / This implies: - Many connectors good. If a word has more connectors it means that other words are occuping the nebouring space, thus more words will fit the grid. - Many letters bad. It's better to have two short words than one bad. The number of words are not taken into account, as all score comparisons are done with grids containg the same number of words. For comparison, I've tries some other formulas, but they didn't work out for the better. ++ Did jigsaw iterate? randomize? attempt to improve it's first solution? Jigsaw uses a non-exaustive width-first tree-search algorithm. The level on which a node resides in the tree indicates the number of words placed. The root contains no words, all nodes on the first level contain 1 word, and so on. The algorithm processes one level at a time, starting at the root. It takes NODEMAX (1500) nodes of a single level with the highest score, adds a word forming a new node of a next tree level. Once the level has been completed, all nodes of the (old) level are deleted to free memory space. This implies that there is no recallable history of how the grid was created. Duplicate grid detection is needed to compensate the lack of history. For example: ---f- your- -n-o- blank -y-t- This grid can be created by placing (in sequence) "your front blank only" or "your only blank front". If there wasn't duplicate detection, the tree would contain many of these (duplicate) combinations, effectively reducing the algorithms outcome dramaticly. ++ How did jigsaw know it was done? Simple, when no more words can be inserted into the grid. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? This scoring algorithm has one flaw. It tends to nonimate very tight grids for the first handful of words consisting mainly of short words. When the grid is about half full, only larger words can be placed that are not so tight, but there are no shorter words available anymore. One solution is to 'pollute' the levels with grids containing relatively bad scores in the hope that they might work out better when the grid is starting to get full. I've implemented poluting by giving NODEMAX a relatively low value of 1500. A better method is to add a random value to the score, but I havn't had the time to implement/test that. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I like to play games (mahjongg, talisman, dragondice), but can't really find play-pals as they prefer Magic cards. I really love POTM as there's a lot of feedback, something I can't say for IOCCC. I had a very nifty one-liner (mastermind solver) but I haven't a clue were it got placed :-( Pity as I like to pat my ego. ================================================================= ======================================= crossroads ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer crossroads 210 251 664 1746.12 C =Stan Peijffers ================= crossroads was submitted by Stan Peijffers at speijffe@hvssa01.ns-nl.att.com ================= ++ WHERE DID crossroads begin A "move" consists in putting one or more interconnected words on the board. Whether a move is better than another is based on an evaluation function. The evaluation function takes into account the following : + the number of words placed (largest factor), + for each word : - a precalculated value for the word which depends on the number of occurrences of each letter totaled over all words in the list, (avoids placement of words which are hard to interconnect with) - the length of the word, where 4 is the optimal length : (longer words are increasingly non-interesting because they take up too much space. shorter words are increasingly non-interesting because they do not generate enough connecting points, and can more easily be added toward the end when the board gets full). - the number of squares on the board that become unplayable as a result of putting the word on the board (normally this is 2) (this favors words that terminate on the edges, and words that terminate close to where previous words have terminated -> compactness) - the number of intersections created (low factor however) The move generator tries to put as many words as possible on the board (see evaluation function) in one move. To make sure that only valid combinations are generated a (recursive) check-function is embedded. The move generator is general-purpose (no special cases for corners, intersections, etc), powerful (any combination of horizontal and vertical words can be found) and fast (about 2/3 secs to fill an empty board). The move generator is called repeatedly until the board is full. Each call to the move generator is in fact a recursive call with a look-ahead of one. OK. So now we have filled up the board (after 2/3 secs of CPU). This may be a good first attempt but should be improved. ++ HOW DID crossroads try to maximize It does not attempt to maximize the number of intersections. It only attempts to maximize the number of words. ++ Did crossroads iterate? randomize? attempt to improve it's first solution? The rest of the 10 minutes worth of CPU is spent in trying to improve the solution. This is done by removing words from the solution and trying a different solution. Removal of words should be such that all the remaining words stay interconnected. This can be achieved by considering the words on the board as a graph (where the words are the nodes of the graph, and the interconnections between 2 words are the edges of the graph). From graph theory we know that there exists an O(n+e) time algorithm to compute the "articulation points" of a graph. These are the nodes (words) that leave 2 (or more) subgraphs when removed from the graph. This algorithm is used to decide which word (together with one of the subgraphs) should be removed. Articulation points are not exercized as they are detected by the algorithm : in stead 3 consecutive scans are made over all articulation points : in a first scan only those articulation points are exercized that remove many words (more than 2/3 of all the words). In a second scan medium sized changes are considered, and in a final scan only small changes are considered (a few words). [Not unlike simulated annealing]. Clearly : everytime a new solution is found which improves upon the previous best, this solution is now taken as a new starting point. This algorithm typically still does not use up all of the alloted 10 minutes : an initial solution + 3 scans of all articulation points on average uses 30 secs. Therefore the above algorithm is repeated with an empty board again and placing a different first word on the board. ++ How did crossroads know it was done? When all words have been put on the grid, or when 10 minutes were used up whichever comes first. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? I have put some ad-hoc code at the beginning of the algorithm to cater for tests that can generate a fully intermeshed raster of words (say 40 words of 20 letters each) and some variants thereof (since you never know what the POTM-master may throw at you). ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Lucent Technologies, International 5ESS SW development, Hilversum NL ================================================================= ======================================= crucigramista ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer crucigramista 207 255 643 1799.33 GCC =Andre' Wilhelmus ================= crucigramista was submitted by Andre' Wilhelmus at hvgtw!hvscg01!awilhelm@attmail.att.com ================= ++ WHERE DID crucigramista begin The first attempt starts with the shortest word in the upper left corner. Following attempts will cycle through the words and fields on the board. ++ HOW DID crucigramista try to maximize It keeps a list of untried occupied fields which could be crossed and tries to fit short words first. If a word fits it is placed on the board. If a word is placed next to another word, it maintains a list of fields which must be resolved first and goes recursive to try to fit other words on those fields. ++ Did crucigramista iterate? randomize? attempt to improve At the end, words which cross another word once are removed and replaced to see if more words can be fitted. ++ How did crucigramista know it was done? After trying to replace the last single word it saves the best solution, empties the board and starts all over again until time runs out. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? ++ COMPANY? Lucent Technologies LOCATION? Hilversum, The Netherlands JOB? maintaining programs for the factory in Huizen DO FOR FUN? playing the adventure game Monkey Island 2 on my Mac INNERMOST SECRET? bishoujo senshi... ^_^ POTM IDEAS? nope ================================================================= ======================================= knuppel ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer knuppel 201 227 613 1777.48 G++ P.Frants S.Pieterse ================= knuppel was submitted by P.Frants S.Pieterse at spieters@cs.vu.nl ================= ++ WHERE DID knuppel begin - short words, complex meshes, corners, etc.??? Why? We started out by throwing away the longest 50% of the words. This speeds up the program enormously. It is clear that short words take less space in the puzzle. The next step was to place words in the puzzle one by one using appropriate heuristics. Words placed on the borders or with many crosses were considered better than others. ++ HOW DID knuppel try to maximize the number of words and intersections used? This was achieved using appropriate heuristics ++ Did knuppel iterate? randomize? attempt to improve it's first solution? Yes, yes, yes :-) ++ How did knuppel know it was done? alarm(592) ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? First make a prototype to get acquainted with the problem. Next leave the POTM alone for about two weeks and throw away the prototype. NOW you are ready to write a killer program. Well almost, don't forget to optimize the hell out of your code! ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? We are both CS-students at Vrije Universiteit Amsterdam and like solving these POTM-style problems. Also we promise to win the next POTM :) Damn! That was our innermost secret! ================================================================= ======================================= Crozzodile ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Crozzodile 200 253 615 1112.07 GCC =Chad Hurwitz ================= Crozzodile was submitted by Chad Hurwitz at churritz@cts.com ================= ++ WHERE DID Crozzodile begin a random word placed randomly. ++ HOW DID Crozzodile try to maximize after the first random word it tried to choose words that scored well. and the scoring involved shortness of word, adjacency to puzzle edges, and count of additional words necessary to be placed for this word to be placed. ++ Did Crozzodile iterate? randomize? attempt to improve it's first solution? yes, yes, yes. my improvement algorithm wasn't very productive though. ++ How did Crozzodile know it was done? time limit. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? well, if you're unwashed (and you don't mind washing), then wash. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? vaxa, usa, well if you insist, mountains, yes, chessers (mix of checkers chess) . ================================================================= ======================================= Wordsworth ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Wordsworth 198 235 607 1788.40 C Davor Slamnig ================= Wordsworth was submitted by Davor Slamnig at slama.pub.hr!slama@ig2.att.att.com ================= ++ WHERE DID Wordsworth begin ++ HOW DID Wordsworth try to maximize the number of words ++ Did Wordsworth iterate? randomize? attempt to improve it's first solution? ++ How did Wordsworth know it was done? Wordsworth uses a simple engine which examines a set of words S1 already on the grid and crosses the words with others, which comprise the set S2. Then S2 becomes S1, etc. Initially, set S1 is one short word placed somewhere. Then the algorithm is looped until no more words can be added. This simple scheme is embellished by constructing "clusters" of 4 words, each of which intersects two other words, e.g.: c bake sit t (I was working on the construction of bigger clusters with words overlapping over a larger area, but I simply ran out of stamina). By feeding it permuted input data, this engine constructs as many crosswords as it can in the time given, and outputs the best one. The permutation goes like this: First randomize the input word-list, then sort it according to word-length. This forces the use of shorter words, and still produces a significant number of different orderings. (The actual implementation is a bit more complicated, since I use various indexing schemes). ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? Freelance contractor / Zagreb, Croatia / Application designer / Play guitar / Debugging 3rd party software takes longer than writing it yourself ================================================================= ======================================= sswordpu ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer sswordpu 192 204 587 1799.94 C Bob Ashenfelter ================= sswordpu was submitted by Bob Ashenfelter at ash@hotsoup.att.com ================= ++ WHERE DID sswordpu begin - short words, complex meshes, corners, etc.??? Why ? Short words, usually, but not the very shortest because these are some- times generated incidentally while fitting in subsequent words and I didn't want to use them up. Usually start at a random point, but some- times in the upper-left corner. Why? Because I couldn't think of any- thing better. ++ HOW DID sswordpu try to maximize the number of words and intersections used? Multiple solutions and pick the best one. ++ Did sswordpu iterate? randomize? attempt to improve it's first solution? All of the above. ++ How did sswordpu know it was done? Time limit. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Well, this appears to be the appropriate heading for a description of how it all works. For this program description, I will take a bottom-up approach. The heart of the program is a routine called addwd(i,j) which attempts to add a crossword to the grid at location (i,j) which presumably already contains a letter, but not a connector. The first thing is to decide whether the crossword goes across or down. Then it searches through all available words and, for each word, all letters in the word. When it finds a letter that matches the letter at (i,j) it checks whether the word can be used as a crossword. The ends are checked to see that it doesn't run into something previously in the grid or off the edge of the grid. Each letter of the possible crossword is then checked. If it matches a previous letter in its position in the grid, all is well. If there is a mismatch then that word at that position doesn't work. If there is a space in the grid at the position of the letter being examined, then there are several possibilities: (1) spaces on both sides of the space; (2) a single letter on either side of the space, a space on the other; (3) a single letter on both sides of the space, (4) a pre-existing word ends on one side with a space or single letter on the other side; (5) pre-existing words end on both sides. Of these, (1) is OK. (2) and (3) will create an additional 2- or 3-letter word (I call it a double- crossword) which is OK if that word is available, NG if not. (4) will add to the pre-existing word which would be OK if the augmented word is available, but I was too lazy to implement this since it would require returning the previous pre-existing word to the available word list (but only potentially, since the crossword being examined may not pan out at other letters), so (4) is considered NG. (5) will bridge two words into one and this is probably not a good idea in any case, not to mention the horrendous complications in implementing it. After all letters of the potential crossword have been approved, it is accepted as a candidate and the search goes on. After all positions for all available words have been searched, the best candidate (i.e. most words added to the grid), if any, is chosen and added to the grid and the crossword and all double- crosswords are removed from the list of available words. As you can tell, this is an excessively complicated routine! (If you can understand the above paragraph, my hat's off to you.) But as the heart of the program, it is where the game is won or lost. Probably it was a mistake not to try to implement possibility (4) despite the daunting add- itional complications. Now things get easier. The routine addwd(i,j) is used by two higher-level routines, addrnd() and addall(). In either case, there is a list of possible positions in the grid to use addwd(i,j). Routine addrnd() keeps picking from the list randomly until some number of choices result in no successful crossword being added. Routine addall() just goes through the whole list. Of course, whenever a crossword is added to the grid, the list gets longer. Either of these routines will take a partially completed grid and add words to it until they run out of steam. Routines addrnd() and addall() are used by several solver routines, each of which starts from scratch and generates a possible solution grid. Solve0() picks a random word and places it in a random spot in a blank grid and them calls addall() to add as many other words as it can. Solve1() is similar except it first calls addrnd() and then addall(). Solve2() is similar except the first word is placed in an even-numbered row and addrnd() only adds 4-letter words and only in even-numbered rows and columns; then addall() is called several times with successively larger and smaller words allowed and all positions allowed. The idea is to fill the grid up with short words before considering the long ones, hopefully getting more words in. Solve3() starts off by trying to place only 3-letter words in a special lattice that is optimum for 3-letter words; then, like solve2() it allows ever more words in all positions. Solve4() is like solve2() without the initial restrictions to even-numbered rows and columns. Solve5() is more complicated. It starts with an 8x8 grid, generates a number of solutions, and chooses the best. It then expands to 12x12 and adds words to the best solution for the smaller size. Again, it does this a number of times and chooses the best. This is repeated for 16x16 and finally for 20x20. Finally, we have come to the top. Main() starts by reading in the wordlist and computing the word lengths. It then sorts the wordlist, first by length, and then alphabetically. I can't remember why I did this but I don't make any use of it and the wordlist is immediately scrambled by the solvers, never to be re-sorted again. Then it enters an endless loop which calls each of the solvers in turn. If any solution is better than the previous best then that solution is saved as the best. Actually, on the very last day, I found that there is a bug somewhere that results in an occasional invalid grid for a certain class of wordlists. Not having the time to fix the problem, I grafted in a routine, chkgrid(), from the program I wrote at the very beginning to grade solutions and check them for validity. So a "better" solution is only saved if it passes checks for words being in the wordlist, words not repeated, and a completely connected solution. As it turned out, Fred didn't challenge us with such a wordlist. Oh yes, the endless loop really isn't endless; at various points in the program the clock is polled and when the 10 minutes are up, the best solution is printed. Most of the time, for most wordlists, solve5() ends up computing the best solution. However, because of the use of random choices, any of the them is capable of coming up with the best. For a wordlist containing only three-letter words, solve3() usually comes up with a significantly better solution. I was hoping this would give me an edge if Fred used such a wordlist. In fact, I rather expected he would; why else would he have left them out of the system test wordlist? But, once again, he put his energies into choosing clever sources for his test inputs rather than making the test inputs themselves clever. In the end the winning programs were sufficiently better than sswordpu that an all-three-letter input would not have made up the difference. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Lucent Technologies, soon to transfer back to AT&T. (Just got word that it was signed while writing this blurb.) Holdmel, N.J., U.S.A. (Will have to move some day--no longer an AT&T location.) Circuit design. (So why am I going back to AT&T? Submarine Systems.) Bicycling (new bike has been ordered), sailing (got rid of the boat...), grow orchids (big new one recently acquired, small lady-slipper in bloom on my desk), travel. No way... See questionnaire for previous POTM. ================================================================= ======================================= Binky ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Binky 189 201 596 180.13 GCC Robert Rounthwaite Sorry ... no description available for Binky ================================================================= ======================================= Gak ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Gak 188 218 559 1787.23 G++ Justin Legakis ================= Gak was submitted by Justin Legakis at legakis@cs.ucdavis.edu ================= ++ WHERE DID Gak begin Gak begins by trying to fit the words into "clumps", groups of words that fit together to form a solid rectangular block of letters. Such clumps cannot be found by solvers that attempt to place words one at a time. Gak then treats the clumps as a single unit that can be placed onto the board. ++ HOW DID Gak try to maximize the number of words and intersections used? Gak only uses 2-6 letter words. The upper limit of 6 was chosen based on experimentation. Searching for clumps of words with a solid rectangle of letters in the middle increases the number of intersections. ++ Did Gak iterate? randomize? attempt to improve it's first solution? Gak starts with a clump/word in a random place, and repeatedly tries to add clumps/words to the board. Rather than tring to juggle words around on the board, Gak tries to fill the board as fast as it can so it can start over and make as many attempts as possible. Between each attempt, the list of clumps and words is randomized. ++ How did Gak know it was done? When the time is up. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Gak was able to find the clumps of words quickly by putting all the words into a series of lists. For example, a list of words is generated for all words that have an 'r' as their first letter, or a 'u' as thier third letter, or an 'i' as their second to last letter. Gak stores the placed horizontal and vertical words separately in order to more efficiently determine if a given word will fit. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm finishing my undergraduate degree in computer science at UC Davis, and am trying to decide where to go for graduate school. I'd like to try a puzzle where the programs compete against each other, like Numbers Game, Boxing Match, or Chomp. ================================================================= ======================================= DontCrossMe ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer DontCrossMe 185 182 586 1698.50 G++ Mike Goldshteyn Sorry ... no description available for DontCrossMe ================================================================= ======================================= theos_cross ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer theos_cross 173 183 540 1457.99 GCC Theo Sprokholt ================= theos_cross was submitted by Theo Sprokholt at tsprokho@intgp1.att.com ================= ++ WHERE DID theos_cross begin First it sorted approximately 100 shortest words out of the list, since it appeared that the longest words almost never showed up in the final result. The program does a few trials with different orders of the words: - short words first - long words first - lengths 5,6,7..20,2,3,4 - lengths 4,5,6,7..20,3,2 It starts at the left top corner, placing one word horizontally, and then one word vertically. The first eight words are placed with the only restriction of having only one cross. Every next word is tried with the requirement of 4 crosses. If that does not succeed, 3, 2, or 1 cross is allowed. This is repeated until all words are tried to fit in. ++ HOW DID theos_cross try to maximize The number of crosses are set to a minimum value while trying to place a word. When no word can make it with this requirement, the level is lowered until at least 1. ++ Did theos_cross iterate? randomize? The best solution is stored. After every new trial, it is verified if that solution is better, if so, that one was stored as best one. There was some postprocessing done by removing the 2, 3 and 4 letter words that had only one cross. These words were tried to fit at different locations. Maybe that results in new gaps for other words. ++ How did theos_cross know it was done? It did a fixed number of trials with the words sorted in different orders. It tried to do as much as possible in the 10 minutes. It uses a unix signal after 9:55 minutes to show the best found solution. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Throw away all the longest words, they only consume a lot of space but don't contribute to the word count. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Theo Sprokholt Lucent Technologies, Hilversum, the Netherlands. Software development engineer for 5ESS software and firmware for peripherals. ================================================================= ======================================= 2RoadsCroz ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer 2RoadsCroz 173 177 571 1504.98 C Gary Gressel ================= 2RoadsCroz was submitted by Gary Gressel at ggressel@attmail.com ================= ++ WHERE DID 2RoadsCroz begin It reorganized the word list into a variety of orders (short, long, common letters, etc.) and then tried starting with different words in each of the lists in different spots on the board. ++ HOW DID 2RoadsCroz try to maximize The code worked its way through different word sorts and starting positions for the first word for the first 5 minutes. After 5 minutes the program looked at its best word sort order and tried numerous additional combinations for that wordlist. At just before 10 minutes, the program produced its best result. The functions which handled complex meshes never got completed due to work actually expecting me to spend time on their projects instead of my own! ++ Did 2RoadsCroz iterate? randomize? attempt to improve it's first solution? After 5 minutes it attempted to improve on the best solution at that time. I didn't use random generation--didn't want to realize that the program _could_ have won had the random generator been different. ++ How did 2RoadsCroz know it was done? Generally speaking a time limit. There were a set number of combinations it would try, but as long as the word list was of any significant size, the time limit would be reached first. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Nothing much has changed other than my company...I now work for "The New AT&T" instead of just AT&T. Btw, have we filed for that with the FCC yet? I'm a Programmer/Security/Disaster Recovery/Administrator for AT&T in Kansas City, MO. Oh, and am getting married June 1st; just as work distracted me the last 2 months of this contest, that marriage thing will do it for the next POTM; hope you can get the puzzle out soon! ================================================================= ======================================= CrossIt ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer CrossIt 173 171 590 1642.85 C Dennis Brooks ================= CrossIt was submitted by Dennis Brooks at dab@aloft.att.com ================= ++ WHERE DID CrossIt begin It begins with the "best" words. Each word receives a figure of merit based on the frequency of use of each letter in the entire word list and normalized to the length of the word. The normalization removes any bias pertaining to word length. The "best" word is the word with the highest figure of merit and is placed horizontally in the center of the grid. The next "best" word is placed vertically; if a connector letter can be found. The building continues with horizontal and then vertical placements. ++ HOW DID CrossIt try to maximize the number of words and intersections used? Only the number of words was maximized. This was done using iteration. The puzzle is actually done 80 times using 80 different "fudge factors". The "fudge factor" derates long words. A "fudge factor" of 0% does not derate long words. A "fudge factor" of 100% derates the longest word such that its' figure of merit is 0 and it will become the last word to try and be placed. Fudge factors from 20% to 100% were used. ++ Did CrossIt iterate? randomize? attempt to improve it's first solution? It iterates using 80 different "fudge factors". ++ How did CrossIt know it was done? After completing all 80 (actually 81) tries, the one with the most number of words, highest number of connectors, and highest number of overall letters was outputted. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? ++ COMPANY? Lucent Technologies. ++ LOCATION? 1247 S. Cedar Crest Blvd. Allentown, Pa. ++ JOB? Circuit designer of DSP Integrated Circuits. ++ DO FOR FUN? Write computer programs. ++ INNERMOST SECRET? ++ POTM IDEAS? Keep up the good work. Your promptness, thoroughness, and sense of humor are what make it fun to compete. ================================================================= ======================================= alphaCross ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer alphaCross 170 202 640 678.19 C++ Glenn Bradford ================= alphaCross was submitted by Glenn Bradford at jupiter!gmb@ffast.ffast.att.com ================= ++ WHERE DID alphaCross begin? In a corner. At first I tried centering the first two crossed words in the middle of the grid, but I found that the final solns had holes in the hard to get corners. So I figured to start in one corner, and at least nail one of them. It seemed to give better scores. ++ HOW DID alphaCross try to maximize When presented with a letter on the board that I wanted to cross with a word, I searched through all the available words with that letter and for those that fit, I scored each on how many intersections they made. The word making the most intersections won the spot. I didn't do a great job maximizing words. For example, I didn't attempt to fit smaller words first. I experimented with this but it tended to choke the solution. A smarter way, perhaps, judging from the finals lists, would have been to "prefer" smaller words, or at least stay away from the longest ones, but I didn't do this. I had "wissenschaftliches" in the german soln! My results were near the top in letters used, for this reason. ++ Did alphaCross iterate? randomize? attempt to improve it's first solution? I put every word in a corner and crossed it with every other word that would fit it in the corner square. I did this for all four corners. Then I recursively, in a depth first manner, placed words in a long string, alternating between crosswise and downward words until no more words could fit. Words running in the same direction were always separated by at least one blank square, which I called 'the non-packed scheme'. I scored the grid and saved the best running soln. ++ How did alphaCross know it was done? When it had tried all solns starting with every pair of words connected in all four corners. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Advice: Don't participate in a POTM if you know you are going to have a baby anytime before the deadline. One trick I used was to denote '#' as a black square (like on a real crossword puzzle) internally. At some point I decided to try to place words side-by-side, like in a real crossword puzzle. I strongly suspected that Fred would choose a real crossword puzzle soln. for the finals (which he didn't!), and while I didn't imagine my program could recreate it all, I was going to try to recreate part of it. So I abandoned the "corner" method above and tried a two phase attack. First, start the grid with a partial soln. with about 10-20 words packed closel y together, with as many intersections as possible. Second, use the standard non-packed algorithm to finish the puzzle. Packing was hard, but on the night of the deadline, I thought I had it mostly working. The system test file made it dump core, though, and I wasted most of the night trying to debug it, to no avail. For other test files I made up, it worked OK. I took a chance. I was extremely tired. I mailed Fred a version that had no output. I had commented out the print routine by mistake just before I mailed it! He was nice enough to use my last version, which is just as well. When I got the finals lists the next day, I ran my packed version program and got slightly better results, but the german list, with all its long words, could not be packed well and my program ran for a long time, over an hour, trying to pack it. I didn't have time to put in an alarm to tell my program its time was up. As an example of packing, here is the output from the packing phase on the worldnet list: -------------------- -------------------- -------------------- -------------------- -------------------- ------s------------- ------e----s-------- ------r----e-------- ------v--p-l-------- ------i-truly------- ------choose-------- ------e--very------- ------s--i-security- ---------d--top----- ---------e---n------ ---------r---n------ ---------s---e------ -------------c------ -------------t------ -------------------- number of words = 13 number of conns = 20 number of letrs = 47 And the final solution after the second phase: -p--bringing-with-s- -how-------o-a----i- -o-information--p-n- -n-loo-----n-through -e-l-r-using--i-r-l- --r-b-s-a---together -we-o-e-m--s--h-a--- --att-r-e-key--bbn-f its-have-p-l----l--i n-o---i-truly-them-n t-n---choose-----and risks-e--very----t-- o---easy-i-security- d-a-e--o-d--top--e-t u-c-k-buyers-n-worth c-c-e-a--r---n-e---e their-close-set--way i-s-s-k-u----c-n-h-- o-s-----traditional- n----------o--t--t-- number of words = 63 number of conns = 75 number of letrs = 223 It did only 2 words better than my totally unpacked soln. ++ COMPANY? Lucent LOCATION? Red Hill JOB? Software Developer, TDIL Operations System DO FOR FUN? tennis, racquetball, woodworking INNERMOST SECRET? fib to my wife so I can work on POTM POTM IDEAS? some kind of packing problem? ================================================================= ======================================= WordMatrix ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer WordMatrix 170 173 578 1794.57 C Annemarie Kram ================= WordMatrix was submitted by Annemarie Kram at akram@xs4all.nl ================= ++ WHERE DID WordMatrix begin Shortest word, with most used letters, every possible place. Why not? ++ HOW DID WordMatrix try to maximize Not ++ Did WordMatrix iterate? randomize? generate all. ++ How did WordMatrix know it was done? All solutions tested or time. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? None, Delft, Nurse, Yes, Just Guess, {Integer arithmetic, knapsack, balistics, go, 4-in-a-row, nesting) ================================================================= ======================================= nonplussed ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer nonplussed 168 175 532 71.44 C Greg Marston Sorry ... no description available for nonplussed ================================================================= ======================================= Crozzilla ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Crozzilla 167 182 557 112.34 C++ James Rothenberger Sorry ... no description available for Crozzilla ================================================================= ======================================= mash ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer mash 163 170 597 1651.39 C Dave Lynch ================= mash was submitted by Dave Lynch at dfl@esun.att.com ================= ++ WHERE DID mash begin - short words, complex meshes, corners, etc.??? Why? Started with a randomly sorted list of words greater than 2 letters, using only alternate rows and columns. First word was placed randomly. When there were no more opportunities, I also considered the 2-letter words and all rows and columns. ++ HOW DID mash try to maximize the number of words and intersections used? Brute force and repeated trials. ++ Did mash iterate? randomize? attempt to improve it's first solution? Made repeated attempts with different list orderings and different starting points, keeping the best solution. Wanted to implement a local search improvement scheme, but had to attend to other areas of my life. ++ How did mash know it was done? Out of time. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? Last I heard, I'm in AT&T in Holmdel. POTM IDEAS? How to keep upper management from laying off, outsourcing, etc., so many people. ================================================================= ======================================= santacroz ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer santacroz 156 172 611 12.79 C Ag Primatic Sorry ... no description available for santacroz ================================================================= ======================================= CrossEyed ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer CrossEyed 147 151 606 1232.29 GCC Randy Saint ================= CrossEyed was submitted by Randy Saint at saint@phoenix.phoenix.net ================= ++ WHERE DID CrossEyed begin First started with a sorted list based with most number of "popular" letters first. Then tried random lists. ++ HOW DID CrossEyed try to maximize Words were tried from the list, if they fit they were put on the board and move on to the next word. ++ Did CrossEyed iterate? randomize? Tried recursion, but it was too time consuming for little gain. Used random beginning lists and stopped once it could not put any more words from the list on the board. ++ How did CrossEyed know it was done? Used a fixed number of random lists and tried starting with each. Saved best solution. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? I submitted early with plans for improvements... I was glad I did. I got too busy with other things and didn't get back to it. ++ COMPANY? Loral LOCATION? Houston, TX JOB? Systems Analyst DO FOR FUN? Sling Code INNERMOST SECRET? My boss thinks I use the internet to do "market research" POTM IDEAS? I like the extra "awards" that are presented! Keep it up! --- Randy & Marianne Saint Houston, TX saint@phoenix.phoenix.net http://www.phoenix.net/~saint ================================================================= ======================================= lacrosse ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer lacrosse 145 150 417 1795.53 C Mark Schnitzius Sorry ... no description available for lacrosse ================================================================= ======================================= RedCrozzleDevils ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer RedCrozzleDevils 144 144 483 1614.49 G++ Peter Conrad ================= RedCrozzleDevils was submitted by Peter Conrad at conrad@unix-ag.uni-kl.de ================= ++ WHERE DID RedCrozzleDevils begin We use a function depending on the length of the word and the letters in each word to determine the 'quality' of a word. Letters that appeared more often in the wordlist were 'better' letters, words of (I think) 5 letters have 'best' length. We choose one of the 'best' words in the list and place it in the middle of our grid. Then we try to add more words in any direction until the maximum size of the grid is reached. ++ HOW DID RedCrozzleDevils try to maximize After each step we try to place each of the remaining word in each place of the grid. Every combination of the word/grid-position is assigned a value depending on the 'quality' of the word and the number of intersections caused by the word. We then choose one of the 'best' of these combinations. ++ Did RedCrozzleDevils iterate? randomize? We use a non-deterministic approach. In each step we choose (more or less) randomly a word to place, until no more words can be placed. So we find a solution pretty quickly. We remember the best solution, and after nearly ten minutes of computing time the best solution so far is printed to stdout. So with a bit of luck we *could* have won... ;-) ++ How did RedCrozzleDevils know it was done? See above, after a predetermined amount of time. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? *We* are a team, consisting of Nils Magnus, magnus@unix-ag.uni-kl.de, and myself, conrad@unix-ag.uni-kl.de. Since we were both pretty busy during the last months, our entry to this contest was more of the 'quick hack' type. This may change in the future... :-) ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? We're both students of CS at the Universitaet Kaiserslautern, Germany. We've taken part in several other contests in the past, and we've always had a lot of fun. ================================================================= ======================================= CUTE ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer CUTE 143 144 566 1611.11 C Corin Anderson ================= CUTE was submitted by Corin Anderson at corin@cs.washington.edu ================= ++ WHERE DID CUTE begin - short words, complex meshes, corners, etc.??? Why? CUTE (Crossword Utilization Transmogrifying Engine) begins with some word at random dropped into the center of the board. From there, random words were chosen and attempted to be placed at random positions. Legal moves were kept and illegal moves were discarded. I chose this strategy because it seemed like the easiest to program. I didn't have to perform any analysis of the input words and pay close attention to how the board was being filled in. I betted that fast and furious would be just as effective as slow and sure. Unfortunately, CUTE failed on the fast part (lots of simple strcpy()s), so I couldn't try a whole lot of possible word combinations. ++ HOW DID CUTE try to maximize the number of words and intersections used? CUTE really didn't pay attention to the number of words and intersections explicitly. The basic algorithm was random sampling of the solution space and choosing the highest score. Because the scoring function weighted more words higher than more intersections, CUTE followed these basic rules. ++ Did CUTE iterate? randomize? attempt to improve it's first solution? As hinted as earlier, CUTE would fill in a board as much as possible and compare its score to a known current best score. If the current board's score exceeded the best score, CUTE replaced the best score (and its board) with the current. Each board examined was generated by randomly selecting words and positions, as described earlier. Each board was generated independently of previous boards. ++ How did CUTE know it was done? CUTE had a little wrist watch that it checked frequently. Once about 5 and a half minutes elapsed, CUTE settled with the best-known-good board and quit. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm presently an undergraduate at the University of Washington, and will be a graduate student this fall here. I take part in the POTM contest because I really like doing programming contests and showing off my C skills. Besides, it's a lot of fun! ================================================================= ======================================= SundayTimes ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer SundayTimes 136 140 491 41.17 C++ Joe Eccles ================= SundayTimes was submitted by Joe Eccles at mink!joe@ffast.ffast.att.com ================= ++ WHERE DID SundayTimes begin Started with longest words first. Just by experimentation, this usually fared better then starting with long words first. ++ HOW DID SundayTimes try to maximize The version entered simply started trying to add words, shortest first, then repeat the list until a traversal failed to add any new words to the board. The first word was added to the center of a 40x40 board, and as any word was added, the size of the board was shrunk to ensure that any new words added woul d be within a 20x20 sub-board. This eliminated the decision of where on the board the first word would go. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? AT&T, Middletown NJ ================================================================= ======================================= krozz-it ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer krozz-it 132 138 400 1166.40 C Jan Venema Sorry ... no description available for krozz-it ================================================================= ======================================= Cross-Stitch ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Cross-Stitch 129 188 427 1023.72 C Alex Popiel ++ WHERE DID Cross-Stitch begin Cross-Stitch began by sorting the input words by length, and then building huge tables of (a) lengths, (b) letter occurences, (c) two-letter combination occurences, and (d) known impossible word adjacencies. (The last table there is a table of all words by all words by all offsets such that if the first word may be laid parallel immediately above/left the second word at the designated offset and still yield a legal grid, the table contains a true value.) After the tables are built, Cross-Stitch picks a word at random, placing it in the center of an oversized grid (the grid is oversized and floating boundaries are maintained so that there is no confusion about shifting everything to the left one square or some such nonsense). A second word is picked, and laid below the first word. Crossing words are chosen for all places where two letters are adjacent, via depth first recursive search until a legal grid is formed. This legal grid is placed in a priority queue of partial solutions, and the process is repeated a few hundred times. The top few entries of the priority queue are then improved upon, through attempts to add words parallel to existing words (followed by cross-filling), or words inserted perpendicular to existing words (again followed by cross- filling). The new solutions (which always have more words than the original) are inserted into the priority queue. If a solution cannot be improved, it is compared to the best solution to date, possibly replacing it. This process of incremental improvement is repeated until a magic number of unimprovables have been encountered, at which time the entire queue is deemed "stale" and wiped. New grids are then generated as described in the preceeding paragraph. Cross-Stitch continues this cycle of iterative improvement until it runs out of time, after which it prints out the best it has. ++ HOW DID Cross-Stitch try to maximize Cross-Stitch miximized wordcount by heavy emphasis on complex meshes. unforunately, I was unable to come up with an intelligent way of building good meshes, so I relied on random chance. This yielded decent solutions, but not great ones. ++ Did Cross-Stitch iterate? randomize? All of the above, at different levels. It iterated through the improvement cycle, which used randomization internally. ++ How did Cross-Stitch know it was done? It knew any particular grid was done by being unable to add words to it. It knew the run was done when time ran out. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Cross-Stitch was an exploration into many ideas that did not work. My first implementation used a fixed 20x20 grid to build stuff in; this proved to be overly arbitrary, denying certain avenues of expansion because all the free space was divided on opposite edges instead of being on one side or other. I tried a number of "intelligent" improvers, all of which took too much time for results. At one point, I was spending over three minutes of runtime generating the (d) table (yielding more early cutoffs in the improvers), but it turned out that the time was better spent trying combinations. Data structures were also very important; changing the storage methods for various information yielded 20:1 speed improvements on a couple occasions. One of the traps I fell into was duplicate code. Nearly all my improver code is duplicated for each of horizontal and vertical alignments. This became a problem as I neared the 25K source limit. The one benefit is that the loops are optimized for each of the alignments, sometimes iterating in row-major order, and sometimes in column-major. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Company? Please. Location? Initial meetings in public places. Job? He was persecuted by Yahweh. Do for fun? Sure. Innermost secret? Not here. POTM ideas? Gibberish generators. ================================================================= ======================================= manhattan ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer manhattan 126 136 413 1141.31 GCC Michael Strauch ================= manhattan submitted by Michael Strauch at strauch.bbs@sx1.hrz.uni-dortmund.de ================= ++ WHERE DID manhattan begin Manhattan starts in the middle of the grid, inserting the first word from the list with six characters (or less, if there is no such word). The idea was to start with a short word (leaving much space for other words), but not too short (to prevent being stuck at the beginning). ++ HOW DID manhattan try to maximize Manhattan does only try to maximize the number of words, it does not care for the number of intersections. ++ Did manhattan iterate? randomize? attempt to improve it's first solution? Manhattan uses two different strategies, one completely deterministic and one random strategy. (A) Remove one word from the current grid, make a depth search trying to insert at least two words (so you get at least one word more than before). If no such two words are found, reinsert the removed word, and repeat the same with the next word from the current grid. (B) Remove up to 8 words randomly from the grid, then try to fill as many words as possible from the list of remaining words, starting with a randomly choosen one. Accept the resulting grid if it contains at least as many words as before, with a possible loss of up to four words. Do not accept the grid if the words in the resulting grid are not connected. These two strategies are applied as follows: (1) strategy A is used as long as the depth search works (increasing the number of words by one in each step) (2) when (A) fails, strategy B is used up to ten times; do not apply strategy (B) any more if more words could be inserted than in step (1) (3) if enough time is left, go to step (1) One problem "Manhattan" had to deal with was: when is it allowed to insert one word near to another word (so you need other words crossing the first two ones)? So if this case occurs, manhattan makes a complete depth search to find out if there are enough other words in the list to fill the cross points. This is the slowest part of the whole program, but I had no good idea how to improve this. ++ How did manhattan know it was done? Manhattan stops if the time is up. I should have better checked the time more frequently. (sigh) ================================================================= ======================================= CrozzApp ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer CrozzApp 120 128 381 552.08 JAVA James Rothenberger ================= CrozzApp was submitted by James Rothenberger at jar@rdga3.att.com ================= ++ WHERE DID CrozzApp begin In the center, just a best guess. I didn't have time to try multiple solutions for the first placement. ++ HOW DID CrozzApp try to maximize the number of words and intersections used? I created many placement algorithms (27), ran all, kept track of the results and spit out the best one as the answer. These algorithms included placement towards edges, placement towards middle, probability of placement by letter content, length, collisions with other words, gravity towards center of puzzle, among others. ++ Did CrozzApp iterate? randomize? attempt to improve it's first solution? It was more of a recursion than an iteration. There was nothing random about it. It did not try to improve on a solution, just try a different approach (certainly not the optimal solution). ++ How did CrozzApp know it was done? It was done when it tried all possible strategies. Completion time was not an issue in the C++ program (ran in less than a minute). JAVA program took SUBSTANTIALLY longer to run, but I took a chance that it would finish in the allotted time (no built-in timer). ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? This was great fun, hope to participate again!! ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Software Developer Lucent Technologies (Formerly AT&T) Reading, PA Do for fun? Check my homepage! Inside Lucent, AT&T - http://rdga3.att.com/~jar Outside - http://www.clever.net/bitwise/jar ================================================================= ======================================= WizardOfCrozz ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer WizardOfCrozz 119 135 645 905.76 GCC Chris Hendrie ================= WizardOfCrozz was submitted by Chris Hendrie at cihendri@uwaterloo.ca ================= ++ WHERE DID WizardOfCrozz begin WizardOfCrozz employs a simple brute-force strategy, trying to use big words with frequently-occuring letters first. It assembles a puzzle one word at a time, depth first. (best I could do in the 8 hours before the deadline...) ++ HOW DID WizardOfCrozz try to maximize See above. ++ Did WizardOfCrozz iterate? randomize? attempt to improve It uses randomization to select which site to attempt to connect to next. This improves things a bit. ++ How did WizardOfCrozz know it was done? It keeps recursing, trying every possible 'simple' crossword puzzle, until it runs out of time. Unfortunately, it doesn't seem to accomplish much after the first 10 seconds or so. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Next time I'm using C++ instead of C. Relentless optimization was the wrong track: I would have been better off writing cleaner code and perfecting my algorithm. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? I'm a second year Computer Science student at the University of Waterloo. I am currently looking for a summer job. Fun? With final exams around the corner? Christopher Hendrie * Shad Valley 93A * IMO 94 * UW Comp.Sci 98 ACM ICPC 96 * http://www.undergrad.math.uwaterloo.ca/~cihendri/ ================================================================= ======================================= mots ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer mots 114 115 394 18.30 C Ralph Meira ================= mots was submitted by Ralph Meira at ralph.meira@sophia.attgis.com ================= ++ WHERE DID mots begin Mid-sized words (5 letters), then 4 & 6, then 7 & 3, .... and so on. I used the concept of work area: words would be linked, and each time round, my program would calculate the potential work-area around the existing words: e.g.: for a 3x3 Matrix with word "You" already in there. - - - - - - Y O U - - - - - - ++ HOW DID mots try to maximize the number of words and intersections used? Mots did a histogram of letters used and then weighed the existing words sorting them first by size (as previously mentioned) and then by the letter-weighting. ++ Did mots iterate? randomize? attempt to improve it's first solution? Mots skipped words it could not fit in, but iterated back once on those same words - just in case. ++ How did mots know it was done? Once the program had executed the steps necessary ... that was it. I just wanted to have an POTM-entry out there, and I was happy to have one that did a reasonable job in less than 1 second (at least on my machine). ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? It's been 2.5 years since I last did something in C, so it was great fun ! ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? NCR CORPORATION (formerly AT&T GIS) SOPHIA-ANTIPOLIS SOUTH OF FRANCE FINANCIALS AND ORDER SYSTEMS SUPPORT FOR EUROPE, MIDDLE EAST, AFRICA REGION. I'M GETTING ALL MY TEAM TO ENTER THE NEXT POTM. PLUS A FEW PEOPLE I KNOW AROUND THE GLOBE. ================================================================= ======================================= Crozzlometry ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Crozzlometry 108 113 532 387.82 C Brace Stout Sorry ... no description available for Crozzlometry ================================================================= ======================================= Bhagvan ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Bhagvan 101 113 431 1204.23 G++ Bhagvan Konmadi ================= Bhagvan was submitted by Bhagvan Konmadi at gt4501c@prism.gatech.edu ================= ++ WHERE DID Bhagvan begin Started off with long word , thought will get more connections,hence more words. ++ HOW DID Bhagvan try to maximize try with a next long word. ++ Did Bhagvan iterate? randomize? attempt to improve it's first solution? yes, iterate till you get maximum words ++ How did Bhagvan know it was done? just a guess. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? bad guess , hence the result ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Research Assistant,Georgia Tech,Industrial systems engineering do for fun. ================================================================= ======================================= crozzlectomy ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer crozzlectomy 50 47 171 1781.69 KSH =Fred Hicinbothem ================= crozzlectomy was submitted by Fred Hicinbothem at fah@ffast.ffast.att.com ================= ++ WHERE DID crozzlectomy begin upper left going across, then took the third letter and worked down, then took the third letter and worked across, etc., etc. ... guarantees no conflicts that way but makes for a real low score. ++ HOW DID crozzlectomy try to maximize It was tough enough just getting ANYTHING to work within the time constraints when using a shell language (at least for ME!) ++ Did crozzlectomy iterate? randomize? Ha! The code WAS recursive though ... recursive shell functions ... imagine! ++ How did crozzlectomy know it was done? It was done when it reached the lower right hand corner or fell off the board! ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? Learn to program - giving up your day job helps as well ... ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? AT&T (honest) in West Long Branch New Jersey USA ... I do software architecture and requirements and proposals and stuff like that for a living, so the POTM offers the opportunity to communicate with REAL programmers. ================================================================= ======================================= Croissant ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Croissant 26 23 164 0.45 C++ David Peterson ================= Croissant was submitted by David Peterson at dpeterso@isd.net ================= ++ WHERE DID Croissant begin Center. Allowed the greatest number of possible connections from the highest scoring word alternating up and down. ++ HOW DID Croissant try to maximize the number of words and intersections used ? Used the letter frequency and letter count to sort the words. ++ Did Croissant iterate? randomize? It did not. ++ How did Croissant know it was done? It was done with the center word. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? C-Applied Systems, Inc. L-Bloomington, MN J-Senior Systems Analyst D-Surf the Web I-Hate Windows programming P-Random walk through Dinky Town or Traveling Tony's Shortest Journey ================================================================= ======================================= Just_Becroz ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer Just_Becroz 6 3 35 0.33 C Scott Everett ================= Just_Becroz was submitted by Scott Everett at severett@intgp1.att.com ================= ++ WHERE DID Just_Becroz begin The program created a sorted list of words. It placed the words sharing common letters with other words higher on the sorted list. This way, a word like "zzzz" would not be examined over a word like "the". Within this sort, words of equal value that were shorter were placed above longer words. ++ HOW DID Just_Becroz try to maximize Insufficient time to work on the program due to job requirements. ++ Did Just_Becroz iterate? randomize? See above ++ How did Just_Becroz know it was done? It was planned to monitor time and end before time was up. Then it would print best solution found. ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? The program knew that if a word was placed horizontally in the 3rd through 5th columns that only those columns should be examined for potential placement of vertical words. Thus, the entire puzzle did not have to be searched after each move. Further, a look ahead of only one move was programmed and I was going to implement back-up moves. In order to keep track of moves I kept a move list showing all moves made so that the moves could be popped off the stack if a dead end was reached. Before backing up from a dead end I save the current score of the puzzle and what it looked like. That way, the most optimal solution is always known up to that point. If time would run out then I compare saved solution to current puzzle and print the one with the highest score. Unfortunately, this last piece of the puzzle was never finished due to work load. ++ COMPANY? LOCATION? JOB? DO FOR FUN? INNERMOST SECRET? POTM IDEAS? Lucent Technologies. Indian Hill (Illinois). GlobeView ATM Development. Ski, Water Ski, Tennis, Wind Surf, Read, ... Love POTM puzzles Develop programs that fight other programs (like two programs that take turns making tic-tac-toe moves). The competition would take place on a tournament ladder system until a winner was found. It would not be tic-tac-toe, since too easy to deadlock and everyone knows how to do that one. Design a different type of competition. ================================================================= ======================================= one ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer one 3 0 13 0.27 C++ Ionel Vasilescu Sorry ... no description available for one ================================================================= ======================================= hongtao ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer hongtao 0 0 0 0.00 C++ Hongtao Gu Sorry ... no description available for hongtao ================================================================= ======================================= xid ============= ================================================================= ENTRY WORDS CONNS LETTR Seconds LANG Programmer xid 0 0 0 0.00 C Ken Weinert ================= xid was submitted by Ken Weinert at kenw@ihs.com ================= ++ WHERE DID xid begin - short words, complex meshes, corners, etc.??? Why? ++ HOW DID xid try to maximize the number of words and intersections used? The intent was to start in the middle with the two longest words and work my way down the list. ++ Did xid iterate? randomize? attempt to improve it's first solution? iterate over the sorted list, longest to shortest. ++ How did xid know it was done? no new "transactions" ++ ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER? if I didn't have a real job or three, xid would have gone beyond the concept phase. =================================================================