Fibonacci One-Liner

Question

I'm trying to solve questions from Project Euler in Ruby one-liners, and I'm curious if there's a more elegant solution for question two:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Here is my one line solution in 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}

My main concern here is that I'm using the range (1..32) only because I happen to know that that's all that's necessary until numbers in the Fibonacci sequence begin to exceed 4,000,000. I would prefer that this be built into the one-line somehow, but I haven't been able to figure it out.

Semi-colons are not allowed!

Answer 1

My favorite solution to this is to use a Hash, the values of which can be determined by an anonymous function:

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

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

It's a "genuine" one-liner and very Ruby-ish.

Answer 2

Using a Ruby 1.9 Enumerator:

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]

As one line:

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

Answer 3

Inspired on Alex's answer:

# 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 4

My favorite is:

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

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

Answer 5

How about this?

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

(See this answer for an explanation.)

Answer 6

Here's a ruby 2.0 solution, without using inject/reduce which is not lazy:

(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(&:+)

I don't particularly like the fibonacci generator, because it doesn't include the initial 0. This solution also takes advantage of the first odd number being F₃ (F₁ in this sequence generator).

A cleaner (Fibonacci-wise) and correct (In Liber Abaci's definition) solution would be:

(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(&:+)

This solution includes a semi-colon, but I don't know if it counts when used this way :).

[Update]

Here's a proper Fibonacci generator (starting on 0) solution, with no semi-colon (btw, is this a javascript semi-colon wars thingy ?!?) :)

(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 7

I realize this is an ancient question and has been classed as answered but no-one manages to solve the question in one block, none of them actually give the sum of the even valued terms in one line and in one block and with no semi colons (just noticed that waynes does solve with one line but I thought a one block solution might be nice in response to aroth). here is a solution that does:

(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 }

for a slightly clearer version with one semi colon.

(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 }

I figure I'll explain it too, three pieces of information get carried forward in the array (as a at each iteration) the first fibonacci number, the second fibonacci number and the sum of the even terms. bearing this in mind I think this code is quite clear ruby.

it should be noted that this is basically the same as clems except in one block

Answer 8

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

This is the best solution I ever had used to print the Fibonacci series using inject keyword. Explanation: 1) .inject([0,1]) will hold the default value (0) first value of collection (1) element of the series. 2) At first Fibonacci object will have 0, 1 using Fibonacci.last(2) that will be passed through inject 3) .inject(:+) will add the 0+1 4) This will add 0+1 = 1 and then will be pushed to Fibonacci which on next iteration with outer inject([0,1]) will become inject(1,2) here 1 is the value after sum (0+1) and 2 is the next iteration value of collection. and so on till the end of collection

So the series will be like

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

Answer 9

I can think of 4 ways for now to achieve the fibonacci goal!

1. Using a stabby lambda:

puts 'Fibonacci Sequence in a Line: ', ->(a=1, b=0) { 10.times.collect { (a, b = b, a + b)[0] } }.call

This evaluates 10 series. But if you want to get the user's number:

puts 'Fibonacci Sequence in a Line: ', ->(a=1, b=0) { gets.to_i.times.collect { (a, b = b, a + b)[0] } }.call

2. Using the tap method:

[0, 1].tap { |a| 10.times { a.push(a[-1] + a[-2]) } }

3. Using the reduce / inject method:

(1..10).reduce([0, 1]) { |a| a.push(a.last(2).sum) }

or

10.times.reduce([0, 1]) { |a| a.push(a.last(2).sum) }

4. Using the each_with_object or map.with_object method:

10.times.each_with_object([0, 1]) { |_, a| a.push(a.last(2).sum) }

Note: If you don't have Ruby 2.4+ you may not have the sum method. In that case, you can add the last two elements with ary[-2] + ary[-1] or ary.last(2).reduce(:+).

Coming to your problem:

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

[0, 1].tap { |a| until (s = a.last(2).sum) > 4_000_000 do a.push(s) end }.select(&:even?).sum

Or (which is not that great):

[0, 1].tap { |a| loop while a.push(a.last(2).sum)[-1] < 4_000_000 }.tap(&:pop).select(&:even?).sum

Outputs: 4613732

Hope this helps!

Answer 10

Building on Alex's Hash, this may make you go blind, but it's one line, no semicolons and eliminates the range dependency. the instance_eval trick is very useful for oneliners and golf, although it's 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)}

Outputs: 4613732

I warned you it was horrible. I can't make it actually return the value without using a semicolon, sorry.

Answer 11

Returns correct values up to Fib(70), beyond that just an approximation. But extremely fast:

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

(see https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding for explanation)

Answer 12

With the new lazy in ruby 2.0, you can write like this.

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 13

As a summarizing solution for the answers above, with my humble additions:

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(:+)

I don't really like how currying looks, but didn't want it to look similar to other answers. Alternative take_while just for the case:

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

Answer 14

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

Answer 15

Here's a one line ruby solution to 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(:+)

Or for better readability??

(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 16

Here is my one liner, with the @fib table being populated as we get the method returns..

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

Answer 17

Simple and elegant is the best way, right?

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

Output:

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