Ståle’s weblog

Euler problem 15 is a bit more complex than the earlier problems I have tackled. The problem is as follows:

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

So, here we are dealing with finding routes through a simple maze. We could brute force this by just exhausting all options in a recursive program, however, this would quickly evolve to take a lot of time. Instead we need to look at how we reach the final number of options, which for 2×2 is 6. The easiest way is to see if we can figure out how to solve it for the next size maze, 3×3, easily. As this would also be possible to verify manually.

We can also solve for a 1×1 maze quickly, which we arrive at 2 possible solutions. Starting from 1×1 we can learn a bit about how 6 for 2×2 is found. If we look at the maze, we know that there is 6 routes ending at the last point. If we look at the previous intersections, one above and one to the left, we see that there are 3 paths to each off those points, going to the final point. So, there are 2 intersections before the end, each with 3 paths, so the final point then of course has 6 entry points.

Now, how can we calculate that there are 3 points to the penultimate intersections. Well, we know from the 1×1 solutions that there is only 2 possible paths to the center. Also, since we can’t backtrack, there is only 1 possible path to each corner. So the 2 entries to each penultimate intersection have 1 and 2 paths, total of 3.

So, we can define the function f(x,y), which is the number of paths to point x,y as f(x-1,y)+f(x,y-1). If x or y is 0, then the result is always 1, as all edge points only have 1 possible path leading to them. The scala code for this function is as follows:

1

def f(x:Int, y:Int):BigInt = if (x==0 || y==0) 1 else f(x-1,y)+f(x,y-1)

However, when x and y gets bigger, the number of recursions skyrocket, and the program is all too slow. Also, it calculates a lot of numbers we don’t need. We can solve this by creating a 20×20 lookup cache. But, if we look at the numbers along the edges, we can see a pattern emerging:

1
2
3
4
5

0 to 1 map {f(1,_)} // RangeM(1, 2)
0 to 2 map {f(2,_)} // RangeM(1, 3, 6)
0 to 3 map {f(3,_)} // RangeM(1, 4, 10, 20)
0 to 4 map {f(4,_)} // RangeM(1, 5, 15, 35, 70)
0 to 5 map {f(5,_)} // RangeM(1, 6, 21, 56, 126, 252)

For each off these lists, the last number is equal to the penultimate number * 2, as we have seen earlier. We can see here a function f2(x) = 0 to x map {f(x,_)}. We can optimize this function by working with f2(x-1). So f2(x)[n] is the same as f2(x)[n-1] + f2(x-1)[n]. Since we need to calculate each number in the array based on earlier values, the best solution here is to use an array to store values as we calculate them. Index 0 will always be 1, and the last index will always be the double of the second to last index:

1
2
3
4
5
6
7
8
9
10
11
12

def f2(n:Int):List[BigInt] = {
    if (n<2) {
        return 0 to n map {f(n,_)} toList
    } else {
        val prev = f2(n-1)
        val res = new Array[BigInt](n+1)        
        res(0) = 1
        for (i <- 1 until prev.size) res(i) = prev(i)+res(i-1)
        res(n) = res(n-1)*2
        return res toList
    }
}

This method is very fast for the values we are using here. We can also define a simple replacement now to calculate the number of paths in an arbitrarily shaped grid:

1

def euler15(x:Int,y:Int) = f2(x max y)(x min y)

We need the first value to be the max off the 2 to avoid list out of bound exceptions.

Thats it for this time. No complete program as I did all off this through the scala console. This solution is using my limited math knowledge and programming skills though. There are mathematics that will allow you to solve this pretty easily, which I found after preparing this post.

Staale Uncategorized

Problem 8 in project Euler is:

Find the greatest product of five consecutive digits in the 1000-digit number.

The first step is just to copy and paste the big block off numbers into a new file. I preserved line breaks and everything in my file, and called it Euler008-data.txt.

Since I day to day program in Python, and have been pretty happy with how Python handles file reading, I wanted to compare the Scala code for this to the equivalent Python code. I first present the Python solution for extracting the number into 1 long string:

1

digit = "".join(open("Euler008-data.txt").read().split())

