Sigo a full con el Proyecto Euler. Y hoy hice 6 problemas. Les cuento como los solucioné:
El problema 5 es bastante fácil. Esencialmente se trata de encontrar el mínimo común múltiplo de los números 1..20. Lo más molesto es que ni el divisor común mayor ni el mínimo común múltiplo están en mi versión de ruby (ruby 1.8.6 patchlevel 111, ubuntu hardy), así que lo implementé:
class Integer
def gcd(other)
values = [self > 0 ? self : -self, other > 0 ? other : -other]
a = values.min
b = values.max
while (a != 0)
a, b = b % a, a
end
b
end
def lcm(other)
self * other / self.gcd(other)
end
end
puts (2..20).inject(1) {|ac, n| ac.lcm(n)}
Sólo por curiosidad, el número me dio 232792560.
El problema 6 es calcular la diferencia entre la suma de los cuadrados y el cuadrado de la suma de una secuencia 1..n (con n=100). Tampoco fue muy difícil.
class Integer
def sum_square
(1..self).inject(0) { |acum,n| acum + n * n }
end
def square_sum
((self * (self+1)) / 2) ** 2
end
end
puts 100.square_sum - 100.sum_square
También por curiosidad, el resultado es 25164150.
El problema 7 es encontrar el primo número 10001. Para eso usé la criba que definí
en el post anterior e iteré hasta el primo nro 10001.Acá va el código:
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
op = OddPrimes.new
p = 2
(2..10001).each {
p = op.next
}
puts p
El primo que dio es el número 104743.
El problema 8 es medio rebuscado. Lo que me resultó más difícil es entender el enunciado. Te dan un número gigante y tenés que buscar cuáles son los 5 dígitos consecutivos que multiplicados dan el número más grande. Como en el problema 4 había implementado como obtener un dígito arbitrario y la cantidad de dígitos de un número, usé eso y resolví el asunto.
class Integer
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
end
n = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
pos = -1
prod = -1
(0..995).each do
|p|
candidate = n.digit(p) * n.digit(p+1) * n.digit(p+2) * n.digit(p+3) * n.digit(p+4)
if candidate > prod
pos = p
prod = candidate
end
end
puts "Digits: #{n.digit(pos)}, #{n.digit(pos+1)}, #{n.digit(pos+2)}, #{n.digit(pos+3)}, #{n.digit(pos+4)}"
puts "Position: #{pos}"
puts "Product: #{prod}"
El resultado que dio es:
Digits: 9, 7, 8, 9, 9
Position: 631
Product: 40824
El problema 9 consiste en buscar número a,b,c tal que son enteros a+b+c=1000 y a^2+b^2=c^2 (teorema de pitágoras para triangulos rectos). Para hacer eso, busqué una tripleta (a,b,c) tal que la suma divida a 1000 y después multipliqué cada número. La verdad es que este problema me costó un ratito. Acá va el código.
#Find a triplet that fits the pitagoras formula and its components divide 1000
def primogenial_triplet
(3..100).each do
|c|
(2...c).each do
|b|
(1...b).each do
|a|
return [a,b,c] if a ** 2 + b ** 2 == c ** 2 and 1000 % (a+b+c) == 0
end
end
end
end
tr = primogenial_triplet
factor = 1000 / (tr[0] + tr[1] + tr[2])
puts tr.map {|x| x * factor}
Los a,b y c que encontré son: 200, 375 y 425 respectivamente.
El problema 10 es el más interesante hasta ahora. El mismo consiste en sumar los números primos menores a 2000000. Primero usé el generador de primos que tenía, y lo implementé, pero tardó más de un minuto. El código es:
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
op = OddPrimes.new
sum = 2
while ( (p = op.next) < 2000000 )
sum += p
end
puts sum
Pero me quedé enojado porque tardaba mucho, así que googlié un toque y encontré
este post que mostraba otra forma de generar números primos. Y lo implementé. La idea es ir marcando todos los múltiplos (menores a un número dado) de los números primos que voy encontrando para encontrar los primos sin hacer divisiones. Y anduvo más rápido. Igualmente, hay que notar que gasta bastante más memoria que la versión anterior. Así que tiene un trade-off distinto entre memoria y tiempo de procesamiento. El código está acá:
MAX = 2000000
class OddPrimes
def initialize(max)
@max = max
@prime_matrix = [false,true] * ((max / 2) + 1)
@prime_matrix[1] = false
@current = 1
end
def next
while not prime?(@current += 2)
throw :max_reached if @current >= @max
end
mark
@current
end
def mark
i = @current
step = @current * 2
while (i<@max)
@prime_matrix[i] = false
i += step
end
end
def prime?(n)
@prime_matrix[n]
end
end
op = OddPrimes.new(MAX)
sum = 2
catch :max_reached do
while ( (p = op.next) < MAX )
sum += p
end
end
puts sum
Esta solución corrió en 6 segundos:
$ time ruby euler10.rb
142913828922
real 0m6.179s
user 0m5.780s
sys 0m0.356s
Voy a tratar de seguir resolviendo los problemas del proyecto Euler, así que sigan sintonizados.
Happy hacking,
Aureliano.
