public
Created

This is the FP implementation of the "Telephone Words" where the program accept 7 digit ph number and spit out all possible word combination e.g. 464-7328 can be "GMGPDAS ... IMGREAT ... IOIRFCU"

  • Download Gist
Telephone Words
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
/*
http://blog.aunndroid.com/2011/11/learning-scala-recursion-and-tco-1.html
This is the FP implementation of the "Telephone Words"
where the program accept 7 digit ph number and spit out
all possible word combination e.g. 464-7328 can be
"GMGPDAS ... IMGREAT ... IOIRFCU"
Per following table, where 1 and 0 does not represent any alphabet
------------
| |ABC|DEF|
| 1 | 2 | 3 |
------------
|GHI|JKL|MNO|
| 4 | 5 | 6 |
-------------
|PQR|STU|VWX|
| 7 | 8 | 9 |
-------------
| | | |
| * | 0 | # |
-------------
*/
object TelWords {
def main(args : Array[String]) = {
val input = args.flatten.foldLeft(List[Int]()) {
case (l, x) if x.isDigit => l:+x.getNumericValue
case (l, x) => l
}.take(7)
if (input.length < 7) printUsage()
else {
val t0=System.currentTimeMillis();
val result = getTelWords(input)
val t1=System.currentTimeMillis();
val tailresult=tailGetTelWords(input)
val t2=System.currentTimeMillis();
printResult(tailresult)
println("For the number : "+input.mkString(""))
println("The two lists match : "+(tailresult.sorted == result.sorted)+"\nRegular Recursion : "+(t1-t0)+" TCO recursion : "+(t2-t1))
}
}
/*Generate the alphabet table*/
val alphabet = (for (ch <- 'a' to 'z') yield ch.toString).toList
 
/*Given the number, return the possible alphabet List of String(Instead of Char for convenience)*/
def getChars(num : Int) : List[String] = {
if (num > 1) return List[String](alphabet((num - 2) * 3), alphabet((num - 2) * 3 + 1), alphabet((num - 2) * 3 + 2))
List[String](num.toString)
}
 
/*Recursion without TCO*/
def getTelWords(input : List[Int]) : List[String] = {
if (input.length == 1) return getChars(input.head)
getChars(input.head).foldLeft(List[String]()) {
(l, ch) => getTelWords(input.tail).foldLeft(List[String]()) { (ll, x) => ch + x :: ll } ++ l
}
}
 
import scala.annotation.tailrec
/* TCO'ed function and supporting functions.
The TCO'ed function makes use of tracker, which is a List of alphabet variation already used.
e.g. List(0,0,0,0,0,0) means to create the string using the alphabet from the first position
thus, for 464732(8), it will be GMGPDA using all the first alphabet of corresponding number
List(0,0,0,0,0,1) will be GMGPDB
List(0,0,0,0,0,2) will be GMGPDC , then we need to move on to the next position
List(0,0,0,0,1,0) => GMGPEA , so it is simply incrementing the list
with the exception of the number 0,1 in e.g. 4641328 => GMG1DAS
*/
def tailGetTelWords(input : List[Int]) : List[String] = {
 
/*Check the end case */
def getTrackerCount(tracker : List[Int], input : List[Int]) : Int = {
tracker.foldLeft(0, 0) {
case ((count, pos), num) if (num == 2 || `input`(pos) <= 1) => (count + 1, pos + 1)
case ((count, pos), num) => (count, pos + 1)
}._1
}
/*Generating List of String from tracker*/
def getListFromTracker(tracker : List[Int], input : List[Int]) : List[String] = {
/* Using the tracker, we will create the String of 6 characters length */
val entry = tracker.foldLeft("", 0) {
case ((str, pos), num) if (`input`(pos) > 1) => (str + `alphabet`((`input`(pos) - 2) * 3 + num), pos + 1)
case ((str, pos), num) => (str + `input`(pos), pos + 1)
}._1
 
/*Append the last number's alphabets to the string and return the List*/
getChars(input.last).foldLeft(List[String]()) {
(l, end) => l :+ `entry` + end
}
}
 
@tailrec
/* Increment the tracker*/
def trackerAddition(tracker : List[Int], input : List[Int], pos : Int = input.length - 2) : List[Int] = {
// println(tracker+" : "+pos+" : "+input(pos))
if (input(pos) > 1 && tracker(pos) < 2) {
tracker.foldLeft(List[Int](), 0) {
case ((l, p), value) if (`pos` == p) => (l :+ `tracker`(`pos`) + 1, p + 1)
case ((l, p), value) => (l :+ value, p + 1)
}._1
} else {
trackerAddition(tracker.foldLeft(List[Int](), 0) {
case ((l, p), value) if (`pos` == p) => (l :+ 0, p + 1)
case ((l, p), value) => (l :+ value, p + 1)
}._1, input, pos - 1)
}
}
 
@tailrec
def tailRecursion(input : List[Int], tracker : List[Int], accu : List[String]) : List[String] = {
// println("tailRecursion tracker :" + tracker + " ")
if (getTrackerCount(tracker, input) == input.length - 1) return accu ++ getListFromTracker(tracker, input)
 
val trk = trackerAddition(tracker, input)
tailRecursion(input, trk, accu ++ getListFromTracker(tracker, input))
}
 
val trk = (for (i <- 0 until input.length - 1) yield 0).toList
tailRecursion(input, trk, List[String]())
}
 
def printResult(output : List[String]) = {
val result = output
println(result.mkString(" ") + "\n" + "posssible combination : " + result.length)
}
 
def printUsage() = {
val input = "1234567".foldLeft(List[Int]()) { (l, num) => num.getNumericValue :: l }.toList.reverse
//val result = getTelWords(input)
val result=tailGetTelWords(input)
printResult(result)
println("Above is the result of the usage example below.")
println("Usage is :")
println("scala TelWords.scala " + input.mkString(""))
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.