#daimonscala 16

gistfile1.scala

// *** 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: