# Scala algorithm: Check word in grid (stack-safe)

Published

## 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-")
``````

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))
``````
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")
``````
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))
``````
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)
``````
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)
``````
7. ### View

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

# Scala Algorithms: The most comprehensive library of algorithms in standard pure-functional Scala

## How our 100 algorithms look

1. A description/goal of the algorithm.
2. An explanation with both Scala and logical parts.
3. A proof or a derivation, where appropriate.
4. Links to Scala concepts used in this specific algorithm, also unit-tested.
5. An implementation in pure-functional immutable Scala, with efficiency in mind (for most algorithms, this is for paid subscribers only).
6. Unit tests, with a button to run them immediately in our in-browser IDE.

### Study our 100 Scala Algorithms: 6 fully free, 100 published & 0 upcoming

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

### Explore the 22 most useful Scala concepts

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

## Subscribe to Scala Algorithms

Maximize your Scala with disciplined and consistently unit-tested solutions to 100+ algorithms.

Use it from improving your day-to-day data structures and Scala; all the way to interviewing.