Forum Discussion
Patrick2788
Jul 14, 2022Silver Contributor
A LAMBDA Word Search Puzzle
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.
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 ) ));
- flexyourdataIron Contributor
Patrick2788 SergeiBaklan PeterBartholomew1 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)));
- Patrick2788Silver Contributor
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 ) )
- flexyourdataIron Contributor
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.
- mtarlerSilver Contributorsimilar 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) )- flexyourdataIron Contributor
Great point about minimizing the rotations needed to get all positions. Now I want to make the times arg optional with default 1.
- PeterBartholomew1Silver Contributor
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'.
- Patrick2788Silver Contributor
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))
- PeterBartholomew1Silver Contributor
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?
Nice idea, need to play with it bit more. Do I understood correctly you don't generate "Words found in puzzle" ?
- PeterBartholomew1Silver ContributorTrue. 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.
Perhaps close to PeterBartholomew1 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 ));
- PeterBartholomew1Silver Contributor
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.
- Patrick2788Silver Contributor
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.
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 ) ));