2008-10-20

Proyecto Euler - Primeros 4 problemas resueltos en Ruby

Mirando el blog de xkcd encontré un site donde postean un montón de problemas "matematicosos" para ser resueltos mediante programas de computadora que se llama proyecto Euler. Así que me copé, me puse a resolverlos e hice los primeros 4.
El primero es calcular la suma de los múltiplos de 3 o 5 menores a 1000, que lo saqué con un one-liner en ruby:


irb(main):006:0> (1...1000).select {|x| x % 3 == 0 || x % 5 == 0}.inject(0) {|sum,num| sum + num }
=> 233168

El segundo es calcular la suma de los números de fibonacci pares menores a 4000000. Este también lo hice en el irb, pero quizás debería haberlo escrito en un archivo. Lo que escribí en el irb es:

irb(main):007:0> class Fib
irb(main):008:1> def initialize()
irb(main):009:2> @a = 0
irb(main):010:2> @b = 1
irb(main):011:2> end
irb(main):012:1> def next()
irb(main):013:2> @a, @b = @b, @a+@b
irb(main):014:2> @b
irb(main):015:2> end
irb(main):016:1> end
irb(main):027:0> sum = 0
=> 0
irb(main):028:0> f = Fib.new
=> #
irb(main):029:0> while (n = f.next) <= 4000000 irb(main):030:1> sum += n if n% 2 == 0
irb(main):031:1> end
=> nil
irb(main):032:0> sum
=> 4613732

O sea, la suma me dio 4613732, espero no haberme equivocado.
El tercer problema es encontrar el factor primo más grande de un número gigante (n=600851475143) . En este ya me puse a escribirlo en un archivo, porque me llevó más de 2 minutos. Lo que hice fue programar una criba para generar los números primos e ir dividiendo el n por los primos hasta que quede 1. Entonces el último primo por el que dividí es el factor primo más grande. El código en Ruby es así:

class OddPrimes
def initialize
@current = 1
@primes = []
end
def next
while not prime?(@current += 2)
end
@primes << @current
@current
end
def prime?(n)
i = 0
p = 1
while true
break if i >= @primes.length
p = @primes[i]
break if p * p > n
break if n % p == 0
i += 1
end
return i >= @primes.length || p * p > n
end
end

n = 600851475143
max_p = 1
op = OddPrimes.new
while n>1
max_p = op.next
while n % max_p == 0
n /= max_p
end
end

puts max_p

Según mi código, el factor primo más grande es el 6857.
Y, por último porque me tengo que ir a dormir, resolví el cuarto problema. El mismo consiste en calcular el número "capicúa" más grande que resulta de multiplicar 2 números de hasta 3 dígitos. El código es medio bestia, y fue la primera vez que el resultado no se sintió "instantáneo" (tardó como 2 segundos). Pero calculó el resultado. La idea del mismo es trivial. Probar todas las posibles multiplicaciones (que son como 500000) y fijarse si el resultado es capicúa y más grande que el número más grande encontrado. El código en ruby es:

class Numeric
def digit(pos)
(self / (10 ** pos)) % 10
end
def digit_count
1 if self == 0
dc = 0
while self - (10 ** dc) > 0
dc += 1
end
dc
end
def palindromic
digit_count = self.digit_count
(0...(digit_count / 2)).each do
|pos|
return false if self.digit(pos) != self.digit(digit_count - pos - 1)
end
return true
end
end

lp = 0
f1, f2 = 0,0
(1..999).each { |x| (1..x).each { |y|
candidate = x * y
if candidate > lp and candidate.palindromic
lp = candidate
f1 = x
f2 = y
end
}}
puts "Largest Palindromic: #{lp}"
puts "Factors: #{f1}, #{f2}"

El resultado que dio es:

Largest Palindromic: 906609
Factors: 993, 913

Estoy seguro que se puede optimizar "bocha" este código.

Bueno, me voy a dormir.
Espero escribir próximamente más problemas resueltos del proyecto Euler.
Happy hacking,
Aureliano.

No hay comentarios.: