Algorithm goal

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).

Explanation

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

1. Def Inside Def

   A great aspect of Scala is being able to declare functions inside functions, making it possible to reduce repetition.

   def exampleDef(input: String): String = {
     def surroundInputWith(char: Char): String = s"$char$input$char"
     surroundInputWith('-')
   }
   
   assert(exampleDef("test") == "-test-")
   

   ▶ Run code in the IDE

   It is also frequently used in combination with Tail Recursion.

2. For-comprehension

   The for-comprehension is highly important syntatic enhancement in functional programming languages.

   val Multiplier = 10
   
   val result: List[Int] = for {
     num <- List(1, 2, 3)
     anotherNum <-
       List(num * Multiplier - 1, num * Multiplier, num * Multiplier + 1)
   } yield anotherNum + 1
   
   assert(result == List(10, 11, 12, 20, 21, 22, 30, 31, 32))
   

   ▶ Run code in the IDE

3. Pattern Matching

   Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

   assert("Hello World".collect {
     case character if Character.isUpperCase(character) => character.toLower
   } == "hw")
   

   ▶ Run code in the IDE

4. Range

   The (1 to n) syntax produces a "Range" which is a representation of a sequence of numbers.

   assert((1 to 5).toString == "Range 1 to 5")
   
   assert((1 to 5).reverse.toString() == "Range 5 to 1 by -1")
   
   assert((1 to 5).toList == List(1, 2, 3, 4, 5))
   

   ▶ Run code in the IDE

5. Stack Safety

   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.

   def sum(from: Int, until: Int): Int =
     if (from == until) until else from + sum(from + 1, until)
   
   def thisWillSucceed: Int = sum(1, 5)
   
   def thisWillFail: Int = sum(1, 300)
   

   ▶ Run code in the IDE

6. Tail Recursion

   In Scala, tail recursion enables you to rewrite a mutable structure such as a while-loop, into an immutable algorithm.

   def fibonacci(n: Int): Int = {
     @scala.annotation.tailrec
     def go(i: Int, previous: Int, beforePrevious: Int): Int =
       if (i >= n) previous else go(i + 1, previous + beforePrevious, previous)
   
     go(i = 1, previous = 1, beforePrevious = 0)
   }
   
   assert(fibonacci(8) == 21)
   

   ▶ Run code in the IDE

7. View

   The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.