Scala algorithm: Compute keypad possibilities
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("").isEmpty) assert(keypadCombinations("7").toSet == Set("p", "q", "r", "s")) assert( keypadCombinations("42").toSet == Set("ga", "gb", "gc", "ha", "hb", "hc", "ia", "ib", "ic") ) assert( keypadCombinations(List.fill(102)("2").mkString).head.nonEmpty, "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!
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
The for-comprehension is highly important syntatic enhancement in functional programming languages.
The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').
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.