Proyecto Euler: Problemas 13 a 15

Los problemas 13 a 15 resultaron más faciles que el 12. El 13 consiste en saber los primeros 10 dígitos de una suma de 100 números re-grandes. Como ruby soporta números arbitrariamente grandes, una vez que obtuve los números lo resolví en un one-liner:

data_text = <<DATA_TEXT
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690
DATA_TEXT

puts (data_text.split("\n").map { |n| n.to_i(10) }.inject(0) { |sum,n| sum + n }).to_s[0..9]

El resultado fue (solo por curiosidad):

$ ruby euler13.rb
5537376230

Y la corrida fue casi instantánea.
El problema 14 consiste en buscar el número menor a 1000000 que genera la secuencia de Collatz más grande. La secuencia de Collatz se calcula así:

• Si n es 1, terminó
• Si n es par, es n:collatz(n/2)
• Si n es impar, es n:collatz(n*3 + 1)

Este problema se resuelve con un poco de memoization:

class PathLengthMemoizator
  def initialize
    @lengths = {1 => 0}
    @max_n = 1
  end
  attr_reader :max_n
  
  def max_length
    @lengths[max_n]
  end
  
  def calculate_length(n)
    return @lengths[n] if @lengths.include?(n)
    @lengths[n] = calculate_length( n % 2 == 0 ? n/2 : 3*n + 1 ) + 1
    @max_n = n if @lengths[n] > @lengths[@max_n]
    @lengths[n]
  end
end

plm = PathLengthMemoizator.new
(1...1000000).each do
  |n|
  plm.calculate_length(n)
end
puts "Longest path number: #{plm.max_n}"
puts "Length: #{plm.max_length}"

Y cuando lo corrí, dio este resultado:

$ time ruby euler14.rb
Longest path number: 837799
Length: 524

real    0m15.058s
user    0m13.609s
sys     0m1.284s

El problema 15 es el más interesante. En un cuadriculado de tamaño 20 * 20, yendo por las rayitas para abajo y a la derecha, ¿cuántas formas hay de ir desde la posición (0,0) hasta la (20,20)? En un principio, parecía un quilombo. Pero, calculando cuantos caminos hay desde (0,0) hasta (X,Y) me di cuenta que en las diagonales se armaba el Triángulo de pascal. Entonces, mirando fijo, me salió la fórmula general para calcular cuantos caminos hay hasta (X,Y) desde (0,0). Es (X*Y)! / (X! * Y!).
Aplicando la fórmula a la coordenada (20,20) queda 40! / (20! * 20!), que corriendo en el irb queda así:

$ irb
irb(main):001:0> class Integer
irb(main):002:1>   def fact
irb(main):003:2>     (1..self).inject(1) { |f,n| f*n }
irb(main):004:2>   end
irb(main):005:1> end
=> nil
irb(main):006:0> 40.fact / (20.fact * 20.fact)
=> 137846528820

Habiéndo resuelto el problema en forma elegantísima, me voy a dormir antes que encuentre otro.
Happy hacking,
Aureliano.

Proyecto Euler: Problema 12

Sigo enfermo con el proyecto Euler. Y ya hice el problema 12. El mismo consiste en encontrar el primer número triangular con más de 500 divisores. Un número triangular es de la forma 1 + 2 + 3 + ... + n. Y, se puede calcular rápidamente como n*(n+1)/2.
Mi primer intento de resolución (que anduvo pero fue lento) consistió en usar el generador de números primos del ejercicio 3 para calcular la cantidad de divisores del número, calculándolo directamente. Acá va el código:

class Integer
  def triangle
    (self * (self + 1)) / 2
  end
  def divisor_count
    n = self
    pg = Primes.new
    count = 1
    while n != 1
      p = pg.next
      pow = 0
      while n % p == 0
        pow += 1
        n /= p
      end
      count *= (pow + 1)
    end
    count
  end
end

class OddPrimes
  def initialize
    @current = 1
    @primes = []
  end
  attr_reader :current
  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

class Primes < OddPrimes
  def initialize
    super
    @first = true
  end
  def next
    if @first
      @first = false
      2
    else
      super
    end
  end
  def current
    odd_super = super
    odd_super == 1 ? 2 : odd_super
  end
end

n = 1
while n.triangle.divisor_count <= 500
  n += 1
end

puts "Triangle #{n} (#{n.triangle}) is the first with over 500 divisors"

Anduvo, pero la corrida tardó como 4 minutos. Este es el resultado:

$ time ruby euler12.rb
Triangle 12375 (76576500) is the first with over 500 divisors