Pretty short one-liner. I first open the file and read the entire content, giving me a single big string with linebreaks. I then use the default split method which splits on whitespace to create an array of strings, one for each line. Then finally that list is joined with nothing between the numbers. The result is one big number of strings.

Next I need a method for calculating the product of the digits in a string, I will use this method on each segment of 5 numbers in the digit string:

1
2
3
4

def prodDigits(n):
    prod = 1
    for d in n: prod *= int(d)
    return prod

Her it’s just a matter of iterating over the characters in the string, converting each to an int and multiplying them together.

Finally we need to test each subset of 5 digits. I include here the complete program for finding the solution.

1
2
3
4
5
6
7
8
9
10

if __name__ == "__main__":
    def prodDigits(n):
        prod = 1
        for d in n: prod *= int(d)
        return prod
    digit = "".join(open("Euler008-data.txt").read().split())
    maxval = 0
    for n in xrange(0,len(digit)-5):
        maxval = max(maxval, prodDigits(digit[n:n+5]))
    print maxval

Now for the Scala solution. I import and use the scala.io.Source.fromFile method for extracting the data from the file. The fromFile returns a list of characters, for the content off a file. To convert this into one big digit string, I just filter out all the newlines, then turn the list into a string with mkString:

1

val digit = fromFile("Euler008-data.txt") filter (_!='\n') mkString

Next we need the method for converting a string to the product of its digits. To do that, I map the string from a list of chars to a list of ints, by substracting ‘0′ from each value, then I fold that list using the multiply operator:

1

def prodDigits(n:String) = (1 /: (n map (_-'0'))) (_*_)

Thanks to Scalas functional nature, this is a much shorter function than the same in Python. I add an extra step in scala, where I convert the digit string into a list of parts, each beeing 1 subset of 5 strings from the digit string:

1

val parts = for (n <- 0 until digit.length-5) yield digit.substring(n,n+5)

The final step is to map all the parts into products, then find the max value, here is the complete program:

1
2
3
4
5
6
7
8
9
10
11

import scala.io.Source.fromFile
 
object Euler008 extends Application {
    def prodDigits(n:String) = (1 /: (n map (_-'0'))) (_*_)
 
    val digit = fromFile("Euler008-data.txt") filter (_!='\n') mkString
    val parts = for (n <- 0 until digit.length-5) yield digit.substring(n,n+5)
 
    val max = parts map prodDigits reduceLeft((a,b) => if (a>b) a else b)
    println(max)
}

I think Scala is great for simple file handling (there are other methods to turn files into a list of strings as well), and the product method gets pretty small thanks to functional programming. The actual runtime is faster for the Python program though. Partly because of the JavaVM startup overhead, and also because I didn’t create a list of substrings in Python, which is an extra 995 object creations.

Staale Euler, Scala Euler, Python, Scala

I am an avid reader of The Daily WTF, and recently there was a small challenge posted on the site. It deals with something called Russian multiplication. The explanation on the site is much better to understand than something I could reproduce myself, so I urge you to read the full text there. Basically, in order to multiply 2 numbers, you set them in 2 columns. You then add a row with half and double of the first and second number in the previous row. Keep doing that until you have reached 1. Here is a simple table example for 47*131:

You then add all the numbers in the second column, when the number in the first column is odd, 131 + 262 + 524 + 1048 + 4192 = 6157.

Now to create a small Scala program that can solve this. First, I need a method that just produces the table above. This is rather simple to create:

1
2

def sumParts(a:Int, b:Int): List[(Int,Int)] = 
    if (a==0) List() else (a,b) :: sumParts(a/2, b*2)

Notice the list type here is (Int, Int), which indicates it’s a list of tuples. If you have used scripting languages, you might be aware of tuples already. Tuples in Scala allows us to define a list like type with fixed size, and fixed type for each value. This is a tuple of 2 Ints, and the actual type off the method is a List of tuples, each with 2 Ints. If we send 47,131 as arguments to this method, we will get List((47,131), (23,262), (11,524), (5,1048), (2,2096), (1,4192)) in return. We can now iterate over this list to create a presentable output:

1
2
3
4

val numbers = sumParts(47, 131)
for ((a,b) <- numbers) {
    println("% 8d % 8d %5s" format(a, b, if (a%2==1) "*" else ""))
}

Which produces this output:

      47      131     *
      23      262     *
      11      524     *
       5     1048     *
       2     2096
       1     4192     *

To format the output nicely, I use the format operator on the string. I have used the “%” operator to format stuff extensivly when printing in python, so I was happy to find the same functionality easily available in Scala. It would be nice if they also added a “%” overloaded method for RichString in Scala for this. I also use an if to print out a “*” next to each number that should be included in the addition. Next we need to filter out the numbers we actually need for the addition, and add them together.

1
2
3

val addNums = for ((a,b) <- numbers; if (a%2==1)) yield b
val sum = (0 /: addNums) (_+_)
println("Numbers: %s, ansver: %d" format(addNums mkString(" + "), sum))

To get addNums, we use a for loop, and Scalas powerfull pattern matching. The for syntax is (item <- iterable). Instead of accessing each entry as a tuple, we use the (a,b) pattern to indicate the shape to Scala. The shape of the List ([(Int, Int)]) matches this, and each value in the tuple will be unpacked into a and b. When then filter on values where a is odd, and yield b. We will then have a list of only those numbers that had a corresponding odd number in our original table. Using mkString we can create a presentable String version off those numbers, and using the fold operator we add the numbers together.

It's also possible to create a smaller method for just calculating the sum from the list of parts returned by sumParts:

1

def calc(a: Int, b: Int) = (0 /: (sumParts(a,b) filter(_._1%2==1))) (_+_._2)

Here I fold on the tuples, so I need to use _2 to access the 2nd value off the tuple.

Finally, here is the program in full, accepting 2 numbers on the command line. No error checking and verification is present in this version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

object RussianMultiplication {
    def sumParts(a:Int, b:Int): List[(Int,Int)] =
        if (a==0) List() else (a,b) :: sumParts(a/2, b*2)
 
   def main(args: Array[String]) {
        val numbers = sumParts(args(0) toInt,args(1) toInt)
        for ((a,b) <- numbers) {
            println("% 8d % 8d %5s" format(a, b, if (a%2==1) "*" else ""))
        }
        val addNums = for ((a,b) <- numbers; if (a%2==1)) yield b
        val sum = (0 /: addNums) (_+_)
        println("Numbers: %s, ansver: %d" format(addNums mkString(" + "), sum))
    }
}

Staale Programming, Scala Scala, TheDailyWTF

I have gotten the opportunity to work a bit with GWT likely, which is a technology I really like. And I am happy that I am now able to try it out more, and learn how to use it. One off the things I needed to work, was to request data from a different server, as I integrate with Python Django on the back end. I could create a forwarding servlet to handle the communication to deal with the same origin policy off browsers, but I have instead opted for using a Script tag approach that I found from the GWT faq and elsewhere.

However, I had one job that resulted in over 20 additional request jobs. So I wanted a system that throttled this, and only kept a limited amount of requests live at the same time. So I needed a solution a bit beyond what I had in the examples.

Circumventing the SOP when fetching JSON data

The way you circumvent the SOP in browsers, is to use script tags. You add a script tag to the document with the url for the JSON service, and you also add a parameter for which callback method the service should use. The service then creates the json data, and wraps it in “callback(<json-data>)”, so when the page loads, that method will get invoked, giving you the data. This does of course require the server you are communicating with to support this method of data fetching.

Server side Django views

To ease the creation off the JSON views in Python, I created a decorator that, when applied to a method, would wrap it such that it only needed to return something that could be json encoded. Then encode and send the result. The actual code for this relies on en extension off the DecoratorBase I posted about here, so I will not post it here. Maybe I can update this in a seperate post.

Easy request building

To make it easier to code the requests, I used the builder pattern to create JsonRequestJob objects. The JsonRequrestJob objects are rather simple:

1
2
3
4
5
6
7
8
9
10
11
12

private static class JsonRequestJob<T extends JavaScriptObject> {
    private final String url;
    private final String params;
    private final AsyncDataCallback<T> callback;
 
    public JsonRequestJob(String url, String params, AsyncDataCallback<T> callback) {
        this.url = url;
        this.params = params;
        this.callback = callback;
    }
 
}

And here is the builder:

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

public static class JsonRequestBuilder {
    private final String url;
    private final StringBuilder params = new StringBuilder();
 
    private JsonRequestBuilder(String url) {
        this.url = url;
    }
 
    public JsonRequestBuilder param(String key, String value) {
        params.append('&').append(key).append('=').append(value);
        return this;
    }
 
    public void exec(AsyncDataCallback<? extends JavaScriptObject> callback) {
        jobs.add(new JsonRequestJob(url, params.toString(), callback));
        dispatchJob();
    }
 
}

To actually create a builder, I have a DataFetcher class (which contains the above 2 classes), and it has a get method for creating a builder. The DataFetcher also need configuration in the form off a base url. This is set up by including a script tag in the root element:

1
2
3
4
5

<script language="javascript">
 
var dataUrlBase = "http://localhost:8000/etc"
 
<script>

And here is the get method. Keep in mind that the function argument here refers to which view/function I am calling on the Python Django side off things:

1
2
3
4
5
6

private static native String getDataUrlBase() /*-{
    return $wnd["dataUrlBase"]
}-*/;
public static JsonRequestBuilder get(String function) {
    return new JsonRequestBuilder(getDataUrlBase()+function+".json?callback=");
}

Finally, the actual DataFetcher needs to have a que for adding and dequing jobs, as well as an implementation that actually creates and inserts the script tag, sets up the callback method to call when data is loaded, as well as ensuring the max number of requests is kept at a minimum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public class DataFetcher {
 
    private static Queue<JsonRequestJob> jobs = new LinkedList<JsonRequestJob>();
    private static final int MAX_JOB_COUNT = 3;
    private static int jobCount = 0;
    private static int requestCount = 0;
 
    private static void dispatchJob() {
        if (jobCount >= MAX_JOB_COUNT || jobs.isEmpty()) {
            return;
        }
        jobCount++;
        final JsonRequestJob job = jobs.poll();
        makeJSONRequest(job.url, job.params, job.callback, requestCount);
        requestCount = (requestCount + 1) % 5000;
    }
 
    private static native <T extends JavaScriptObject> void makeJSONRequest(String url, String params, AsyncDataCallback<T> handler, int requestId) /*-{
    var callback = "callback" + requestId;
 
    var script = document.createElement("script");
    script.setAttribute("src", url+callback+params);
    script.setAttribute("type", "text/javascript");
 
    $wnd[callback] = function(jsonObj) {
        $wnd[callback + "done"] = true;
        @DataFetcher::dispatchJSON(Lcom/google/gwt/core/client/JavaScriptObject;LAsyncDataCallback;)(jsonObj, handler);
    }
 
    setTimeout(function() {
        if (!$wnd[callback + "done"]) {
            @DataFetcher::dispatchJSON(Lcom/google/gwt/core/client/JavaScriptObject;LAsyncDataCallback;)(null, handler);
        }
 
        // cleanup
        $wnd.document.getElementsByTagName("head")[0].removeChild(script);
        delete $wnd[callback];
        delete $wnd[callback + "done"];
    }, 1000);
 
    $wnd.document.getElementsByTagName("head")[0].appendChild(script);
 
    }-*/;
 
    public static <T extends JavaScriptObject> void dispatchJSON(JavaScriptObject jsonObj, AsyncDataCallback<T> handler) {
        jobCount--;
        dispatchJob();
        handler.handleData((T) jsonObj);
    }
 
}

Thankfully, JavaScript client side is singlethreaded, so we don’t have to worry about race conditions or synchronizations. If we needed to do that, this could could obviously break, as it has race conditions in relation to the increment/decrement and checking off the jobCount variable. Also notice that there is a timeout added that checks that the page is loaded within 1 second. If it doesn’t, null is sent to the callback, and the actual callback method is removed from the page.

The code is not entirely complete. The AsyncDataCallback interface is missing (but it’s tiny and easy to implement).

Staale Programming, Python Django, GWT, Java, Python

