Jul 14 2022 12:13 PM - edited Jul 14 2022 12:14 PM
Jul 14 2022 12:13 PM - edited Jul 14 2022 12:14 PM
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.
Jul 14 2022 01:52 PM
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.
Jul 14 2022 02:42 PM
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 ));
Jul 14 2022 03:17 PM
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. @Sergei Baklan - 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.
Jul 16 2022 06:09 AMSolution
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 ) ));
Jul 16 2022 01:11 PM
Jul 19 2022 09:41 AM
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:
Jul 19 2022 04:10 PM
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.
Jul 19 2022 04:45 PM
Jul 20 2022 03:45 PM
Jul 21 2022 03:03 PM
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'.
Jul 22 2022 12:18 PM
Jul 22 2022 04:28 PM
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. @Sergei Baklan 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))
Jul 23 2022 02:43 AM - edited Jul 23 2022 02:44 AM
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?
Jul 24 2022 06:39 AM
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.
Jul 24 2022 07:59 AM
@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).
Jul 24 2022 10:45 AM
Jul 25 2022 05:32 AM