Ståle’s weblog

23rd April Ubunty 9.04 Jaunty Jackalope got released. I upgraded my home comp yesterday, and now did my workstation at work today. At home I have an nvidia graphic card, and the upgrade went flawless. At work I have an ATI card and was using the fglrx driver, which seems to be discontinued or something in Ubuntu 9.04.

I did try and upgrade at work yesterday, however I got a warning about the fglrx driver not existing in the next version, so I didn’t go ahead. However since everything went smooth at home I decided to go straight ahead and upgrade my work comp as well today. Things mostly went fine, except I kinda had 2 issues I need to fix asap at work while installing Ubuntu, and I was leaving for a long lunch. During the actual install off the downloaded packages the network driver got disabled, so I was unable to work for about 25 mins.

I did however manage to resolve the issues (well, 1 issue was a IE bug that my superior resolved by saying I should just tell the user to install FireFox (I will justify this at the end off the post)). However, after rebooting my x setup was in clone mode rather than dual head. Which feels like a waste when you have 2 monitors. I tried installing the fglrx driver that is in the Jaunty repository, but that just crashed my computer, and the aticonfig utility didn’t even detect my card for automatic setup.

After going a bit back and forward, it seemed I was going to be stuck with clone mode setup for my 2 monitors, which I was not to happy about. I needed to dig deeper and find some docs on how to actually setup 2 monitors. It turns out that the ati driver in xorg, is just a front package for 3 different ati drivers, and from those 3 drivers I was using the radeon driver. From the docs in that package I was able to locate a page on the debian wiki about the radeon driver. It also deals with the randr util.

Checking through my xorg.log file, I did see that the driver did in fact detect my 2 monitors, I just needed to figure out how to configure xorg.conf to properly use them. I tried various solutions and approaches, and I finally got something working:

Section "Device"
  Identifier    "ATI 1"
    Option "Monitor-DVI-0" "Monitor 1"
    Option "Monitor-DVI-1" "Monitor 2"
  EndSection

  Section "Monitor"
    Identifier    "Monitor 1"
    Option    "RightOf" "Monitor 2"
  EndSection

  Section "Monitor"
    Identifier    "Monitor 2"
  EndSection

  Section "Screen"
    Identifier    "Screen 1"
    Monitor        "Monitor 1"
    Device        "ATI 1"
    SubSection "Display"
      Depth           24
      # big virtual screen to place
      Virtual         3360 1050
    EndSubSection
  EndSection

Now I need to explain some details about this setup. Since I have 2 monitors, I just need to define 2 “Monitor” sections in the config file, and in one off them I specify that it’s to the right off the other monitor. I then need to refer to these 2 monitors in the Device section. The way I do this is via the options “Monitor-DVI-0″ and “Monitor-DVI-1″ under the “Device” section. The option names are important here. They need to start with “Monitor-” followed by the device identifier. The device identifier you can find using xrandr. If I run xrandr on my comp, I get the output:

Screen 0: minimum 320 x 200, current 3360 x 1050, maximum 3360 x 1050
DVI-1 connected 1680x1050+0+0 (normal left inverted right x axis y axis) 473mm x 296mm
   1680x1050      59.9*+
   1280x1024      75.0     60.0
   1152x864       75.0
   1024x768       75.0     60.0
   800x600        75.0     60.3
   640x480        75.0     59.9
   720x400        70.1
DVI-0 connected 1680x1050+1680+0 (normal left inverted right x axis y axis) 473mm x 296mm
   1680x1050      59.9*+
   1280x1024      75.0     60.0
   1152x864       75.0
   1024x768       75.0     60.0
   800x600        75.0     60.3
   640x480        75.0     59.9
   720x400        70.1

As you can see here, I have 2 lines starting with a monitor identifier (mine are “DVI-0″ and “DVI-1″). You will also see the same identifiers several places in your xorg.log file. You also need to set the Virtual display size in the “Screen” section. I tried without this first, and ended up with half my monitor being garbled, as the max resolution got set to 2560×1600 or something, less than I need.

If you are going to use my setup on your own comp, you of course need to adjust values to your display setup. Also check what actual identifiers you get for your monitors. My setup is working great with the open source ati drivers, and I also got compiz to work fully. Now I just need to figure out how I can replace xfwm4 with compiz on my home computer, but that is something for a later date.