real    4m17.556s
user    3m57.519s
sys     0m16.117s

Así que me puse a pensar como hacer para que ande más rápido. Se me ocurrieron varias cosas:

• Puedo calcular la factorización de n*(n+1)/2 sabiendo la factorización de n y n+1
• Puedo calcular la factorización de cada número una sola vez (guardando factorizaciones viejas)
• La factorización la puedo escribir recursivamente para usar las factorizaciones que ya calculé

Usando todo esto, hice una nueva implementación:

class OddPrimes
  def initialize
    @current = 1
    @primes = []
  end
  attr_reader :current
  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

class Primes < OddPrimes
  def initialize
    super
    @first = true
  end
  def next
    if @first
      @first = false
      2
    else
      super
    end
  end
  def current
    odd_super = super
    odd_super == 1 ? 2 : odd_super
  end
end

class MemoFactorizator
  def initialize
    @factored = {1 => {} }
  end
  def factorize(n, pg = Primes.new)
    return @factored[n] if @factored.include?( n )
    p = pg.current
    while n % p != 0
      p = p.next
    end
    factorization = factorize( n / p, pg ).dup
    factorization[p] = factorization.include?(p) ? factorization[p] + 1 : 1
    @factored[n] = factorization
    factorization
  end
end

n = 1
mf = MemoFactorizator.new
while true
  fact_n = mf.factorize(n)
  fact_nn = mf.factorize(n+1)
  triangle_factorization = fact_n.merge(fact_nn) { |k,old,new| old + new }
  triangle_factorization[2] -= 1
  
  divisor_count = triangle_factorization.values.inject(1) { |c,pow| c*(pow+1) }
  break if divisor_count > 500
  n += 1
end

puts "First triangle: #{n} (#{n*(n+1)/2})"
puts "Factorization: #{triangle_factorization.inspect}"
puts "Divisor count: #{divisor_count}"

La nueva implementación tardó 6 segundos en correr.

$ time ruby euler12.rb
First triangle: 12375 (76576500)
Factorization: {5=>3, 11=>1, 17=>1, 7=>1, 13=>1, 2=>2, 3=>2}
Divisor count: 576

real    0m6.690s
user    0m6.568s
sys     0m0.100s

Ahora estoy contento porque dio el mismo resultado que la vez anterior pero mucho más rápido y con código más lindo.

Happy hacking,
Aureliano.

Cumplí 0x20

El 18 cumplí años de nuevo. Parece que es cada vez más rápido.

Un poquito más del proyecto Euler

Sigo enfermo resolviendo ejercicios del proyecto euler. Hoy resolví el ejercicio 11. El mismo consiste en encontrar en una matriz de 20x20 los cuatro números consecutivos en una misma línea (que puede ser horizontal, vertical o diagonal en cualquiera de sus 2 variantes) tal que su multiplicación sea lo más grande posible.
He aquí el código fuente en ruby:

require 'matrix'

RAW_DATA = <<RAW_DATA
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
RAW_DATA
data = Matrix[*RAW_DATA.split("\n").map { |row| row.split(" ").map { |n| n.to_i(10) } }]

DIRECTIONS = [[1,0],[0,1],[1,1],[1,-1]]
best_product = -1
best_row = -1
best_col = -1
best_dir = [0,0]

DIRECTIONS.each do 
  |dir|
  (0...20).each do 
    |row|
    (0...20).each do 
      |col|
      product = (0...4).inject(1) do 
        |prod, pos|
        target_row = row + pos * dir[0]
        target_col = col + pos * dir[1]
        (0...20).include?(target_row) && (0...20).include?(target_col) ? prod * data[target_row, target_col] : 0
      end
      if product > best_product then
        best_product = product
        best_row = row
        best_col = col
        best_dir = dir
      end
    end
  end
end

puts "Product: #{best_product}"
puts "Row: #{best_row}"
puts "Col: #{best_col}"
puts "Dir: #{best_dir.inspect}"

(0...4).each do 
  |pos|
  target_row = best_row + pos * best_dir[0]
  target_col = best_col + pos * best_dir[1]
  puts "Position: #{target_row}, #{target_col}"
  puts "Value: #{data[target_row, target_col]}"
end

Y para que vean cuanto dio, esta es la salida de la corrida

Product: 70600674
Row: 12
Col: 6
Dir: [1, -1]
Position: 12, 6
Value: 89
Position: 13, 5
Value: 94
Position: 14, 4
Value: 97
Position: 15, 3
Value: 87

