A LAMBDA Word Search Puzzle

[Patrick2788]

I've created a 15x10 Word Search.  I've included a word list (dynamic range) containing words which might be found in the word search.  The goal is to then extract those words when they appear in the word search.  The catch is the words can appear 1 of 4 ways:  horizontal left-to-right, horizontal in reverse, vertical, and vertical in reverse (No diagonals!).  (The words currently in the puzzle are in blue for illustrative purposes)

When I started this exercise, I thought of a solution involving SCAN and some text accumulation.  There are a few issues with this method.  SCAN would need to go through the puzzle twice (Can't VSTACK then SCAN) - once going through the range as normal then through the range when flipped (w/CHOOSECOLS and TRANSPOSE).  The dimensions of each are not the same and it gets messy.  

Ultimately, the method I used starts by finding the position of words (Regular or in reverse) for a given row, pulling the words, filtering, splitting (Have to account for potentially multiple words in a line), stacking, and producing a list of words found.  That's the short of it. You'll have to see the workbook.

I'm interested in if SCAN can potentially make the solution a bit simpler.

[#2]

@Patrick2788 

Congratulations on what you have achieved to date.  The coding looks neater than I might have expected.  I don't know how long it took you to code the method but it will take a while to unravel the approach.  

Until such time, some thoughts on SCAN.  Given a 2D array to scan, the function works through the entire 2D array row by row, so a strategy that works on one row could work over the entire range.  There is a catch, in that some apparent matches might appear due to the string wrapping round rows.  To avoid that, one could insert a column of blanks using HSTACK and then apply SCAN.  Something similar can be achieved with the latest batch of array shaping functions such as TOCOL.

A different approach would be to use CONCAT to reduce the entire puzzle to a single string and exploit text searches within the Lambda functions.  Such a strategy probably works best when there is only a single occurrence of a word to find.  In each case, the transposing and reversing of strings is needed.

I will try to take another look and your workbook later.

[#3]

@Patrick2788 

Perhaps close to @Peter Bartholomew latest idea

checkWord=
LAMBDA( str, vector,
    LET(
        getIt, IF( ISNUMBER( SEARCH( str, TAKE( vector, 1))), str, ""),
            IF(
                ROWS( vector ) = 1,
                getIt,
                VSTACK( getIt, checkWord( str, DROP( vector, 1)) )
    )));

checkWords=
LAMBDA( wordsVector, vector,
    LET(
        a, checkWord( TAKE( wordsVector, 1), vector),
            IF(
                ROWS( wordsVector ) = 1,
                a,
                VSTACK( a, checkWords( DROP( wordsVector, 1), vector) )
    )) );

reverseRow=
LAMBDA( r,
    LET(
        n, COLUMNS( r ),
        INDEX(r,SEQUENCE(,n,n,-1))
    ) );

wordsFoundInPuzzle=
LAMBDA( data, wordsVector,
    LET(
        combinedVector, VSTACK(
            BYROW(data, LAMBDA(v, TEXTJOIN("",,v) ) ),
            BYROW(data, LAMBDA(v, TEXTJOIN("",, reverseRow( v )) ) ),
            TOCOL( BYCOL(data, LAMBDA(v, TEXTJOIN("",,v) ) ) ),
            TOCOL( BYCOL(data, LAMBDA(v, TEXTJOIN("",, reverseRow( TOROW(v) )) ) ) )
        ),
        withBlanks, checkWords( wordsVector, combinedVector ),
        return, FILTER( withBlanks, withBlanks <> ""),
        return
    ));

[#4]

@Peter Bartholomew 

Thank you for your reply.  I spent a couple days on it on and off then dropped it for a few days because I couldn't resolve it with SCAN.  I did go through the paces with TOCOL and reducing the letters to a scalar.  I didn't feel good about where I was headed.  I revisited the task when I thought of how the new Text functions may be helpful by using delimiters, so I played with feeding TEXTSPLIT/TEXTBEFORE/TEXTAFTER a stack of words to delimit on.  @SergeiBaklan - I need to take some time to study this solution.  I've been looking at this puzzle too much lately but will come back to it soon.

The part I couldn't get around with SCAN was achieving something like this (A sample of the first two rows done manually):

The closest I came was getting WAVE and AES (placed in row 2) but the rest that followed was not accurate.

[#5 · Accepted solution]

@Patrick2788 

Here is one more variant

//------ variant without TEXTJOIN()

reverseColumns=
LAMBDA( data,
    LET(
        n, COLUMNS( data ),
        CHOOSECOLS( data, SEQUENCE(n,,n,-1) )
    ));

reversedText=
LAMBDA( str,
    LET(
        head, LEFT(str),
        tail, RIGHT(str, LEN(str) - 1),
        IF(str = "", "", reversedText(tail) & head)
    ));

isPolindrom=
LAMBDA( text, text = reversedText( text ) );

checkSingleWord=
LAMBDA( str, vector,
    LET(
        getWord, REDUCE("", vector,
            LAMBDA( a,v,
                IF( LEFT(str, LEN(a&v)) = a&v, a&v,
                IF( LEFT(str) = a, v,
                    IF( a = str, a, "" )
                ) ) ) ),
        IF( getWord = str, str, "")
    ));

checkListOfWords=
LAMBDA( wordsVector, vector,
    LET(
        getWords,
            REDUCE("", wordsVector,
                LAMBDA(a,v, VSTACK(a, checkSingleWord( v, vector) ) )
            ),
        IFERROR( FILTER( getWords, getWords <> ""), "" )
    ));

wordsInMatrix=
LAMBDA( data, wordsVector,
    LET(
        k, SEQUENCE( ROWS(data) ),
        scanData, REDUCE(1, k,
            LAMBDA(a,v,
                CHOOSECOLS(
                    IF( v < SEQUENCE(,v,v,-1),
                        a,
                        VSTACK(a, checkListOfWords( Words, CHOOSEROWS(data,v) ) ) ),
                1 )
            )),
        removeFirst, DROP( scanData, 1 ),
        FILTER( removeFirst, removeFirst <> "")
));

wordsInPuzzle=
LAMBDA( data, wordsVector,
    LET(
    allWords, SORT( VSTACK(
        wordsInMatrix( data, wordsVector ),
        wordsInMatrix( reverseColumns( data ), wordsVector ),
        wordsInMatrix( TRANSPOSE( data ), wordsVector ),
        wordsInMatrix( reverseColumns( TRANSPOSE( data ) ), wordsVector )
    )),
    ifPolindroms, MAP(allWords, LAMBDA(v, isPolindrom(v) ) ),
    polindroms, UNIQUE( FILTER(allWords, ifPolindroms)),
    notPolindroms, FILTER(allWords, ifPolindroms -1),
    stack, IF( ISERR(polindroms), notPolindroms, VSTACK( polindroms, notPolindroms ) ),
    SORT( stack )
));

[#6]

Thank you for the examples. I really need to improve on recursion. I've been doing some things the long way and can refine my methods much more!

[#7]

@SergeiBaklan 

I'm wondering if it's possible (or even sensible) to use recursion with SCAN to check an element in the array to see if it contains a word from the word list when the element LEN is at least 3. The word would be returned and the excess letters would be discarded.  I'm messing around with recursion and SUBSTITUTE and receiving memory errors.
Ideally, the SCAN results would be like this:

[#8]

@Patrick2788 

Not sure I understood your idea correctly. If we scan only one row (one by one) and expected result is like

when it could be

///--- SCAN row on Words
getWord=
LAMBDA( str, words,
    XLOOKUP( str, words, words, 0) );

getWordOnRight=
LAMBDA( str, words,
    IFNA( INDEX( Words, XMATCH( TRUE, RIGHT(str, LEN(Words) )= Words ) ), 0 )
);

getReversedWordOnRight=
LAMBDA( str, words,
    IFNA( INDEX( Words, XMATCH( TRUE, LEFT( reversedText(str), LEN(Words) )= Words ) ), 0 )
);

scanVector=
LAMBDA( vector, words,
    SCAN("", vector, LAMBDA(a,v,
        IF( getWord( a, Words ) <> 0, v,
            IF( getWordOnRight( a&v, Words ) <> 0,
                getWordOnRight( a&v, Words ),
                IF( getReversedWordOnRight( a&v, Words ) <> 0,
                    getReversedWordOnRight( a&v, Words ),
                    a&v )
            )
        )
    ) )
);

I guess could could be more compact, just first iteration.

[#9]

That's exactly it. My idea involved scanning the entire target array, but it looks like going by row is much better. No need to account for the change in row and less text to discard.

[#10]

I have been trying something different with some success. I reduce the entire puzzle to a single string, padded with "|" between source rows and, rather than reversing the puzzle, I reverse the search words and append them to the original set. The location of the matches within the string is related to the position within the puzzle grid. So far, I have 0 and 1 to show where the matches are, but by combining that with the original grid, I could display the words in their original setting.

[#11]

@Patrick2788 

Rather than listing the words found, I have identified them on copies of the puzzle.

Worksheet formula
= Solveλ(Puzzle, WordList, 0) +
  Solveλ(Puzzle, WordList, 1)

Solveλ = LAMBDA(grid, findlist, d,
    LET(
        puzzleStr,      Grid2Stringλ(grid,d),
        extendedList,   VSTACK(findlist, MAP(findlist, Reverseλ)),
        pointer,        MAP(extendedList, LocateWordλ(puzzleStr)),
        ptr,            FILTER(pointer,pointer),
        wLen,           FILTER(LEN(extendedList),pointer),
        puzzleIdx,      SEQUENCE(LEN(puzzleStr)),
        n,              IF(d, ROWS(grid), COLUMNS(grid)),
        String2Gridλ(puzzleIdx,ptr,wLen,n,d)
    )
);

Grid2Stringλ = LAMBDA(grid,d,
    LET(
        nRow,           ROWS(grid),
        nCol,           COLUMNS(grid),
        extendedGrid,   EXPAND(grid, nRow+1, nCol+1, "|"),
        CONCAT(TOCOL(extendedGrid,,d))
    )
);

String2Gridλ = LAMBDA(k,wp,wl,n,d,
    LET(
        s, XLOOKUP(k,wp,wp,0,-1),
        ℓ, XLOOKUP(k,wp,wl,0,-1),
        b, SIGN(k+1-s <= ℓ),
        ext, IF(d, 
            WRAPCOLS(b,n+1),
            WRAPROWS(b,n+1)),
        DROP(ext,-1,-1)
    )
);

LocateWordλ = LAMBDA(puzzleStr, LAMBDA(word, 
    IFERROR(FIND(word, puzzleStr),0))
);

Reverseλ = LAMBDA(word,
    LET(n, LEN(word), k, SEQUENCE(n, 1, n, -1), CONCAT(MID(word, k, 1)))
);

Something else that occurs to me is that your recursion technique might be the only way forward if the standard across and down wordsearch had words that change direction like a game of 'snake'.

[#12]

@Peter Bartholomew 

Nice idea, need to play with it bit more. Do I understood correctly you don't generate "Words found in puzzle" ?

[#13]

True. For each word, I record where it occurs (pointer/ptr) and how many characters it occupies (wLen). I do not need to store the word itself, though that would be easier than identifying its location within the grid.

[#14]

@Peter Bartholomew 

This is a very elegant solution and you delivered on the ideas you suggested last week. This is an interesting exercise because there's multiple ways to manipulate the matrix to locate the words. It looks like you took the approach that it's better to locate the words in a vector than a matrix. If I follow correctly, you converted the matrix to a vector, located the words, and then ultimate wrapped it back into a matrix. Very cool!

I have some general observations:
-I typically use REDUCE and some sequencing to reverse text. I noticed you used SEQUENCE with your LAMBDA. @SergeiBaklan utilized some clever recursion to reverse text.  I'm trying to get a feel for when to use recursion.  My guess is recursion might calculate a bit slower but for a small data set the difference is negligible.

-This may be a matter of style but I'm curious why LAMBDA is nested here. I removed one LAMBDA and noticed it still calculates correctly:

LocateWordλ = LAMBDA(puzzleStr, LAMBDA(word, 
    IFERROR(FIND(word, puzzleStr),0))

[#15]

@Patrick2788 

So many points to answer!  Your introductory paragraph captures the intent of the solution perfectly.  I also used the fact that the number returned for a character in the string corresponds to its sequence number in the grid.

With few exceptions, I have consigned recursion to the past, since I find it intensely difficult to construct solutions or explain them and, for preference, I use the most appropriate Lambda helper function.  I suspect, but have not demonstrated, that the helper functions improve the computational efficiency and are they are not constrained by size of the parameter stack.  Something that recursion can do that SCAN (say) cannot, is terminate the calculation according to a criterion that is not known at the outset (convergence to some tolerance, for example).  SCAN would continue processing nothing very much until it reached the end of the scanned array.  TAKE, DROP or FILTER could be used to 'trim' the result.

Whether the LAMBDA is in Curried form (one parameter fed at a time to nested functions) or as a single multi-argument function is of little importance (they are equivalent), until you come to use it within a Lambda helper function that will expect a specific signature in terms of the parameters it passes.  Currying allows the leftmost arguments to be provided explicitly by the developer whilst the final arguments are provided by the helper function.  Maybe the subject would be worthy of a uTube clip in its own right?

[#16]

@Peter Bartholomew 

I could agree that built into SCAN and REDUCE recursion shall be faster than manual recursion. However, didn't do any test and have no idea how dramatical the difference is and are there differences in stack limits.

Without that the only point to use this or that is do we have ready to use patterns or not.

[#17]

@Patrick2788 I haven't evaluated the actual functions developed here (but duly impressed). but I noticed this proposed method:

Ideally, the SCAN results would be like this:

and wanted to mention that in word search you can often have overlapping words.  So you could have WAVE and VENUS overlapping so after finding WAVE you shouldn't reset the search array to the next letter D but should start with AVE (maybe the next word is AVENUE).

[#18]

For this exercise, I didn't do overlapping words or diagonals (Things might really get out of hand if those were included!). I think SCAN can locate the words, but it seems easier to go by the row (Less letters to discard and no need to account for the row changing) or convert the matrix to a vector to pull the words.

[#19]

yes I saw the no diagonals but didn't see any exclusion for overlap. Besides, I don't think overlap adds a lot of complexity, just prevents some tricks that make it more efficient.

[#20]

@mtarler 

@SergeiBaklan 

@Peter Bartholomew 

I thought it would be interesting to re-visit this task with a fresh set of eyes.  I scrapped my solution from 2022 and made things more interesting.

Functionality added:

• Diagonals are now supported
• Multiple dictionary support

There's a bit of calculation crunch when using the dictionary with 9,500+ words.  I was going to add an Oxford dictionary that contained 100,000 words but the CSV needed extensive cleanup (Probably for the best as larger word lists contain a lot of made-up words).

=LET(
    height, ROWS(Puzzle),
    width, COLUMNS(Puzzle),
    AccumulateText, LAMBDA(a, letter, a & letter),
    Letter2Array, LAMBDA(arr, SCAN("", arr, AccumulateText)),
    WordsReversed, MAP(dictionary, LAMBDA(e, Reverse(e))),
    results, REDUCE(
        "",
        Puzzle,
        LAMBDA(a, letter,
            LET(
                r, ROW(letter),
                c, COLUMN(letter),
                across, INDEX(Puzzle, r, SEQUENCE(, width - c + 1, c, 1)),
                down, INDEX(Puzzle, SEQUENCE(height - r + 1, , r), c),
                diagonal_c, SEQUENCE(width - c + 1, , c),
                diagonal_r, SEQUENCE(width - c + 1, , r),
                diagonal, INDEX(Puzzle, diagonal_r, diagonal_c),
                neg_diagonal_c, SEQUENCE(c, , c, -1),
                neg_diagonal_r, SEQUENCE(width - c, , r),
                neg_diagonal, INDEX(Puzzle, neg_diagonal_r, neg_diagonal_c),
                arrAcross, TOCOL(Letter2Array(across)),
                arrDown, Letter2Array(down),
                arrDiagonal, Letter2Array(diagonal),
                arrDiagonalNeg, TOCOL(Letter2Array(neg_diagonal)),
                WordStack, IF(
                    c = width,
                    VSTACK(arrDown, arrDiagonalNeg),
                    IF(
                        r = height,
                        VSTACK(arrAcross, arrDiagonal, arrDiagonalNeg),
                        IF(
                            c = 1,
                            VSTACK(arrAcross, arrDown, arrDiagonal),
                            VSTACK(arrAcross, arrDown, arrDiagonal, arrDiagonalNeg)
                        )
                    )
                ),
                WordBank, VSTACK(dictionary, WordsReversed),
                FoundWords, VSTACK(dictionary, dictionary),
                GetWords, TOCOL(XLOOKUP(WordStack, WordBank, FoundWords, ""), 2),
                VSTACK(a, GetWords)
            )
        )
    ),
    SORT(FILTER(results, results <> "", "no words found"))
)