As for requiering our users to use FireFox instead off IE, the application I am making will in the end have a single client on a single computer, placed on a boat. Since we control everything about this, requiring that one browser is FireFox doesn’t seem like that big off a deal. There will actually be others using parts off the app as well from other browsers, but not the data entry view which has all the JavaScript magic.

Staale Linux linux ubuntu xorg ati

Long time since last update now. I have been out traveling in Americaland again, but I am now back. Not that there are many reading this blog, but I at least try and keep myself busy working through these Euler problems to practice my Scala.

Problem 5 in project euler deals with finding the smallest number that divides with a range off numbers:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

This is actually pretty easy to just solve directly. We start with just multiplying all the numbers from 1 to 20:

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20

If you examine this, 20 is 10*2, and we allready have that in our set, so we can drop it. 18 is 2*9, so we can drop that as well. 16 is 2*2*2*2, 8 is 2*2*2, 4 is 2*2 and 2 is just 2. Since 16 covers all those divisors, we can drop 2,4 and 8. With that, we are reduced to:

1 * 3 * 5 * 6 * 7 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 19

Still, we can remove more numbers. 15 is 3*5, 14 is 2*7, 12 is 2*6, and 10 is 2*5, leaving us with:

1 * 3 * 5 * 6 * 7 * 9 * 10 * 11 * 13 * 16 * 17 * 19

2 and 3 are factors of 16 and 9 respectivly, which means we can remove both 3 and 6. 10 is 5*2, we have 5 and 2 as a factor off 16. This finally leaves us with:

5*7*9*11*13*16*17*19

Which proves to be the right answer. So this can be pretty easily solved just using conventional math.

Now for a Scala solution. What I intend to do here is to create a list of 1 to 20. For each value at index n in the list, I divide the value at n+1 -> max by n if it’s divisible by n. For the first number, 1, nothing changes. But applying the same to the list using 2, results in the following updated list:

1,2,3,2,5,3,7,4,9,5,11,6,13,7,15,8,17,9,19,10

Every even number after 2 gets divided by 2. This produces a new list, and we repeat this process for the next number, 3:

1,2,3,2,5,1,7,4,3,5,11,2,13,7,5,8,17,3,19,10

Since 6 was divisible by both, it’s now reduced to 1. If we keep repeating this process, we will end up with a list of unique factors in the final answer. Now for the code applying this to a list.

1
2
3
4
5
6
7
8

def reduceMuls(src:List[Int]):List[Int] = {
    src.head :: reduceMuls(src.head, src.tail)
}
def reduceMuls(div:Int, target:List[Int]):List[Int] = {
    if (target.tail.isEmpty) return target
    val res = target map(a=>if(a%div==0) a/div else a)
    res.head :: reduceMuls(res.head, res.tail)
}

