Kalanand's October 2014 Log
October 1st
Scala week-2: improving methods implemented in week-1
package example
import math.abs
object fixedpoint {
val tolerance = 0.0001 //> tolerance : Double = 1.0E-4
def isCloseEnough(x: Double, y: Double) =
abs((x - y) / x) / x < tolerance //> isCloseEnough: (x: Double, y: Double)Boolean
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
} //> fixedPoint: (f: Double => Double)(firstGuess: Double)Double
fixedPoint(x => 1 + x / 2)(1) //> res0: Double = 1.999755859375
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2
//> averageDamp: (f: Double => Double)(x: Double)Double
def sqrt(x: Double) = fixedPoint( averageDamp(y => x / y))(1)
//> sqrt: (x: Double)Double
sqrt(2) //> res1: Double = 1.4142135623746899
}
October 2nd
How to delete a song from iTunes library from the playlist view
Ordinarily, pressing the delete key while in a playlist only prompts me to remove the song from that playlist.
To remove it from the library entirely, I needed to press Option+Delete.
This keyboard shortcut saves the hassle of going all the way back to the "Music" view in order to delete songs.
October 4th
Scala week-2 continued: functions
package example
object functions {
val x = new Rational(1, 3) //> x : example.Rational = 1/3
val y = new Rational(5, 7) //> y : example.Rational = 5/7
val z = new Rational(3, 2) //> z : example.Rational = 3/2
x.numer //> res0: Int = 1
x.denom //> res1: Int = 3
def addRational(r: Rational, s: Rational): Rational =
new Rational(r.numer * s.denom + s.numer * r.denom,
r.denom * s.denom) //> addRational: (r: example.Rational, s: example.Rational)example.Rational
def makeString(r: Rational) =
r.numer + "/" + r.denom //> makeString: (r: example.Rational)String
makeString(addRational(new Rational(1, 2), new Rational(2, 3)))
//> res2: String = 7/6
x - y - z //> res3: example.Rational = -79/42
y+ y //> res4: example.Rational = 10/7
x < y //> res5: Boolean = true
x.max(y) //> res6: example.Rational = 5/7
}
class Rational(x: Int, y: Int) {
require( y != 0, "denominator must be non-zero")
def this(x: Int) = this(x, 1)
private def gcd(a: Int, b: Int): Int = if(b==0) a else gcd(b, a % b)
private val g = gcd(x, y)
def numer = x / g
def denom = y / g
def < (that: Rational) = numer * that.denom < denom * that.numer
def max(that: Rational) = if(this < that) that else this
def + (that: Rational) = new Rational(
numer * that.denom + that.numer * denom,
denom * that.denom)
def unary_- : Rational = new Rational(-numer, denom)
def - (that: Rational) = this + -that
override def toString = numer + "/" + denom
}
October 5th
Scala week-3: maps and sets
package example
import common._
object scrapsheet {
/**
* We represent a set by its characteristic function, i.e.
* its `contains` predicate.
*/
type Set = Int => Boolean
/**
* Indicates whether a set contains a given element.
*/
def contains(s: Set, elem: Int): Boolean = s(elem)
//> contains: (s: Int => Boolean, elem: Int)Boolean
/**
* Returns the set of the one given element.
*/
def singletonSet(elem: Int): Set = (x: Int) => x == elem
//> singletonSet: (elem: Int)Int => Boolean
/**
* Returns the union of the two given sets,
* the sets of all elements that are in either `s` or `t`.
*/
def union(s: Set, t: Set): Set = (x: Int) => s(x) || t(x)
//> union: (s: Int => Boolean, t: Int => Boolean)Int => Boolean
/**
* Returns the intersection of the two given sets,
* the set of all elements that are both in `s` and `t`.
*/
def intersect(s: Set, t: Set): Set = (x: Int) => s(x) && t(x)
//> intersect: (s: Int => Boolean, t: Int => Boolean)Int => Boolean
/**
* Returns the difference of the two given sets,
* the set of all elements of `s` that are not in `t`.
*/
def diff(s: Set, t: Set): Set = (x: Int) => s(x) && !t(x)
//> diff: (s: Int => Boolean, t: Int => Boolean)Int => Boolean
/**
* Returns the subset of `s` for which `p` holds.
*/
def filter(s: Set, p: Int => Boolean): Set = (x: Int) => s(x) && p(x)
//> filter: (s: Int => Boolean, p: Int => Boolean)Int => Boolean
/**
* The bounds for `forall` and `exists` are +/- 1000.
*/
val bound = 1000 //> bound : Int = 1000
/**
* Returns whether all bounded integers within `s` satisfy `p`.
*/
def forall(s: Set, p: Int => Boolean): Boolean = {
def iter(a: Int): Boolean = {
if (a > bound) true
else if (s(a)== true && p(a)==false) false
else iter(a+1)
}
iter(-bound)
} //> forall: (s: Int => Boolean, p: Int => Boolean)Boolean
/**
* Returns whether there exists a bounded integer within `s`
* that satisfies `p`.
*/
def exists(s: Set, p: Int => Boolean): Boolean =
!forall(s, (x: Int) => !p(x) ) //> exists: (s: Int => Boolean, p: Int => Boolean)Boolean
/**
* Returns a set transformed by applying `f` to each element of `s`.
*/
def map(s: Set, f: Int => Int): Set = (x: Int) => exists(s, (y: Int) => f(y) ==x)
//> map: (s: Int => Boolean, f: Int => Int)Int => Boolean
/**
* Displays the contents of a set
*/
def toString(s: Set): String = {
val xs = for (i <- -bound to bound if contains(s, i)) yield i
xs.mkString("{", ",", "}")
} //> toString: (s: Int => Boolean)String
/**
* Prints the contents of a set on the console.
*/
def printSet(s: Set) {
println(toString(s))
} //> printSet: (s: Int => Boolean)Unit
contains(Set(1, 2), 1) //> res0: Boolean = true
singletonSet(1) //> res1: Int => Boolean =
contains( union( Set(1,2,3), Set(3,4,5) ), 7) //> res2: Boolean = false
contains( filter( Set(1,2,3,4,5,6), Set(3,5) ), 3)
//> res3: Boolean = true
printSet(Set(1,2,3)) //> {1,2,3}
printSet( map( Set(1,2,3,4,5,6,7,8), (x: Int) => 2*x) )
//> {2,4,6,8,10,12,14,16}
forall( Set(2,4,6,8), (x: Int) => x % 2==0) //> res4: Boolean = true
}
October 11th
Scala week-4: Evaluating expressions
package week4
object exprs {
def eval(e: Expr): Int = e match {
case Number(n) => n
case Sum(e1, e2) => eval(e1) + eval(e2)
} //> eval: (e: week4.Expr)Int
def show(e: Expr): String = e match {
case Number(x) => x.toString
case Var(x) => x
case Sum(l, r) => show(l) + " + " + show(r)
case Prod(l: Number, r: Number) => show(l) + " * " + show(r)
case Prod(l: Number, r: Var) => show(l) + " * " + show(r)
case Prod(l: Var, r: Number) => show(l) + " * " + show(r)
case Prod(l: Number, r) => show(l) + " * (" + show(r) + ")"
case Prod(l, r: Number) => "(" + show(l) + ") * " + show(r)
case Prod(l: Var, r: Var) => show(l) + " * " + show(r)
case Prod(l: Var, r) => show(l) + " * (" + show(r) + ")"
case Prod(l, r: Var) => "(" + show(l) + ") * " + show(r)
case Prod(l, r) => "(" + show(l) + ") * (" + show(r) + ")"
} //> show: (e: week4.Expr)String
show(Sum(Number(1), Number(44))) //> res0: String = 1 + 44
show(Sum(Prod(Number(2), Var("x")), Var("y"))) //> res1: String = 2 * x + y
show(Prod(Sum(Number(2), Var("x")), Var("y"))) //> res2: String = (2 + x) * y
}
October 12th
Scala week-4 continued: expressions and numbers
Let's first define a trait for numbers and have various classes like sum, product, etc inherit from it.
package week4
trait Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr
case class Var(name: String) extends Expr
case class Prod(x: Expr, y: Expr) extends Expr
Now, let's create an object which is a set of integers.
package week4
object intsets {
val t1 = new NonEmpty(3, new Empty, new Empty) //> t1 : example.NonEmpty = {.3.}
val t2 = t1 incl 4 //> t2 : example.IntSet = {.3{.4.}}
}
abstract class IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
def union(other: IntSet): IntSet
}
class Empty extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty)
def union(other: IntSet): IntSet = other
override def toString = "."
}
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
def contains(x: Int): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
def incl(x: Int): IntSet =
if (x < elem) new NonEmpty(elem, left incl x, right)
else if (x > elem) new NonEmpty(elem, left, right incl x)
else this
def union(other: IntSet): IntSet =
((left union right) union other) incl elem
override def toString = "{" + left + elem + right + "}"
}
October 15th
Scala week-4 continued: lists
Define list as a trait, then define its properties as classes, and finally create a list object.
package week4
trait List[+T] {
def isEmpty: Boolean
def head: T
def tail: List[T]
def prepend[U >: T] (elem: U): List[U] = new Cons(elem, this)
}
class Cons[T](val head: T, val tail: List[T]) extends List[T] {
def isEmpty = false
}
object Nil extends List[Nothing] {
def isEmpty: Boolean = true
def head: Nothing = throw new NoSuchElementException("Nil.head")
def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}
object test {
val x: List[String] = Nil
def f(xs: List[NonEmpty], x: Empty) = xs prepend x
}
Class of natural numbers
package week4
// Peano numbers
abstract class Nat {
def isZero: Boolean
def predecessor: Nat
def successor: Nat = new Succ(this)
def +(that: Nat): Nat
def -(that: Nat): Nat
}
object Zero extends Nat {
def isZero = true
def predecessor = throw new Error("0.predecessor")
def +(that: Nat) = that
def -(that: Nat) = if(that.isZero) this else throw new Error("negative number")
}
class Succ(n: Nat) extends Nat {
def isZero = false
def predecessor = n
def +(that: Nat) = new Succ(n + that)
def -(that: Nat) = if(this.isZero) this else n - that.predecessor
}
October 19th
Scala week-5: operations on lists
package week5
object listfun {
val nums = List(2, -4, 5, 7, 1) //> nums : List[Int] = List(2, -4, 5, 7, 1)
val fruits = List("apple", "pineapple", "orange", "banana")
//> fruits : List[String] = List(apple, pineapple, orange, banana)
nums filter (x => x > 0) //> res0: List[Int] = List(2, 5, 7, 1)
nums filterNot (x => x > 0) //> res1: List[Int] = List(-4)
nums partition (x => x > 0) //> res2: (List[Int], List[Int]) = (List(2, 5, 7, 1),List(-4))
nums takeWhile (x => x > 0) //> res3: List[Int] = List(2)
nums dropWhile (x => x > 0) //> res4: List[Int] = List(-4, 5, 7, 1)
nums span (x => x > 0) //> res5: (List[Int], List[Int]) = (List(2),List(-4, 5, 7, 1))
def pack[T](xs: List[T]): List[List[T]] = xs match {
case Nil => Nil
case x :: xs1 =>
val (first, rest) = xs span (y => y == x)
first :: pack(rest)
} //> pack: [T](xs: List[T])List[List[T]]
def encode[T](xs: List[T]): List[(T, Int)] =
pack(xs) map (ys => (ys.head, ys.length)) //> encode: [T](xs: List[T])List[(T, Int)]
val data = List("a", "a", "a", "b", "c", "c", "a")
//> data : List[String] = List(a, a, a, b, c, c, a)
pack(data) //> res6: List[List[String]] = List(List(a, a, a), List(b), List(c, c), List(a))
//|
encode(data) //> res7: List[(String, Int)] = List((a,3), (b,1), (c,2), (a,1))
def sum(xs: List[Int]) = (0::xs) reduceLeft(_+_)//> sum: (xs: List[Int])Int
def product(xs: List[Int]) = (1 :: xs) reduceLeft(_ * _)
//> product: (xs: List[Int])Int
def concat[T](xs: List[T], ys: List[T]) =
(xs foldRight ys) (_ :: _) //> concat: [T](xs: List[T], ys: List[T])List[T]
}
October 20th
Scala week-5 continued: merge sort using lists
package week5
object mergesort {
def msort(xs: List[Int]): List[Int] = {
val n = xs.length / 2
if (n == 0) xs
else {
def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {
case (Nil, ys) => ys
case (xs, Nil) => xs
case (x :: xs1, y :: ys1) =>
if (x < y) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
val (fst, snd) = xs splitAt n
merge(msort(fst), msort(snd))
}
} //> msort: (xs: List[Int])List[Int]
val nums = List(2, -4, 5, 7, 1) //> nums : List[Int] = List(2, -4, 5, 7, 1)
msort(nums) //> res0: List[Int] = List(-4, 1, 2, 5, 7)
}
Generalization
We can make the above implementation of merge sort more generic.
Here is an improved version.
package week5
import math.Ordering
object mergesort2 {
def msort[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = {
val n = xs.length / 2
if (n == 0) xs
else {
def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
case (Nil, ys) => ys
case (xs, Nil) => xs
case (x :: xs1, y :: ys1) =>
if (ord.lt(x, y)) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
val (fst, snd) = xs splitAt n
merge(msort(fst), msort(snd))
}
} //> msort: [T](xs: List[T])(implicit ord: scala.math.Ordering[T])List[T]
val nums = List(2, -4, 5, 7, 1) //> nums : List[Int] = List(2, -4, 5, 7, 1)
val fruits = List("apple", "pineapple", "orange", "banana")
//> fruits : List[String] = List(apple, pineapple, orange, banana)
msort(nums) //> res0: List[Int] = List(-4, 1, 2, 5, 7)
msort(fruits) //> res1: List[String] = List(apple, banana, orange, pineapple)
}
Removing elements from list
package week5
object week5 {
def
removeAt[T](xs: List[T],n: Int) = (xs take n) ::: (xs drop n + 1)
//> removeAt: [T](xs: List[T], n: Int)List[T]
}
October 25th
Scala week-6: list of books as an example
package week6
object books {
case class Book(title: String, authors: List[String])
val books = List(
Book(
title = "Structure and Interpretation of Computer Programs",
authors = List("Abelson, Harald", "Sussman, Gerald J.")),
Book(
title = "Introduction to Functional Programming",
authors = List("Bird, Richard", "Wadler, Phil")),
Book(
title = "Effective Java",
authors = List("Bloch, Joshua")),
Book(
title = "Java Puzzlers",
authors = List("Bloch, Joshua", "Gafter, Neal")),
Book(
title = "Programming in Scala",
authors = List("Odersky, Martin", "Spoon, Lex", "Venners, Bill")))
//> books : List[week6.books.Book] = List(Book(Structure and Interpretation of
//| Computer Programs,List(Abelson, Harald, Sussman, Gerald J.)), Book(Introduct
//| ion to Functional Programming,List(Bird, Richard, Wadler, Phil)), Book(Effec
//| tive Java,List(Bloch, Joshua)), Book(Java Puzzlers,List(Bloch, Joshua, Gafte
//| r, Neal)), Book(Programming in Scala,List(Odersky, Martin, Spoon, Lex, Venne
//| rs, Bill)))
for (b <- books; a <- b.authors if a startsWith "Bloch,")
yield b.title //> res0: List[String] = List(Effective Java, Java Puzzlers)
for {
b1 <- books
b2 <- books
if b1.title < b2.title
a1 <- b1.authors
a2 <- b2.authors
if a1 == a2
} yield a1 //> res1: List[String] = List(Bloch, Joshua)
}
An example showing use of maps
package week6
object maps {
val romanNumerals = Map('I' -> 1, 'V' -> 5, 'X' -> 10)
//> romanNumerals : scala.collection.immutable.Map[Char,Int] = Map(I -> 1, V ->
//| 5, X -> 10)
val capitalOfCountry = Map("US" -> "Washington", "Switzerland" -> "Bern")
//> capitalOfCountry : scala.collection.immutable.Map[String,String] = Map(US -
//| > Washington, Switzerland -> Bern)
def showCapital(country: String) = capitalOfCountry.get(country) match {
case Some(capital) => capital
case None => "missing data"
} //> showCapital: (country: String)String
showCapital("US") //> res0: String = Washington
showCapital("Andorra") //> res1: String = missing data
}
More examples using maps, arrays, and lists
package week6
object week6 {
val xs = Array(1, 2, 3, 44) //> xs : Array[Int] = Array(1, 2, 3, 44)
xs map ( x => x * 2) //> res0: Array[Int] = Array(2, 4, 6, 88)
val s = "Hello World" //> s : String = Hello World
s filter (c => c.isUpper) //> res1: String = HW
s exists (c => c.isUpper) //> res2: Boolean = true
s forall (c => c.isUpper) //> res3: Boolean = false
val pairs = List(1, 2, 3) zip s //> pairs : List[(Int, Char)] = List((1,H), (2,e), (3,l))
pairs.unzip //> res4: (List[Int], List[Char]) = (List(1, 2, 3),List(H, e, l))
s flatMap (c => List('.', c)) //> res5: String = .H.e.l.l.o. .W.o.r.l.d
xs.sum //> res6: Int = 50
xs.product //> res7: Int = 264
xs.max //> res8: Int = 44
xs.min //> res9: Int = 1
/* To list all combinations of numbers x and y where x is drawn from 1..M and y is drawn from 1..N: */
(1 until 10) flatMap (x => (1 until 5) map (y => (x, y)))
//> res10: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (1,
//| 2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4), (4
//| ,1), (4,2), (4,3), (4,4), (5,1), (5,2), (5,3), (5,4), (6,1), (6,2), (6,3), (
//| 6,4), (7,1), (7,2), (7,3), (7,4), (8,1), (8,2), (8,3), (8,4), (9,1), (9,2),
//| (9,3), (9,4))
/* To compute the scalar product of two vectors */
def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
(xs zip ys).map(xy => xy._1 * xy._2).sum //> scalarProduct: (xs: Vector[Double], ys: Vector[Double])Double
def isPrime(n: Int): Boolean = (2 until n) forall (d => n % d != 0)
//> isPrime: (n: Int)Boolean
isPrime(5) //> res11: Boolean = true
}
Pairs
package week6
object pairs {
val n = 7 //> n : Int = 7
def isPrime(n: Int): Boolean = (2 until n) forall (d => n % d != 0)
//> isPrime: (n: Int)Boolean
/* Given a positive integer n, find all pairs of positive integers
i and j, with 1 <= j < i < n such that i + j is prime. */
for {
i <- 1 until n
j <- 1 until i
if isPrime(i + j)
} yield (i, j) //> res0: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((2,1), (3,2
//| ), (4,1), (4,3), (5,2), (6,1), (6,5))
/* Scalar product again */
def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
(for( (x,y) <- xs zip ys) yield x*y).sum //> scalarProduct: (xs: Vector[Double], ys: Vector[Double])Double
}
October 26th
Scala week-6 continued: the classic n-queens problem !
package week6
object nqueens {
/* Find the solution of classical n-queens problem on a n x n chess board */
def queens(n: Int): Set[List[Int]] = {
def placeQueens(k: Int): Set[List[Int]] =
if (k == 0) Set(List()) /* return empty list*/
else /* check the remaining n-1 queens and see if it is safe to place*/
for {
queens <- placeQueens(k - 1)
col <- 0 until n
if isSafe(col, queens)
} yield col :: queens
placeQueens(n)
} //> queens: (n: Int)Set[List[Int]]
/* Checks if it is safe to place a queen in a given column */
def isSafe(col: Int, queens: List[Int]): Boolean = {
val row = queens.length
val queensWithRow = (row - 1 to 0 by -1) zip queens
queensWithRow forall {
case (r, c) => col != c && math.abs(col - c) != row - r
}
} //> isSafe: (col: Int, queens: List[Int])Boolean
/* Utility for nice print out */
def show(queens: List[Int]) = {
val lines = for (col <- queens.reverse)
yield Vector.fill(queens.length)("* ").updated(col, "X ").mkString
"\n" + (lines mkString "\n")
} //> show: (queens: List[Int])String
(queens(8) take 3 map show) mkString "\n" //> res0: String = "
//| * * * * * X * *
//| * * * X * * * *
//| * X * * * * * *
//| * * * * * * * X
//| * * * * X * * *
//| * * * * * * X *
//| X * * * * * * *
//| * * X * * * * *
//|
//| * * * * X * * *
//| * * * * * * X *
//| * X * * * * * *
//| * * * X * * * *
//| * * * * * * * X
//| X * * * * * * *
//| * * X * * * * *
//| * * * * * X * *
//|
//| * * * * * X * *
//| * * X * * * * *
//| * * * * * * X *
//| * * * X * * * *
//| X * * * * * * *
//| * * * * * * * X
//| * X * * * * * *
//| * * * * X * * * "
}
Polynomials
package week6
object polynomials {
class Poly(val terms0: Map[Int, Double]) {
def this(bindings: (Int, Double)*) = this(bindings.toMap)
val terms = terms0 withDefaultValue 0.0
def +(other: Poly) = new Poly((other.terms foldLeft terms)(addTerm))
def addTerm(terms: Map[Int, Double], term: (Int, Double)): Map[Int, Double] = {
val (exp, coeff) = term
terms + (exp -> (coeff + terms(exp)))
}
override def toString =
(for ((exp, coeff) <- terms.toList.sorted.reverse) yield coeff + "x^" + exp) mkString "+"
}
val p1 = new Poly(1 -> 2.0, 3 -> 4.0, 5 -> 6.2) //> p1 : week6.polynomials.Poly = 6.2x^5+4.0x^3+2.0x^1
val p2 = new Poly(0 -> 3.0, 3 -> 7.0) //> p2 : week6.polynomials.Poly = 7.0x^3+3.0x^0
p1 + p2 //> res0: week6.polynomials.Poly = 6.2x^5+11.0x^3+2.0x^1+3.0x^0
p1.terms(7) //> res1: Double = 0.0
}
October 29th
Scala week-6 continued: make mnemonics for telephone numbers
package week6
import scala.io.Source
object telephone {
val in = Source.fromURL("http://lamp.epfl.ch/files/content/sites/lamp/files/teaching/progfun/linuxwords.txt")
//> in : scala.io.BufferedSource = non-empty iterator
val words = in.getLines.toList filter (word => word forall (chr => chr.isLetter))
//> words : List[String] = List(Aarhus, Aaron, Ababa, aback, abaft, abandon, ab
//| andoned, abandoning, abandonment, abandons, abase, abased, abasement, abasem
//| ents, abases, abash, abashed, abashes, abashing, abasing, abate, abated, aba
//| tement, abatements, abater, abates, abating, Abba, abbe, abbey, abbeys, abbo
//| t, abbots, Abbott, abbreviate, abbreviated, abbreviates, abbreviating, abbre
//| viation, abbreviations, Abby, abdomen, abdomens, abdominal, abduct, abducted
//| , abduction, abductions, abductor, abductors, abducts, Abe, abed, Abel, Abel
//| ian, Abelson, Aberdeen, Abernathy, aberrant, aberration, aberrations, abet,
//| abets, abetted, abetter, abetting, abeyance, abhor, abhorred, abhorrent, abh
//| orrer, abhorring, abhors, abide, abided, abides, abiding, Abidjan, Abigail,
//| Abilene, abilities, ability, abject, abjection, abjections, abjectly, abject
//| ness, abjure, abjured, abjures, abjuring, ablate, ablated, ablates, ablating
//| , ablation, ablative, ab
//| Output exceeds cutoff limit.
val mnem = Map('2' -> "ABC", '3' -> "DEF", '4' -> "GHI", '5' -> "JKL",
'6' -> "MNO", '7' -> "PQRS", '8' -> "TUV", '9' -> "WXYZ")
//> mnem : scala.collection.immutable.Map[Char,String] = Map(8 -> TUV, 4 -> GHI
//| , 9 -> WXYZ, 5 -> JKL, 6 -> MNO, 2 -> ABC, 7 -> PQRS, 3 -> DEF)
/** Invert the mnem map to give a map from chars 'A'...'Z' to '2'...'9' **/
val charCode: Map[Char, Char] =
for ((digit, str) <- mnem; ltr <- str) yield ltr -> digit
//> charCode : Map[Char,Char] = Map(E -> 3, X -> 9, N -> 6, T -> 8, Y -> 9, J -
//| > 5, U -> 8, F -> 3, A -> 2, M -> 6, I -> 4, G -> 4, V -> 8, Q -> 7, L -> 5,
//| B -> 2, P -> 7, C -> 2, H -> 4, W -> 9, K -> 5, R -> 7, O -> 6, D -> 3, Z -
//| > 9, S -> 7)
/** Map a word to the digit string it can represent, e.g., "JAVA" -> "5282" **/
def wordCode(word: String): String = word.toUpperCase.map(charCode)
//> wordCode: (word: String)String
wordCode("Java") //> res0: String = 5282
/**
* A map from digit strings to the words that represent them,
* e,g. "5282" -> List("Java", "Kata", "Lava", ...)
* Note: A missing number should map to the empty set, e.g. "1111" -> List()
*/
val wordsForNum: Map[String, Seq[String]] =
words groupBy wordCode withDefaultValue List()//> wordsForNum : Map[String,Seq[String]] = Map(63972278 -> List(newscast), 29
//| 237638427 -> List(cybernetics), 782754448 -> List(starlight), 2559464 -> Li
//| st(allying), 862532733 -> List(uncleared), 365692259 -> List(enjoyably), 86
//| 8437 -> List(unties), 33767833 -> List(deportee), 742533 -> List(picked), 3
//| 364646489 -> List(femininity), 3987267346279 -> List(extraordinary), 785539
//| 7 -> List(pulleys), 67846493 -> List(optimize), 4723837 -> List(grafter), 3
//| 86583 -> List(evolve), 78475464 -> List(Stirling), 746459 -> List(singly),
//| 847827 -> List(vistas), 546637737 -> List(lionesses), 28754283 -> List(curl
//| icue), 84863372658 -> List(thunderbolt), 46767833 -> List(imported), 264374
//| 64 -> List(angering, cohering), 8872267 -> List(turbans), 77665377 -> List(
//| spoolers), 46636233 -> List(homemade), 7446768759 -> List(rigorously), 7464
//| 4647 -> List(ringings), 633738 -> List(offset), 847825 -> List(visual), 772
//| 832 -> List(Pravda), 47
//| Output exceeds cutoff limit.
/** Return all ways to encode a number as a list of words */
def encode(number: String): Set[List[String]] = {
if (number.isEmpty) Set(List())
else {
for {
split <- 1 to number.length
first <- wordsForNum(number take split)
rest <- encode(number drop split)
} yield first :: rest
}.toSet
} //> encode: (number: String)Set[List[String]]
def translate(number: String): Set[String] = encode(number) map(_ mkString " ")
//> translate: (number: String)Set[String]
translate("7225247386") //> res1: Set[String] = Set(sack air fun, pack ah re to, pack bird to, Scala ir
//| e to, Scala is fun, rack ah re to, pack air fun, sack bird to, rack bird to
//| , sack ah re to, rack air fun)
}
Go to September's log
Last modified: Wed Mar 26 11:51:06 CST 2014