Skip to content

Instantly share code, notes, and snippets.

@jadamcrain jadamcrain/gist:5374293
Last active Dec 16, 2015

Embed
What would you like to do?
Functional solution in Scala to: http://www.scoopshot.com/hiring-developer Hopeless plagiarism of multiple sources
/**
* Functional solution in Scala to:
* http://www.scoopshot.com/hiring-developer/
*
* Hopeless plagiarism of multiple sources
*/
object PiFinder extends App {
def isPalindrome(digits: Seq[BigInt]): Boolean = digits == digits.reverse
case class State(sum: BigInt, mult: BigInt)
def fromDigits(digits: Seq[BigInt]): BigInt =
digits.reverse.foldLeft(State(BigInt(0),BigInt(1)))((s, d) => State(s.sum + d*s.mult, 10*s.mult)).sum
def solution = PiSpigot.digits.sliding(7).find(d => isPalindrome(d) && Primality.isPrime(fromDigits(d)))
// Some simple test cases
assert(PiSpigot.digits.take(6).toList == List(3,1,4,1,5,9).map(BigInt.apply))
assert(Primality.primes.take(8).toList == List(2,3,5,7,11,13,17,19))
assert(fromDigits(Stream(2,3,5,7).map(BigInt.apply)) == BigInt(2357))
println(solution)
}
object Primality {
// memoize primes into a lazy-ily generated infinite stream
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))
// try to find a prime divisor that is < sqrt(number)
def isPrime(i: BigInt) : Boolean = primes.takeWhile(p => p*p <= i).find(i % _ == 0).isEmpty
}
/**
* Spigot algorithm for streaming digits of pi
*/
object PiSpigot extends App {
private def initialState = State(1,0,1,1,3,3)
private case class Converged(digit: BigInt, s: State)
private case class State(q: BigInt, r: BigInt, t: BigInt, k: BigInt, m: BigInt, x: BigInt) {
@tailrec
private def nextState(state: State): (BigInt, State) = state.next match {
case Right(Converged(digit, s2)) => (digit, s2)
case Left(s2) => nextState(s2)
}
def nextDigit: (BigInt, State) = nextState(this)
private def next : Either[State, Converged] = {
if(4 * q + r - t < m * t) {
val q1 = 10 * q
val r1 = 10 * ( r - m * t )
val t1 = t
val k1 = k
val m1 = ( 10 * ( 3 * q + r ) ) / t - 10 * m
val x1 = x
Right(Converged(m, State(q1, r1, t1, k1, m1, x1)))
}
else {
val q1 = q*k
val r1 = ( 2 * q + r ) * x
val t1 = t * x
val k1 = k + 1
val m1 = ( q * ( 7 * k + 2 ) + r * x ) / ( t * x )
val x1 = x + 2
Left(State(q1, r1, t1, k1, m1, x1))
}
}
}
def digits : Iterator[BigInt] = new Iterator[BigInt] {
var currentState = initialState
def hasNext = true
def next: BigInt = {
val (digit, s2) = currentState.nextDigit
currentState = s2
digit
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.