ACROSS and DOWN
Vector 21:1, page 99
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 99
All of us have pondered automating the craft of authoring crossword puzzles. My daydreaming drifted toward a grid of select words – words of a hobby, locale, or clan, for example. Using the short scripts developed so far, I have produced word crossings for birthday party attendees, contra dance lovers, common sayings, and J primitives; to me its all for fun.
across and down are my workhorse verbs. The dyadic forms of across and down take as a left argument the incumbent grid of words crossed and its key features (boxed in three parts) and as a right argument a new candidate word. across and down return a grid of words crossed and its key features (boxed in three parts). If a place has been found for the new candidate word in the incumbent grid, then the output result is revised appropriately; if not, the output result is unchanged from the input left argument. In either case, the output result can be used as a left argument for a subsequent across or “down.” Typically, in my usage of across and down the two verbs are applied alternately with a new word or an unsuccessful word from a list of words I have created.
The monadic forms of the verbs across and down were created to seed a word grid. For example, see the excerpted session below exercising monadic down.
down 'contra'
+---+-------+---+
|3 1|3 3 1 1| % |
| |1 6 1 1| c |
| | | o |
| | | n |
| | | t |
| | | r |
| | | a |
| | | % |
+---+-------+---+
Boxed output/input of across and down
The three boxed results of this example contain the following information. The third box contains an array, named AD, of shape 8 3. The % character – called Dot in my script – was arbitrarily chosen to demarcate the beginning and end of each word added to the grid. In addition to being place-holders, Dots are treated as special characters which enable the program code to prohibit any words from touching. (After a final grid is achieved I have typically replaced all Dots with spaces, but other alternatives are possible.)
The first box contains the row-column indices of the center of the grid, named Center0 in the code (all indexing is 0-origin). In this case the index 3 1 corresponds to the row-column position of the letter “n” in the grid.
The centre box contains AD grid indices; the 4 columns correspond to NSWE (north-most, south-most, west-most, east-most) and the 2 rows correspond to the location in the grid of the across words (first row) and the down words (second row) which are thought to frame the current grid. The indices are given the following 8 names in the script.
NSWE
+--+--+--+--+
across |Na|Sa|Wa|Ea|
+--+--+--+--+
down |Nd|Sd|Wd|Ed|
+--+--+--+--+
NB. north-most letter of a horizontal word (Na)
NB. south-most letter of a horizontal word (Sa)
NB. west-most letter of a horizontal word (Wa)
NB. east-most letter of a horizontal word (Ea)
NB. north-most letter of a vertical word (Nd)
NB. south-most letter of a vertical word (Sd)
NB. west-most letter of a vertical word (Wd)
NB. east-most letter of a vertical word (Ed)
In the example Nd is 1 and Sd is 6 because the letters c and a are the north-most and south-most letters of the (only) down word, contra. Wd and Ed are both 1 because the word contra is in column 1, making the west- and east-most letters in a down word 1. Na and Sa are both 3 and are somewhat arbitrarily set, because there is no across word in this grid. The value 3 was chosen because it is near the middle of the down word, contra.
Dyadic across and down overview¶
The dyadic forms of across and down take as left arguments the boxed output of across and down – either monadic or dyadic output – and as right arguments, a word to be added to the word crossing grid. A simple example, building on the previous example is shown next. dance is added to the grid as a horizontal word. (Notice that the J primitive adverb “Passive” is employed to finesse the need for parentheses.) across and down are case-sensitive to the input words, so Dance is different from dance, for example.
'dance' across~ down 'contra'
+---+-------+-------+
|3 3|3 3 1 5| % |
| |1 1 3 8| c |
| | | o |
| | |%dance%|
| | | t |
| | | r |
| | | a |
| | | % |
+---+-------+-------+
dance has been crossed with contra at the letter “n” because the result is closer to the center of contra than if dance had intersected at “c” or “a”. Other such word placement protocols are described later.
Initial processing in dyadic across: expanding AD (called AD0) into ADI0
To understand the processing in across and down, only examples from across will be given; the down processing parallels that of across and can be seen in the scripts.
Before the string dance can be placed in the original down, contra-only string array grid AD, the grid of shape 8 3 is expanded to shape 8 13. A boxed, expanded, and enhanced grid ADI0 from the execution of across, is shown below as it appears during a J debug session. The asterisks are placed in the augmented version of ADI0 to show all of the potential positions of the Dot preceding dance.
$ADI0
8 13
<'*'(TryNdx)}ADI0
+-------------+
| % |
|*****c |
|*****o |
|*****n |
|*****t |
|*****r |
|*****a |
| % |
+-------------+
Next I describe how two key arrays, illustrated in the previous example, are constructed in across: ADI0 and TryNdx. ADI0 is the expanded grid described above. TryNdx is an array of the left-most Dot positions of each potential Word placement in ADI0.
Inputs to across are read as follows. Their content was explained earlier.
SHAPEI0, the shape of ADI0, is computed in terms of the “core” and “shoulders” of the input to across – AD and Word – as described next. The “core” of the array ADI0 is defined as a rectangular region. The height of the rectangle is determined by the north- and south-most existing horizontal words; the width of the rectangle is determined by the west- and east-most existing vertical words. The size of the core of AD is CoreI0 and is computed as follows. The regions outside the core, but inside the array AD, is called MinShoulder. It is a minimum shoulder in the sense that the shoulder may have to be extended if the new candidate Word (with one of its Dots added) is larger than the western or eastern minimum shoulder.
(,NSWE0) =. ,NSWE0val
CoreI0 =. >: (0&>.) (Sa0-Na0),(Ed0-Wd0)
WordLengthX =. 2+WordLength =. #Word
MinShoulder =. >:|-/NSWE0val
Shoulders =. MinShoulder >.&(_2:]\]) 2#0,>: WordLength
ShapeI0 =. CoreI0 + +/rows Shoulders
IndicesInI0, an array of boxed row-column pairs, is computed to properly place the original array AD0 into an expanded (i.e., with the shape of ADI0), empty (i.e., space-filled) array. The placement is accomplished using J’s } primitive conjunction, “Amend”.
NB. OriginI0 is an offset needed if the western MinShoulder is < #Word
OriginI0 =. 0, (0&>.) WordLength- 2{MinShoulder
Shape0 =. $AD0
InI0 =. OriginI0 + each i. each Shape0
IndicesInI0 =. {InI0
ADI0 =. AD0 IndicesInI0}ShapeI0$' '
The corners of the array of valid placement positions, TryCrnr, are used to compute the full array of row-column positions, TryNdx, as shown below.
TryCrnr =. 2 2&$ 1 , 0 , _2+ ({.Shape0) , ({:ShapeI0-WordLengthX)
ifc =: {@:(([)+each i. each @:>:@:(-~))/ NB. indices from corners
TryNdx =. ifc TryCrnr
Some constants and utility verbs
Dot and other constants are supplied as follows.
Some more utility verbs are listed next. Verbs whose names are suffixed with “Q” produce binary results.
ppA =: [,],[ NB. pre- and post-append x. to y.
ppADot =: Dot&ppA NB. pre- and post-append Dot to y.
wordDot =: [: ppADot word NB. word surrounded by Dot character
unemptyQ =: [:-.(a:,a:)&-:"1 NB. mask for not empty boxed pairs from list
noEmpty =: #~unemptyQ NB. remove empty boxes
neqDotQ =: ~:&Dot NB. produces mask for ~: Dot
nonDot =: #~neqDotQ NB. selects letters ~: Dot
nnDot =: [:#[:nonDot] NB. count of letters w/o Dots
neqSpQ =: Sp&~: NB. produces mask for ~: ' '
nonSp =: #~neqSpQ NB. select non-spaces
allne0Q =: [: +./@:(0&~:) , NB. are all values ~: 0?
low0 =: 0&>. NB. at least 0
firstlast =: {. , {:
butfrstlst =: }:@:}. NB. remove Dots
Main across processing¶
The main processing in across involves supplying to the dyadic verbs the array ADI0 as left argument and as right argument supplying the list of boxed pairs of valid starting positions boxed and the Word boxed. The right argument initially is Tries and is computed as follows.
An example of Tries is given next. The example is taken from a J debug session of adding dance across, as in the example above.
Once the initial list Tries is created, a major aspect of the processing in across involves culling and arranging this list of candidate starting positions for the present Word. The following 4 input utility verbs deconstruct many such verbs’ inputs. The left argument to all these verbs is a string array like ADI0 and the right argument of these verbs is list of boxed items like Tries. As such, in ultimate use in the across script, these verbs are assigned left and right ranks 2 1. An adverb rank is defined to simplify such rank assignments.
By “in ultimate use” I mean that because when a verb is constructed in J using mathematical composition, then the rank assigned to the composed verb applies inwardly to the composing verbs, that the explicit rank assignment is only required for the composed verb. To simplify the appearance of verb definitions of verbs which use these target input utility, and on other higher order verb definitions, the rank is not given explicitly.
By “in ultimate use” I am distinguishing between a verb’s definition and its application. Verb rank can be defined at either stage; to simplify in across a verb’s rank is applied when the verb is applied. When a verb is applied in J using mathematical composition, then the rank assigned to the composed verb applies inwardly to the composing verbs; the explicit rank assignment is only required for the composed verb.
row =: {.@>@{.@] NB. (row,col) is the first boxed item in y.
col =: {:@>@{.@] NB. (row,col) is the first boxed item in y.
word =: >@{:@] NB. word is the last boxed item in y.
target =: [
After the inputs are read using the above 4 input utility verbs, the next sequence of dyadic verbs are used to extract information from ADI0 pertinent to each item in the list argument.
atoms =: col +(i.@#)@wordDot NB. column indices of Word
letters =: atoms {row {target NB. letters and Dots of Word
intersect =: [:nnDot[:nonSp letters NB. count of real letters crossed
rowba =: ([:<:row ),([:>:row ) NB. row Before/After target row
lettersba =: [: butfrstlst rows atoms {rows rowba {target
along =: [:+/[: +./[: neqSpQ@nonDot rows lettersba NB. count of lettersba
The following group of verbs are used to check if various requirements are satisfied for the given Word to be placed at the given position in ADI0.
validQ =: matchQ *. intersectQ *. unequalQ *. roomQ
matchQ =: (wordDot #~[: neqSpQ letters ) -: [: nonSp letters
intersectQ =: 1:<. intersect
unequalQ =: [: -. wordDot -: letters
roomQ =: [: *./ rows along <:"1 0 intersect
validQ combines all the others.
matchQ checks whether all the letters in the grid match the corresponding letters in Word, excluding any spaces. Unfortunately this exception makes the result of matchQ true even for any completely empty areas of ADI0.
intersectQ overcomes the problem with matchQ because the two verbs are always used together and intersectQ is always 0 in such problem situations.
unequalQ is designed to insure that no Word is superimposed over itself in the grid, if that Word is submitted again.
roomQ insures that there are no letters running horizontally parallel immediately adjacent to where Word will be placed; but letters of intersecting vertical words are acceptable.
Depending on the binary value of validQ, valid either returns unaltered the right argument or an empty item.
With these workhorse verbs defined, the list of valid candidate placement positions are found with the following two lines of across. CandAll contains results for each item in Tries, many of which are empty indicating they are not viable.
To clarify, consider the following excerpt from a J debug session extending the simple example above.
$CandAll
30 2
3{.CandAll
+---+-----+
| | |
+---+-----+
|1 1|dance|
+---+-----+
| | |
+---+-----+
noEmpty CandAll
+---+-----+
|1 1|dance|
+---+-----+
|3 2|dance|
+---+-----+
|6 3|dance|
+---+-----+
That completes the discussion of the global workhorse verbs in across. Next I discuss some of the details of across.
More details of across processing¶
Although arguably the definition of the verb valid is quite logical, the resulting calculation of CandAll described above is very inefficient because the verb train which defines valid repeatedly processes very similar arguments. To overcome this inefficiency, the following verb definitions were constructed. The efficiency is gained by first capturing all three repeated calculations into wrdletal and then using at most two of the three at a time for the calculation of the four main condition-checking verbs. This efficiency can best be seen in the verb validEQ below.
NB. "E" stands for Efficient
nSp =: nonSp@] NB. simplifies Efficient definitions
pk1 =: 1&{ NB. simplifies Efficient definitions
matchEQ =: (([ #~[: neqSpQ ])&>/@}: ) -: (nSp &>@pk1)
intersectEQ =: (1:<.[:nnDot nSp)&>@pk1
unequalEQ =: ([: -. [-: ])&>/@}:
roomEQ =: ([: *./ rows ] <:"1 0[:nnDot nonSp@[)&>/@}.
wrdletal =: wordDot;letters;along NB. simplifies definitions
validEQ =: [: (matchEQ *. intersectEQ *. unequalEQ *. roomEQ) wrdletal
valid =: (i.0 )"_`]@.validEQ
valid has been given two different and valid definitions in this description. As in J when this is done, only the last definition is actually remembered by J.
Some programming and style conventions follow.
NB. In general, processing in the verbs across and down
NB. follows a cycle suggested by the following sequence
NB. of grid name suffixes.
NB. AD name of the external grid which seeds the system
NB. AD0 name of the internal grid - Originates the system
NB. ADI0 Intermediate expanded grid of Original
NB. ADI Intermediate grid containing new word
NB. ADtmp retrimmed grid;
NB. really the next AD with an unnecessary new name
NB. Non-noun names begin with a lower case letter.
NB. noun names begin with an Upper case letter.
NB. Several verb pairs are defined for across and down
NB. processing, respectively. The suffix 'D' denotes
NB. the down version of the pair.
NB. Verbs which produce boolean results have the letter 'Q'
NB. as a suffix.
NB. Word and word refer to candidate new words.
NB. letters refer to existing words in the grid.
NB. The nouns NSWE, NSWEI and NSWEI0 contain noun names,
NB. which are used for indirect naming.
The naming pattern for each of the name groups – NSWE, NSWEI and NSWEI0 – follow the pattern described above for NSWE.
The utility verb vw is used frequently to implement indirect assignments by extracting information from the NSWE… series of values into corresponding names.
The sorting rules in across determine the placement of each word in the existing grid. First, the rules favor placing each word in positions for which the word intersects the most existing words. Next the rules favor placing each word in positions for which the central “core” of words is is least changed. The “core” is defined to be words inside a border defined by the following four values Na, Sa, Wd, and Ed. Finally, sortwise, preference is given to word placement which is closest to the original center of the word-crossing array.
To anticipate sorting criteria needs, once the list Cand of valid locations has been computed, across computes potential updates for the NSWE values for each valid Cand item. Values stored in nouns for which the NSWE name has the suffix “I0” are updated into parallel nouns for which the name has the suffix “I”. The single actual update cannot be determined until after the list Cand is sorted in order to choose the best of its items, though. Notice that {. is used extensively and that only “a” named nouns, not “d”, are employed because across values are manipulated here.
NB. Anticipate the potential change in NSWEI
NSWEI0t =. {.NSWEI0
(NSWEI0t) =. ({.NSWE0val) + 2#OriginI0
NSWEIt =. {.NSWEI
(NSWEIt) =. vw {.NSWEI0
Row =. ADI0 row rank Cand
NaI =. NaI0<. Row
SaI =. SaI0>. Row
Atoms =. ADI0 atoms rank Cand
WaI =. WaI0<. >:@:{.rows Atoms
EaI =. EaI0>. <:@:{:rows Atoms
The sorting section is a 3-level sort performed in reverse order of the importance of the sort criterion. Each sort level is done in 4 steps.
- Calculate or determine the sort variable value.
- Perform the “GradeUp” or “GradeDown”.
- Bond the “Grade” indices into a “Pick”.
- Incorporate the previous “Bond” into an verb which combines the “Pick” with the with the current one. For the first level this last step is unnecessary.
The least important criterion is the “city street” Distance between each valid placement position and CenterI0. Next important are the Changes the values of NSWE values which will result from each Cand value. The calculation of Changes employs the following global verbs.
signcap =: 0&<.&.:maskTimes NB. disallows irrelevant changes
maskTimes =: Mask &* NB. Mask multiplied by ...
Mask =: 1 _1 1 _1
The most important criterion is the number of words already in the ADI0 grid which will be crossed (“Xrossed”) by the new Word.
NB. sorting section follows
Distance =. +/|(vw NSWEIt) -"_ 2#CenterI0
DG =. /: Distance NB. DistanceGrade
dG =. DG&{
Changes =. +/|signcap (vw NSWEIt) -"_ (vw NSWEI0t)
CbDG =. /: dG Changes NB. ChangesbyDistanceGrade
cbDG =. CbDG&{
cbDg =. dG (cbDG@)
Xrosses =. ADI0 intersect rank Cand
XbCbDG =. \: cbDG Xrosses NB. XrossesbyChangebyDistanceGrade
xbCbDG =. XbCbDG&{
xbCbDg =. cbDG (xbCbDG@)
Once xbCbDg is determined, the overall sort order selection verb has been computed, it can be applied to Cand, NSWEIt, and Atoms.
Once the best placement for the new Word has been identified, replc amends ADI0 to ADI. Because the values of Cand have been sorted, the best one is the first one, so {. “Takes” it.
Completing across processing¶
Finally across must produce as outputs, the left argument input required for the subsequent implementation of down or across. Although ADI contains the correct number of rows for the updated array AD, the number of columns is unnecessarily many. “Center” and NSWE must be correspondingly revised.
The two boxed items in InI0 contain the row and column indices of AD0 in ADI0, respectively. But we need to extract from ADI0 the expanded row and column indices of ADI for the output ADtmp. So InI0 is extended to InI which contains the required extended indices. The extension is done in four steps.
0 The extreme values of the two boxed items in InI0 are extracted.
1 The selected across values of “NSWEI” are taken from all such values.
2 Corners, the new extreme row and column values, are computed using “extend”.
Mask =: 1 _1 1 _1
minusMask =: -&Mask
maskTimes =: Mask &*
extnd =: [: 0&<. &.maskTimes minusMask@[ - ] NB. define sequence extensions
Corners =. _2<\NSWEaI extnd InI0extrm
3 eSeqXbyY computes InI by extending the index sequence in InI0 using the Corners.
NB. extend Sequence in X using Y
eSeqXbyY0 =: (*@]+each([{.~_1:**@])+each *each @]*each i. each@ ])"1 0
eSeqXbyY =: ([:(,@(>@{.@])) eSeqXbyY0&{.),[,([:(,@(>@{:@])) eSeqXbyY0&{:)
InI =. InI0 eSeqXbyY each Corners
The required output array ADtmp is computed by picking values from ADI.
Next, default NSWE0val values are altered as needed. Mostly values with names containing “a” are altered, but potentially two “d”s are too.
temp =. low0 WaI0 -&{. WaI
if. temp
do.
Wd =. Wd + temp
Ed =. Ed + temp
end.
Na =. Na - low0 NaI0 -&{. NaI
Sa =. Sa + low0 SaI -&{. SaI0
Ea =. +/ low0 Ea, temp, EaI -&{. EaI0
Finally “Center” is updated.
Some applications¶
The script tests has been developed for experimenting with grid creation. Although there is no looping in the workhorse verbs across and down, this verb loops through a word list. The global nouns Last, LastS, and LastW, contain details of the final result of tests, and were used for debugging and continue to be used in experimentation.
Because at any point of grid development, it may be impossible to place individual items in the supplied list of words, a strategy for dealing with such cases is required. In this version of tests, such words are recycled by being placed at the end of the yet-unprocessed list of words.
Another input to tests is a list named Sequence containing only the two boxed words “across” and “down”, which correspond to the two verbs across and down, and control the sequence in which the two verbs are applied. In this version of tests, when a word is unusable, as discussed just above, the list Sequence is rotated one place, also.
History is maintained in order to determine whether the processing loop in tests needs to be halted due to a lack of change in the developing grid.
The global CountMax allows multiple cycles of the inputs to be processed. However, with the setting shown, only one cycle with be processed.
CountStart =: 0
CountMax =: 1 NB. maximum number of iterations of the word list
sm =: ] NB. can be changed to sm =: smoutput to show intermediate output
tests =: dyad define
Start =. x.
'Words Sequence' =. y.
Vocab =. Words
Incumbent =. empty 0
New =. Start
Count =. CountStart
History =. ;/i. Length =. 2>.Words *&# Sequence
while. (Count<CountMax)*.-. -:/firstlast History
do.
Incumbent =. New
History =. (<New) ,}: History
Inc =. lr 'Incumbent'
LastS =: FSeq =. >@{.Sequence
LastW =: FWd =. >@{.Vocab
sm FSeq;FWd
Tmp =. '(',Inc,')',Sp,FSeq,Qu,FWd,Qu
Last =: New =. ". Tmp
sm New
if. Incumbent -: New
do.
Vocab =. Vocab,{.Vocab
end.
Vocab =. }. Vocab
Sequence =. 1&|. Sequence
if. 0=#Vocab
do.
Vocab =. Words
Sequence =. |. Sequence
LastC =: Count =. >:Count
end.
if. 0&=25|#Vocab do. smoutput Count,6!:0'' end.
end.
New
)
The seven-word phrase “I sing of Olaf glad and big,” appears in early J documentation. Coincidentally it is difficult to fit all of the words in this phrase into a single word-crossing grid. After some experimentation with a verb named “tests” I found the index permutation 4 2 1 6 3 5 0 of the seven words “i sing of olaf glad and big” which omits only one word from the final grid (can you tell the missing word?).
(across 'tables') tests (<4 2 1 6 3 5 0{;:'i sing of olaf glad and big'),<;:'down across'
+---+-------+---------+
|3 4|1 5 1 7| %% |
| |1 6 2 7|%big%% |
| | | %l o % |
| | | %tables%|
| | | d a i |
| | | %of%n |
| | | % g |
| | | % |
+---+-------+---------+
The verb tests creates a global noun Last which contains the final result, the familiar list of three boxed values. The final grid can be more attractively viewed with the following command.
<(Dot;' ') rplc"1~ toupper >{:Last
+---------+
| |
| BIG |
| L O |
| TABLES |
| D A I |
| OF N |
| G |
| |
+---------+
Below are two experimental runs of tests with the eleven words of “The Golden Rule.” In the first run, two words – “others” and “as” – are unused in the grid. The randomly generated permutation of the word sequence is found to be 5 0 4 0 4 3 6 1 7 1 2 . (The permutation does not really contain repeat indices, as it appears.) In the second example, all eleven words are used. I have enjoyed contemplating the variety of grids produced by changing only the list order.
(K -.;:(,,,@|:)>{:Last)[(across 'the-golden-rule') tests (<a=:({~#?#)K=:;:'do unto others as you would have them do unto you'),<;:'down across'
+------+--+
|others|as|
+------+--+
Last
+---+--------+-----------------+
|5 7|2 5 1 15| % |
| |1 8 2 15| w |
| | | %do% % % |
| | | %%unto%y t |
| | | % y l o h |
| | |%the-golden-rule%|
| | | a u % % m |
| | | v % % |
| | | e |
| | | % |
+---+--------+-----------------+
K i. a
5 0 4 0 4 3 6 1 7 1 2
(K -.;:(,,,@|:)>{:Last)[(across 'the-golden-rule') tests (<a=:({~#?#)K=:;:'do unto others as you would have them do unto you'),<;:'down across'
Last
+----+---------+-------------------+
|10 9|1 15 1 17| % |
| |1 16 2 16| %you% |
| | | n % |
| | | t % a |
| | | %others% |
| | | %% a %% |
| | | w v a |
| | | %others% |
| | | % %you%%% % |
| | | t l u % |
| | | %the-golden-rule%|
| | | % e %%t n |
| | |%them% %do%%t |
| | | a % %unto%%you% |
| | | v % o%% |
| | | e %would% |
| | | % % o |
| | | % |
+----+---------+-------------------+
K i. a
5 4 0 2 3 1 1 6 0 7 4
Helpful hints from various J programmers via the JForum have been invaluable to me in code development. Oleg Kobchenko was especially helpful in explaining how display of the final grids can be controlled for clearer web viewing using html.
The scripts can be found at http://www.gsu.edu/~dscbms/ad/ad.ijs .