Today I am feeling generous, so I will go through a couple off Euler problems in 1 post. First up is the 6th problem, here is the short version off the problem:

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum

Thanks to the ease of creating ranges and applying functions to them in Scala, this turns out to be pretty easy:

1
2
3

val sumOfSquares = (1 to 100) map (a=>a*a) reduceLeft (_+_)
val squareOfSum = (BigInt(0) /: (1 to 100)) (_+_) pow(2)
println squareOfSum - sumOfSquares

Pretty simple code. The first line just maps each number in the 1 to 100 range to their 2nd power, then sums them all using reduceLeft. The second line uses the fold left operator (/:) to sum all the numbers in the 1 to 100 range into a single BigInt, which we then call the pow(2) method on to get the power off 2. Finally it’s just subtracting the 2 numbers.

Now onto problem 7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

The best way to find prime numbers, is to use the Sieve of Eratosthenes. We do this using a bitset. We start at index 2, and for each index we find that is not marked, we mark all the multiples for that index. So we first look at index 2, this is not marked, so we mark 4,6,8,10 and so on, up to our max. We then check index 3, this is not marked, so we mark 6,9,12,15 and so on. Then we go to index 4, this is marked, so we don’t do anything. This goes on until half the max value. Now we have a bit set where all non-primes are marked. Here is the method implemented in Scala using a mutable BitSet:

1
2
3
4
5
6
7
8

import scala.collection._
def primesUpTo(max:Int) = {
    val nonPrimes = new mutable.BitSet
    for (n <- 2 to (max/2); if !nonPrimes(n); x <- n*2 until(max,n)) {
        nonPrimes += x
    }
    for (n <- 1 to max; if !nonPrimes(n)) yield n
}

We first import everything in the scala.collections package, then mutable.BitSet can be resolved to scala.collections.mutable.BitSet. This is an extension to the package system in Java where only classes can be imported, in Scala we can import namespaces and refer to things within those namespaces. Now we iterate from 2 until max/2, for each number we see if it’s not set in the bitset, if it isn’t we iterate until max with a step off n, and mark off each multiple. Finally we just iterate over the entire bitset, and yield all unmarked values, as those will be the primes.

Now to get the solution to the problem, we just need to figure out a max value that creates more than 10001 primes, and get the 10001th prime from that:

1

println(primesUpTo(500000)(10001))

Now I am going to skip number 8, as I can use that to deal with file parsing, and instead move directly on to number 9:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

There are some clever ways off doing this, but I am just heading straight for brute force solution to this one, as the solution space is pretty small.

1
2

val n = 1000
for (a <- 1 to n; b <- a to n-a; c=n-a-b;if a*a+b*b==c*c) println(a*b*c)

Since I use the target value 1000 a few times, I just put it in a constant that I can refer to. I first iterate a from 1 to 1000, then b goes from a to n-a, and c will then have to be 1000-a-b for the a and b that are set at that part in the iteration. We then just check if the values we have for a,b and c fulfill the Pythagorean formula, and print the product off the first one we find. Short and sweet.

That’s it for todays program. Next up will problem 8, and file parsing, which I haven’t looked into yet for Scala. I will have to compare it to Python, which has some nice and simple features for text file parsing.

Staale Euler, Scala Euler, Scala

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

I have been using BerkeleyDBs JDP on and off a bit, just experementing with it to see how it works. BerkeleyDB is basically a B-Tree with transaction support. You store key/value pairs, both being byte arrays. JDP – Java Direct Persistence – is a layer that is built on top off this using annotations. It provides you with JPA like architecture for storing objects. Except there is no underlying SQL, just pure key lookups. This means you can’t write complex queries to select data, you will have to use code instead. But imho. this also means the complexity off what you are doing becomes more apparent.

I have fiddled around a bit with this, and I wanted to create a clean way off configuring environments. When you are using BerkeleyDB, you need to set up an Environment first:

1

Environment(File envHome, EnvironmentConfig configuration)

The EnvironmentConfig in return is set up using a setters:

1
2
3
4

EnvironmentConfig envConfig = new EnvironmentConfig();
envConfig.setTransactional(true);
envConfig.setAllowCreate(true);
envConfig.setCacheSize(1000000);

