Square the Sum

I'm teaching myself F#. It's the first time I've worked with a language of this type, it's also been a while since I spent anytime with algorithms. Maths was never really my strong point. In the past I've learnt languages through necessity but I don't usually find myself in situations where neither C# or JavaScript will do the job.

I decided to learn F# by solving mathematical puzzles. To that end I've found a number of suitable puzzles, the first of which can be found here.

The first of the problems listed at Foo Hack is called 'Square the Sum', it is this puzzle that is the subject of this post. I won't describe the problem here, for more information see the original post at Foo Hack. What I will describe are the challenges I faced while devising the solution.

As my first attempt at writing anything significant in F#, I felt like a fish out of water. I was unsure how to layer multiple steps within a single function, my head was swimming with features (I'd yet to try in C#) like anonymous methods and lambda expressions, that I knew had there roots in languages like F#. The mist cleared when I understood that all functions in F# are essentially single parameter functions. Functions that appear to have multiple parameters are actually curried, each parameter is parsed by a function generated by the function that parsed the previous parameter. I hope that makes sense, it took me a little while to get my head around it. The concept is best explained at Inside F#.

With this point explained, the idea of layering multiple functions on top of each other is easier to swallow. I believe the pipeline operator can be used to do something similar, but I've not touched on that yet. I now have a function called sqSum that performs all the steps required to split x in half, add those halves together and square the total. Now I need to iterate through a range of integers and identify those that match the criteria as laid out in the original problem. This functionality was provided in the form of List.filter. List is part of the FSharp.Collections namespace, the filter function allows you create a collection based on the condition set in your anonymous function, in this case when the result of sqSum equals the original figure.

My last hurdle was the dynamic typing performed by F#. In C# I'm used to strongly typing everything, in JavaScript I'm used checking whenever possible. After a few implicit conversion errors I soon remembered when to decimalise and explicitly type.

My solution is below:

let sqSum x : float =
 let top = round (x / 1000.00)
 let bot = x - (top * 1000.00)
 let tot = top + bot
 tot * tot

let lst = List.filter (fun x -> float x = sqSum (float x)) [100000 .. 999999]

Which returns:

[494209; 998001]

I'm sure there are a myriad of ways in which you can come to this solution, what I'd be interested in is some insight into the efficiency of my solution and how it might bettered. This is a learning exercise after all.