Pi

Some time ago, a hiring post went viral on proggit. This was a very clever way to filter resumes and I’d definitely consider doing something similar. The various pieces required to implement this can be cobbled to together by searching and you don’t have to be a math genius to write this program. More interesting to me then solving it, is how you frame the problem and craft an elegant solution. I decided to take a crack in Scala.

  • Digits of Pi - we don’t know how many we’ll need so whatever algorithm we choose should allow us to consume the digits lazily.  I chose Iterator to implement this since it doesn’t memoize and is lazy
  • A primality test
  • A palindrome test (easy. reverse a number and check for equality)
def pi : Iterator[BigInt]
def isPrime(n: Seq[BitInt]) : Boolean
def isPalindrome(n: Seq[BigInt]) = n == n.reverse
def solution = pi.sliding(7).find(n => isPalindrome(n) && isPrime(n))

Framing the problem this way makes that final line read like English. All I needed was a way to generate digits of Pi and test for primality. Any decent software engineer is a master plagiarist so finding these bits and pieces was not hard. I took a java algorithm for calculating digits of pi I found on stack overflow, tested it, and re-factored it into a pure functional style. It returns a Scala iterator so I the digits can be lazily-consumed.

Basic primality tests are pretty simple. The simplest ones just look for a divisor that’s an odd number less than the square root of the number being tested. There are algorithmic-ally better algorithms than the one I found, but there’s a lot going on in this one line:

val primes : Stream[BigInt] = BigInt(2) #:: Stream.from(3).map(BigInt.apply).filter(i => primes.takeWhile(j => j * j <= i).forall(k => i % k > 0))

The val above is a lazy stream of all primes numbers, defined in terms of itself. This works, because the next prime in the list is only defined in terms of the primes before it that are less than or equal to it’s square root! It is very efficient since Stream memoizes all the primes it’s found to date and new primes are only searched for using existing primes as test divisors. Whoever wrote this is a functional programming god. If see this post, send me your name so I can credit you.

Pretty happy with the end result. It’s factored in such a way that it’s easy to change the program to look for all kinds of occurrences in transcendental numbers.  I think the most interesting thing about this exercise is writing the digits of Pi as an Iterator. This allows you to take advantage of Scala’s amazing combinators like sliding and find.