Thursday, October 15, 2009

P12: Decode run-length encoding

Following is the direct solution:

1:  def decode(list:List[(Int,Any)]):List[Any] = {  
2: val b = new ListBuffer[Any]()
3: var temp = list
4: while(!temp.isEmpty){
5: for(i<- 1 to temp.head._1){
6: b+=temp.head._2 }
7: temp = temp.tail
8: }
9: b.toList
10: }
11: println("input List = "+dlist)
12: println(decode(dlist))

The input:
List((6,'a), (2,'c), (4,'e))
The output:
List('a, 'a, 'a, 'a, 'a, 'a, 'c, 'c, 'e, 'e, 'e, 'e)

P11: Modified run-length encoding that includes only repeated elements

Use unflatten method from P9 and filter it before mapping the sublist as a tuple:
println(ulist.filter(_.length > 1).map(e=>(e.length,e.head)))

Output:
List((6,'a), (2,'c), (4,'e))

Wednesday, October 14, 2009

Installing Eclipse, Scala and Groovy in Windows 7

There are many ways to install them on Windows 7. I am just listing following simple ways that worked for me:
1. Installing Eclipse 3.5
The latest 3.5 version works just fine on Windows 7. download it then unzip it to a location of your choice.
2. Installing Scala
Download IzPack installer, Just follow the wizard and you are done.
3. Installing Groovy
Download the Windows-Installer package. After installation, you need to do following:
1. Open Control Panel->System and Security->System and click on Advanced system settings.(Shortcut: Win+Pause/Break combination is your friend)
2. Click on Environment Variables
3. Make sure to create User variables such as GROOVY_HOME as name, installation location as value. (Note: Creating System variables did not work for me)
That is all there is to it. I hope someone find this post helpful.

P10: Run-length encoding of a list.

The idea is to use above unflatten function to group consecutive duplicates into a list and them map it to length, head pair. Here is the example:
val x = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
val ulist = unflatten(x)
println(ulist)
println(ulist.map(e=>(e.length,e.head)))

Output:
List(List('a, 'a, 'a, 'a, 'a, 'a), List('b), List('c, 'c), List('d), List('e, 'e, 'e,'e))
List((6,'a), (1,'b), (2,'c), (1,'d), (4,'e))

Tuesday, October 13, 2009

P09: Pack consecutive duplicates of list elements into sublists.

This might be a good candidate for recursive solution. But much faster iterative solution is shown below:


import scala.collection.mutable.ListBuffer
def unflatten[T](list:List[T]):List[List[T]]={
val uniq = list.removeDuplicates
val c = new ListBuffer[List[T]]()
var uniqv = uniq
while(!uniqv.isEmpty){
c.append(list.filter(_==uniqv.head))
uniqv=uniqv.tail
}
c.toList
}
val x = List(1,2,3,1,2,3,1,2,3,1,2,3)
println(unflatten(x))

Output:
List(List(1, 1, 1, 1), List(2, 2, 2, 2), List(3, 3, 3, 3))

Thursday, October 8, 2009

P08: Eliminate consecutive duplicates of list elements.

The simple solution:
scala> val x = List(1,2,2,3,4,4,5,5)
x: List[Int] = List(1, 2, 2, 3, 4, 4, 5, 5)

scala> x.removeDuplicates
res0: List[Int] = List(1, 2, 3, 4, 5)

For the curious under the hood:

scala> import scala.collection.mutable.ListBuffer
import scala.collection.mutable.ListBuffer

scala> def myRemoveDuplicates[T](in:List[T]):List[T] = {
| val b = new ListBuffer[T]
| var temp = in
| while(!temp.isEmpty){
| if(!temp.tail.contains(temp.head)) b+=temp.head
| temp = temp.tail
| }
| b.toList
| }
myRemoveDuplicates: [T](in: List[T])List[T]

scala> myRemoveDuplicates(x)
res2: List[Int] = List(1, 2, 3, 4, 5)

Wednesday, October 7, 2009

P07: Flatten a list

Just use flatten method:
scala> val m = List(List(1, 2), List(3, 4))
res2: List[List[Int]] = List(List(1, 2), List(3, 4))

scala> m.flatten
res3: List[Int] = List(1, 2, 3, 4)

Just out of sheer curiosity, here another implementation with much better performace:

scala> import scala.collection.mutable.ListBuffer
import scala.collection.mutable.ListBuffer

scala> def myFlatten[T](nl:List[List[T]]):List[T] = {
| val b = new ListBuffer[T]
| for(list<-nl){
| var tlist = list
| while(!tlist.isEmpty){
| b+=tlist.head
| tlist = tlist.tail
| }
| }
| b.toList
| }
myFlatten: [T](nl: List[List[T]])List[T]

scala> myFlatten(m)
res1: List[Int] = List(1, 2, 3, 4)

Tuesday, October 6, 2009

P06: Is a list palindrome

scala> val plist = List(1, 2, 3, 2, 1)
res19: List[Int] = List(1, 2, 3, 2, 1)

scala> plist == plist.reverse
res20: Boolean = true

P03 - P05: Find nth element, length, reverse a list

scala> val list = List(1,2,3,4,5)
list: List[Int] = List(1, 2, 3, 4, 5)

scala> list(4)
res0: Int = 5

scala> list.length
res1: Int = 5

scala> list.reverse

scala> list.reverse
res2: List[Int] = List(5, 4, 3, 2, 1)

Monday, October 5, 2009

How to simply sum values in a Map in Scala

Here is a code snippet that sums up the values in a map in Scala:
m.foldLeft(0)(_+_._2)

It may look cryptic at first but once you get the Scala feel, you will appreciate its conciseness and elegance. Here below is the explanation:
m stands for a Map, foldLeft is a method that takes an initial value (0 here since sum is 0 at the beginning) and feeds it to its next iteration on this map entry. Note that the first _ stands for the result of previous iteration result. And _+_._2 means:
take previous result and add it to the next map entry's value, which _._2 stands for. In Scala, Map values can be accessed as Tuples. _1 is the key and _2 is the value. Here is a working example:

scala> val m = Map("one"->1,"two"->2,"three"->3)
m: scala.collection.immutable.Map[java.lang.String,Int] = Map(one -> 1, two -> 2, three -> 3)
scala> m.foldLeft(0)(_+_._2)
res0: Int = 6

Note: You can change + to * and use 1 for the initial value to get the product of values.

Best Note Taking Tools

In line with the spirit of why I started this blog, I would like to provide my take on following note taking tools and provide my biased verdict at the end.
  1. Google Note : This is your friend to collect any text clips from the web. You select a text and click on Google Note Bookmarklet and magically it will be saved on you Google note. If you use iPhone or iPod touch, you can sync view it offline with apps like Byline.
  2. Ever Note: You would like this one if you have take notes from web and offline and sync across multiple computers. It has a free iPhone app that does much more than text notes.
  3. My Writing Nook: It is a very simple writing tool works on any browser and it uses Google account. All you need is a browser to start writing. It also has an iPhone app that syncs your notes.
My verdict is My Writing Nook. Because it follows KISS principle and let you focus on what you want - Writing, without being a mind boggling tool. Here is the link: http://www.mywritingnook.com/

P02: Find the last but one element of a list.

scala> List(1,2,3,4,5).takeRight(2).head
res0: Int = 4

Friday, October 2, 2009

Over all these years of Software development, I came to really value the KISS principle, as the name of the blog suggests. Keeping up with a good programmer tradition of learning a new language every year, my journey took me from Ruby -> Groovy ->Now Scala. I used both Ruby and Groovy for rapid prototyping and where I feel it simplifies things that I am working on. Since I started to wonder in the Scala world, I started to feel strongly that Scala have chosen me over other of my favorites namely Ruby and Groovy, which by the way I still use and love. Writing programs in Scala feels so natural to me now that I really wish it is the only language that I work with. There are lots of Scala tutorials on the web and I won't be starting one. I recently came across an interesting site that talks about 99 things in Scala(http://aperiodic.net/phil/scala/s-99/). Most of problems has solutions in more than one way, which prompted me to blog about writing one and only one simple way of solving them. I will gradually work my way with them as my schedule allows me. Without much rant, here is the simple solution to first problem:
P1: Find the last element of a list

A: scala> List(1,2,3,4,5).last
res0: Int = 5