This week's giveaway is in the Android forum. We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line! See this thread for details.

I've done the first 50 or so of the problems at Project Euler in Java, but thought I'd have a go at the same problems in Scala, for practice. I am a novice, but it would be fun if other people would like to join in and post their solutions, and/or suggestions for improving other peoples'. There must be a ton of different ways to solve these. Below are the first three. Later problems will be trickier.

Let the games begin!

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.

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.

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Cool, I didn't know about the sum method, and the anonymous function is more concise. When you were trying out functional style, how did you know if you were doing it right? I'm trying to do the same. I've read a little bit about functional programming and the things that have stuck are:
- use recursion or folds instead of loops
- use tail recursion where possible
- don't use objects / state in your functions, so that a function with the same arguments always yields the same results

Here are the next 3 if anyone wants to take a stab:

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.

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

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

Problem 6

The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Problem 5 was kind of interesting. I'm aware that there are much better ways to do this than brute force (you can do it in a couple of minutes with pen and paper), but found that using "for" or "forall" can make your code run literally 50 times slower (see Stack Overflow topic). Hence 2 versions : the first is more elegant but takes 40 seconds, and the second takes less than 1 second (which seems quite fast given it needs to loop over 100 million times).

Problem 6 wouldn't compile without a semicolon at the end of line 4.

OK, I'll chime in. I won't do number 10 since it's trivial if you use your Sieve function, but I will post my version of the sieve. I use the same algorithm as Luigi, but it's a few lines shorter.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Good stuff. That's pretty helpful and I've learnt a few things, because I couldn't think what a more idomatic / functional way to code the sieve algorithm would be, so had to cheat an use while loops. I'm still just picking up the language so I don't know about most of the methods available. It's not helped by these implicit defs on Arrays, which make it hard to find legal methods in the documentation.

Problem 10 is almost trivial, except for the fact you can't use the sum function on the list, becuase it overflows the max value of Int. So I had to do Anyone know a better way of summing a list of Ints to get a Long?

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296

posted

0

We're getting into spoiler alert territory here. My solution would have been nice if I could have come up with a nicer algorithm for my transposeDiagonal function. But quick & dirty:

My solution is pretty dirty as well, coded late at night when I didn't feel like thinking too much (so it could be shortened substantially, probabaly at the expense of legibility).

Gotta say, that map(_.toInt) thing is pretty handy, compared to Java.

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

^I did it the naive way first, but it took too long, so checked my Java solution and realised that that you only need to check factors up to the square root of the number and double it for reciprocals.
^easy one-liner. Learnt how to read a file and BigInt from String idiomAgain, pretty easy in Scala, the only complication being that the required answer was the start value, rather than the max number of steps. Don't know if reducing a list of tuples is really the way to go, but it seemed natural.

The number of paths to any point is just the sum of those above and to the left. So if you consider the number of routes to points on the grid in diagonalrows starting at the top left, you have
1
1 1
1 2 1
1 3 3 1
etc which happens to be Pascal's Triangle. Since each grid point only depends on routes from above and left, for a square we can ignore the fact that it is not an infinite grid.

Alternatively if you know about Pascal's Triangle, you can use the combination function to find out the value of the 20th element of row 40.

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

Problem 17

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Nice solution Stefan. Here are my comments if you're interested.

In your regex, if you put a "+" after your bracket expression, i.e. "[\n\t ]+", this will match 1 or more instances, so you don't need the trim or filter for length > 0. I thought you had to double-escape control characters but it looks like you don't have to with \n or \r or \t (but you do with \s).

You can probably see from the other solutions that map (_.toInt) can be used instead of the Java Integer.parseInt function.

It's normal in Scala code to make your indents 2 spaces, because you get more nesting with closures, and chaining functions means that lines tend to be longer. 8 is certainly overkill.

If you use curly braces instead of parentheses in your for-statement, you don't need the semicolons.

I was a bit confused by your maxProduct method because "max" is a function defined in List, until I realised it was a variable. From what I've read, it's better to avoid using vars, unless you have a good reason. Instead of updating a variable, you can put things in Lists, and use a "max" function. The "yield" keyword in a for-statements gives you a List of results. So you can change your methods to:

Luigi Plinge wrote:Nice solution Stefan. Here are my comments if you're interested.

Yes, thanks for your feedback.

I have to excuse myself by stating, that I solved Euler011 in Feb.2009, and I don't know, which methods where present then, and what was introduced later. Afaik, 'max' wasn't available then.

In your regex, if you put a "+" after your bracket expression, i.e. "[\n\t ]+", this will match 1 or more instances, so you don't need the trim or filter for length > 0. I thought you had to double-escape control characters but it looks like you don't have to with \n or \r or \t (but you do with \s).

Well - Sting.split and [...]+ is from Java, and old enough. That simplifies much, while it isn't measurable for such a small grid. The method returns immediately on my old 2Ghz Laptop. And _.toInt is too more elegant.

It's normal in Scala code to make your indents 2 spaces, because you get more nesting with closures, and chaining functions means that lines tend to be longer. 8 is certainly overkill.

Yes, I've given up my resistance to two-blank indent, and code to the Scala standards, when coding Scala now, but either I use 2 or 8 - nothing in between.
The problem with tabs is, that the REPL tries to autocomplete, if it finds a tab, so tabs aren't usable there. But I never got problems with 8-pos indentation either.

If you use curly braces instead of parentheses in your for-statement, you don't need the semicolons.

Yes. On the other hand - is there a problem with semicolons? They're more easy to type on a german keyboard than curly braces.

I was a bit confused by your maxProduct method because "max" is a function defined in List, until I realised it was a variable. From what I've read, it's better to avoid using vars, unless you have a good reason.

Well - I have a good reason, I want to find the max, and there is no problem, until you find one. Of course, the max-call you use is more elegant, but I think it wasn't available 2009, but a roll-your-own function to use in a fold would have been possible over then too.

Yes. On the other hand - is there a problem with semicolons? They're more easy to type on a german keyboard than curly braces.

If you use parentheses you need 6 extra semicolons, whereas replacing them with curly braces is no extra characters. Usually when people use parentheses + semicolons it for saving space by putting everything on one line (and maybe to make it look a bit more like a Java for-loop).

On a bit of a tangent,

Well - I have a good reason, I want to find the max, and there is no problem, until you find one. Of course, the max-call you use is more elegant, but I think it wasn't available 2009, but a roll-your-own function to use in a fold would have been possible over then too.

That would work if you know you have at least 1 positive value; you could use Int.MinValue instead of 0, but better would be or equivalently For Int lists as in the case above, this could be simplified to This "max" method is the one on Int that has been around forever (I assume...), rather the one on lists that we're trying to emulate.

On even more of a tangent, I've done some research and found you can make a general version of this for anything that can be ordered (i.e. has the Ordered trait) using the Pimp My Library pattern: (Here <% is a view bound which translates into English as "can be seen as". Int is not an Ordered, but can be seen as a RichInt, which has the Ordered[Int] trait.)