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"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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("")) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment