Akerue
- variable board size;
- scoring system;
- choice of dictionary;
- word selection by edit box or by clicking on letters in the grid;
- optional timer;
- use of compressed dictionary supported by a library of routines;
- enabling the user to add words to and remove words from the dictionary;
- sophisticated searching.
Searching a new grid of letters is processor-intensive and not ideally suited to JavaScript, so this may seem a strange choice for a web preview. However, it does offer great potential for improvement as hardware and software improve over the years! We could have pre-prepared some grids with associated lists of computer-found words (instead of requiring the download and searching of a large dictionary text file) in order to minimise the initial delay, but such an approach would not be in the spirit of this "Challenges" section of the website.
See the Smart Pascal code and the XML code of the form beneath the online demonstration. Please be patient (for about 20 seconds using Chrome) while the program finds the words and ignore any message to the effect that the page is unresponsive. (We use both a dictionary index and binary search so have tried to minimise the delay, but the dictionary is admittedly on the large side. The delay was not reduced noticeably by (a) changing the binary search from recursive to iterative or (b) finding, storing then using the start and end indices of the three letter word stems instead of the prepared initial letter indices to restrict the range of the dictionary searches).
When the edit box becomes active (changing in colour from pale grey to white), found words that you enter there will be shown in alphabetical order in the memo. Press the button to see the other possibilities. The dictionary has many words that you will not know (some of them archaic) and also the program is very likely to find words that you do know but have missed. If you find the occasional legitimate word that the program has missed, please find our programming error and let us know your fix!
If the program does not work, try another browser such as Chrome. If you see no display at school, the security system might have blocked it. You can try instead this direct link to the program running on its own page.
Smart Pascal Code
unit Form1; {Much of this code is similar to that in unit U_Akerue4 with copyright statement: "Copyright © 2001, 2006. 2014, Gary Darby, www.DelphiForFun.org This program may be used or modified for any non-commercial purpose so long as this original notice remains in place. All other rights are reserved" Converted to Smart Pascal by PPS, 2016. Dictionary and searches used here are simpler and do not use compression. } interface uses SmartCL.System, SmartCL.Graphics, SmartCL.Components, SmartCL.Forms, SmartCL.Fonts, SmartCL.Borders, SmartCL.Application, SmartCL.Grid, SmartCL.Grid.Columns, System.Lists, System.Types, SmartCL.Inet, SmartCL.Controls.Memo, SmartCL.Controls.Button, SmartCL.Controls.EditBox, SmartCL.RegEx, SmartCL.Controls.Label; type TForm1 = class(TW3Form) procedure W3EditBox1Changed(Sender: TObject); procedure W3Button1Click(Sender: TObject); private {$I 'Form1:intf'} const // number of occurrences per 1000 characters LetterFreqs: array[1..26] of integer = { a b c d e f g h i j k l m} (86,31,47,31,114,22,23,28,79,2,12,55,32, { n o p q r s t u v w x y z} 64,71,33,3,75,55,75,37,16,14,5,29,4); FHttp: TW3HttpRequest; Words, Found, UserFound: TStrArray; CumulativeFrequencies: array[1..26] of integer; TotFreqCount, PathCount: integer; TextCols: array[1 .. 4] of TW3TextColumn; Stems: TStringList; Paths: array of array of integer; BoardSize: TPoint; // rows and columns Offsets: array[1..8] of TPoint = [(x: -1; y: -1), (x: 0; y: -1), (x: +1; y: -1), (x: +1; y: 0), (x: +1; y: +1), (x: 0; y: +1), (x: -1; y: +1), (x: -1; y: 0)]; FromPoint: TPoint; FirstLetterIndices: array[96..122] of integer := [0, 4463, 9841, 16767, 21112, 23842, 27546, 30831, 33803, 35524, 36487,37739, 40732, 44928, 46552, 48812, 54675, 55110, 59766, 69158, 73796, 75676, 77075, 79446, 79514, 79974, 80368]; protected procedure InitializeForm; override; procedure InitializeObject; override; function BinarySearch(Target: string; First, Last: integer; Stem: Boolean): Boolean; procedure ZeroPaths; procedure ZeroBoard; // Clear out path tracking array and make borders inaccessible procedure CalcAllWords; procedure GetNextPath(StartPoint: TPoint; var PathString: String); function AddToArray(w: string; arr: TStrArray): Boolean; procedure CalcIndices; end; implementation { TForm1 } procedure TForm1.CalcIndices; // Used to generate indices in hard coded array, but not called in online version var CurrentLetter := 'a'; IndexString: String; begin FirstLetterIndices[96] := -1; // Will be incremented to 0 FirstLetterIndices[122]:= Words.Count - 1; for var i := 0 to Words.Count - 1 do begin if Words[i][1] <> CurrentLetter then begin FirstLetterIndices[ord(CurrentLetter)] := i - 1; // end pos of current letter IndexString := IndexString + inttostr(i) + #13#10; CurrentLetter := Words[i][1]; end; end; W3Memo1.Text := IndexString; end; procedure TForm1.InitializeForm; var n, r, PositionInAlphabet: integer; WordList: string; begin inherited; Stems := TStringList.Create; FHttp := TW3HttpRequest.Create; FHttp.OnDataReady := lambda WordList := FHttp.ResponseText; Words := WordList.split('\n'); // CalcIndices; // Time saved by hard coding generated values CalcAllWords; W3EditBox1.Enabled := True; W3Button1.Enabled := True; end; FHttp.Get('res/DictWordlist.txt'); BoardSize.x := 4; BoardSize.y := 4; Paths.SetLength(BoardSize.x + 2); // +2 allows for sentinel border to simplify search // set initial FromPoint FromPoint.x := 1; FromPoint.y := 1; randomize; {Make an array of cumulative relative frequency values of letters as they appear in the English language. Used to generate random letter board.} n := 0; for var i := 1 to 26 do begin n := n + LetterFreqs[i]; CumulativeFrequencies[i] := n; end; TotFreqCount := n; for var i := 1 to 4 do begin TextCols[i] := TW3TextColumn.Create(BoardGrid as IW3ColumnsControl); TextCols[i].Width := 20; BoardGrid.Columns.Add(TextCols[i]); end; BoardGrid.AddRow(4); for var i := 0 to 3 do for var j := 0 to 3 do begin r := randomint(TotFreqCount); PositionInAlphabet := 1; while (PositionInAlphabet <= 26) and (CumulativeFrequencies[PositionInAlphabet] < r) do inc(PositionInAlphabet); BoardGrid.Cell[i, j].Value := chr(64 + PositionInAlphabet); end; end; procedure TForm1.InitializeObject; begin inherited; {$I 'Form1:impl'} memInstructions.ScrollH := soNone; memInstructions.ScrollV := soNone; memInstructions.Font.Size := 13; W3Button1.Font.Size := 13; end; procedure TForm1.W3Button1Click(Sender: TObject); begin W3Memo1.Text := W3Memo1.Text + #13#10 + 'Found by program:' + #13#10; for var i := 0 to Found.Length - 1 do if UserFound.IndexOf(Found[i]) = -1 then W3Memo1.Text := W3Memo1.Text + Found[i] + #13#10; end; procedure TForm1.W3EditBox1Changed(Sender: TObject); var s: string; begin if Found.IndexOf(lowercase(W3EditBox1.Text)) <> -1 then begin AddToArray(lowercase(W3EditBox1.Text), UserFound); asm (@UserFound).sort(); end; for var i := 0 to UserFound.Length - 1 do s := s + UserFound[i] + #13#10; W3Memo1.Text := s; end else Showmessage('Not found by program so refused'); end; function TForm1.BinarySearch(Target: string; First, Last: integer; Stem: Boolean): Boolean; // Search of dictionary Words (Stem false) or first 3 letters of words (Stem true) var MidPoint: integer; DictionaryString: string; begin if First > Last then result := false else begin Midpoint := (First + Last) DIV 2; if Stem then DictionaryString := Words[MidPoint].Left(3) else DictionaryString := Words[MidPoint]; if DictionaryString = Target then result := True else if DictionaryString < Target then result := BinarySearch(Target, MidPoint + 1, Last, Stem) else result := BinarySearch(Target, First, MidPoint - 1, Stem); end; end; procedure TForm1.ZeroPaths; // Make all the cells within the borders accessible begin for var i := low(Paths) + 1 to high(Paths) - 1 do for var j := low(Paths[i]) + 1 to high(Paths[i]) - 1 do Paths[i, j] := 0; PathCount := 1; end; procedure TForm1.ZeroBoard; // Initialize the Paths array marking borders inaccessible var i, j: integer; begin for i:= low(Paths) to high(Paths) do Paths[i].setlength(BoardSize.y + 2); for i := low(Paths) to high(Paths) do for j := low(Paths[i]) to high(Paths[i]) do if (i = low(Paths)) or (i = high(Paths)) or (j = low(Paths[i])) or (j = high(Paths[i])) then Paths[i, j] := max_int else Paths[i, j] := 0; PathCount := 1; end; Procedure TForm1.CalcAllWords; // Calculate the paths from one point on each entry, then increment the point var PartialWord: String; begin // Solve paths from a single starting point and increment starting point to next cell ZeroBoard; while FromPoint.x <= BoardSize.x do begin ZeroPaths; PartialWord := BoardGrid.cell[FromPoint.x - 1, FromPoint.y - 1].Value; Paths[FromPoint.x, FromPoint.y] := PathCount; // mark as visited GetNextPath(FromPoint, PartialWord); inc(FromPoint.y); if FromPoint.y > BoardSize.y then begin FromPoint.y := 1; inc(FromPoint.x); end; end; asm (@Found).sort(); end; end; procedure TForm1.GetNextPath(StartPoint: TPoint; var PathString: String); // The heart of the recursive path search for new words var Len, StartIndex, EndIndex: integer; NextPoint: Tpoint; c, Left3: string; CouldBeWord: Boolean; begin for var i := 1 to 8 do {try all 8 possible move directions} begin NextPoint.x := StartPoint.x + Offsets[i].x; NextPoint.y := StartPoint.y + Offsets[i].y; if Paths[NextPoint.x,NextPoint.y] = 0 then {we can visit} begin Paths[NextPoint.x,NextPoint.y] := PathCount; {mark as visited} // add character from grid to potential word c := BoardGrid.cell[NextPoint.x - 1, NextPoint.y - 1].Value; PathString := PathString + c; Len := length(PathString); if Len >= 3 then {we've gone three steps - check and see if any words start with these three} // Could it be a word? begin CouldBeWord := False; Left3 := lowercase(PathString.Left(3)); if Stems.IndexOf(Left3) <> -1 then CouldBeWord := True else begin StartIndex := FirstLetterIndices[ord(Left3[1]) - 1] + 1; EndIndex := FirstLetterIndices[ord(Left3[1])]; if BinarySearch(Left3, StartIndex, EndIndex, True) then begin CouldBeWord := True; Stems.Add(Left3); end; end; // If it is a word, add it to the Found array if CouldBeWord then begin StartIndex := FirstLetterIndices[ord(lowercase(PathString)[1]) - 1] + 1; EndIndex := FirstLetterIndices[ord(lowercase(PathString)[1])]; if BinarySearch(lowercase(PathString), StartIndex,EndIndex, False) then AddToArray(lowercase(PathString), Found); // also if in continue searching GetNextPath(NextPoint, PathString); end; end else // len < 3 so don't check if it could be a word GetNextPath(NextPoint, PathString); // make this node available again Paths[NextPoint.x, NextPoint.y] := 0; // and erase the last character delete(PathString, length(PathString), 1); end; // end of if can visit end; // end of for loop testing all 8 directions end; function Tform1.AddToArray(w: string; arr: TStrArray): Boolean; // adds a word to an array if it is not already there var index: integer; begin index := arr.indexof(w); if index < 0 then begin arr.add(w); result := True; end else result := False; end; initialization Forms.RegisterForm({$I %FILE%}, TForm1); end.
XML Code of Form
<SMART> <Form version="2" subversion="2"> <Created>2016-12-07T12:25:37.260</Created> <Modified>2016-12-18T17:36:33.628</Modified> <object type="TW3Form"> <Caption>W3Form</Caption> <Name>Form1</Name> <object type="TW3Grid"> <Width>112</Width> <Left>46</Left> <Height>96</Height> <Name>BoardGrid</Name> </object> <object type="TW3Memo"> <Width>120</Width> <Left>208</Left> <Height>336</Height> <Name>W3Memo1</Name> </object> <object type="TW3Button"> <Caption>Show unfound words</Caption> <Width>176</Width> <Top>360</Top> <Left>160</Left> <Height>32</Height> <Name>W3Button1</Name> <OnClick>W3Button1Click</OnClick> </object> <object type="TW3EditBox"> <Value></Value> <Range></Range> <Width>128</Width> <Top>360</Top> <Left>16</Left> <Height>32</Height> <Enabled>False</Enabled> <Name>W3EditBox1</Name> <OnChanged>W3EditBox1Changed</OnChanged> </object> <object type="TW3Memo"> <Text>Find as many words as you can from letters that are connected vertically, horizontally or diagonally. Words must have 3 or more letters. The same letter square cannot be used twice within any single word. No word may be repeated. Wait for the edit box to be enabled. Ignore any "page unresponsive" messages and wait until edit box is active.</Text> <Width>200</Width> <Top>104</Top> <Left>4</Left> <Height>232</Height> <Name>memInstructions</Name> </object> <object type="TW3Label"> <Caption>Enter word</Caption> <Width>128</Width> <Top>330</Top> <Left>16</Left> <Height>32</Height> <Name>W3Label1</Name> </object> </object> </Form> </SMART>