# Scala algorithm: Compute keypad possibilities

Published

## Algorithm goal

On a classic mobile keypad, a key can produce a different letter based on the number of times it's pressed. Pressing 2 once writes 'a', twice produces 'b', and so forth.

Produce a list of possible letter combinations that can be achieved via key presses, eg '4', '2', can produce 'ga', 'gb', 'gc', 'ha', 'hb', 'hc', 'ia', 'ib', 'ic'.

## Test cases in Scala

``````assert(crossProduct(List.empty[Set[Int]]).toList == List(List.empty))
assert(
crossProduct(List(Set(1, 2, 3), Set(4, 5, 6))).toList == List(
List(1, 4),
List(1, 5),
List(1, 6),
List(2, 4),
List(2, 5),
List(2, 6),
List(3, 4),
List(3, 5),
List(3, 6)
)
)
assert(keypadCombinations("7").toSet == Set("p", "q", "r", "s"))
assert(
Set("ga", "gb", "gc", "ha", "hb", "hc", "ia", "ib", "ic")
)
assert(
"No stack overflow when generating a large first combination"
)
``````

## Algorithm in Scala

26 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!

## Explanation

In essence, we need a function that produced a cross product. We choose to use a lazy way to produce this set of combinations, in order to be more memory efficient as any type of 'combination' or 'permutation' typically produces a large set of data.

To produce a cross-product of all the variations in 'crossProduct', we iterate through the list, and for each possibility of a variation, we combine it with the cross-product of the remaining variations using a for-comprehension that is recursive. (this is © from www.scala-algorithms.com)

Lastly, to utilize this generic function, we take a cross product all the possible letters for each input from the keypad, and create a String output from that.

## Scala concepts & Hints

1. ### 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))
``````
2. ### Lazy List

The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').

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

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

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

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

### Explore the 21 most useful Scala concepts

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

## Register now (free)

Register with GitHub

This gives you access to free test cases & hints for all our 89 published algorithms as well as our installation-free Scala IDE.

You can then choose to subscribe to "Scala Algorithms Unlimited", which gets you access to every current and upcoming algorithm solution. We use Stripe so your data is safe.

We will e-mail you at most once per week with new algorithms and relevant content.
Your data is protected and unsubscribing is straightforward. 