Me voy a dormir.
Happy hacking,
Aureliano.

Algunas verdades y mentiras infundadas del desarrollo de software

• Java es el nuevo Cobol
• Eclipse es el nuevo emacs
• Java es lento
• Ruby es lento
• C es rápido
• C++ es rápido
• PHP es una bosta
  
• Las 3 virtudes de un gran programador son la pereza, la impaciencia y la soberbia
• Haciendo test-first y refactoring se puede mantener la calidad del código
• Los sistemas en producción tienen código fuente feo
• Haciendo test-first y refactoring no se hacen sistemas que queden en producción
• Los programadores tienen pocas habilidades interpersonales
• Los programadores deben hablar con los clientes para hacer los desarrollos
• Barato, rápido, bueno: elija 2
• Programando en Rails un programador es 10 veces más productivo que programando en J2EE
• Lisp es el mejor lenguaje de programación
• Smalltalk es el mejor lenguaje de programación
• A python hay que agregarle closures y sería un lenguaje espectacular
• Los verdaderos programadores programan en Fortran
• Los verdaderos programadores programan en C++
• Los verdaderos programadores programan en Assembler
• Los verdaderos programadores programan en código máquina
• Los verdaderos programadores silvan en el teléfono para transmitir datos a un modem, hacer un buffer overflow y reprogramar el server

Happy hacking,
Aureliiano.

Proyecto Euler - Problemas 5 a 10

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.

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.

Jugando con un proxy HTTP

El proxy transparente de Telefónica está andando mal y trae versiones viejas de un montón de páginas. Así que estuve pensando la forma de forzarlo a que traiga la última versión. Lo hablé con algunos compañeros de laburo, y lo que me sugirieron es que instale un proxy que agregue headers que fuercen el no-cacheo de las páginas. En particular, sugirieron que instalara privoxy y lo configurara con los headers que quiero agregar.
Pero, ¿para que voy a hacer algo rápida y fácilmente si me puedo meter en un quilombito? El mismísimo whytheluckystiff hizo mousehole, un proxy implementado en ruby puro. Pero mousehole está pensado para transformar las páginas a medida que van bajando, no para cambiar los headers a la ida. Así que tuve que toquetear un poquito.
Por lo que pude ver, mousehole tiene 3 capas. Una primera capa es el handler de mongrel que atiende los pedidos de http, la capa del medio es una capa que maneja los plug-ins del proxy (a los que llama apps) y una tercera capa son las apps propiamente dichas. Para agregar la funcionalidad de cambiar el request tuve que tocar estas 3 capas.
En el handler, agregué un lugar para interceptar la página antes de pedir al host la página. Este es el diff del svn:

Index: lib/mouseHole/proxyhandler.rb
===================================================================
--- lib/mouseHole/proxyhandler.rb       (revision 129)
+++ lib/mouseHole/proxyhandler.rb       (working copy)
@@ -46,6 +46,8 @@
       choose_header(reqh, header)
       set_via(header)

+      uri, header = @central.change_request(uri, header)
+
       http = Net::HTTP.new(env['server-name'], env['server-port'], @central.proxy_host, @central.proxy_port)
       http.open_timeout = 10
       http.read_timeout = 20

En la capa que maneja los plugins (que en el código se llama central) hice que cuando llegue un pedido, intente reescribir los headers en cada app. Este es el diff del svn:

Index: lib/mouseHole/central.rb
===================================================================
--- lib/mouseHole/central.rb    (revision 129)
+++ lib/mouseHole/central.rb    (working copy)
@@ -95,6 +95,13 @@
       end
     end

+    def change_request(uri, header)
+      @apps.values.each do |app|
+        uri, header = app.change_request(uri, header)
+      end
+      [uri, header]
+    end
+
     def rewrite(page, resin)
       apps = find_rewrites(page)
       return false if apps.empty?

Y por último, en la clase base de las apps hice que por default deje los headers y el URI original, así es todo retrocompatible (o casi). Acá está el diff del svn:

Index: lib/mouseHole/app.rb
===================================================================
--- lib/mouseHole/app.rb        (revision 129)
+++ lib/mouseHole/app.rb        (working copy)
@@ -58,6 +58,10 @@
       end
     end

+    def change_request(uri, header)
+      [uri, header]
+    end
+
     def do_rewrite(page)
       @document = page.document
       begin

Con todo esto andando, pude hacer mi cometido, que es hacer un proxy que le agregue el header "Cache-Control: no-cache" a los requests, para que Speedy no me de versiones viejas. El código de la app que hace esto quedó resimple:

