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.