Perl Weekly Challenge 112: Climb Stairs

If we can climb stairs one or two steps at a time, then the number of ways to climb a stair with $N$ steps is the number of ways to climb a stair with $N - 1$ steps (if we first climb one step), plus the number of ways to climb of stair with $N - 2$ steps (if we first climb two steps).

Since there is just one way to climb a stair case with 0 or with 1 step, we have the following formula to climb a stair case with $N$ steps:

\[ S (N) = \begin{cases} 1 & \text{if } N = 0 \\ 1 & \text{if } N = 1 \\ S (N - 1) + S (N - 2) & \text{if } N > 1 \end{cases} \]

But this means that $S (N)$ is $F (N + 1)$, where $F$ is the Fibonacci Sequence. And we have a closed formula for this:

\[ F (N) = \frac{\varphi^N - \psi^N}{\sqrt{5}} \]

where

\[ \varphi = \frac{1 + \sqrt{5}}{2} \text{ and } \psi = \frac{1}{\varphi} \]

Since $\psi < 1$, the component $\psi^N$ goes to $0$. Hence

\[ F (N) \approx \frac{\varphi^N}{\sqrt{5}} \]

In fact,

\[ F (N) = \left[ \frac{\varphi^N}{\sqrt{5}} \right] \]

where $[\text{expr}]$ rounds the expression to the nearest integer.

So, if we have a stair case with $N$ steps, the answer we are looking for is:

\[ S (N) = \left[ \frac{\varphi^{N + 1}}{\sqrt{5}} \right] \]

Solutions

For most languages, we use the formula above. In Bash and Befunge-93, we can only do integer arithmetic, so we use the recursive definition.

In the solutions below, the number of steps the stair case is in a variable n (or $n):

Perl

AWK

Java

Lua

Node.js

Pascal

Python

Ruby

Scheme

Bash

Here we use a starndard recursive definition of the Fibonacci numbers. We're using a cache to speed things up:

declare -A cache
cache[0]=1
cache[1]=1

function fib () {
    local n=$1
    if   [[ -z ${cache[$n]} ]]
    then fib $((n - 1))
         cache[$n]=$result
         fib $((n - 2))
         cache[$n]=$((cache[$n] + result))
    fi
    result=${cache[$n]}
}

Calling fib and printing the results:

fib  $n
echo $result

Find the full program on GitHub.

Befunge-93

The program above is an iterative formula to calculate the Fibonacci numbers. We use the cells (1, 1) and (1, 2) to store the two previous numbers in the sequence. These numbers are initialized to 1, using the following fragment:

On the stack we keep track how often we still need to iterate. If the number on the stack is 0, we break out of the loop:

Inside the loop, we set the second to last number to the last number, and the last number to the sum of the last and second to last number. And then we substract 1 from the number on the stack:

This line is run left to right, and it fetches the number from the cell (1, 1), which is printed (.), followed by a newline (55+,).