SOLVED

A LAMBDA Word Search Puzzle

Silver Contributor

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)

Patrick2788_0-1657824914652.png

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.

 

 

28 Replies

@Patrick2788  so I finally got back to this and did my version.  Love to hear about the performance testing you do on them ....

 

 

 

=LET(
    h, ROWS(puzzleRange),
    w, COLUMNS(puzzleRange),
    space, " ",
    spaceLine, EXPAND(space, 1, w, space),
    PuzzleReverseH, CHOOSECOLS(puzzleRange, SEQUENCE(, w, w, -1)),
    PuzzleStack1, VSTACK(puzzleRange, spaceLine, PuzzleReverseH),
    PuzzleReverseV, CHOOSEROWS(PuzzleStack1, SEQUENCE(, 2 * h + 1, 2 * h + 1, -1)),
    PuzzleStack2, HSTACK(TRANSPOSE(puzzleRange), TRANSPOSE(TAKE(PuzzleReverseV, -h - 1, ))),
    PuzzleDiags, LAMBDA(stack,
        LET(
            nr, ROWS(stack),
            nc, COLUMNS(stack),
            REDUCE(
                EXPAND(INDEX(stack, , 1), nr + nc - 1, 1, space),
                SEQUENCE(nc - 1),
                LAMBDA(p, q,
                    HSTACK(
                        p,
                        EXPAND(
                            VSTACK(EXPAND(space, q, 1, space), INDEX(stack, , q + 1)),
                            nr + nc - 1,
                            1,
                            space
                        )
                    )
                )
            )
        )
    ),
    PuzzleStacksHalf1, VSTACK(
        PuzzleStack1,
        spaceLine,
        PuzzleDiags(VSTACK(PuzzleStack1, spaceLine, PuzzleReverseV))
    ),
    PuzzleStacksHalf2, PuzzleStack2,
    findWord, LAMBDA(puzzlestack,
        REDUCE(
            "",
            SEQUENCE(ROWS(puzzlestack)),
            LAMBDA(p, r,
                VSTACK(
                    p,
                    FILTER(
                        dictionary,
                        ISNUMBER(SEARCH(dictionary, CONCAT(INDEX(puzzlestack, r, )))),
                        ""
                    )
                )
            )
        )
    ),
    findWords, VSTACK(findWord(PuzzleStacksHalf1), findWord(PuzzleStacksHalf2)),
    out, SORT(FILTER(findWords, findWords <> "")),
    out
)

 

 

ok so I did a quick test and mine seems to fair pretty well.  (*** note I have made a few edits as I found my diagonals were not as I thought and needed to adjust my sets to get all 4 diagonals correctly.  Note, I also found that your solution is also missing some)

btw my concept was to take the puzzle and create a stack of:

orig puzzle, 

puzzle reversed by rows, columns, and both

the above 2 shifted by 1 row for each column (i.e. creating the diagonals)

and then find any words found in any row

and repeat for the transpose of the orig and rev by rows to get vertical up/down words.

so I originally output the UNIQUE list but noted you showed all.  As noted above I orig had some issues with missing 1 or 2 diagonals so my list had some you didn't you had some i didn't.  I fixed it and now have every word in your list but when I removed UNIQUE i notice you have more copies in a couple cases.  I don't know why that is the case but submit this as is for now)

@mtarler 

I didn't pull duplicates because I figure if a word appears more than once in the puzzle the formula should return each instance.

 

The big difference between the solutions is I have the expensive operation of reversing the dictionary entries.  My first thought was to move ReverseWords from Solve to a new named item.

 

The result:

Patrick2788_0-1690924639147.png

 

