Skip to content

Instantly share code, notes, and snippets.

# samklr/TontonMartin.scala Created Sep 27, 2012

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) } }
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.