However, for Scala I wanted to use chaining to set up the environment config. The base implementation does not return this in the setters, so you can’t chain the statements. My first idea was to use implicit to convert the EnvironmentConfig to a richer version, that simply returned itself, so you could chain it.

1
2
3
4

class RichEnvConfig(val config: EnvironmentConfig) {
    def transactional() = {config.setTransactional(true); this}
    def allowCreate() = {config.setAllowCreate(true); this}
}

However I didn’t get it to work properly. I also thought about using operators to chain together traits. But then it occured to me that using traits themselves might make things clearer. So I created the following class:

1
2
3
4
5
6
7
8

object EnvConfig {
    implicit det unwrap(envCfg: EnvConfig) = envCfg.config
}
class EnvConfig {
    val config = new EnvironmentConfig()
    trait Transactional { config.setTransactional(true) }
    trait AllowCreate { config.setTransactional(true) }
}

Now I could more easily create EnvironmentConfigs and use them in code:

1
2

val config = new EnvConfig with Transactional with AllowCreate
val env = new Environment(new File("."), config)

I do however want to use the loan pattern with the Environment, as the Environment requires you to call close on it after use. So I thought instead off having a class for EnvironmentConfig, I could use have one for Environment itself, with an apply method. The Environment wouldn’t be created until it was required in apply, and using traits you could configure the Environment. Pretty happy with myself with the final solution for the Environment part:

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

class Env(val path:File) {
    trait Transactional extends Env { config.setTransactional(true) }
    trait AllowCreate extends Env { config.setAllowCreate(true) }
 
    val config = new EnvironmentConfig()
    def apply[T](f:(Environment) => T) = {
        val env = new Environment(path, config)
        try { f(env) } finally { env.close() }
 
    }
}
 
object EnvTest extends Application {
    val env = new Env(new File(".")) with Transactional with AllowCreate
    env { e =>
        println(e)
    }
}

Some handy links to BerkeleyDB Java Edition:

• BerkeleyDB Java Edition
• Getting started guide
• BerkeleyDB JavaDoc

Staale Programming, Scala BerkeleyDB, JDP, Scala

The third project Euler problem is about finding the largest divisor for a single number:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143

One small “problem” here is that the number 600851475143 exceeds Integer.MAX_VALUE which is 2147483647, so we have to use either Long or BigInt. I went for BigInt for this one. The algorithm I choose is pretty simple:

Take the number n, and divisor d:

• if n mod d is 0, divide n by d and check again
• if n is larger than d, increase d by 1 and check again
• d is the answer

In Scala code, the method turns out as follows:

1
2
3
4
5
6

def largestDivisor(n:BigInt, d:BigInt):BigInt = {
    if (n%d == 0) largestDivisor(n/d,d) 
    else if (n>d) largestDivisor(n,d+1) 
    else d
}
def largestDivisor(n:BigInt): BigInt = largestDivisor(n,2)

We have a convinience method here to help us out, as we always start the divisor with a value off 2. If we started with 1 we would have an endless loop, as all numbers mod 1 is 0. It’s then just a matter of printing out the result.

Again we are using tail recursion, which Scala will rewrite to a loop instead. To look at the actual result off the code, I ran the resulting class file through jad, and got the following result:

1
2
3
4
5
6
7
8
9

public BigInt largestDivisor(BigInt n, BigInt d) {
        do {
            for(; BoxesRunTime.equals(n.$percent(d), BoxesRunTime.boxToInteger(0)); n = n.$div(d));
            if(n.$greater(d))
                d = d.$plus(BigInt$.MODULE$.int2bigInt(1));
            else
                return d;
        } while(true);
    }

In line 3 we see the continual division off n/d as long as n%d == 0. This corresponds exactly to my Scala code in line 2, recursivly calling it self while dividing n by d. Line 4-7 corresponds to line 3-4 in the Scala progam, increasing d by 1 if d is less than n, or returning d. By running my Scala compiled class file through jad, I am able to exactly see how Scala converts tail recursion to loop code.

Staale Euler, Scala Euler, Math, Scala