Learn a new programming language (pt. 3)

If you've read part 1 and part 2 you know I set out to solve each of the Euler problems in a set of languages that I'm not so familiar with:

  1. Clojure
  2. C#
  3. Objective-C
  4. Scala
  5. Python
  6. JavaScript

In this last part I'll illustrate each language with code samples. By solving the first six Euler problems, while attempting to leverage the best of each language.

  

Euler problem #1 solved in Clojure

"If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000."

Clojure is a modern functional language for the JVM, which derives its syntax from Lisp. It was created by Rich Hickey in 2007 to be a general-purpose language that encourages a functional programming style. One of the main goals of the language is to simplify multithreaded programming through the use of software transactional memory, an agent system, and a dynamic var system.

     (range 3 1000 3)

The above code returns a lazy sequence of all multiples of 3 below 1000. How? A range in Clojure starts with the first number, 3 in the example, and adds the last number, again 3, as long as the result stays below 1000. A lazy sequence is like an Iterator in Java. Each next multiple of 3 is only computed when you ask for it.

     (map #(range % 1000 %) [3 5])

The map function applies the earlier piece of code to both the numbers 3 and 5, returning two sequences. The # symbol turns the code fragment that comes immediately after it into an anonymous function, with % as the default name of its argument.

In functional programming "folding a list" means applying a function to the first two elements of a list, then applying that same function to the result and the third element, and so forth. For example, left folding the minus operator on [3 5 6 9] results in 3 - 5 - 6 - 9 = -17. You could also start on the other side of the list, 9 - 6 - 5 - 3 = -5. This is called right folding.

In the Clojure language there are tons of higher-order functions that operate on lists. The function that folds left is called "reduce". Reducing the two sequences of multiples of 3 and 5 to just one sequence is done by concatenating both of them:

     (reduce concat (map #(range % 1000 %) [3 5]))

We're almost there. We now have one long sequence of multiples of 3 and 5, but some of them, like the number 15, occur twice. Filtering these out can be done by turning the sequence into a set:

     (set (reduce concat (map #(range % 1000 %) [3 5])))

Finally, we reduce the numbers down to their sum:

     (reduce + (set (reduce concat (map #(range % 1000 %) [3 5]))))

There you have it, the solution implemented on just one line.

For good measure let's wrap this in a function which can be called with the arguments [3 5] and 1000. In the code sample below, you'll find on the first line the name of the function, on the second line the function description that's used to generate documentation, on the third line a unit test, on the fourth line the arguments and on the last line the implementation:

     (ns com.blogger.gertverbruggen
         (:use clojure.test))

     (defn sum-of-multiples
         {:doc "Sum of all multiples less than 'end' of the numbers in 'coll'"
          :test (fn [] (is (= 233168 (sum-of-multiples [3 5] 1000))))}
         [coll end]
         (reduce + (set (reduce concat (map #(range % end %) coll)))))

     (run-tests)

Netbeans as an IDE is a definite winner for me here, with support for not just Clojure but also Scala, Python and JavaScript.

Note that you can solve this problem in another way. Simply run through the first 1000 natural numbers and filter out those that are divisible by either 3 or 5:

     (1 until 1000).filter(n => n % 3 == 0 || n % 5 == 0).sum

That piece of code is Scala, but I might just as well have chosen Python or C#. You can write the same one-liner in any of today's functional languages.

Answer: 233168



Euler problem #2 solved in C#

"Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms."

Some 800 years ago in Italy a man aged 30 by the name of Leonardo Pisano Bigollo thought that MCMLIV - MDCCCCX = XLIV wasn't such a practical way to do calculus. So he introduced the Arabic numerical system: 1954 - 1910 = 44. This and a lot of other stuff made him one of the most talented western mathematicians in history.

Incidentally he was also interested in the reproduction of rabbits and thus came across the sequence 0, 1, 1, 2, 3, 5, 8, … If you think of Mr. Bigollo as being old, the sequence is twice that old. It first appeared in the 6th century in India. But nonetheless, the sequence is accredited to him because he wrote it down in his book "Liber Abaci" and gave it a name: the Fibonacci numbers.

Computing the numbers is easy. Say you have a tuple (a, b), then the rule is that the next tuple in line will be (b, a+b). If you start with (0, 1) then you get (0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), … Take the first number of each tuple and there you have it.

It's hard to express this more clearly than in C#. Below is a method which returns an IEnumerable object. When you call the method nothing happens. Only when you ask for the first element will the body of the method be executed. Right until "yield" is encountered, at which point further execution is suspended. When you ask for the next element execution of the method is resumed where it left off, until once again it's asked to yield:

    public static IEnumerable<int> Fibonacci()
    {
        var f = new {A = 0, B = 1};
        while (true)
        {
            yield return f.A;
            f = new {A = f.B, B = f.A + f.B};
        }
    }

If you find the yielding a bit confusing, take a look at this identical code sample from JavaScript. It follows the well known iterator pattern:

    function fibonacci() {
        var f = {a: 1, b: 0};
        this.next = function () {
            f = {a: f.b, b: f.a + f.b};
            return f.a;
        }
    }

Python:

    def fibonacci():
        return (a for (a, b) in iterate((0, 1), lambda (a, b): (b, a + b)))

Clojure:

    (def fibonacci
        (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))


Thanks to the expressiveness of LINQ on the .NET platform the rest of the algorithm flows naturally in C#:

    Fibonacci()
        .TakeWhile(x => x < 4000000)
        .Where(x => x % 2 == 0)
        .Sum();

For writing code in C# the Mono project is a good option. First install the Mono compiler and after that install the free IDE called MonoDevelop. It's no Visual Studio but it runs on Mac and Linux. And it's free. Did I mention that?

Again, like with the first solution, you can write similar code in the other functional languages. In Scala, for example:

    fibonacci takeWhile(_ < 4000000) filter(_ % 2 == 0) sum

Notable differences are that in Scala it's more common to write things on one line and not have dots in between. Although you can still write the dots, if you should find that more readable. Also the anonymous predicates are shorter because in Scala the default argument is always symbolized with an underscore.

In Clojure you end up writing it backwards:

    (reduce + (filter even? (take-while #(< % 4000000) fibonacci))))

That's because in Clojure you're looking at the problem from the perspective of what you want, not from the perspective of where-do-I-start. Read the Scala or C# samples out loud: "Generate the Fibonacci numbers, take those below 4 million, limit yourself to the even ones and sum them up." Now read out loud the Clojure sample: "Add up all the numbers that are even below 4 million of the Fibonacci sequence." See the difference?

Answer: 4613732



Euler problem #3 solved in Objective-C

"The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?"

As object-orientation became more trendy several software companies have taken the most widely used language ever, C, and added the idea of classes to it. Bell Labs and StepStone were the first in the early eighties with C++ and Objective-C respectively. 10+ years later Sun Microsystems, now Oracle, came along with Java, and another five years later Microsoft with C#. StepStone got absorbed by NeXTstep, which got swallowed by Apple Inc. Which is why today everyone's writing iPhone apps in what's essentially C with objects.

So here's how to find the largest prime factor in Objective-C:

    - (int)largestPrimeFactor:(unsigned long long)n
    {
        for (unsigned long long i = 2ULL; i * i <= n; i++) {
            while (n % i == 0) {
                n /= i;
            }
        }
        return n;
    }

After half an hour drag 'n dropping the user interface together in the XCode IDE, I've got a largest prime factor calculator app on my iPhone. Super useful stuff.

The solution is almost identical in C#, Python, Scala and JS. Clojure on the other hand, being a purely functional language, isn't well suited to do for- or while-loops, favoring a recursive strategy instead:

    (defn factors
        "Returns all prime factors of x in ascending order"
        ([x] (factors x 2 []))
        ([x y primes]
            ((if (> x 1)
                (if (zero? (rem x y))
                    (factors (/ x y) y (conj primes y))
                    (factors x (inc y) primes))
                primes))))

    (last (factors 600851475143))

Answer: 6857



Euler problem #4 solved in Scala

"What's the biggest palindrome that's also the product of two three-digit numbers?"

The solution across all languages is to:

  1. run through two lists of numbers, both ranging from 100 to 999,
  2. check which products are palindromic, and then
  3. return the largest of those products.

So we'll have some for-loops involved, even in Clojure. We have to either keep track of the maximum as we go, or look for it after we've found all palindromic numbers. And we have to identify a number as being palindromic, of course.

It's with that last bit that there's a lot of variation. In JS the most straightforward thing to do is to start at both ends and compare number by number as you move towards the center:

    function palindrome(n) {
        var s = n.toString(), left = 0, right = s.length - 1;
        while (left < right) {
            if (s.charAt(left++) !== s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }

But the shortest, clearest implementation of the palindrome predicate is in Scala:

    def palindrome = (s:String) => s == s.reverse

The solution is found like so:

    val palindromes = for (x <- 100 until 1000; y <- x until 1000;
        val xy = x * y if palindrome(xy.toString))
            yield xy
    palindromes toList max

Python looks similar:

    products = (x * y for x in range(110, 1000, 11) for y in range(x, 1000))
    max(xy for xy in products if palindrome(xy))

Remark here that x = 110, 121, 132, 143, … which comes from the observation that any palindrome must logically be a multiple of 11. A nice optimization.

In Clojure the syntax is still a bit shorter:

    (apply max (filter palindrome?
        (for [x (range 110 1000 11) y (range x 1000)] (* x y))))

In my earlier post I criticized the experience of programming in Scala. Which prompted Guido to ask whether I had tried the plugin for IntelliJ? I haven't. Thanks for the tip! It does seem like had I used the IntelliJ plugin I would have felt better equipped: IDE and editor plugins for Scala

Answer: 906609



Euler problem #5 in Python

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

If you think about it, of all the numbers that are evenly devisable by 1 to 20 the smallest one must be what's called in mathematics the least common multiple of the numbers 1, 2, 3, …, 20. This can be found by computing the least common multiple of 1 and 2, which is 2. Then the least common multiple of that result and 3, which is 6. And so on...

    def smallest_evenly_divisible(n):
        """Returns the smallest number that is evenly divisible by 1 .. n"""
        return reduce(lcm, range(1, n + 1))

The lcm function is easy: divide the product by the greatest common divisor.

    def lcm(a, b):
        """Returns the least common multiple"""
        return a * b / gcd(a, b)

This leaves us with implementing the gcd function, using Euclid's algorithm. This can be written quite elegantly in Python:

    def gcd(a, b):
        """Returns the greatest common divisor"""
        while b:
            a, b = b, a % b
        return a

In C#, Scala and JS the solution is the same. Clojure wins. It only requires one line of code since the lcm function is part of the language:

    (reduce lcm (range 1 (inc 20))))

Objective-C is the most verbose because it lacks a functional style of programming.

Answer: 232792560



Euler problem 6 in JavaScript

"What is the difference between the square of the sums and the sum of the squares of the first 100 natural numbers?"

This is a fun math question. The sum of the natural numbers 1 .. n is captured in this simple formula:

    n (n + 1) / 2

We square that, and then subtract "the sum of the squares". As you can see in this drawing, the sum of the squares form a pyramid.

What we're looking for is called the "square pyramidal number" and its formula is:

    n (n + 1) (2n + 1) / 6

I find any mathematical formula is easiest expressed in Python:

    def solve_problem_6(n):
        return (n * (n + 1) / 2) ** 2 - (n * (n + 1) * (2 * n + 1) / 6)

But without a large comment the casual reader will have no idea what this function is doing.

Scala allows for a more understandable, albeit less efficient, solution:

    def solveProblem6(n:Int) : Long = {
        val numbers = 1 to n
        def square(x:Int) = x * x
        square(numbers.sum) - numbers.map(square).sum
    }

But what about JavaScript?

JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. The language was release together with Java in 1995. But don't confuse it with Java, or with Javanese script.

The latest release of JavaScript is 1.8.5 and the language is being pushed forward by Firefox. Every browser includes some dialect of this language, like for example JScript in IE. To prevent the dialects from diverging too much there's a standard called the ECMA-262 specification, currently in its 5th edition.

There's a wide choice of editors for writing JS. At first I started out with Aptana Studio, but it felt slow. Now I recommend Netbeans.

Can we express the solution in JS like we did in Scala? Yes, but we need to gear up first. Both the sum function and the expression "1 to 100" to define a range are missing from JS. But we can easily extend the language:

    /**
     *  Extends Array with a range() function that returns a new Array from
     *  start to end (excl.), by step, where start defaults to 0 and step to 1
     */
    if (!Array.range) Array.range = function (start, end, step) {
        var r = [], i;
        if (arguments.length > 3) {
            throw new Error("Call to Array.range(start, end, step) with "
                + arguments.length + " arguments");
        }
        step = step || 1;
        if (!end) {
            end = start;
            start = 0;
        }
        start = start || 0;
        for (i = start; i < end; i += 1) {
            r.push(i);
        }
        return r;
    }

The first line of this code adds the range() function to the Array global object, if that object doesn't have a range() function. It normally doesn't, but still it's good to check. Notice also that in the comment it's stated that the "start" argument defaults to 0 if not present and likewise the "step" argument defaults to 1.

In Java you would be adding these methods to the ArrayList class:

    public static List<Integer> range(int start, int end, int step);
    public static List<Integer> range(int start, int end);
    public static List<Integer> range(int end);

Of course, in Java you can't add methods to a standard library class. Except maybe with Tapestry Plastic, a wrapper around ASM. Use of this will not collide with another framework like Hibernate. I used to think that Hibernate had AspectJ-like internals but it turns out that instead it plugs in on a deeper level of the JVM.

Immediately you see a benefit of the JS language being dynamically typed. You can define functions in a terse way. You only need to specify its name, not whether it returns anything, the return type, the types of the arguments or even the number of arguments.

That last bit implies you can't overload a method, by the way. So we have to handle the different calling signatures in the body of the function:

    Array.range(3, 8, 2); // expected to return [3, 5, 7]
    Array.range(3, 8); // expected to return [3, 4, 5, 6, 7]
    Array.range(5); // expected to return [0, 1, 2, 3, 4]

Can you see how the second and third case are handled inside the body of the above range() function?

Keep in mind that nothing can stop you to call:

    Array.range();
    Array.range(7, 9, 7, 2, 0, 4);

For completeness these cases are also handled inside the function. The former will return an empty Array while the latter will throw an Error.

Notice also that although JS will let you write more concise code I refrained to do this. For example, I could have:

• gotten rid of half the curly braces and half the semicolons,
• defined the variables r and i later on in the code,
• used i++ instead of i += 1,
• written the if and for statements on a single line.

Doing so would be bad practice since it increases the chance of uncaught syntax errors. Especially leaving out semicolons is a problem because what the compiler does is auto-correcting your source code. How it works is, when the compiler encounters a parsing error it will back-track to the first spot where it thinks you might have forgotten a semicolon, insert it for you and try again.

A tip is to always run the style checker JSLint on your JS code and follow it's suggestions. That way you'll avoid possible errors and quickly learn what's best practice.

The other function that's missing is sum(). This is not a "static method" so we add it to Array.prototype instead of to Array. By adding something to Array's prototype you add it to all Array objects created with the new keyword or with the [ ] notation. The sum() function works by passing an anonymous addition operator to the reduce() function:

    /**
     *  Extends Array with a sum() function that returns the sum of all
     *  elements of this Array
     */
    if (!Array.prototype.sum) Array.prototype.sum = function () {
        return this.reduce(function (x, y) {
            return x + y
        });
    }

With both extensions of the Array object in place we can solve the problem in JavaScript just like in Scala:

    var numbers = Array.range(1, 100 + 1);
    var square = function (x) { return x * x; };
    return square(numbers.sum()) - numbers.map(square).sum();

Answer: 25164150