Skip to content

Instantly share code, notes, and snippets.

@samklr
Created September 27, 2012 10:24
Show Gist options
  • Save samklr/3793333 to your computer and use it in GitHub Desktop.
Save samklr/3793333 to your computer and use it in GitHub Desktop.
ScalaFistes
object FuncourseWithUncleMartin{
*/
object Setsss{
def contains(s: Set, elem: Int): Boolean = s(elem)
def singleton(elem: Int): Set = Set(elem)//(x :Int) => x == elem
def union(s: Set, t: Set): Set = (x : Int) => s(x) || t(x)
def intersect(s: Set, t: Set): Set = (x : Int) => s(x) && t(x)
def diff(s: Set, t: Set): Set = (x: Int) => s(x) && !t(x)
def filter(s: Set, p: Int => Boolean): Set = (x :Int) =>p(x) && s(x)
val bound = 1000
def forall(s: Set, p: Int => Boolean): Boolean = {
def iter(a: Int): Boolean = {
if (s(a) && !p(a)) false
else if (a > bound) true
else iter(a+1)
}
iter(-bound)
}
def exists(s: Set, p: Int => Boolean): Boolean = {
def iter(a: Int): Boolean = {
if (s(a) && p(a)) true
else if (a > bound) false
else iter(a+1)
}
iter(-bound)
}
def exists(s: Set, p: Int => Boolean): Boolean = ! forall(s, (i:Int) => !p(i))
def map(s: Set, f: Int => Int): Set = {
def iterate (x : Int) : Set = {
if (x > bound ) ((y:Int) => false)
else if (s(x)) union(singleton(f(x)),iterate(x +1))
else iterate(x+1)
}
iterate(-bound)
}
def pascal(c: Int, r: Int): Int = if (c == r || c==0 || r==1) 1 else pascal(c-1,r-1) + pascal(c,r-1)
def balance(chars: List[Char]): Boolean = balance_aux(chars, Nil)
def balance_aux(chars : List[Char], stack : List[Char]) : Boolean = (chars, stack) match {
case (Nil, Nil) => true
case (Nil, _) => false
case (h :: tail, stack) => h match {
case '(' => balance_aux(tail, h :: stack)
case ')' => !stack.isEmpty && balance_aux(tail, stack.tail)
case _ => balance_aux(tail, stack)
}
}
def countChange(money: Int, coins: List[Int]): Int = (money, coins) match {
case (0,_) => 1
case (_, Nil) => 0
case (_ , h :: tail) => if (money < 0) 0 else countChange(money , tail) + countChange(money - h , coins)
}
//NonEMpty
def filter0(p : Tweet => Boolean, accu : TweetSet) : TweetSet =
if (isEmpty) accu
else if (p(elem)) new NonEmpty(elem,left.filter0(p, accu),right.filter0(p,accu))
else (remove(elem)).filter0(p,accu)
override def union(that: TweetSet): TweetSet =
if (that.isEmpty) this
else (that.head, that.tail.isEmpty) match {
case (_ , true) => if (!contains(that.head)) incl(that.head)else this
case (_, false) => if (!contains(that.head)) incl(that.head).union(that.tail) else union(that.tail)
}
override def ascendingByRetweet0(accu : Trending): Trending =
if (isEmpty) accu
else if (tail.isEmpty) (accu + head)
else remove(findMin).ascendingByRetweet0(accu + findMin)
//EMpty
def filter0(p: Tweet => Boolean, accu: TweetSet): TweetSet = new Empty
override def union(that: TweetSet): TweetSet = that
override def ascendingByRetweet0(trend : Trending): Trending = new EmptyTrending
object GoogleVsApple {
val google = List("android", "Android", "galaxy", "Galaxy", "nexus", "Nexus")
val apple = List("ios", "iOS", "iphone", "iPhone", "ipad", "iPad")
val googleTweets = TweetReader.allTweets.filter((x:Tweet) => x.text.contains("google"))
val appleTweets = TweetReader.allTweets.filter((x:Tweet) => x.text.contains("apple"))
val trending: Trending = (googleTweets union appleTweets).ascendingByRetweet
}
}
package patmat
import common._
import scala.util.Sorting
import scala.annotation.tailrec
/**
* Assignment 4: Huffman coding
*
*/
object Huffman {
/**
* A huffman code is represented by a binary tree.
*
* Every `Leaf` node of the tree represents one character of the alphabet that the tree can encode.
* The weight of a `Leaf` is the frequency of appearance of the character.
*
* The branches of the huffman tree, the `Fork` nodes, represent a set containing all the characters
* present in the leaves below it. The weight of a `Fork` node is the sum of the weights of these
* leaves.
*/
abstract class CodeTree
case class Fork(left: CodeTree, right: CodeTree, chars: List[Char], weight: Int) extends CodeTree
case class Leaf(char: Char, weight: Int) extends CodeTree
// Part 1: Basics
def weight(tree: CodeTree): Int = tree match {
case Leaf(c,w) => w
case Fork(left ,right ,chrs,w)=>weight(left) + weight(right)
}
def chars(tree: CodeTree): List[Char] = tree match{
case Leaf(char, w) => List(char)
case Fork(left, right, charList, w) => chars(left) ::: chars(right)
}
def makeCodeTree(left: CodeTree, right: CodeTree) =
Fork(left, right, chars(left) ::: chars(right), weight(left) + weight(right))
// Part 2: Generating Huffman trees
/**
* In this assignment, we are working with lists of characters. This function allows
* you to easily create a character list from a given string.
*/
def string2Chars(str: String): List[Char] = str.toList
/**
* This function computes for each unique character in the list `chars` the number of
* times it occurs. For example, the invocation
*
* times(List('a', 'b', 'a'))
*
* should return the following (the order of the resulting list is not important):
*
* List(('a', 2), ('b', 1))
*
* The type `List[(Char, Int)]` denotes a list of pairs, where each pair consists of a
* character and an integer. Pairs can be constructed easily using parentheses:
*
* val pair: (Char, Int) = ('c', 1)
*
* In order to access the two elements of a pair, you can use the accessors `_1` and `_2`:
*
* val theChar = pair._1
* val theInt = pair._2
*
* Another way to deconstruct a pair is using pattern matching:
*
* pair match {
* case (theChar, theInt) =>
* println("character is: "+ theChar)
* println("integer is : "+ theInt)
* }
*/
def times(chars: List[Char]): List[(Char, Int)] = chars match {
case Nil => Nil
case e :: tail => (e, chars.count(_ == e)) :: times(tail.filterNot (_ == e))
}
/**
* Returns a list of `Leaf` nodes for a given frequency table `freqs`.
*
* The returned list should be ordered by ascending weights (i.e. the
* head of the list should have the smallest weight), where the weight
* of a leaf is the frequency of the character.
*/
def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] = {
val sortedFreqs = Sorting.stableSort(freqs,
(e1 : (Char, Int), e2 : (Char, Int)) => e1._2 <= e2._2)
.toList
sortedFreqs map (e => Leaf(e._1, e._2))
}
/**
* Checks whether the list `trees` contains only one single code tree.
*/
def singleton(trees: List[CodeTree]): Boolean = trees match {
case leaf :: Nil => true
case _ => false
}
/**
* The parameter `trees` of this function is a list of code trees ordered
* by ascending weights.
*
* This function takes the first two elements of the list `trees` and combines
* them into a single `Fork` node. This node is then added back into the
* remaining elements of `trees` at a position such that the ordering by weights
* is preserved.
*
* If `trees` is a list of less than two elements, that list should be returned
* unchanged.
*/
def combine(trees: List[CodeTree]): List[CodeTree] = {
Sorting.stableSort(trees, (t1 : CodeTree , t2: CodeTree) => weight(t1) <= weight(t2)).toList
if (trees.size <= 2) trees
else {
val ftree = makeCodeTree(trees(0), trees(1))
List(ftree) ::: trees.tail.tail
}
}
/**
* This function will be called in the following way:
*
* until(singleton, combine)(trees)
*
* where `trees` is of type `List[CodeTree]`, `singleton` and `combine` refer to
* the two functions defined above.
*
* In such an invocation, `until` should call the two functions until the list of
* code trees contains only one single tree, and then return that singleton list.
*
* Hint: before writing the implementation,
* - start by defining the parameter types such that the above example invocation
* is valid. The parameter types of `until` should match the argument types of
* the example invocation. Also define the return type of the `until` function.
* - try to find sensible parameter names for `xxx`, `yyy` and `zzz`.
*/
// def until(s: List[CodeTree] => Boolean, c: List[CodeTree]=> List[CodeTree])(treeList: List[CodeTree]): List[CodeTree] = treeList match {
// case Nil => Nil
// case e :: Nil => treeList
// case e:: tail => if (singleton(tail)) List(makeCodeTree(e, tail(0)))
// else {
// val lst = until(s,c)(tail);
// List(makeCodeTree(e, lst(0)))
// }
// }
//
def until(s: List[CodeTree] => Boolean, c: List[CodeTree]=> List[CodeTree])(treeList: List[CodeTree]): List[CodeTree]=
treeList match {
case Nil => Nil
case a :: Nil => treeList
case a::a1:: q => if (s(q)) c(makeCodeTree(a, a1) :: q)
else c(makeCodeTree(a,a1) :: until(s,c)(q))
}
/**
* This function creates a code tree which is optimal to encode the text `chars`.
*
* The parameter `chars` is an arbitrary text. This function extracts the character
* frequencies from that text and creates a code tree based on them.
*/
def createCodeTree(chars: List[Char]): CodeTree = {
val freqs = times(chars)
(until(singleton, combine)(combine(makeOrderedLeafList(freqs))))(0)
// freqs match {
// case Nil => throw new Exception("Empty car List, can't create an empty code Tree")
// case (c,w)::Nil => Leaf(c,w)
// case a::q => {
// val lst = combine(makeOrderedLeafList(freqs))
// until(singleton, combine)(lst)(0)
//
// }
// }
}
// Part 3: Decoding
type Bit = Int
/**
* This function decodes the bit sequence `bits` using the code tree `tree` and returns
* the resulting list of characters.
* Decoding starts at the root of the tree. Given a sequence of bits to decode,
* we successively read the bits, and for each 0, we choose the left branch,
* and for each 1 we choose the right branch. When we reach a leaf,
* we decode the corresponding character and then start again at the root of the tree.
* As an example, given the Huffman tree above, the sequence of bits, 10001010 corresponds to BAC.
* Implementation
*/
//def decode(tree: CodeTree, bits: List[Bit]) : List[Char]= decode_aux (tree, bits, List.empty)
@tailrec
def decode_aux (tree: CodeTree, bits: List[Bit], ret : List[Char]) : List[Char]= (tree, bits) match {
case (Fork(l,r,ch,w), Nil) => throw new Exception ("Bad Encoding")
case (Leaf(c,w), Nil) => (c::ret).reverse
case (Leaf(c,w), _) => decode_aux(tree, bits.tail,c::ret)
case (Fork(l,r,ch,w), a::q) => if (a == 0) decode_aux(l,q,ret) else decode_aux(r,q,ret)
}
def decode (tree: CodeTree, bits: List[Bit] ): List[Char] = {
def decode1 (bits: List[Bit], current: CodeTree): List[Char] = bits match {
case Nil => Nil
case head :: tail => {
val br =chooseBranch (head, current)
br match {
case Leaf(symbol,w) => symbol :: decode1(tail, tree)
case Fork(l,r,c,w) => decode1(tail, br)
}
}
}
decode1 (bits, tree)
}
def chooseBranch (bit: Bit, branch: CodeTree) =
(bit, branch) match {
case (_, Leaf(w,c)) => branch
case (0, Fork(l,r,c,w)) => l
case (1 , Fork(l,r,c,w)) =>r
}
/**
* A Huffman coding tree for the French language.
* Generated from the data given at
* http://fr.wikipedia.org/wiki/Fr%C3%A9quence_d%27apparition_des_lettres_en_fran%C3%A7ais
*/
val frenchCode: CodeTree = Fork(Fork(Fork(Leaf('s',121895),Fork(Leaf('d',56269),Fork(Fork(Fork(Leaf('x',5928),Leaf('j',8351),List('x','j'),14279),Leaf('f',16351),List('x','j','f'),30630),Fork(Fork(Fork(Fork(Leaf('z',2093),Fork(Leaf('k',745),Leaf('w',1747),List('k','w'),2492),List('z','k','w'),4585),Leaf('y',4725),List('z','k','w','y'),9310),Leaf('h',11298),List('z','k','w','y','h'),20608),Leaf('q',20889),List('z','k','w','y','h','q'),41497),List('x','j','f','z','k','w','y','h','q'),72127),List('d','x','j','f','z','k','w','y','h','q'),128396),List('s','d','x','j','f','z','k','w','y','h','q'),250291),Fork(Fork(Leaf('o',82762),Leaf('l',83668),List('o','l'),166430),Fork(Fork(Leaf('m',45521),Leaf('p',46335),List('m','p'),91856),Leaf('u',96785),List('m','p','u'),188641),List('o','l','m','p','u'),355071),List('s','d','x','j','f','z','k','w','y','h','q','o','l','m','p','u'),605362),Fork(Fork(Fork(Leaf('r',100500),Fork(Leaf('c',50003),Fork(Leaf('v',24975),Fork(Leaf('g',13288),Leaf('b',13822),List('g','b'),27110),List('v','g','b'),52085),List('c','v','g','b'),102088),List('r','c','v','g','b'),202588),Fork(Leaf('n',108812),Leaf('t',111103),List('n','t'),219915),List('r','c','v','g','b','n','t'),422503),Fork(Leaf('e',225947),Fork(Leaf('i',115465),Leaf('a',117110),List('i','a'),232575),List('e','i','a'),458522),List('r','c','v','g','b','n','t','e','i','a'),881025),List('s','d','x','j','f','z','k','w','y','h','q','o','l','m','p','u','r','c','v','g','b','n','t','e','i','a'),1486387)
/**
* What does the secret message say? Can you decode it?
* For the decoding use the `frenchCode' Huffman tree defined above.
*/
val secret: List[Bit] = List(0,0,1,1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,0,1,1,0,1,0,1,1,0,0,1,1,1,1,1,0,1,0,1,1,0,0,0,0,1,0,1,1,1,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,1)
/**
* Write a function that returns the decoded secret
*/
def decodedSecret: List[Char] = decode(frenchCode, secret)
// Part 4a: Encoding using Huffman tree
/**
* This function encodes `text` using the code tree `tree`
* into a sequence of bits.
* For a given Huffman tree, one can obtain the encoded representation of a character
* by traversing from the root of the tree to the leaf containing the character.
* Along the way, when a left branch is chosen, a 0 is added to the representation,
* and when a right branch is chosen, 1 is added to the representation.
* Thus, for the Huffman tree above, the character D is encoded as 1011.
*/
def encode(tree: CodeTree)(text: List[Char]): List[Bit] = {
def encodeChar (tree : CodeTree, Char char , ret : List[Bit]) : List[Bit]= {
tree match {
case Leaf(c,w) => if (c == char ) ret else (encodeChar)
case Fork (l,r,chs,w) =>
}
}
}
// def successiveMerge (leafSet: List[Tree]): Tree = leafSet match {
// case head :: Nil => head // when 1, we have 1 tree, rather than a set of leaves
// case head :: tail => successiveMerge (adjoinSet (makeCodeTree (head, tail.first), tail.tail))
// case Nil => throw new RuntimeException("Invalid leaf set: "+leafSet)
// Part 4b: Encoding using code table
type CodeTable = List[(Char, List[Bit])]
/**
* This function returns the bit sequence that represents the character `char` in
* the code table `table`.
*/
def codeBits(table: CodeTable)(char: Char): List[Bit] = ???
/**
* Given a code tree, create a code table which contains, for every character in the
* code tree, the sequence of bits representing that character.
*
* Hint: think of a recursive solution: every sub-tree of the code tree `tree` is itself
* a valid code tree that can be represented as a code table. Using the code tables of the
* sub-trees, think of how to build the code table for the entire tree.
*/
def convert(tree: CodeTree): CodeTable = ???
/**
* This function takes two code tables and merges them into one. Depending on how you
* use it in the `convert` method above, this merge method might also do some transformations
* on the two parameter code tables.
*/
def mergeCodeTables(a: CodeTable, b: CodeTable): CodeTable = ???
/**
* This function encodes `text` according to the code tree `tree`.
*
* To speed up the encoding process, it first converts the code tree to a code table
* and then uses it to perform the actual encoding.
*/
def quickEncode(tree: CodeTree)(text: List[Char]): List[Bit] = ???
def main(args: Array[String]) {
println (decodedSecret)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment