Skip to content

Instantly share code, notes, and snippets.

@wmhtet
Created November 22, 2011 23:16
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save wmhtet/1387374 to your computer and use it in GitHub Desktop.
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"
/*
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