Skip to content

Word-search Squares in I-APL

by Bill McLean and Ian Clark

Vector 11:3, page 23

education competitions and puzzles programming techniques

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 23

I needed a Word-Search making program, since there are a lot of good teaching points involved. The program is written using APLomb, which is a Macintosh screen interface construction set based on I-APL, but any port of I-APL should work, although you won’t get to see the square being built up and you won’t get the fancy buttons to control it. However the working functions don’t care whether they’re running on APLomb or not, so simply make all the functions dealing with the interface, viz. APLOMB, BUTTON1, BUTTON2 and REFRESH, into trivial functions that do nothing when called and it should work with any APL (I’m going to try it with Dyalog — Ed).

LIST is a 2D char matrix containing the words to be matched. You can input LIST by assigning to it the result of MAT 10, say, supposing 10 is the maximum width of word you want. MAT will then accept successive words typed-in, stopping when you just press <Enter> without typing anything.

Define GRID to be the size you want, e.g. a 10 by 10 array of asterisks (or anything, they’ll get turned to asterisks), Enter in turn:

BEGIN
TRY
FINALISE

TRY will output into the session log what it’s doing as it runs. This listing also happens to tell you the solution to the finished square, something you’ll need unless you’re very clever at solving these things. You can halt it at any stage (sometimes it doesn’t manage to fit in all the words you give it in LIST since it’s possible to give it an impossible set) and then run FINALISE. This fills in all the remaining asterisks in GRID with random letters. Hey presto! — there’s your finished square for the school newsletter.

And don’t forget, Konky Puzzles made a lot of money selling books of things like this.

Listing of Workspace WDS

(A Macintosh version of this workspace is available. Send a blank disk and SAE to the Editor, EV. Other versions by arrangement.)

ABANDON: YB[;]←0
APLOMB: 100 ⎕MC ''
BUTTON1: BEGIN
BUTTON2: FINALISE
FINALISE: LOSE GRID[;]←GRID SUBST RANDCHAR ⍝sneaky way to update global
G1: GRID[;]←'*'
IF: ⍵/⍺
IFALL: (∧/⍵)/⍺
INDOWN: GRID[SET;COL]←WORD
INHORIZ: GRID[ROW;SET]←WORD
INRIGHT: GRID[ROW;SET]←WORD
LOSE: : 0 : ⍵ ⍝ suppresses output from a direct definition
MAT: (⍵↑V),[1] MAT ⍵ : 0=⍴V←⍞ : (0,⍵)⍴''
NEXT: ((N←N+1)⊖LIST)[1;]
RANDCHAR: 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'[?(⍴GRID)⍴26]
REFRESH: 101 ⎕MC '' ⍝ maintains kompos in mid-execution
SUBST1: : ×⍴⍴Z←(,⍺),[.5],⍵ : (⍴⍺)⍴((,B)⊖Z)[1;] ⍝how DOES it work??
TB: (¯1↑(' '≠⍵)/⍳⍴⍵)↑⍵

    ∇ BEGIN
[1]   ⍝ START THE APLOMB VERSION OF WORD SEARCH
[2]    RUNNING←+0
[3]    CONTINUE←+1
[4]    GRID[;]←'*'
[5]    LORIENT←WORD←'<empty>'
[6]    TEMPGRID←''
[7]    MAX←ROW←COL←U←0
[8]    N←1 ⍝--use first word in LIST
[9]    APLOMB
    ∇

    ∇ BIT;WORD
[1]    WORD←⍞
[2]    →(1 2∊?2)/NORMAL,REVERSE
[3]   NORMAL:
[4]    ⎕←WORD
[5]    →0
[6]   REVERSE:
[7]    ⎕←⌽WORD
[8]    →0
    ∇

    ∇ Z←BYHAND
[1]    'INPUT A WORD'
[2]    WORD←⍞
[3]    L←⍴WORD
[4]    'WHICH ROW DOES THE WORD START ON?'
[5]    ROW←⎕
[6]    D←0,⍳(L-1)
[7]    'WHICH COLUMN?'
[8]    COL←⎕
[9]    SET←ROW+D
[10]   'DO YOU WANT (D)IAGONAL, (H)ORIZONTAL OR (V)ERTICAL?'
[11]   SELECT←⍞
[12]   →('DHV'∊SELECT)/DIAGONAL,HORIZONTAL,VERTICAL
[13]  DIAGONAL:
[14]   TEMPBOX←GRID[(ROW+D);(COL+D)]
[15]   NOS←(ROW⍴0),(⍳(L-1)),((10-(ROW+(L-1)))⍴0)
[16]   TEMPGRID←NOS⌽GRID
[17]   TEMPGRID[ROW+D;COL]←WORD
[18]   GRID←(NOSׯ1)⌽TEMPGRID
[19]   ''
[20]   GRID
[21]   →0
[22]  HORIZONTAL:
[23]   INRIGHT
[24]   ''
[25]   GRID
[26]   →0
[27]  VERTICAL:
[28]   INDOWN
[29]   ''
[30]   GRID
[31]   →0
    ∇

    ∇ Z←X SUBST Y
