Akerue - Word Finder Game

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

Here'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. 

O E L I
F N N I
C I T T
I I R E

This example contains 105 words from three to seven letters in length.   How many can you find? (Partial answer at bottom of this page)

 


Select letters in the program by clicking and enter the word (or start a new word) by double clicking.  Scoring is:  no score for 1 or 2-letter words, 3 to 7-letter words score 1 to 5 points respectively,  8- letter words are worth 10, 9-letter words are worth 15, and 10 letters or more earn 20 points per word.   Take as long as you want, find all the words you can, then click  the "Computer's Turn" button.  It will find the words you didn't find.  and compute his score based on those words.  (I haven't come close to winning yet.)

Background & Techniques

Akerue 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 Programmers

This 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:

bullet Words may be entered by keyboard or mouse clicks.   For earlier versions with mouse only input, only valid letter paths  were accepted.   When the user clicked to end a word,  it only needed to be in the dictionary to be valid.  With keyboard entry, two tests must be met:  the word must be in the dictionary and we must also be able form this from adjacent letters.   As a result, there is now a delay of a few seconds when play is started while the program builds its complete list of valid words.  All user input words are now checked against this list.    
bullet Easy, Medium, Hard levels are gone - users now select board size and dictionary size as separate options.  Each board size has a an associated  default dictionary.
bullet Words lists for each dictionary level specify temporary additions or deletions for the permanent dictionary.  If you enter a word that is missing from the dictionary you can force the program to accept it.  Just remember, that from then on, that word will be fair game for Akerue to find also.   Clicking words in Akerue's answer list will add it to the "Ignored" word list.   The lists (6 in all:  "Added" and "Ignored" for each of the three dictionary sizes) are saved in text files and retained from run to run.     You may also download the "Dicmaint" program  from our WordStuff3 page and apply word list additions to your own dictionaries.
bullet A timer may be activated and used to limit game times. 
bullet A "classic" color scheme (yellow text on blue background) may be set or reset by a menu option.
bullet All of your program settings are retained from run run to run.  
bullet Default dictionaries have been renamed to "AkerueSmall.dic", "AkerueMedium,dic", and "AkerueLarge.dic"  and   are now included in the source and executable zip files.

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:

  • Invalid words could be added to the added words list even when there was no path to it.
  • If a word was entered via keyboard after entering a word with mouse clicks, the first letter was not entered.
  • Invalid word was not reset after mouse entry.  The next word accepted the invalid word.
  • User words were not displayed in alphabetical order for mouse input.
  • Once a word was in the added word list, it could be accepted as a valid user input word if entered from the keyboard, even though there was no valid path with connected letters.   

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

The High Score feature has yet to be implemented.  Since boards are random and not repeatable, I thought that recording the score as a percentage of maximum  possible score for each difficulty level would be the fairest way to track this.  The high score for each ;level would be saved in a file along with the user's name a file, probably an ini file using the TInifile control. 
Done May 23, 2006: I had originally intended to allow users to key in words as well as click letters but didn't get around to it.  .  This approach is slightly more complex than recognizing clicks since we have to identify which letter position the user has in mind.  Each partial word must exist as a valid path somewhere in the letter array.  Probably a new IsValidPath function would be the best way to do this.   
Fixed May 6, 2005:  The original intent was to use small, medium and large dictionaries for the Easy, Medium and Hard playing levels.  Unfortunately the small and medium dictionaries seem to be missing lots of 3-letter words;  the ones I find most often.  So all levels run with the large dictionary for now.   I think it would be easy to limit maximum word lengths for the automatic search, say to 5 letters for Easy and 7 for Medium  play levels, just to make the contest a little more fair.  
And finally, since the player is usually beaten so badly,  when the program wins,  it should gently question the user's native language, IQ, ancestry, or educational level.      

 

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

Modified:November 18, 2016  

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2016, Gary Darby    All rights reserved.