Problem thirteen from Project Euler is one of those problems that's so simple, I don't understand why it's in the double digits section. The problem reads: “Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.”
It then proceeds to list 100 long numbers. I'm not going to paste them here because they are in the code solutions below and I don't want to clog up the “tubez” with more redundant information than I'm about to.
Enough of my jibber-jabber. Here is my Haskell solution first (trying to change things up here):
followed by my Python solution:
and to continue adding in the spice, I have included a solution in Scala:
Some of you may be wondering, “Why a Scala solution?” To which I respond, “Why not?” Because that's a little short, I'll add that it has something to do with Scala starting to gain traction in the industry and me seeing if I would like to get paid to program in it.
The solution, in all three languages, is pretty simple. The recipe essentially says, “Put all numbers into a list. Get the sum of that list, turn that number into a string, and get the first 10 characters of that string.”
Times:
Haskell (compiled) : real 0m0.004s
Haskell (runghc) : real 0m0.314s
Python : real 0m0.059s
Scala (compiled) : real 0m0.757s
For the most part it's pretty standard in these tests to see performance times such that Haskell (compiled) < Python < Haskell (runghc). Java and Perl usually fall somewhere between the Haskell (compiled) and Python, in that order. To see Scala be 2x slower than Haskell (runghc) was a shocker. The only thing that makes sense to me for the slowdown is having to use the BigInt library. That is probably the biggest thing I took away from these time tests - if I want to do REALLY large number crunching and performance DOES matter, JVM-based languages might not be the best option.
A few thoughts on Scala:
If I haven't stated it already in this blog, I should now give the disclaimer that I'm not a Java fan. I know it still has its loyal followers, but I'm not one of them. Moving on. This was my first time working with Scala, and I'd like to finally welcome Java to the 21st century. While doing some research on the Scala language itself I read that “the industry” was moving to replace Java with Scala. I welcome that change. Does that mean I “like” Scala? The honest answer is, to butcher the quote the appliances from the Flintstones, “Eh, it's a language.” Scala is definitely an improvement over Java – not really that hard to do in my opinion – but, the language still feels unpolished. One quick way to kill the interpreter in Scala is to type “Int” then hit the enter key. Instead of error-ing out, the interpreter does a great job of interpreting a crash test car hitting a cement wall (I had to restart the whole thing.) When I tried the same “technique” in the Python interpreter, I got
All that being said, I do like the way Scala is trying to handle the reducing of Java's dot notation, and I think it's starting to make strides in the right direction in other areas. I'm open to working with Scala more, and look forward to seeing how it evolves over the next few years.
I think print has been backported to Python 2 already.
So you might not need the import.
the "from __future__ import
the "from __future__ import print_function" is needed to use the backport.
If the import was not used, he would have use the print *statement* like this :
print str(number)[0:10] #Note the lack of parenthesis.Nope, you don't need the "from __future__ import print_function"
If you put parenthesis around what you want to print, python 2.x treats it as a print statement with one value, and python 3.x treats it as a function call with one parameter.
I tested it, and it works without the __future__ import in python 2.4 -> 3.3 inclusive.
Also, also (sorry to keep
Also, also (sorry to keep spamming :-) are you using a recent version of scala? When I type "Int" into my interpreter, I get:
scala> Int
res0: Int.type = object scala.Int
No worries about the spam. I
No worries about the spam. I believe I was using 2.8.2 in Fedora 16. I'm glad that they fixed that bug! Thank you for sharing.
And what is wrong with:
And what is wrong with:
In general, scala does some really clever stuff, but if you try to write it like java, you will miss all of the interesting bits.
Thank you for answering my
Thank you for answering my question about how to reduce my code. I knew there was a way to do it, but I couldn't figure it out with the space syntax. I was trying to do things like this:
x sum toString take 10and that wasn't working I was getting this error:
<console>:10: error: type mismatch;
found : java.lang.String
required: Numeric[?]
^
Am I trying to use the space notation in a way that was not inteded?
Parsing is done before
Parsing is done before typing, so
(x sum toString)must be parsed in exactly the same way as(x take 10)or(2 + 2).That means
x.sum(toString). If you wantx.sum.toStringyou need to say so.Thank you for the
Thank you for the explanation. I guess I thinking more like Haskell and less like Scala then. I will remember this in for the future.
Your scala code is slower
Your scala code is slower because you are doing a bunch more work! You are creating a list of Strings, and then mapping a function over that list to make a list of BigInts. That mapping isn't free.
If you want to have the _same_ code in all three languages, then the list creation would look like:
I think Scala has such bad
I think Scala has such bad times because you're including JVM startup time, which is notoriously long.
Scala should beat Python by tons after warming up the JVM.
Hi Lucian, thank you for the
Hi Lucian, thank you for the comment. I completely agree, Java generally does execute faster than Python and that even includes the start up time. That is why the results were so shocking. As Andrew talked about above, my process could be optimized a bit. I'm not sure how much it would help, but I'm willing to spend the time modifing the code to expirement.
But can you do it faster?
Can you do it without using big ints? It is possible to do it without calculating the whole sum but just calculating the first 100 digits!
What if the numbers were 100,000 digits long?
Project Euler is about algorithms, not just code. If your solution doesn't scale, you're likely to have to find one that does for some other, later problem. The prime number problems show this the best; see
http://stackoverflow.com/questions/6789649/how-can-i-get-this-python-code-to-run-more-quickly-project-euler-problem-7
and my answer to it for an example.
Since you know how many digits you need in the output and you know how many numbers you are adding, you can calculate how many digits you need to consider in the input to get the output digits.
Look at the case of adding two four digit numbers, where you need two digits to be correct. Assume the numbers are of the same magnitude (as in the test data) or left-padded with zeros.
If you consider two digits of each input number, then at worst case you're ignoring a 99 at the end of each number. 99 * 2 = 198, so your second digit could be wrong because of a carried digit you're ignoring.
If you consider three digits of each input number, then at worst case you're ignoring a 9 at the end of each number. 9 * 2 = 18, so the second digit of your answer can't be affected by the ignored digit -- only the third digit of your answer could be affected, and you only need two digits.
So for 2-10 numbers, one digit more than the output length is sufficient (since any number * 10 will carry over only one digit).
For 11-100 numbers, two digits more than the output length are sufficient (since any number * 100 will carry over only two digits).
The algorithm for determining how many extra digits you need should be clear. In Python, it can be written as:
int(math.ceil(math.log10(number_of_input_numbers)))If you rewrite your code to use that algorithm -- and maybe load the numbers from an external file for the sake of your post length :) -- it will be a much more interesting problem.
Agf, Thank you for sharing
Agf,
Thank you for sharing with me the "inner" thoughs of project euler. I've always thought it more as coding exercises than algorithm excersices. Sadly algo's has never been my strongest suit. Are there materials that I could read, preferably in book form, that would help me understand more of these "math" algorithms? I ask because I would never have guessed that I could reduce the size of each number to speed up computation; like you explained above.