Project Euler with Groovy

Urbansky's Euler banner

Project Euler with Groovy (11-20) ->

Problem 1

Add all the natural numbers below one thousand that are multiples of 3 or 5.

(1..<1000).findAll({ it % 3 == 0 || it % 5 == 0 }).sum()
&#91;/groovy&#93;

<p class="conclusion">Working with Ranges and Collections in Groovy is groovy!</p>

<h2>Problem 2</h2>
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.


fib = [1, 2]
  while (fib.last()   fib << fib&#91;-1&#93; + fib&#91;-2&#93;
}
fib&#91;0..-2&#93;.sum { it % 2 == 0 ? it : 0 }
&#91;/groovy&#93;

<p class="conclusion">Have you seen the subscript operator (fib[-1] for the last element und fib[-2] for the second last)!</p>

<h2>Problem 3</h2>
What is the largest prime factor of the number 600851475143 ?


List primes = [2, 3]

def factor = { value ->
  if (value in primes) return [value]
  for (long i = 2; i < value; i++) {
    if (value % i == 0)  return &#91;i, (value / i) as long&#93;
  }
  primes << value   &#91;value&#93; } def primeFactors = { factors ->
  while ( factors.find { factor(it).size() > 1 } ) {
    factors = factors.collect({ factor it }).flatten()
  }
  factors
}

primeFactors([600851475143]).max()

And a simple solution from the forum:

long testPrime = 600851475143
long divisor = 2

while(testPrime > 1) {
  if (testPrime % divisor == 0) {
    testPrime = (testPrime / divisor) as long;
  } else {
    divisor++;
  }
}

divisor
I’m probably more of a programmer than a mathematician.
And I have seen that the Ranges in Groovy only useful for Integers. See this:

(0..600851475143).last()
// throws
// java.lang.IndexOutOfBoundsException:
//    Index: -443946297 should not be negative

Problem 4

Find the largest palindrome made from the product of two 3-digit numbers.

palindroms = []

(100..999).each { x ->
  (100..999).each { y ->
    cand = x * y
    candList = (cand as String) as List
    if (candList == candList.reverse()) palindroms << cand
  }
}

palindroms.max()
&#91;/groovy&#93;

<p class="conclusion">Have you seen the palindrome test?</p>

<h2>Problem 5</h2>
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?


divider = (2..19)
int cand = 20
while (divider.find({ divider -> cand % divider != 0 })) { cand += 20 }
println cand

Problem 6

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

(1..100).sum()**2 - (1..100).inject(0) { a, v -> a + v**2 }

Hey it’s an One-Liner!!!

Problem 7

What is the 10 001st prime number?

N = 120000 // determined by some tries
candidates = [0] * (N-2)
for (long i = 2; i < N; i++) {
  if (candidates&#91;i as int&#93; == 0) {
    for (long j = i*i; j < N; j += i) {
      candidates&#91;j as int&#93; = 1
    }
  }
}
primes = &#91;&#93;
candidates.eachWithIndex { v, i -> if (v == 0 && i > 1) primes << i }
println primes&#91;10001 - 1&#93;
&#91;/groovy&#93;

It calculates all primes within a range (Algorithm from Wikipedia: <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a>) and then it takes the 10 001st one.
<p class="conclusion">Collections in Java and Groovy don't like Long as index. And have you seen the nice multiply in Line 2 for array initialisation?</p>

<h2>Problem 8</h2>
Find the greatest product of five consecutive digits in the 1000-digit number.


number = """
--the 100 digit as multiline string--
"""
numberList = (number as List).findAll { it in ('0'..'9') }
product = 0
(0..995).each { i -> 
  p = numberList[i..i+4].inject(1) { acc, val -> acc * (val as int) }
  product = p > product ? p : product
}
println product

Creation of a sublist with Ranges is easy (numberList[i..i+4]).

Problem 9

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

(0..1000).findResult { i1 ->
  (i1..1000).findResult { i2 ->
    i3 = 1000 - i2 - i1
    if (i3 > i2 && i1 + i2 + i3 == 1000 && i1**2 + i2**2 == i3**2) i1*i2*i3
  }
}

FindResult iterates the Ranges and stops if a non-null result is returned.

Problem 10

Find the sum of all the primes below two million.

N = 2000000

candidates = [0] * (N-2)

for (long i = 2; i < N; i++) {
  if (candidates&#91;i as int&#93; == 0) {
    for (long j = i*i; j < N; j += i) {
      candidates&#91;j as int&#93; = 1
    }
  }
}

primes = &#91;&#93;
candidates.eachWithIndex { v, idx -> if (!v) primes << idx }

primes.inject(-1 as long) { acc, val -> acc + val}

The solution uses the Sieve of Eratosthenes from Problem 7. The execution time is under 1 minute.

Project Euler with Groovy (11-20) ->

One thought on “Project Euler with Groovy

  1. Pingback: Projekt Euler in Groovy | WebApp-Blogger

Comments are closed.