ruby - Fibonacci One-Liner

Question

Estoy tratando de resolver las preguntas del Proyecto Euler en Ruby one-liners, y tengo curiosidad por encontrar una solución más elegante para la pregunta dos :

Cada nuevo término en la secuencia de Fibonacci se genera al agregar los dos términos anteriores. Al comenzar con 1 y 2, los primeros 10 términos serán:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Al considerar los términos en la secuencia de Fibonacci cuyos valores no exceden los cuatro millones, encuentre la suma de los términos de valor par.

Aquí está mi solución de una línea en Ruby:

(1..32).inject([0,1]) {|arr, i| (arr << arr[-1] + arr[-2] if arr[-1] + arr[-2] <= 4000000) || arr}.inject(0) {|total, i| total += i.even? ? i : 0}

Mi principal preocupación aquí es que estoy usando el rango (1..32) solo porque sé que eso es todo lo que es necesario hasta que los números en la secuencia de Fibonacci comiencen a superar los 4,000,000. Preferiría que esto se integrara en la línea de alguna manera, pero no he podido resolverlo.

¡No se permiten los semi-colones!

Answer 1

¿Qué hay de mi solución:

puts 0, ->(a=0, b=1) { 10.-(1).times.collect { (a, b = b, a + b)[1] } }.call

Esto evalúa 10 series. Pero si quieres obtener el número de usuario:

puts 0, ->(a=0, b=1) { gets.to_i.-(1).times.collect { (a, b = b, a + b)[1] } }.call

Answer 2

¿Qué tal esto?

(((1 + 5 ** 0.5) / 2) ** 35 / 5 ** 0.5 - 0.5).to_i / 2

( Vea esta respuesta para una explicación.)

Answer 3

Aquí está mi liner, con la tabla @fib se rellena a medida que obtenemos los resultados del método ...

@fib=[0,1];def fib num; return 0 if num < 0; @fib[num]||=fib(num-1)+fib(num-2);end

Answer 4

Aquí hay una solución de rubí de una línea para Euler prob # 2

(0..4000000).take_while{|i| (0..i).reduce([1,0]){|(a,b), _| [b, a+b]}[0] <= 4000000 }.map{|i| (0..i).reduce([1,0]){|(a,b), _| [b, a+b]}[0] }.select{|i| i%2 == 0}.reduce(:+)

¿O para una mejor legibilidad?

(0..4000000) .
take_while {|i| (0..i).reduce([1,0]){|(a,b), _| [b, a+b]}[0] <= 4000000} .
map {|i| (0..i).reduce([1,0]){|(a,b), _| [b, a+b]}[0]} .
select {|i| i%2 == 0} .
reduce(:+)

Answer 5

Aquí hay una solución ruby ​​2.0, sin usar inyectar / reducir que no es perezosa:

(1..Float::INFINITY).
  lazy.
  with_object([0,1]).
  map { |x, last| last[1] = last[0] + (last[0] = last[1]) }.
  select { |x| x % 2 == 0 }.
  take_while { |x| x < 4_000_000 }.
  reduce(&:+)

No me gusta particularmente el generador de fibonacci, porque no incluye el 0. inicial. Esta solución también aprovecha que el primer número impar es F ₃ (F ₁ en este generador de secuencias).

Una solución más limpia (según Fibonacci) y correcta (en la definición de Liber Abaci) sería:

(1..Float::INFINITY).
  lazy.
  with_object([0,1]).
  map { |x, last| last[1] = last[0] + (last[0] = last[1]);last[0] }.
  select { |x| x % 2 == 0 }.
  take_while { |x| x < 4_000_000 }.
  reduce(&:+)

Esta solución incluye un punto y coma, pero no sé si cuenta cuando se usa de esta manera :).

[Actualizar]

Aquí hay una solución adecuada para el generador de Fibonacci (a partir de 0), sin punto y coma (por cierto, ¿es esta una guerra de javascript en punto y coma?!?) :)

(1..Float::INFINITY).
  lazy.
  with_object([0,1]).
  map { |x, last| last[0].tap { last[1] = last[0] + (last[0] = last[1]) } }.
  select { |x| x % 2 == 0 }.
  take_while { |x| x < 4_000_000 }.
  reduce(&:+)

Answer 6

Como una solución de resumen para las respuestas anteriores, con mis humildes adiciones:

32.
  times.
  lazy.
  with_object([0, 1]).map { |_, fib| fib[1] = fib[0] + fib[0] = fib[1]; fib[0] }.
  take_while(&:>.to_proc.curry(2)[4*10**6]).
  select(&:even?).
  inject(:+)

Realmente no me gusta cómo se ve el curry, pero no quería que se pareciera a otras respuestas. take_while alternativa take_while solo para el caso:

  take_while { |value| value < 4*10**6 }.

Answer 7

Con el nuevo holgazán en ruby ​​2.0, puedes escribir así.

