Instantly share code, notes, and snippets.

# seratch/gist:1247808 Created Sep 28, 2011

What would you like to do?
#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: