Euler Problem 029 in Scala 04-03-2011
Over the last couple of weeks, I've been slowly stepping through the wonderfully difficult problems at Project Euler. The problems found at Project Euler form a series of progressively challenging mathematical questions, totalling 326 and counting. You can expect questions about everything from counting to prime factorization to sequence evaluation and beyond. For a great many of the exercises, there is an obvious brute force solution; but the fun is in getting as elegant and clever as you can possibly muster.
When I first heard of Project Euler, I signed up and dove right in. The question was not, "Do I want to do this?" or "Do I have the time to work through these?" I was in love with the idea right away. No, the question was, "What language should I tackle these problems with?" Normally, I am not hung up on language choice for any project. I have lost count of how many times I have parroted the old Dijkstra line that goes "Computer science is no more about computers than astronomy is about telescopes" or the similarly framed analogy that programming languages are to engineers as hammers are to carpenters. In short, I think of them as tools. And I would like to think that most problems can be solved by any number of languages. But I would be foolhardy to deny that I prefer some languages to others. My obsession with Python, for instance, is a tad unsettling. And going into a project which so thoroughly tests your mental limits, I wanted to work in a language that would ease the difficulties as much as possible. That's why I chose Scala.
Scala is a compelling mix of object orientation and functional programming, providing a flexibility and range of motion that is hard to find elsewhere. It is statically typed, and infers types pretty amazingly, from what I can tell. Initially, I was concerned that there would be an untold amount of frustration from poor inferences, but the compiler absolutely protects the coder. It has done so well for me, in fact, that it has started to reinforce a sense about when to be explicit and when to be implicit. And this is all well and good, but the functional aspects of the language are what truly intrigued me for this project. The comprehensions, the mapping capabilities, the high-order functions, the built-in pattern matching... they all apply well to purely mathematical pursuits.
And aside from all of that, I was/am still new to Scala and felt that this would be an excellent way to hone my skills and knowledge with the language. So I guess you could say that I came for the education but stayed for the tail recursion.
Problem 029 is a particularly interesting way to demonstrate Scala's abilities to make life easier. It asks:
Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
So what we're looking at here is a problem in which we will have to a) calculate some quite large numbers, up to 10^200 in fact, b) do these calculations over and over again, precisely 9801 times, and c) determine how many of these terms are unique. This is not the most puzzling or perplexing problem by any stretch of the imagination. But it does display Scala's power and flexibility. One of many possible solutions:
That's it. We defined a function getDistinctCount(Int, Int) which takes in lower and upper bounds (2 and 100 from the problem statement) and returns the number of distinct terms generated by our calculations. Scala provides a wonderful mapping function, which essentially takes a list of elements and individually maps each element by some specified function, returning the new list. In the code, we use map to map all b values to a^b, a mapping of Int => Int.
Also take note of the flatMap function, which instead of mapping all elements in the manner of X => Y, maps them in the manner of X => Iterable[Y] (This post by Richard Dallaway is what finally revealed the workings of this function to me). We thus use the flatMap function to map each a value to each respective list produced by the previous b mapping, and then flatten this a-mapping into one list. We then reduce the list into only distinct elements and return the amount of elements in this final list, as seen by the .distinct.size portion of the code. And that integer value is our desired answer.
Basically, the one line of our getDistinctCount function maps each value of a to the mapping produced by mapping each value of b to a^b, and then returns how many unique terms are in that outer, master list. We could have written the entire script in just that one line, actually; the rest is fluff. In more imperative languages, this would have taken some nested for-loops and then some individual calls on the finished product to get our final value. And for most languages, we would have had to explicitly specify everything, including return type and List types and so on. Here, Scala provided the capabilities to allow us to perform nested mapping in an intuitive manner, with absolutely no obstacles to a clean and simple solution. We just did some basic function calls and list comprehensions and called it a day. Pure fun.
And to handle the large numbers calculated by our exponents, we used the exceedingly handy BigInt type. Thanks, Java.
But more importantly, thank you Project Euler for helping me to find such interesting and compelling ways to use Scala, one of my new joys in life.