Perl Weekly Challenge 112: Climb Stairs

by Abigail

Challenge

You are given $n steps to climb Write a script to find out the distinct ways to climb to the top. You are allowed to climb either 1 or 2 steps at a time. Example Input:$n = 3
Output: 3

Option 1: 1 step + 1 step + 1 step
Option 2: 1 step + 2 steps
Option 3: 2 steps + 1 step

Input: $n = 4 Output: 5 Option 1: 1 step + 1 step + 1 step + 1 step Option 2: 1 step + 1 step + 2 steps Option 3: 2 steps + 1 step + 1 step Option 4: 1 step + 2 steps + 1 step Option 5: 2 steps + 2 steps  Discussion 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

my $SQRT5 = sqrt (5); my$PHI   = (1 + $SQRT5) / 2; say int (1 / 2 +$PHI ** ($n + 1) /$SQRT5)


Find the full program on GitHub.

AWK

SQRT5 = sqrt (5)
PHI   = (1 + SQRT5) / 2
print int (0.5 + PHI ^ (n + 1) / SQRT5)


Find the full program on GitHub.

C

# define SQRT5 (sqrt (5))
# define PHI   ((1 + SQRT5) / 2)
printf ("%lld\n", (long long) floor (0.5 + pow (PHI, n + 1) / SQRT5));


Find the full program on GitHub.

Go

import "fmt"
import "math"
var SQRT5 float64 = math . Sqrt (5)
var PHI   float64 = (1 + SQRT5) / 2
r = math . Round (math . Pow (PHI, (n + 1)) / SQRT5)
r = math . Round (math . Pow (PHI, (n + 1)) / SQRT5)


Find the full program on GitHub.

Java

final double SQRT5 = Math . sqrt (5);
final double PHI   = (1 + SQRT5) / 2;
System . out . printf ("%d\n",
(int) Math . round (Math . pow (PHI, n + 1) / SQRT5));


Find the full program on GitHub.

Lua

local SQRT5 = math . sqrt (5)
local PHI   = (1 + SQRT5) / 2
print (math . floor (0.5 + PHI ^ (n + 1) / SQRT5))


Find the full program on GitHub.

Node.js

let SQRT5 = Math . sqrt (5)
let PHI   = (1 + SQRT5) / 2

Math . round (Math . pow (PHI, n + 1) / SQRT5)


Find the full program on GitHub.

Pascal

const
sqrt5 = sqrt (5);
phi   = (1 + sqrt5) / 2;

writeln (round (power (phi, n + 1) / sqrt5));


Find the full program on GitHub.

Python

SQRT5 = sqrt (5)
PHI   = (1 + SQRT5) / 2
print (round (pow (PHI, n + 1) / SQRT5))


Find the full program on GitHub.

R

sqrt5 <- sqrt (5)
phi   <- (1 + sqrt5) / 2
cat (round (phi ^ (n + 1) / sqrt5), "\n", sep = "")


Find the full program on GitHub.

Ruby

SQRT5 = Math . sqrt 5
PHI   = (1 + SQRT5) / 2
puts ((PHI ** (n + 1) / SQRT5) . round)


Find the full program on GitHub.

Scheme

(define sqrt5 (sqrt 5))
(define phi   (/ (+ 1 sqrt5) 2))
(format #t "~d\n" (inexact->exact (round (/ (expt phi (+ n 1)) sqrt5))))


Find the full program on GitHub.

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

> & :1+!#@_ 111p112p > :!#v_ 12g:11g+12p11p :1- v
^                          <
^              ,+55  .g11 <


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:

            111p112p


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:

                     > :!#v_                    v
^                          <
<


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:

                             12g:11g+12p11p :1-


When we break out of the loop, we print the result:

               ,+55  .g11


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+,).

Find the full program on GitHub.