I'm a software developer. I'm passionate, I like what I'm doing and I try to do it better every day. I like open technologies because that's where I'm coming from. Currently working as a freelancer on J2EE applications. Particularly interested in Scala, Liftweb and Functional Programming. Andrew has posted 14 posts at DZone. You can read more from them at their website. View Full User Profile

The power of three lines of scala

10.13.2011
| 5434 views |
  • submit to reddit

I was looking at this problem on project Euler.net and I was amazed it only take 3 lines of scala code (with one being the number itself)!

val bigNum = "73167176531......"
def product(digits: String) = { digits.map(java.lang.String.valueOf(_).toInt).reduceLeft( (prod, c) => prod*c)}
println(bigNum.sliding(5).toSeq.map(s=>product(s)).max)

 

That's it!
Ok let me try to explain what that code does..
First row is the string copied from the website, so far...so good right
Second row is a definition of a function product that takes a String of digits and returns an Int.
The return type is inferred, the compiler will figure out it is an Int

Let's see what each method call does and where are those methods!

digits.map(java.lang.String.valueOf(_).toInt)

map is a function defined in StringOps and there is an implicit convertion between String and StringOps.

It takes every char in the String and applies the provided function. In our case the function is transforming the char to a number.
java.lang.String.valueOf(_).toInt
is just a short for
c => java.lang.String.valueOf(c).toInt
The result of this first function is a Seq of Int. Then applying the reduceLeft function we calculate the product of those digits.
reduceLeft will take two elements at a time and apply the provided binary function and then moves right and applies the same function again till the last element is reached.
our function is simply multiplying elements.

Cool so we know how to multiply elements.

Now what we need to do is go through the string taking a block of 5 digits at a time, multiply them and calculate the maximum.
That is exactly what the last line is doing. The sliding function in StringOps is taking a block of 5 elements (chars in our case) and returning an iterator over them.
The toSeq method creates a sequence out of the passed iterator.

At this stage we have something like Seq["73167","31671","16717"..]

All we need to do is map this elements to their product using our product function and then calculate the maximum so the last two functions couldn't be more expressive!


This is probably not the best way to solve this problem, if you want to post yours you're welcome!

From http://www.devinprogress.info/2011/10/power-of-three-lines-of-scala.html

Published at DZone with permission of its author, Andrew Salvadore.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Der Meister replied on Fri, 2011/10/14 - 1:58am

One line less and shorter in Groovy:

def bigNum = "73167176531......"
println ((0..bigNum.size()-5).collect { bigNum.substring(it,it+5).toList().inject(1) { p,n -> p*n.toInteger() } }.max { it })

So I suppose there is a better way in Scala too ;-) 

Erwin Mueller replied on Fri, 2011/10/14 - 2:49am

But can you go back to the code in 2 or 4 months and still understand it?

There was someone and say, if the developer gets clever, fire him and get a developer who will do it the stupid way. Because nobody will ever touch the clever code and fix bugs or improve it, or worse, even the developer who had the bright idea to be clever will forget what the code does after half a year.

I better write tripple the code in Java then some smart three-lines of code. So I can go back to the code after 6 months and understand perfectly what I did.

André Pankraz replied on Fri, 2011/10/14 - 3:01am

Yes - I would say if you write 3 lines of code and write a one page blog post to explain what it does than you sum up the concerns of some people with Scala quite remarkable ;)

Just kidding...I think if you are used to this you can read it just like Java - but the majority of Joe-the-developer only know this classic C-style stuff - and there you get the problem.

Endre Varga replied on Fri, 2011/10/14 - 3:23am in response to: Erwin Mueller

It took me no more than 15 seconds to understand (I haven't even read the description of the problem it solves), and it is not a code bit written by myself. Once you get comfortable with Scala, this stuff looks very basic. 

Kai Wähner replied on Fri, 2011/10/14 - 5:51am

My Scala skills lie anywhere in between novice and medium. I understand the code, but it takes some time.

I am no fan of "you can do THIS in only X lines with THAT language". I prefer using one or two additional lines. It is much easier to read, also for good developers IMO.

 

Best regards,

Kai Wähner (Twitter: @KaiWaehner)

Bob Jones replied on Fri, 2011/10/14 - 11:13am in response to: Der Meister

+1 for Groovyness! :) Now try to use Gpars to make it really fly ;)

Bob Jones replied on Fri, 2011/10/14 - 12:03pm in response to: Bob Jones

Hm, I could only get a performance boost from Gpars when the problem was looped over many times.

http://groovyconsole.appspot.com/script/576001

Václav Pech replied on Sun, 2011/10/16 - 3:38am in response to: Bob Jones

That's most likely since you include the thread pool creation constant overhead (the withPool() method call) in he measured time.

Second, multiple iterations may allow JIT to optimize the code and so eliminate some of the other overhead associated with parallelizing the collection processing.

 

sun east replied on Sun, 2011/10/16 - 5:10am

scala> val num = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
num: String = 731671765313306249192251196744265747423553491949349698352031277450632623957831801698480186947885184385861560789112949495459501737958331952853208805511125406987471585238630507156932909632952274430435576689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749303589072962904915604407723907138105158593079608667017242712188399879790879227492190169972088809377665727333001053367881220235421809751254540594752243525849077116705560136048395864467063244157221553975369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474821663704844031998900088952434506585412275886668811642717147992444292823086346567481391912316282458617866458359124566529476545682848912883142607690042242190226710556263211111093705442...

scala> num.map{_.asDigit}.sliding(5).map{_.product}.max
res2: Int = 40824

Nicholas Sterling replied on Sun, 2012/11/11 - 5:46am

I enjoyed this post -- and particularly the comments about Groovy and firing clever software developers -- so much that I just had to blog about it.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.