[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionHere's a "Word Finder" game. The object is to find hidden words in a random array of letters. Words are formed by moving vertically, horizontally or diagonally from letter to letter, without revisiting any letter.
This example contains 105 words from three to seven letters in length. How many can you find? (Partial answer at bottom of this page)
Background & TechniquesAkerue was the name used by Borland when they published it as part of a Word Wizard package written in Turbo Pascal (DOS). This was many years ago - mid 1980's as I recall. Use the Unscramble program in Wordfinder2 if you can't figure out what Akerue might anagram to. Non programmers are welcome to read on, but may want to skip to the bottom of the page to download the executable file. Notes for ProgrammersThis program is not quite finished, but other duties are pressing, so I decided to publish as is and leave the completion as an exercise for the reader. I did do the most fun part, deriving the algorithm to find all words in a given array. Random letters are generated in approximate frequencies matching their frequency of occurrence in the English language. How do we do this? Many tables of letter frequencies have been published, I just selected one off of the Web. The numbers reflect the number of occurrences per 1000 letters. So we'll make a table of cumulative frequencies, generate a random number between 0 and 999 and then see where that number falls in our table. For example A, B, and C occur with frequencies 73, 9, and 30 respectively - so the first four entries in our table are 0, 73, 82, 112. If we generate a random value between 0 and 72, we'll generate an A, between 73 and 81, represents a B, etc. Searching out all words in the larger arrays, especially the 6X6, can take a few minutes. To minimize the wait once the user gives up and clicks the "Computer's Turn" button, I used an Application.OnIdle exit to overlap program search time with user think time. The OnIdle exit is called whenever the program has no other activity going on. It's much simpler and has fewer pitfalls than implementing thread processing. I guess still runs as a separate thread though, so be cautious about terminating the program with the debugger (i.e. Ctrl-F2, or Ctrl-F9). It is possible to leave the process running and not be able to recompile until you reboot the system. I'm not sure what really goes on, but if you let the program finish or end it with the Stop or Close buttons, all works OK. I added TMediaPlayer components and load three sound files (OK.wav, Addword.wav and Invalid.wav) to provide audible feedback for letter entry, word addition, and invalid clicks. Finally, the path searching algorithm for words: Each letter position has a maximum of eight eligible neighbors to check. A Paths doubly dimensioned dynamic array is initialized with "sentinel" values (I used Maxint, a predefined Delphi constant representing the maximum integer value) as a border. This avoids testing offset values to see if they are valid - the Paths array ranges from [0,0] to [boardsize+1, boardsize+1] but we check paths between [1,1] and [boardsize, boardsize]. The GetNextPath routine is the heart of the search procedure. It calls CouldBeWord to stop the search down a particular path when there are no more words in the dictionary beginning with these letters. If CouldBeWord returns true that position is marked as visited (with the PathCount field) so we don't visit it again on this search. CouldBeWord also tells us if we actually have a word. If so it is added to the wordlist and then we recursively call GetNextPath starting at that point and passing the new PartialWord string. When CouldBeWord returns false, we check the next neighbor, etc. When all directions have been checked, we back up by "unvisiting" that location and exit. There is some OnDrawCell code used to visually show progress during the "Computer Turn" phase - but I'll let you check that out on your own. Addendum May 6,2005: A viewer had written asking if the program could be converted to use keyboard input because she had trouble double clicking to end a word. I wasn't ambitious enough to do that, but I did improve the word end signaling by accepting a second click on the last letter of the word or a right click anywhere to indicate that the word is complete. While into it, I also improve the "Levels of Play" implementation. The original concept was to use "small", :medium" and "large" dictionaries for "Easy". Medium" and "Hard" levels of play. The problem with abbreviated dictionaries was that words that players entered were often not recognized, so I ended using the large dictionary for all levels. The new implementation uses the large dictionary for checking user input but the smaller dictionaries for the computer word search for "easy" and "Medium" levels. Note for Programmers: The sound effects files are now in a resource file included in the executable so are no longer needed as separate ".Wav" files. The source zipped file now includes Genres.bat which runs Delphi's Resource Compiler to read AkerueSounds.RC and produce AkerueSounds.RES which is included in the Akerue.DPR project file. You can check the source to see the steps necessary to load the sounds into memory at startup time and call PlaySound to play the appropriate sounds. Addendum May 23, 2006: I finally got around to allowing Keyboard entry of words as well as some other changes and features:
June 1,2006: Viewer Jeff Bratt is a programmer/photographer/woodworker who has been spending too much time playing with last week's version. Being a programmer, he also knows how to spot bugs when he sees them so Akerue Version 4.1 was posted today to fix problems he's found including:
Thanks Jeff, the program is much improved as a result of all your "work". November 13, 2016: A viewer recently wrote about problems running Akerue after compiling it with the new Delphi 10.1 Berlin edition. It urns out that the problem was in the UDict dictionary unit which requires ANSI string {1 byte per character) but the new String definition uses wide characters (2 bytes per character). The revised unit has been updated in our DFF Source Code Library file which will be required for recompiling this program (see below). . Running/Exploring the Program
Suggestions for Further Explorations
Partial answer for sample grid: ELITE, ENTER, ENTIRE, EON, FEN, FIN, ....... ONE, RIFE, RITE, TIC, TILE, TIN, TINT, TINTER, TIRE, TRITE. (The seven letter words are INCITER and NITRITE.)
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |