# 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

## How the 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.