Mirando android

Hoy estuve mirando un toque como hacer una aplicación en Android. Después de hacer el HelloWorld correspondiente, seguir parte del tutorial sobre como hacer una aplicación que sirva para guardar notas y leer bastante de la documentación, hice correr el Lunar Lander. El Lunar Lander es un port del archi-conocido juego al android.
Pensé que iba a salir de toque, pero no :(. Así que puse manos a la obra, toque las 2 tonteras que tenía mal y lo hice andar. Para que no tengan que hacer lo mismo que yo, les dejo mi proyecto de eclipse armado. Es igual al de los ejemplos de Google salvo porque como package uso aure en vez de com.android.examples.
Acá está el tar.gz.
Happy hacking,
Aureliano.

Proyecto Euler: Problemas 19 a 21

Sigo avanzando con los ejercicios del proyecto Euler. Les cuento los siguientes 3 ejercicios.
EL ejercicio 19 consiste en contar la cantidad de domingos del siglo 20. Primero pensé en hacer un montón de aritmética modular para resolver esto, pero después se me ocurrió una idea mejor. Así que usé la biblioteca de fechas de ruby, iteré por todos los días de enero del siglo 20 y sumé todos los domingos. Acá abajo pongo el código:

require 'date'

sundays = 0
(1901..2000).each do
  |year|
  Date.civil(year,1,1).upto(Date.civil(year,1,31)) do
    |d|
    sundays += 1 if d.wday == 0 # is sunday
  end
end

puts "# of sundays in the 20th century: #{sundays}"

El resultado de la corrida (casi instantáneo) es:

$ ruby euler19.rb
# of sundays in the 20th century: 443

El ejercicio 20 consiste en encontrar la suma de los dígitos de 100!. Usando las funciones para obtener cada dígito de un número del ejercicio 16, se hace bastante fácil. Este es el código:

class Integer
  def digit(pos)
    (self / (10 ** pos)) % 10
  end
  def digit_count
    dc = 0
    while self - (10 ** dc) > 0
      dc += 1
    end
    dc += 1 if self % (10 ** dc) == 0
    dc
  end
end

fact100 = (1..100).inject { |prod,n| prod * n }
puts "Digits: #{fact100}"
puts "Sum: #{(0...(fact100.digit_count)).inject {|s,n| s + fact100.digit(n)}}"

Y el resultado de la ejecución (también instantánea) es:

$ ruby euler20.rb
Digits: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Sum: 648

El ejercicio 21 es el más complicado de los 3. Consiste en sumar todos los números naturales "amigables" menores a 10000. Un par de números (a,b) es amigable si la suma de los divisores de a (excluyendo a) es b y la suma de los divisores de b (excluyendo b) es a. Un número es amigable si pertenece a un par amigable. Lo que se me ocurrió fue usar el MemoFactorizator (factorizador de números que recuerda factorizaciones previas) del ejercicio 12 para calcular las factorizaciones de todos los números menores a 10000. Usando esto, calculé analíticamente las sumas de los divisores propios (hay una fórmula re-linda que sale de la factorización, pero como no puedo escribir LaTeX facilmente acá, mejor mirenla en el código). Y habiendo calculado todas las sumas de los divisores, buscar en orden n todos los números amigables. Acá está el código:

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
  attr_reader :factored
  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

def divisor_sum(n, factorization)
  acum = 1
  factorization.each_pair do
    |p,pow|
    acum *= (0..pow).inject(0) { |s,i| s + p ** i }
  end
  acum - n
end

MAX = 10000

mf = MemoFactorizator.new
(2...MAX).each do
  |n|
  mf.factorize(n)
end

sums = {}
(2...MAX).each do
  |n|
  sums[n] = divisor_sum(n, mf.factored[n])
end

amicable = []

(2...MAX).each do
  |n|
  amicable << n if n == sums[sums[n]] and n != sums[n]
end

puts "Amicable numbers: #{amicable.inspect}"
puts "Sum: #{amicable.inject {|s,n| s+n}}"

La ejecución tardó un poquito (unos 4 segundos) y dio este resultado:

$ time ruby euler21.rb
Amicable numbers: [220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]
Sum: 31626

real    0m4.681s
user    0m4.560s
sys     0m0.108s

Happy hacking,
Aureliano

Proyecto Euler: Problemas 16 a 18

Update: Reporto la suma en el ejercicio 18.

Sigo con mi maratón euleriana. Ahora resolví los problemas 16 a 18.
El problema 16 consiste en encontrar la suma de los dígitos de 2^1000. Para eso desenpolvé la lógica para obtener la cantidad de dígitos de un número y qué dígito es que había hecho para el problema 4 (pequeño quiz: ¿qué bug le arreglé?) calculé 2^1000 y sumé los dígitos. Este es el código:

class Integer
  def digit(pos)
    (self / (10 ** pos)) % 10
  end
  def digit_count
    dc = 0
    while self - (10 ** dc) > 0
      dc += 1
    end
    dc += 1 if self % (10 ** dc) == 0
    dc
  end
end

n = 2 ** 1000
digits_sum = (0..(n.digit_count)).inject(0) { |sum, pos| sum += n.digit(pos) }
puts digits_sum

Y este el resultado (que sale instantáneamente):

$ ruby euler16.rb
1366

El problema 17 consiste en calcular cuantas letras (con repeticiones) hay en los números del 1 al mil en inglés. Por ejemplo "one two three" tiene 11 letras. Para eso hice una rutina que genera las palabras asociadas a cada número entre 1 y 1000, eso generó un string. Al string le saqué los espacios y conté la cantidad de caracteres. Mientras lo hacía me acordé de cuando estuve probando unos de los ejercicios que usan en ITA para contratar gente, pero lo escribí todo de 0. Acá va el código:

class Integer
  UNITS = ["","one","two","three","four","five","six","seven","eight","nine"]
  TEENS = ["ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"]
  TENS = ["","","twenty","thirty","fourty","fifty","sixty","seventy","eighty","ninety"]
  def to_words
    raise Exception.new("Don't know how to say in words the number #{self}") unless (1..1000).include? self
    return "one thowsand" if self == 1000
    words = []
    if self >= 100 then 
      words << UNITS[self / 100]
      words << "hundred"
    end
    words << "and" if (self % 100) != 0
    case (self % 100) / 10
      when 1
        words << TEENS[self%10]
      else
        words << TENS[(self % 100) / 10]
        words << UNITS[self % 10]
    end
    return words.delete_if{|w| w == ""}.join(" ")
  end
end

char_count = (1..1000).inject(0) { |sum,n| sum + n.to_words.gsub(" ","").length }
puts char_count

Y la corrida (también instantánea):

$ ruby euler17.rb
21521

Por último hice el ejercicio 18, que es el más interesante de los 3. El mismo consiste en navegar por un triángulo (que pongo más abajo), encontrando el camino desde arriba de todo a algún numerito de abajo de tal manera que la suma de los nodos del camino sea lo mayor posible.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Para resolver este problema, calculé las sumas de los mejores caminos posibles para todos los subtriangulos y después, usando eso, elegí en forma greedy el mejor camino. Acá va el código:

data_text = <<DATA_TEXT
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
DATA_TEXT

data = data_text.split("\n").map{ |row_text| row_text.split(" ").map{ |cell_text| cell_text.to_i(10) } }
sums = Array.new(data.length)
sums[-1] = data[-1].dup
(2..(data.length)).each do
  |row|
  sum = []
  prev_sum = sums[-row+1]
  data[-row].each_with_index do
    |v,i|
    sum[i] = v + [prev_sum[i],prev_sum[i+1]].max
  end
  sums[-row] = sum
end

pos = 0
path = []

(1..(data.length - 1)).each do
  |row|
  if sums[row][pos] > sums[row][pos+1] then
    path << :left
  else
    path << :right
    pos += 1
  end
end

puts path.inspect
puts "Sum: #{sums[0][0]}"

Y este es el resultado de la ejecución (también instantáneo, ya que se hacen tantas sumas como subtriángulos no triviales (que son menos que la cantidad de números en el triángulo) y tantas elecciones como la altura del triángulo. Acá les muestro el resultado:

$ ruby euler18.rb
[:right, :right, :left, :left, :right, :left, :left, :right, :right, :right, :right, :right, :left, :right]
Sum: 1074

Happy hacking,
Aureliano.