For a long time I've wanted to try out the Nimrod programming language, which appears to be something in between C and Python. A wonderful idea if you ask me. A statically typed, compiled language that doesn't want to shoot you in the head. After having skimmed through the documentation and manuals, having installed it (a very easy and pleasant experience by the way) I fired up a text editor and got cracking.
For those of you who don't know, the Project Euler problems is a collection of programming puzzles in various difficulties. I have never gotten around to seriously solving them until now so not only the language, but the algorithms themselves are new to me.
Euler Problem 1:
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.
A pretty straight forward puzzle ...or? My first solution is basically just to loop from 1 to 999/3 and 999/5 respectively and add every i3 and i5 to a common sum. But this approach doesn't give you the proper answer because numbers which are multiples of both 3 and 5 (ie. every multiple of 15) gets counted twice, which apparently is wrong. In order to catch these numbers properly we need a common loop, a modulos operator and the OR logical statement.
var sum: int = 0 for i in 1..999: if i mod 3 == 0 or i mod 5 == 0: sum = sum + i echo("Grand total is: ", sum)
A pretty compact, Python-esque program. In the first row we initialize the sum variable, which obviously is an int. Some pretty syntactic sugar for the loop, 1..999 means every number from 1 up to and including 999, unlike Python and other sane languages where the latter number indicates the first number not in the sequence. The modulus operator is not % like you might expect. There is a %% operator which handles unsigned ints. (Yeah, you have to keep track of whats signed and unsigned). Every "unsigned" operator ends with a %, (such as +%, /% and <=%) and before I found out I had to use "mod" instead, I got quite frustrated over the senseless error message. And yeah there doesn't seem to be a += operator by default.
Euler Problem 2:
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:
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.
Fibonacci, more looping.
var a, b : int = 1 sum : int = 0 for i in 1..1000: b = a + b a = b - a if b > 4000000: break if b mod 2 == 0: sum = sum + b echo("total: ", sum)
I just assumed the 1000'th Fib number exceeded four million. There is nothing new here compared to the previous puzzle.
Euler Problem 3:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ? This one is quite a monster puzzle. Prime number factorization is a difficult problem and I was surprised to see one so early. There is a pretty neat algorithm for this which works for small numbers such as this. (For a computer, 6e11 is nothing). Let p1 to pn be our prime factors such that p1 * p2 * ... * pn = target. By trying to divide our target number with a factor until it's evenly divisible, we find p1. We can then divide our target with p1, repeat the process and find p2. Repeat further until you find pn, the largest prime factor.
proc primeFactors(n : int64, start : int64): seq[int64] = var factors : seq[int64] = @[] factor : int64 = start while n mod factor != 0: factor = factor + 1 echo(factor, " is a factor") factors.add(factor) if n > factor: var more : seq[int64] more = primeFactors(n /% factor, factor) for f in items(more): factors.add(f) return factors discard primeFactors(600851475143, 2)
First of all, Nimrod is case insensitive, which is rather neat. Case sensitivity doesn't improve readability and it certainly doesn't prevent you from typing like an arse, so why not. The code starts of with our primeFactor proc(edure, as they're called in Nimrod), it needs a target number, and a starting factor. The first starting factor is obviously 2. We want a sequence to keep our numbers. And the next line might surprise you. We declare a var, factor, which starts at start. Why not use start? This is because parameters are constants in Nimrod, they cannot be changed inside the proc. Trying anything like start = start + 1 would result in compilation errors. There is a way around this though and that is declaring the parameter as a var, like this
proc primeFactors(n : int64, start : var int64): seq[int64] =
This way, we are able to change it inside the proc. However, there is a twist to this. If the parameter say it's a var. Then you have to pass in a var. Ie. you cannot call "primeFactors(600851475143, 2)" like I do below, I would have to declare a var, set it's value to 2, and then pass it in by name. The wonderful side effect of this is that any and all changes inside the proc, are visible outside as well. Just like out-params or whatever they're called in C#. Parameters you pass in for the sole purpose of having them changed. I'm not sure I fancy this.
Moving on, sequences in Nimrod is basically linked lists, they can grow in size dynamically by adding. I became really saddened by the state of Nimrod documentation here. Nowhere is it mentioned how you add stuff to a sequence. After a good while on google, I simply tried .add(). After that came the next problem, integer division. Simply / doesn't work, because that gives a float. And there is no way to type cast the result into an int64 either. (There is a way to cast it to int, but that doesn't work for reasons I'll explain later) However later I found that unsigned division gives wanted results. "/%", isn't is just about the most horrible operator sign you've ever seen? Nowhere would I expect it to perform what I know as simple integer division...
The next and final problem I had with this code was the size of the target number. 6e11 is too big for an int32, and I had to use int64. And because you for some reason cannot do some stuff between different int sizes, I just went ahead and changed everything to int64. Which lead to the problem of not being able to typecast the division to my wanted type.
Finally, the discard statement is needed if you call a function which returns something when you're not interested in the result. I like this.
Euler Problem 4:
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.
Palindrome checking is easily done with string parsing. So let's start with that.
proc isPalindrom(digit : string): bool = for i in 0..int(len(digit)/2): if digit[low(digit)+i] != digit[high(digit)-i]: return false return true
low(someArray) returns the lowest valid index, and high(someArray) returns the highest valid index. We simply check if char at 0+c == char at N-c I don't really know why there is a proc called low(), isn't it always zero?
As you can see, there is a rather messy expression in the for loop. for i in 0..int(len(digit)/2), because simple division returns a float, and you cant count up to a float.
Second task, run this method on all products of three digit numbers.
proc largestPalindrom(nums : int): int = var upper : int = (10 ** nums)-1 lower : int = 10 ** (nums-1) max : int = 0 for x in countdown(upper, lower): for y in countdown(upper, lower): var prod : int = x * y if isPalindrom($prod): if prod > max: max = prod return max
In an attempt to optimize this I changed it from a complete loop, and then finding the max to look through the biggest numbers first. Note that ** is not implemented by default, I had to add this by myself. ^ is already taken to dereference references and as such, shouldn't be used for math. Afterwards it's simply a matter of echo(largestPalindrom(3)).
I also did Problem 5, but I see this post is getting ridiculously long and since that puzzle doesn't teach anyone anything I'm going to skip it.
To say some final words about Nimrod the language. Even though I'm not really qualified to criticize it. It's a neat idea, it's fast and pretty neat. Not too much readability has gone lost in it's attempt to gain speed. However some things doesn't act the way you'd like them to and the documentation really doesn't help. Looking through other peoples examples I can't say it's very intuitive. The type system is too "typy", just like most other statically typed languages I've tried out. There should never ever be a concern for the programmer whether he/she use 16 bit ints or 64 byte ints. Same goes for signed an unsigned. There is no threading support as of yet, but according to their website there are plans for it together with an STM model, which is great and I really want to see how that goes.
I have barely scratched the surface of this language and I bet there's a lot of awesome stuff going on underneath, and a lot of cool toys and powerful syntax later on. I don't want to write an essay on the subject, but I feel I need to say that that isn't necessarily all good, but a garbage collected, STM modeled C-fast language is always worth trying out.