[1]   ⍝ substitutes Y elements into X as identified by 1 in boolean B
[2]   ⍝ X, Y and B must be the same 2D shape.
[3]   ⍝ Here B is assigned internally, but you can remove the B← line
[4]   ⍝ and compose B before calling SUBST.
[5]    B←X='*' ⍝--optional line, see above.
[6]    Z←(,X),[.5],Y ⍝--Form 2×n array, X on top, Y below
[7]    Z←((,B)⊖Z) ⍝--Rotate Z vertically using B
[8]    Z←(⍴X)⍴Z[1;] ⍝--Take row 1 of Z, reshape like X and return it.
    ∇

    ∇ TRY;Z;SIZE;MAX;J;L;LABEL;LAB;ROTATE
[1]   ⍝ fill GRID randomly with WORD chosen from LIST
[2]    LABEL←DOWNRIGHT,HORIZONTAL,DOWNLEFT,VERTICAL
[3]    SIZE←''⍴⍴GRID ⍝--height of GRID, assume=width
[4]   ⍝ N←0 ⍝⍝⍝ N made global to allow restart
[5]   ⍝
[6]   NEXTWORD:
[7]   ⍝--Use existing N, finish at end of list
[8]    →0 IF N>1↑⍴LIST
[9]   ⍝--clear trailing spaces from next WORD
[10]   L←⍴WORD←TB LIST[N;]
[11]  ⍝--keep within MAX row/col for WORD to fit GRID
[12]   MAX←1+SIZE-L
[13]   D←¯1+⍳L ⍝--vector of indexes, 0 1 2... for WORD
[14]  ⍝--optionally reverse WORD at random
[15]   ⍎'WORD←⌽WORD' IF 2=?2
[16]   REFRESH
[17]   LABEL←LABEL[4?4] ⍝--scramble order of labels
[18]   J←1 ⍝--indexes LABEL[]
[19]  ⍝
[20]  NEWORIENT: ⍝--try another orientation
[21]   →ABANDON IF 4<J←J+CONTINUE←+1
[22]   LAB←LABEL[J] ⍝--the label to be used
[23]   YB←(MAX,MAX)⍴1 ⍝--flag array used by UNTRIED
[24]   ⍎'YB←(SIZE,MAX)⍴1' IF LAB=HORIZONTAL
[25]   ⍎'YB←(MAX,SIZE)⍴1' IF LAB=VERTICAL
[26]  ⍝
[27]  NEXTCELL: ⍝--find next untried cell
[28]   Z←UNTRIED
[29]  ⍝--if no cells left try new orientation
[30]   →NEWORIENT IFALL (Z=0)∨~CONTINUE
[31]   ROW←Z[1]
[32]   COL←Z[2]
[33]   TEMPGRID←''
[34]   REFRESH ⍝--update the APLomb kompos
[35]   →LAB ⍝--go to the randomly chosen label
[36]  ⍝
[37]  DOWNRIGHT:LORIENT←'down/right'
[38]   ROTATE←D
[39]   Z←1 1⍉TEMPGRID←GRID[(ROW+D);(COL+D)]
[40]   →DIAGONALLY
[41]  ⍝
[42]  DOWNLEFT:LORIENT←'down/left'
[43]   ROTATE←⌽D
[44]   Z←1 1⍉⌽TEMPGRID←GRID[(ROW+D);(COL+D)]
[45]  ⍝
[46]  DIAGONALLY:
[47]  ⍝--select a block and make Z the diagonal
[48]   REFRESH ⍝--to show TEMPGRID
[49]   →NEXTCELL IF 0∊(Z='*')∨(Z=WORD)
[50]  ⍝--insert WORD in the diagonal of TEMPGRID
[51]   TEMPGRID←ROTATE⌽TEMPGRID
[52]   TEMPGRID[;1]←WORD
[53]   TEMPGRID←(-ROTATE)⌽TEMPGRID
[54]   REFRESH ⍝--to show new TEMPGRID
[55]  ⍝--replace TEMPGRID in GRID
[56]   GRID[(ROW+D);(COL+D)]←TEMPGRID
[57]   →NEXT
[58]  ⍝
[59]  HORIZONTAL:LORIENT←'horizontally'
[60]   TEMPGRID←Z←GRID[ROW;SET←COL+D]
[61]   REFRESH
[62]   →NEXTCELL IF 0∊(Z='*')∨(Z=WORD)
[63]   INRIGHT
[64]   →NEXT
[65]  ⍝
[66]  VERTICAL:LORIENT←'vertically'
[67]   TEMPGRID←Z←GRID[SET←ROW+D;COL]
[68]   REFRESH
[69]   →NEXTCELL IF 0∊(Z='*')∨(Z=WORD)
[70]   INDOWN
[71]  ⍝
[72]  NEXT:WORD,' inserted ',LORIENT,' at ',⍕ROW,COL
[73]   →NEXTWORD,N←N+1
[74]  ABANDON:WORD,' abandoned'
[75]   →NEXTWORD,N←N+1
    ∇

    ∇ Z←UNTRIED;B;I;J
[1]   ⍝ chooses a random YB=1, sets it to 0
[2]    U←+/,YB ⍝--the total of 1s in YB (U global for inspection)
[3]    →EX IF U=I←J←0 ⍝ return 0,0 if there are no 1s left in YB
[4]    Z←(⍴YB)⍴(,YB)\(?U)⌽U↑1 ⍝--one of the 1s in YB selected at random
[5]    YB←YB∧~Z ⍝--turn it off in YB
[6]   ⍝--find coords of the 1 in Z
[7]    I←(∨/Z)/⍳1↑⍴YB
[8]    J←(∨⌿Z)/⍳1↑⍴YB
[9]   EX:Z←I,J
    ∇

      ALPH
ABCDEFGHIJKLMNOPQRSTUVWXYZ