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!

Solution 1

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

Solution 2

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.

Solution 3

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}

Solution 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

Solution 5

How about this?

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

(See this answer for an explanation.)

View more solutions

Comments

[aroth]

I think it's subverting the spirit of your challenge a bit if the "one-liner" solutions include multiple blocks. I mean, you could do a Java one-liner the same way, if you didn't mind having a line that was 500 characters long and completely unreadable.

[clem]

It's nothing to do with Ruby specifically, that's just the language I'm learning. It's just for fun.

[Wayne Conrad]

@aroth, Chaining blocks in Ruby is as natural as an assignment with multiple arithmetic operators. For a one-liner which bends the spirit of the rules more, see my solution: the semicolons are a dead givaway.

[aroth]

@Wayne - If chaining blocks in Ruby is always done by using a single line of code, then all I can say is ugh...I will never understand why seeming rational people take a practice that needlessly obfuscates code and make it "natural". Part of the design philosophy behind Ruby as a language was that it should be easy for a human to read and understand, and of your two example solutions the multi-line one is by far the most readable.

[Wayne Conrad]

@aroth, I agree. I don't chain blocks on one line unless it's more readable. Sometimes it is, often it isn't. The one-liner in my example is because the OP asked for it, not because it's what I'd write. That said, writing one-liners is a valid exercise, like a musician playing musical scales. You wouldn't write one liners in production code, nor would you play musical scales in a concert.

[Mike H-R]

@aroth a one block solution for you sir.

[oligan]

Very clever! But you're using a colon - isn't that twice as bad as using a semicolon?

[Patrick Farrell]

Bravo! You get automagic memoization by using the hash to drive the function. This is elegance!

[pjammer]

I like this solution, but wouldn't you have to know the significance of why you are using 35? Given the Euler project questions, you really only know the number 4000000 and to sum the even numbers.

[Gareth Rees]

@pjammer: 35 can be replaced with (Math.log(4000000 * 5 ** 0.5, (1 + 5 ** 0.5) / 2) + 2).to_i, if you like.

[Jonas Elfström]

fib = ->(n, i=0, j=1){(1..n).map{i=j+j=i}} Call it with fib[7]

[Jonas Elfström]

I wonder why the syntax you used seems to have disappeared in Ruby 1.9.3.

[Jonas Elfström]

A while ago I found out about the strange construct i=j+j=i. It's the same thing as i, j = j, i + j.

[Wayne Conrad]

@Jonas, Did you mean j = i + i = j? It's an interesting construct! It's not one I'd like to use in production code, but a good one for thinking about how Ruby works. Thank you for pointing it out.

[Sony Santos]

@JonasElfström, you must put your code as an answer, it deserves a +1! :) I'd add a [n-1] before the last } to get the same result type (number instead of array). I'll adapt my answer to 1.9.3, thank's for the tip.

[Jonas Elfström]

I wouldn't use it in production code either and me confusing them is a good indicator of why.

[Sony Santos]

@JonasElfström The syntax I've used for 1.9.2 didn't work in 1.9.2. The truth is: I thought that -> was replacing the lambda keyword and the rest would be the same, and I didn't test the code in 1.9.2 (I was not using rvm at that time). Now it's correct. Thank you!

[Jonas Elfström]

I missed that the answer should be the n:th Fibonacci number and not the sequence itself. Here's another silly lambda for that fib = ->(n, i=0, j=1){n.times{i=j+j=i};i} Since i=j+j=i is such a quirky construct I don't think it deserves being an answer.

[Sony Santos]

@JonasElfström .last is better than [n-1], but your ;i is far more interesting. :) Hey, this question is for one-liners, it's hard to not being quirky.

[Mike H-R]

And afaik it seems to be efficient and memoises the information without storing too much of it (so both speed and memory efficient)

[Mike H-R]

sorry @JonasElfström is there any chance you can explain your code? I'm convinced there's genius in there but it's hidden within madness. could you explain what ;i does and why i=j+j=i works? also out of interest where did you come by such arcane and mystical knowledge? :)