Next, I swapped out MAP (e.g.  MAP(dictionary, LAMBDA(e,Reverse(e))) for the other Lambda helper functions to see the difference.

The results:

Patrick2788_1-1690924759496.png

For grins, I even tested REDUCE:

Patrick2788_0-1690925318861.png

 

Is there a more efficient way to reverse each element in a vector?  The main obstacle being that 'exploding' an array is scalar-based so Lambda helpers are needed to deploy 'Explode' on each element.

 

@Patrick2788 @SergeiBaklan @Peter Bartholomew @mtarler 

 

I had a go at solving using a lambda I created a while back called ROTATE. It rotates an array by 90 degrees. By stacking the four rotations and joining the text on each row, I think it becomes a case of scanning the "search for" items against the array of rows. 

 

Spent about 10 minutes on this today. I think it works (and quite quickly), but would appreciate your feedback. 

 

Owen

 

/*
ROTATE
Author: Owen Price
Date: 2022-09-10

Rotates a 2-dimensional array anti-clockwise by 90 degrees. 

This is not the same behavior as TRANSPOSE, which reflects an array on the main diagonal
from top-left to bottom-right.

Inputs:
- arr - the input array
- times - the number of times to rotate by 90 degrees
- [iter] - optional - used as a counter by the recursion

Note: iter should not be used when calling this function from a spreadsheet
*/

ROTATE = LAMBDA(arr,times,[iter],
    LET(
        _times,MOD(times,4),
        IF(_times=0,arr,
            LET(_iter,IF(ISOMITTED(iter),1,iter),
                _cols,COLUMNS(arr),
                _rotated,INDEX(arr,SEQUENCE(1,ROWS(arr)),_cols-SEQUENCE(_cols)+1),
                IF(_iter=_times,_rotated,ROTATE(_rotated,_times,_iter+1))))));

RotatedStacked = IFERROR(VSTACK(Puzzle,ROTATE(Puzzle,1),ROTATE(Puzzle,2),ROTATE(Puzzle,3)),"");

AsRows = BYROW(RotatedStacked,LAMBDA(r,TEXTJOIN("",TRUE,r)));

fnIsFound = LAMBDA(text, OR(NOT(ISERROR(SEARCH(text,AsRows)))));

Search = REDUCE(,table1[Word List:],LAMBDA(a,b,IF(fnIsFound(b),VSTACK(a,b),a)));
similar in concept to mine. I just flipped horizontal, vertical and both. The tricky part was the diagonals which I think you missed. That said, I think yours could be more efficient if you created 3 rotated temps and called your ROTATE using the prior each time so that function doesn't need to repeat those iterations:
RotatedStacked = LET( _R1, ROTATE(Puzzle,1), _R2, ROTATE(_R1,1), _R3, ROTATE(_R2,1), VSTACK(Puzzle,_R1,_R2,_R3) )

@flexyourdata 

I like the Rotate Lambda. A nifty bit of recursion! I've tested it on square and non-square matrices, and it never fails.

 

This is my variant:

 

 

 

RotateM(matrix,turns)
=IF(
    turns = 0,
    matrix,
    RotateM(
        LET(r, ROWS(TRANSPOSE(matrix)), CHOOSEROWS(TRANSPOSE(matrix), SEQUENCE(r, , r, -1))),
        turns - 1
    )
)
can I ask why you have ROWS(TRANSPOSE(matrix)) instead of COLUMNS(matrix) ?

@mtarler 

 

Great point about minimizing the rotations needed to get all positions. Now I want to make the times arg optional with default 1. :happyface:

@Patrick2788 

 

Very neat! I like the way you've used turns-1 to avoid the iter arg. Makes a lot of sense now I see it. 

 

I think I wrote mine before I had a good grasp of CHOOSECOLS. Although I still think it's problematic in some situations where returning single-cell arrays into other functions, what you've done here is really nice. 

On my first draft of the function, I noticed I wasn't accounting for non-square matrices. The function worked on 1 spin but failed on 2+. I went back and realized the problem was where I pulled R from and how it was a step behind. I used the nesting of ROWS-TRANSPOSE because it's how I anticipated the move in my head, if that makes sense. Recursion is usually not my first go-to and it shows a bit here. I do like how recursive functions can be very concise.