puts (1..Float::INFINITY).lazy.map{|n| (0..n).inject([1,0]) {|(a,b), _| [b, a+b]}[0] }.take_while{|n| n < 4000000}.select{|x| x % 2 == 0}.reduce(:+)

Answer 8

Devuelve valores correctos hasta Fib(70) , más allá de eso solo una aproximación. Pero extremadamente rápido:

(((Math.sqrt(5.0) + 1.0) / 2.0)**n / Math.sqrt(5.0) + 0.5).floor

(consulte https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding para obtener una explicación)

Answer 9

Inspirado en la respuesta de Alex:

# Ruby 1.8.7
f = lambda { |x| x < 2 ? x : f.call(x-1) + f.call(x-2) }
puts f.call(6)   #=> 8

# Ruby 1.9.2
f = ->(x){ x < 2 ? x : f[x-1] + f[x-2] }
puts f[6]        #=> 8

Answer 10

Me doy cuenta de que esta es una pregunta antigua y ha sido clasificada como respondida pero nadie logra resolver la pregunta en un bloque, ninguno de ellos en realidad da la suma de los términos de valor par en una línea y en un bloque y sin punto y coma. (Acabo de notar que waynes se resuelve con una línea, pero pensé que una solución de un bloque podría ser buena en respuesta a aroth). Aquí hay una solución que hace:

(1..Float::INFINITY).inject([0,1,0]){|a| if a[0]+a[1] < 4000000 then [a[1],a[0]+a[1],(a[0]+a[1]).even? ? a[2] + (a[0]+a[1]) : a[2]] else break a[2] end }

Para una versión ligeramente más clara con un punto y coma.

(1..Float::INFINITY).inject([0,1,0]){|a| sum=a[0]+a[1]; if sum < 4000000 then [a[1],sum,sum.even? ? a[2] + sum : a[2]] else break a[2] end }

Me imagino que también lo explicaré, tres elementos de información se llevan adelante en la matriz (como en cada iteración) el primer número de fibonacci, el segundo número de fibonacci y la suma de los términos pares. teniendo esto en cuenta creo que este código es bastante claro rubí.

Cabe señalar que esto es básicamente lo mismo que clems excepto en un bloque

Answer 11

Mi favorito es:

def fib(n)
  (0..n).inject([1,0]) { |(a,b), _| [b, a+b] }[0]
end

de https://gist.github.com/1007228

Answer 12

Mi solución favorita para esto es usar un Hash, cuyos valores pueden ser determinados por una función anónima:

fibonacci = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }

fibonacci[6]  # => 8 
fibonacci[50] # => 12586269025

Es un "genuino" de una sola línea y muy Ruby-ish.

Answer 13

Simple y elegante es la mejor manera, ¿verdad?

a0 = 1; a1 = 1; 20.times {|i| b = a0 + a1; a0 = a1; a1 = b; puts b };

Salida:

2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
=> 20

Answer 14

Sobre la base de Alex''s Hash, esto puede volverte ciego, pero es una línea, sin punto y coma y elimina la dependencia del rango. El truco instance_eval es muy útil para oneliners y golf, aunque es horrible Ruby.

Hash.new{|h,k|h[k]=k<2?k:h[k-1]+h[k-2]}.update(sum: 0,1=>1).instance_eval {self[:sum]+= self[keys.last+1].even? ? self[keys.last] : 0 while values.last < 4E6 || puts(fetch :sum)}

Salidas: 4613732

Te advertí que era horrible. No puedo hacer que realmente devuelva el valor sin utilizar un punto y coma, lo siento.

Answer 15

Usando un enumerador Ruby 1.9:

fib = Enumerator.new do |yielder|
  i = 0
  j = 1
  loop do
    i, j = j, i + j
    yielder.yield i
  end
end

p fib.take_while { |n| n <= 4E6 }
# => [1, 1, 2 ... 1346269, 2178309, 3524578]

Como una línea:

p Enumerator.new { |yielder| i, j = 0, 1; loop {i, j = j, i + j; yielder.yield i} }.take_while { |n| n <= 4E6}

Answer 16

(1..32).inject([0, 1]) { |fib| fib << fib.last(2).inject(:+) }

Answer 17

puts (1..20).inject([0, 1]){|Fibonacci| Fibonacci << Fibonacci.last(2).inject(:+) }

Esta es la mejor solución que he usado para imprimir la serie de Fibonacci usando la palabra clave inyectar. Explicación: 1) .inject([0,1]) mantendrá el valor predeterminado (0) primer valor del elemento de la colección (1) de la serie. 2) Al principio, el objeto Fibonacci tendrá 0, 1 utilizando Fibonacci.last(2) que se pasará por inyectar 3) .inject(:+) agregará el 0 + 1 4) Esto agregará 0 + 1 = 1 y luego se enviará a Fibonacci que en la siguiente iteración con inject([0,1]) externa inject([0,1]) se inject(1,2) aquí 1 es el valor después de la suma (0 + 1) y 2 es el siguiente valor de iteración de la colección. Y así sucesivamente hasta el final de la colección.

Así que la serie será como

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946