Ståle’s weblog

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 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

I have a project at work where in Python, where I use decorators to wrap functionality for views. I hit on a snag when I used 2 decorators on 1 function. I like using class decorators, I read some recommendations regarding that, and it fits better with my Java upbringing . The 2 decorators I needed to apply to the same function looked like this (__call__ method omitted for brevity):

1
2
3
4
5
6
7
8
9

class AutoTemplate(object):
    def __init__(self, func):
        self.func = func
        pathElems = func.__module__.split(".")[:-1]+["%s.html"%func.__name__]
        self.template = os.path.join(* pathElems)
 
class AccessRequired(object):
    def __init__(self, func):
        self.func = func

In addition, I used the functions actual name in the urls.py file to generate the url tuple:

1
2
3

def createUrl(method):
    name = method.func.func_name
    return (r'^%s.html$'%name, method, {}, name)

So the finished product after decorators where applied needed to work for that. Because the decorators resulted in a class rather than a function being assigned to the the view, this didn’t work properly.

With a little help from Stackoverflow however, I came upon a good solution, that makes it really transparent that a function is actually decorated:

1
2
3
4
5
6
7
8

class DecoratorBase(object):
    def __init__(self, func):
        self.func = func
        for n in set(dir(func)) - set(dir(self)):
            setattr(self, n, getattr(func, n))
 
class AutoTemplate(DecoratorBase): pass
class AccessRequired(DecoratorBase): pass

This does not work for decorators requiring parameters, I will see if I can find a solution for that if I need it.

Staale Programming, Python Decorators, Python