class NoCache < MouseHole::App
  title "No Cache"
  namespace "aure"
  description %{
    Forces all the request to be non cached.
    Sets the Cache-Control header to no-cache.
  }
  version "0.1"

  def change_request(uri, header)
    header << ['Cache-Control', 'no-cache']
    [uri, header]
  end
end

Gracias Speedy y Telefónica por la inspiración y happy hacking,
Aureliano.

PD: si los headers no sirven, voy a cambiar el URI agregando parámetros aleatorios y listo, así que no me provoquen.

Conferencias al cuadrado

Esta semana estuve a full. En Buenos Aires hubo 2 conferencias de seguridad informática y tuve la suerte de poder ir a las 2.

El martes y miércoles estuve en BA-Con. Ahí conocí un montón de gente interesante y tuve la suerte de que las charlas también fueron re-interesantes.
Algunas charlas que me llamaron la atención y quería comentarles son:

• En la charla "WPA/WPA2: how long is it gonna make it" Cédric Blancher y Simon Maréchal contaron una forma interesante de generar passwords para brutforcear. La idea es que armás una cadena de markov donde cada caracter es un estado y la probabilidad de pasar de un estado "a" a un estado "b" es el porcentaje de las veces que viene una "b" después de una "a" de los passwords con los que generaste la cadena.
  
• La charla "All the Crap Aircrafts Receive and Send" fue divertida. Hendrik Scholz contó cómo se enteran los aeropuertos de los tiempos de arribo de los aviones (entre otras cosas). Y cómo hizo para reversear los mensajes (incluyendo ir con un receptor de radio en el auto al aeropuerto).
  
• En "LeakedOut: the Social Networks You Get Caught In", mi amigo y compañero de trabajo José Orlicki presentó sus avances de su trabajo de doctorado, donde estudia las redes sociales que se arman en los sitios Web 2.0 y sus implicancias en seguridad. A mi me pareció que fue la charla más original de las 2 conferencias.
• En "Pass-the-hash Toolkit for Windows" mi compañero de trabajo Hernán Ochoa mostró una vez más porqué es un groso en el mundo de la seguridad informática. Esta vez contó de su proyecto "Pass-the-hash" y su implementación en Windows. El proyecto sirve para afanar tokens de autenticación de la memoria de un Windows (!) y conectarse a otros hosts. La verdad, una masa. Si quieren usarlo, pueden bajarselo de acá.

El jueves y viernes tocó Ekoparty. Y también fue re-interesante. Les cuento que charlas me llamaron más la atención:

• En "Code injection on virtual machines", mi compañero de laburo Nicolás Economou se disfrazó de Neo y mostró como escribir memoria usada por un proceso de VM-Ware desde afuera para modificar el comportamiento de un programa corriendo adentro (!).
• En "Atancando RSA mediante un nuevo métodos de factorización de enteros", Hugo Scolnik mostró el laburo que están haciendo para tratar de romper RSA. La verdad, pareció re-interesante. Transformó el problema de factorización de un número de la forma p*q en un árbol de decisiones y muchas formas de podar el árbol. Y mostró como, si se pudiera elegir correctamente en ese árbol (cosa que todavía no hacen), la factorización del RSA640 tomaría un par de minutos en una Pentium 3.
• En "Smartphones (in)security" mis compañeros de laburos Alfredo Ortega y Nicolás Economou (que ya se había sacado el traje de Neo), mostraron cómo explotar un stack overflow en iPhone y Android. Fue una charla interesante y entretenida, donde también explicaron re-bien como funciona la técnica "return to libc" para escribir exploits cuándo la memoria que podemos sobreescribir no tiene derechos de ejecución.
• Y en "Debian's OpenSSL random number generator Bug" Luciano Bello y Maximiliano Bertacchini contaron los detalles técnicos y las consecuencias de comentar una línea de código para que el valgrind no se queje. Esa línea, hacía que la entropía del generador sea tomada solamente del nro. de proceso (o sea, que si repetís el número de proceso, generás los mismos números aleatorios) y cómo usar esto para hacer ataques.

Al final, después de una semana de conferencias quedé con la cabeza que explota de conocimientos nuevos, conocí un montón de gente interesante y tengo un muchas tarjetas personales (que nunca sé que hacer con ellas).

Happy hacking,
Aureliano.

Blog de Nicolás

Cómo les había contado en un post anterior, voy a ser papá. Y hoy, junto con Agus inauguramos su propio blog. Ahí vamos a ir poniendo todas las fotos, videos y etcéteras mientras sea un proyecto o un bebé.