Determine whether a specified word exists contiguously a grid. The rules are: letters cannot be re-used, you can only go left, right, up, or down. For example, 'ALGO' is a word in the following grid:
ALGQ WGRQ WORQ SWOD
Test cases in Scala
assert( wordInGridStackSafe( Array( Array('A', 'L', 'G', 'Q'), Array('W', 'G', 'R', 'Q'), Array('W', 'O', 'R', 'Q'), Array('S', 'W', 'O', 'D') ), "ALGO" ) ) assert( !wordInGridStackSafe( Array( Array('A', 'L', 'E', 'Q'), Array('W', 'G', 'R', 'Q'), Array('W', 'L', 'R', 'Q'), Array('S', 'W', 'O', 'D') ), "ALGLE" ) ) assert( wordInGridStackSafe( Array( Array('A', 'L', 'E', 'Q'), Array('W', 'G', 'R', 'Q'), Array('W', 'L', 'E', 'Q'), Array('S', 'W', 'O', 'D') ), "ALGLE" ) )
Algorithm in Scala
41 lines of Scala (compatible versions 2.13 & 3.0).
This solution is stack-safe (Stack Safety), especially useful when searching longer words.
We first turn the grid into a map for ease of lookup, and then instead of doing a recursive step, we create a list of 'next considerations', which we then pass into the tail-recursive step. (this is © from www.scala-algorithms.com)
Items are not ignored, but rather, explicitly stated as remaining/available, unlike in the other solution CheckWordInGridDepthFirst, to demonstrate a different way to going about it.
Scala concepts & Hints
Def Inside Def
A great aspect of Scala is being able to declare functions inside functions, making it possible to reduce repetition.
It is also frequently used in combination with Tail Recursion.
The for-comprehension is highly important syntatic enhancement in functional programming languages.
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
(1 to n)syntax produces a "Range" which is a representation of a sequence of numbers.
Stack safety is present where a function cannot crash due to overflowing the limit of number of recursive calls.
This function will work for n = 5, but will not work for n = 2000 (crash with java.lang.StackOverflowError) - however there is a way to fix it :-)
In Scala Algorithms, we try to write the algorithms in a stack-safe way, where possible, so that when you use the algorithms, they will not crash on large inputs. However, stack-safe implementations are often more complex, and in some cases, overly complex, for the task at hand.
In Scala, tail recursion enables you to rewrite a mutable structure such as a while-loop, into an immutable algorithm.
.viewsyntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.