Akerue

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 &quot;page unresponsive&quot; 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>