Recent post as DoD (Director of Development – not Department of Defense) for ACLTC Ruby Bootcamp:
The Fibonacci Sequence.
You start with two numbers – 0 and 1 – you add them together, and then you keep adding the last two numbers in your list to get the next number.
0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 3 + 2 = 5, and so on.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6785, 10946, 17711, 28657, 46368, 75025…
…ahem. Sorry…got carried away there.
It’s easy to do when you don’t have to add the numbers yourself.
Just write a computer program to do it for you. Easy! Take 60 seconds.
…oh.
Maybe it’s not so easy.
Don’t worry – coding the Fibonacci Sequence sounds deceptively simple, which is why software companies like to ask interviewees how they would do it.
A human can understand the sequence after two lines of explanation. Why is it so hard to tell a computer how to do this?
Well, unlike humans, computers don’t understand context. “The last two items in your list” is a description that requires context. And then, when you add those two numbers together to get the next number, those numbers are no longer the last two in your list. So you’ve changed up the context, and now your computer is completely lost…unless you can find an unambiguous way to explain to it what you want.
So what gives? How do we solve the problem?
As it turns out, there’s not just one way. Stick eleven programmers in a room, pair them off, and give them twelve minutes, and you’ll come up with multiple solutions. We tried it, and we got three.
Three solutions – on the second day of class. These are brand new programmers.
So no arrays.
No recursion.
No methods, even.
It makes you wonder how many solutions there are with all the tools in a programming language.
Have a look at the three different ways we came up with – and for the moment, suspend your judgment on which one is the best.
Instead, let’s replace the question of “Which one is best?” with a different question: “What kinds of other problems can we solve with the three different problem-solving techniques displayed here?”
It’s a much more productive question, really…especially since, once you get the job as a programmer, you’ll probably never need to know the best way to code the Fibonacci Sequence…uh, ever.
Okay, Solution 1:
x = 0
y = 1
puts x
puts y
20.times do
x = x + y
puts x
y = x + y
puts y
end
So what’s happening here? We have two variables – x and y – we print them, add them together, assign that number to x, print it, add that number to y, print it, and so on.
So X and Y take turns being the variable that holds the sum so far.
And this is key, because when we do the Fibonacci Sequence…
1+2=3, 3+2=5, 5+3=8…
We can’t throw away both of the last two numbers. We add the second-to-last number and the last number to get a sum, and that’s the next number. So we don’t need the second-to-last number anymore. But we still need the last number, because we are going to add it to the next number – the sum we just took – to get the number that comes after it.
Once we have that, we don’t need what used to be our last number anymore…but we still need the two sums we just did.
by reassigning the second-to-last number to the value of the new sum, this code always keeps only the two numbers it needs!
You’ll notice, though, that there has to be that extra step: two puts commands. If the code doesn’t do that, then both variables will be reassigned to the sum before it’s time to print them…and then the program will just print out a string of numbers, each one double what the last one was. THE HORROR!
That’s a common theme, and we’ll see it again in the other two solutions: an extra step without which the code would just double our number each time it printed.
OK, solution number two:
first_number = 0
second_number = 1
puts first_number
puts second_number
20.times do
third_number = first_number + second_number
puts third_number
first_number = second_number
second_number = third_number
end
In this case, the extra step is the third variable: third_number.
Now, for solution number three:
first_number = 0
second_number = 1
coin = "heads"
puts first_number
puts second_number
while (first_number + second_number)<=10000 do
puts first_number + second_number
if coin == "heads"
first_number = first_number + second_number
coin = "tails"
else
second_number = first_number + second_number
coin = "heads"
end
end
And in this case, the extra step is the “coin” flipping – a counter that goes back and forth to determine which of the two number variables should store the latest Fibonacci sum.
This exercise made a great reminder: there can be multiple ways to solve a problem. But that’s a discussion for a future post.