[Jonas Elfström]

It's an offensive way to exploit operator precedence order. Try this is irb. i=0;j=1 then run i=j+j=i; puts "i:#{i}, j:#{j}" a couple of times.

[Jonas Elfström]

i=j+j=i is evaluated from left to right. Starting point i=0;j=1. First i will be set to 1 + 0 since = precedes +. Now i=1;j=0. i will be set to 0 + 1. We arrive at i=1;j=1. i will be set to 1 + 1. i=2;j=1. i will be set to 1 + 2. i=3;j=2. i will be set to 2 + 3. i=5;j=3 and so on, thus producing the Fibonacci sequence.

[Sony Santos]

@MikeH-R ...and the ;i is synonym for ; return i.

[Mike H-R]

ahh, so it is functionally equivalent to i,j = j, j+i since the exact same operations are performed, cool. thanks for the explanation. also I see now, of course it's a return i, that makes sense. incidentally, I couldn't ask why that's necessary, could I? shouldn't the inside block (the times one) return i as it's final value by default? instead it seems to return n, which is obviously why you fix it with the ;i. Am I mistaken in remembering that blocks return the last value in them?

[Mike H-R]

hmmm. So playing around in IRB it looks like a blocks return value isn't the last value in it, but here and my memory say that it is (from the link: "A code block's return value (like that of a method) is the value of the last expression evaluated in the code block.") can someone explain why I'm mistaken?

[Mike H-R]

oh and code saying that blocks don't return the last expression: a=10.times {i=j+j=i} #returns 10, (1..10).each {i=j+j=i} # returns (1..10) e.t.c. with some more things I tried.

[Jonas Elfström]

Array#each returns the array and Integer#times returns self. ruby-doc.org/core-2.0.0/Array.html#method-i-each ruby-doc.org/core-2.0.0/Integer.html#method-i-times

[Jonas Elfström]

@MikeH-R Your comments made me "improve" it. ->(✌, ❤=0, ♥=1){(1..✌).map{❤=♥+♥=❤}}[8] :)

[Amit Kumar Gupta]

fibonacci[2299] # => stack level too deep (SystemStackError)

[DavidSilveira]

I'd like to highlight the performace difference between both approaches. Hash: codefibonacci = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] } puts fibonacci[30] 832040 [Finished in 0.1s] code Lambda: code fibo = lambda { |x| (x<2) ? x : fibo.call(x-1) + fibo.call(x-2) } 832040 [Finished in 1.7s] code

[jasonleonhard]

p fibonacci # {1=>1, 0=>0, 2=>1, 3=>2, 4=>3, 5=>5, 6=>8, 7=>13, 8=>21, 9=>34, 10=>55, 11=>89, 12=>144, 13=>233, 14=>377, 15=>610, 16=>987, 17=>1597, 18=>2584, 19=>4181, 20=>6765, 21=>10946, 22=>17711, 23=>28657, 24=>46368, 25=>75025, 26=>121393, 27=>196418, 28=>317811, 29=>514229, 30=>832040, 31=>1346269, 32=>2178309, 33=>3524578, 34=>5702887, 35=>9227465, 36=>14930352, 37=>24157817, 38=>39088169, 39=>63245986, 40=>102334155, 41=>165580141, 42=>267914296, 43=>433494437, 44=>701408733, 45=>1134903170, 46=>1836311903, 47=>2971215073, 48=>4807526976, 49=>7778742049, 50=>12586269025}

[look]

This is by far the fastest. And unbelievably fast too.

[Dennis]

Without a colon: fib = Hash.new { |fib, n| fib[n] = fib[n - 1] + fib[n - 2] }.merge!(0 => 0, 1 => 1)

[Wayne Conrad]

+1 for pointing out what the rest of missed: We were so focused on the fib. generator that we forgot to add that last bit that the OP asked for.

[YasirAzgar]

can any one please explain how this piece of code wokrs

[s1mpl3]

In a regular laptop at least it doesn't perform well at all on values above 35. f[35]