February 19th, 2010

Project Euler Code

My 2010 New Year's resolution is to solve the first 50 problems on Project Euler. I chose to code in Scala for a few reasons: (1) Its functional abilities should lend itself to concise code; (2) It's fast, portable, and easy to execute; and (3) I wanted to build familiarity with a new language. I'm not necessarily going in any specific order, but it makes sense to start with the easy ones first.

Problem One

Add all the natural numbers below one thousand that are multiples of 3 or 5. 
0 until 1000 filter(i => {
  (i % 3 == 0) || (i % 5 == 0)
}) reduceLeft { _ + _ }
Reveal code

Problem Two

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million. 
def fib_list(upto:Int) : List[Int] = {
  var l = List(0) 
  var a = 0
  var b = 1
  var c = 0

  for(i <- (0 until upto)) {
    c = a + b
    a = b
    b = c

    l = l ++ List(c)
  }
  l
}

fib_list(32).filter { _ % 2 == 0 } reduceLeft { _ + _ }
Reveal code

Problem Three

Find the largest prime factor of a composite number. 
var biggy = BigInt("600851475143")

// would use Math.sqrt, but not avail for BigInt
def cap_search = { biggy / 2 }

def find_next_factor(i:BigInt) : Option[BigInt] = {
  if(i > cap_search) None
  else if(biggy % i == 0) Some(i)
  else find_next_factor(i + 2)  
}

def find_biggest_factor(i:BigInt) : BigInt = {
  find_next_factor(i+2) match {
    case None => biggy
    case Some(x) => {
      biggy /= x
      find_biggest_factor(x)
    }
  }
}

// beginning the search with 3 because
// 1 is a trivial factor and 2 is trivially not
println(find_biggest_factor(3))
Reveal code

Problem Four

Find the largest palindrome made from the product of two 3-digit numbers. 
def is_palindrome(x:Int) = {
  // reverse won't return a RichString in scala 2.8 :-)
  x.toString.reverse.toString == x.toString
}

var biggest = 0

for(a <- (100 to 999)) {
  for(b <- (a to 999)) {
    val prod = a * b
    if(is_palindrome(prod))
      biggest = Math.max(biggest, prod)
  }
}

println(biggest)
Reveal code

Problem Five

What is the smallest number divisible by each of the numbers 1 to 20? 
var guess:BigInt = 380
var continue = true

def div_by_all(guess:BigInt, r: Range) = r map { guess % _ == 0 } reduceLeft { _ && _ }

while(continue) {
  if(div_by_all(guess, 1 to 20))
    continue = false
  else
    guess += 380
}

println(guess)
Reveal code

Problem Six

What is the difference between the sum of the squares and the square of the sums? 
def sq_of_sum(n: Int) { (n*n*n*n + 2*n*n*n + n*n) / 4 }
def sum_of_sq(n: Int) { (0 to n) map { i => i*i } reduceLeft { _+_ } }
println(sq_of_sum(100) - sum_of_sq(100))
Reveal code

Problem Eight

Discover the largest product of five consecutive digits in the 1000-digit number. 
val str =  """73167176531330624919225119674426574742355349194934
              96983520312774506326239578318016984801869478851843
              85861560789112949495459501737958331952853208805511
              12540698747158523863050715693290963295227443043557
              66896648950445244523161731856403098711121722383113
              62229893423380308135336276614282806444486645238749
              30358907296290491560440772390713810515859307960866
              70172427121883998797908792274921901699720888093776
              65727333001053367881220235421809751254540594752243
              52584907711670556013604839586446706324415722155397
              53697817977846174064955149290862569321978468622482
              83972241375657056057490261407972968652414535100474
              82166370484403199890008895243450658541227588666881
              16427171479924442928230863465674813919123162824586
              17866458359124566529476545682848912883142607690042
              24219022671055626321111109370544217506941658960408
              07198403850962455444362981230987879927244284909188
              84580156166097919133875499200524063689912560717606
              05886116467109405077541002256983155200055935729725
              71636269561882670428252483600823257530420752963450""".replaceAll("\\s","")

def five_at_a_time(s:String)(block: String => Unit) = {
  for(i <- (0 to str.length - 5))
    block(str.substring(i, i + 5))
}

var biggest = 0

five_at_a_time(str) { substr =>
  val prod = substr.toList.map[Int](x => x.toString.toInt).reduceLeft { _ * _ }
  biggest = Math.max(biggest, prod)
}

println(biggest)
Reveal code

Problem Fourteen

Find the longest sequence using a starting number under one million. 
val tops = 1000000
val start = 500000
var biggest = 0

for(i <- start to tops) {

  var last:BigInt = i
  var len = 1

  while(last != 1) {
    last =  if(last % 2 == 0) last / 2 else last*3 + 1
    len += 1
  }

  if(len > biggest) {
    biggest = len
    println(i + " results in length " + len)
  }

  len = 0

}
Reveal code

Problem Sixteen

What is the sum of the digits of the number 2^1000? 
var two_exp_k:BigInt = 2
for(i <- 1 until 1000) { two_exp_k = two_exp_k * 2 }
val digit_chars = two_exp_k.toString.toCharArray
val digit_ints = digit_chars.map { _.toString.toInt }
println(digit_ints.reduceLeft{_+_})
Reveal code

Problem Twenty

Find the sum of digits in 100! 
def factorial(n: BigInt): BigInt = { if (n == 0) 1 else n * factorial(n-1) }
val digit_chars = factorial(100).toString.toCharArray
val digit_ints = digit_chars.map { _.toString.toInt }
println(digit_ints.reduceLeft{_+_})
Reveal code