Ok, the first function here is just a simple wrapper that extracts the first and reminder off the list, and passes it on to the second method. Line 5 is just a check for empty lists. Line 6 does the magic, it maps the target list by dividing all numbers in it if it’s divisible by div, the first argument. This new list is then modified by applying the same function to all but it’s first element, and adding the first element to the start. The argument at each stage off the process looks as follows:

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
List(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
List(3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
List(2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8, 17, 9, 19, 10)
List(5, 1, 7, 4, 3, 5, 11, 2, 13, 7, 5, 8, 17, 3, 19, 10)
List(1, 7, 2, 3, 5, 11, 1, 13, 7, 5, 4, 17, 3, 19, 5)
List(7, 2, 3, 1, 11, 1, 13, 7, 1, 4, 17, 3, 19, 1)
List(2, 3, 1, 11, 1, 13, 7, 1, 4, 17, 3, 19, 1)
List(3, 1, 11, 1, 13, 1, 1, 4, 17, 3, 19, 1)
List(1, 11, 1, 13, 1, 1, 2, 17, 3, 19, 1)
List(11, 1, 13, 1, 1, 2, 17, 1, 19, 1)
List(1, 13, 1, 1, 2, 17, 1, 19, 1)
List(13, 1, 1, 2, 17, 1, 19, 1)
List(1, 1, 2, 17, 1, 19, 1)
List(1, 2, 17, 1, 19, 1)
List(2, 17, 1, 19, 1)
List(17, 1, 19, 1)
List(1, 19, 1)
List(19, 1)
List(1)

The final list returned will actually look like this:

1, 2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, 13, 1, 1, 2, 17, 1, 19, 1

Now we need to call this method, and multiply all the numbers to get the smallest number divisible by all numbers from 1 to 20. The numbers reduced to 1 in the above list will of course not have any effect on the result, as they are included in other factors.

1
2

val res = reduceMuls(1 to 20 toList).foldLeft(1) (_*_)
println(res)

We need to convert the Seq to a list so it can properly be used in our function. I actually discovered after doing most off the code in this post that I could also do this with a Seq[Int], however it doesn’t work for how I intend to evolve the code a bit later. What we can do first, is to replace the foldLeft method with the fold left operator, /:. Though it is actually a method rather than an operator, as there are no operators in Scala, just methods. The code is then:

1

val res = (1 /: reduceMuls(1 to 20 toList)) (_*_)

This post is already quite long, but now I am actually coming to the part I want to demonstrate a bit more here, Scala’s pattern matching. When we have if/else constructs (though technically the else is missing), they can often be simplified with match expressions. Here is the same method rewritten to use Scala’s match operator:

1
2
3
4
5

def reduceMuls(src:List[Int]):List[Int] = src match {
        case 1::rest => reduceMuls(rest)
        case a::rest => a::reduceMuls(rest map(x=>if(x%a==0) x/a else x))
        case _ => src
    }

The match expressions look a bit similar to Javas switch, but it’s much more powerful. It takes any object and compares it to the expression in the case statement. The case statement can also use variable names that can then be used in the resulting handler. One important thing here is that for methods you need to handle all cases, which usually ends with a default case at the end. There are partial functions and case classes that allows you to work around this, but I won’t go into that here. Let’s look at the cases in the above example. There is also no fall through and breaks. Each handler is separate.

The first cases say the number 1 followed by a list. This will match all lists that have at least 1 element, and the first element is 1. I say 1 element because the rest off the list can be the empty list. The rest keyword then refers to a variable name that is in scope for the handler. For this case, we can drop the 1, and just reduce the rest of the list.

The second case is any value followed by a list of values. This will match all other entries except the empty list. For this we create a new list of a, and then rest divided by a where the values are divisible by a.

The final case handles anything. _ is the wildcard operator for Scala, and this just simply returns the src as is. This will be hit when we try reduceMuls on the empty list, which has no element followed by a tail.

Now we are almost done, but I have one more trick to show first:

1
2
3
4
5
6

def divBy(div:Int)(x:Int) = if(x%div==0) x/div else x
def reduceMuls(src:List[Int]):List[Int] = src match {
    case 1::rest => reduceMuls(rest)
    case a::rest => a::reduceMuls(rest map divBy(a))
    case _ => src
}

I have added a divBy method here, which takes 2 sets of arguments. A divisor, and a value to divide by. This is Scala’s way of doing something called Currying. This has a lot of uses, but here we use it in the reduceMuls map to make it more readable. divBy(a) returns a partial function that is missing it’s last argument, x, before it can be called. This method is then applied for each element in rest using the map function.

Our final program is then:

1
2
3
4
5
6
7
8
9

object Euler005 extends Application {
    def divBy(div:Int)(x:Int) = if(x%div==0) x/div else x
    def reduceMuls(src:List[Int]):List[Int] = src match {
        case 1::rest => reduceMuls(rest)
        case a::rest => a::reduceMuls(rest map divBy(a))
        case _ => src
    }
    println ((1 /: reduceMuls(1 to 20 toList))(_*_))
}

A bit sorry for this long post, I actually started it over 2 weeks ago at an airport while a bit bored. However, I have been really busy so this post didn’t get done until now. I will try to get back with more posts more regularily, as I have solved quite a few more Euler problems in Scala already. It’s also getting easier and easier to think in more Scala like terms for this, producing ever shorter programs faster than I would in Java.

Staale Euler, Scala Euler, Scala

The fourth problem in project euler deals with palindromes:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

One off the main functions we will need for this, is off course a method to check if a number is a palindrome. This is easiest to check on strings rather than numbers directly. And a string function would work for all integral types we could want to check (Int, Long, BigInt).

object Util {
    def isPalindrome(txt: String, s:Int, e:Int):Boolean = {
        if (s>e) true
        else if (txt(s) == txt(e)) isPalindrome(txt,s+1,e-1)
        else false
    }
    def isPalindrome(txt:String): Boolean = isPalindrome(txt,0,txt.length-1)
    implicit def toStr(n:Int): String = n.toString
}

I have created a separate Util object for this, as I know there are future problems that also deal with palindromes. The code uses 2 pointers, one from the start and one from the end. As long as they point to the same character we move them towards the middle of the string. If the end is less than the start, no conflicts found, and we have a palindrome. Otherwise the number is not a palindrome.

A new concept in this Util class is the implicit def method, that is just a simple converter from Int to String. The implicit tells the Scala compiler that it can use this function for implicit conversion. Implicit conversions are a neat feature off scala that converts expressions to new types if necessary. Here it allows us to call the isPalindrome method with an Int rather than a String. The Compiler sees that there is a mismatch, but it has an implicit conversion in scope that can turn the Int into a String.

So given the following usage:

isPalindrome(91 * 99)

This would be an error, as isPalindrome expects a String, but we are giving it an Int. The compiler finds the implicit conversion, and changes the code to the following:

isPalindrome(toStr(91*99))

With the palindrome method in hand, we can now look for ways to find the highest palindrome that is a product of 2 3 digit numbers. This actually provided me with some problems, as I spent some time finding the optimal solution. If we look at the most brute force approach first, we have:

val products = for (a <- 100 to 999;b <- 100 to 999) yield a*b
println(products.filter(isPalindrome(_)).toList.sort(_>_).head)

The for loop at line 1 will have a iterate from 100 to 999, and for each a iterate b 100 to 999. yield evaluates an expression to return a Seq, in this case off Int. This gives us over 800000 numbers, all the possible products.
Line 2 first filters on all values that are palindromes. isPalindrome(_) is equivalent of (a) => isPalindrome(a). The filtered list will now just contain the Int values that are palindromes. Next we sort the list, here (_>_) is equivalent of (a,b) => a > b as a sort method. And finally we pick the first element from the result.

However, we go through too many solutions here that aren’t necessary. We should instead start from 999*999 and go down, and stop whenver we exceed the highest palindrome earlier found. To do this we are going to take advantage off the filter functions that exists in for loops in Scala. Scala for loops are a lot more powerfull than those we have in Java.

My final solution is thus:

object Euler004 extends Application {
    var max = 0
    val palindromes = for {
        a <- 100 to 999 reverse;
        if (a*999 > max);
        b <- a to 999 reverse;
        c = a*b;
        if (c > max && isPalindrome(c))
    } yield {max=c;max}
    println (palindromes.reverse(0))
}

We here need to have a variable to keep track off the max value found so far. The for expression now expands across multiple lines. On line 3 we say to iterate a from 999 to 100, so every following expression will be evaluated for each value off a from 999 to 100. Next we have an if, this checks if a*999 is bigger than our currently found max. If it isn’t, we don’t need to check anything else. This serves as a guard for the rest of the expressions in the for loop. On line 5 we iterate b from 999 to a, and on line 6 we just store the product in c. Finally we have a guard to check that c is bigger than max, and it is a palindrome.

In the yield we now have a block instead of just a single expression. This is because we need to assign max first, then return max.

Now we have a list of palindromes in increasing order. Any product found less than the highest palindrome will be skipped. To find the actual result, we just reverse the list and print out the first entry.

I did spend quite some time on this task to get a good solution. I have a faster one using while loops, but it doesn’t look as elegant. Additionally I read parts off the for loop segment in the Scala book yesterday, so I was interested in trying out some off the principles on this problem. I was originally planning on doing this with actors, just to see how they worked out, but I haven’t yet read fully about them. Perhaps I will deal with a later problem using actors.

Staale Euler, Scala Euler, Scala