Create a gist now

Instantly share code, notes, and snippets.

#daimonscala 16
// *** S-99: Ninety-Nine Scala Problems ***
// http://aperiodic.net/phil/scala/s-99/
type B = Boolean
// P46: Truth tables for logical expressions.
// Define functions and, or, nand, nor, xor, impl,
// and equ (for logical equivalence) which return true or false
// according to the result of their respective operations;
// e.g. and(A, B) is true if and only if both A and B are true.
object P46 {
def not(a: B) = a match {
case true => false
case false => true
}
def and(a: B, b: B) = (a, b) match {
case (true, true) => true
case _ => false
}
def or(a: B, b: B) = (a, b) match {
case (true, _) => true
case (_, true) => true
case _ => false
}
def equ(a: B, b: B) = or(and(a, b), and(not(a), not(b)))
def xor(a: B, b: B) = not(equ(a, b))
def nor(a: B, b: B) = not(or(a, b))
def nand(a: B, b: B) = not(and(a, b))
def impl(a: B, b: B) = or(not(a), b)
def table2(f: (B, B) => B): String = {
val header = "A B result\n"
val values = { for( a <- List(true, false); b <- List(true, false))
yield "%-5s %-5s %-5s".format(a, b, f(a, b))
}.mkString("\n")
header + values + "\n"
}
def test {
println(and(true, true))
println(and(true, true)==true)
println(xor(true, true))
println(xor(true, true)==false)
val actual = table2((a: B, b: B) => and(a, or(a, b)))
val expected = """A B result
true true true
true false true
false true false
false false false
"""
print(actual)
print(expected)
}
}
object P47 {
class P47B(a: B) {
import P46._
def and(b: B) = P46.and(a: B, b: B)
def or(b: B) = P46.or(a: B, b: B)
def equ(b: B) = P46.equ(a: B, b: B)
def xor(b: B) = P46.xor(a: B, b: B)
def nor(b: B) = P46.nor(a: B, b: B)
def nand(b: B) = P46.nand(a: B, b: B)
def impl(b: B) = P46.impl(a: B, b: B)
}
implicit def toP47B(a: B) = new P47B(a)
def test {
import P46._
print(table2((a: B, b: B) => a and (a or not(b))))
}
}
object P49 {
def gray(n: Int): List[String] = {
def _gray(m:Int): List[List[Int]] = {
List(0,1) flatMap {
case i if m == 1 => List(List(i))
case i => _gray(m-1) map { l => i :: l }
}
}
_gray(n) map { case list => list.mkString("") }
}
def test {
println(gray(1))
println(gray(2))
println(gray(3))
}
}
object P50 {
abstract class Tree[A] {
val freq: Int
def toCode: List[(A, String)] = toCodePrefixed("")
def toCodePrefixed(prefix: String): List[(A, String)]
}
case class InternalNode[A](left: Tree[A], right: Tree[A]) extends Tree[A] {
val freq: Int = left.freq + right.freq
def toCodePrefixed(prefix: String): List[(A, String)] =
left.toCodePrefixed(prefix + "0") ::: right.toCodePrefixed(prefix + "1")
}
case class LeafNode[A](element: A, freq: Int) extends Tree[A] {
def toCodePrefixed(prefix: String): List[(A, String)] = List((element, prefix))
}
def huffman[A](ls: List[(A, Int)]): List[(A, String)] = {
import collection.immutable.Queue
def dequeueSmallest(q1: Queue[Tree[A]], q2: Queue[Tree[A]]) = {
// This ordering chooses q1 in case of ties, which helps minimize tree
// depth.
if (q2.isEmpty) (q1.front, q1.dequeue._2, q2)
else if (q1.isEmpty || q2.front.freq < q1.front.freq) (q2.front, q1, q2.dequeue._2)
else (q1.front, q1.dequeue._2, q2)
}
def huffmanR(q1: Queue[Tree[A]], q2: Queue[Tree[A]]): List[(A, String)] = {
if (q1.length + q2.length == 1) (if (q1.isEmpty) q2.front else q1.front).toCode
else {
val (v1, q3, q4) = dequeueSmallest(q1, q2)
val (v2, q5, q6) = dequeueSmallest(q3, q4)
huffmanR(q5, q6.enqueue(InternalNode(v1, v2)))
}
}
huffmanR(
Queue.empty.enqueue(ls sortWith { _._2 < _._2 } map { e => LeafNode(e._1, e._2) }),
Queue.empty
)
}
def test {
val f = huffman(
List(
("a", 45),
("b", 13),
("c", 12),
("d", 16),
("e", 9),
("f", 5)
)
)
println(f)
// List((a,0), (b,101), (c,100), (d,111), (e,1101), (f,1100))
}
}
P46.test
P47.test
P49.test
P50.test
// vim: set ts=4 sw=4 et:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment