Tackling the Staircase Problem with Coding and Math
During his TED talk, Conrad Wolfram describes
computer programming as a means of recording procedures and processes and he
offers that it is a great way to fully engage students and to check that they
truly understand the concept being explored. He says that
students gain intuition and experience in far greater quantities through
programming and are able to tackle more challenging problems. Thus, they are
“able to play with the math, interact with it, feel it. We want people who can
feel the math instinctively. That's what computers allow us to do.” In other words, programming is an opportunity to do and
understand mathematics!
With this in mind, let's take a look at the following problem:
How
many different ways are there to climb a staircase with n steps (for example,
100 steps) if you are allowed to skip steps but not more than one at a
time?
A programming approach to this problem was discussed by
Maria Litvin during a panel discussion at the 2011 PyCon Conference. Litvin’s approach begins by first listing the
number of ways for n = 1 through 4 steps as follows.
n=1: 1 -->1 way
n=2: 1+1,2 --> 2 ways
n=3: 1+1+1,1+2,2+1 -->
3 ways
n=4:
1+1+1+1,1+1+2,1+2+1,2+1+1,2+2 --> 5 ways
Once we get to 5 steps,
listing the number of ways becomes somewhat tedious. Instead, let’s ask the computer to generate
all sequence of 1s and 2s of length from 1 to n, and count the sequences for
which the sum of the elements is equal to n.
But how do we ask the computer to do this?
We can model the
situation in a different way to take advantage of bitwise logical
operators. 0 marks a step we step on; 1
marks a step we skip. A valid path cannot have two 1s in a row and also must
end with a 0. If not, then all n steps were not
climbed. So we restate the problem as
“count all sequences of 0s and 1s of length n with no two 1s in a row and
discard sequences that end in 1s.”
If we look at n=4, the
valid sequences would then be:
0000,0010,0100,1000,1010
Let’s take a look at the
code in Python using this strategy:
def
countPaths(n):
count = 0
We name the function
countPaths that takes as its input the number of steps in the staircase and
returns count, the number of ways to climb n steps if
you’re allowed to skip steps but not more than one at a time. We also set the counter, count at 0.
The script to create a
list of numbers that when written in binary code are all possible sequences of
1s and 0s of length n is:
for x in range (0,2**n,2):
In Python, (2**n) denotes 2 to the nth power, and range
(0,2**n,2) will generate a list of all the even numbers from 0 to 2**n-1 so that 2**n will not be included in the list
and 2**n -2 is the last number on the list.
Thus, we first discard the sequences that end in 0 by discarding the odd
numbers. In her presentation, Litvin
doesn’t remove the sequences that end in 1 in the body of the code but takes
this into account by the way she calls the function once the program is
written.
Next we use bitwise
logical operators, << and &, that operate on numbers, but instead of treating a number as if
it were a single value, they treat it as if it were a string of bits (0 or 1),
written in binary code.
x << y returns x with the bits shifted to the
left by y places (and the new bits on the right-hand side are zeros). This is
equivalent to multiplying x by 2**y.
x & y does a
"bitwise and". Each bit of the output is 1 if the corresponding bit
of x AND of y is 1, otherwise it's 0.
The script that tests
whether the sequence of 1s and 0s has no two 1s in a row is:
if x & (x<<1)==0:
count = count + 1
return count
If the binary
representation of x does not have two 1s in a row, then when the sequence is
shifted 1 place to the left and aligned to the original sequence, there are no
columns with two 1s so that the output of x
& (x<<1) will be all 0s.
For example, if we begin with the sequence 00010100010, shifting the
sequence 1 place to the left and adding a 0 at the right will result in
00101000100. Align the two sequences
from the right-hand side and you will see there are no columns that have two
1s.
00010100010
00101000100
--------------------
00000000000
Now begin a sequence that
has two 1s and shift the sequence 1 place to the left and add a 0 at the
right. When you align the two sequences
from the right-hand side, the output has at least one 1 in the sequence.
00101100100
01011001000
--------------------
00001000000
Therefore, if the output
is 0, then the sequence is valid and we add it to the count.
When we print the number
of paths for n = 1 through 100, we see a fascinating result emerge. The number of paths for n steps is the nth
Fibonacci number (as we are considering the 0th and 1st terms of the Fibonacci
sequence as 1 and 1.) Recall that the
Fibonacci sequence is a sequence of numbers for which each term is the sum of
the 2 previous terms.
Why do we see that the
number of paths for n steps is the nth term in the Fibonacci sequence?
Let’s go back to HOW we
can climb 4 steps:
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
How do these ways relate
to how we can climb 3 steps? If we know
all the ways to climb 3 steps, then we can add a 2-step to each way to climb 5
steps. Similarly, if we know all the
ways to climb 4 steps, we can add 1-step to each way to climb 5 steps. Since we are allowed only to use 1-steps and
2-steps, we have exhausted all the ways to climb 5 steps!
Add a 2-step to each way
to get 2 steps: 1+1+2, 2+2
Add a 1-step to each way
to get 3 steps: 1+1+1+1, 1+2+1, 2+1+1
Once we see this relationship
mathematically, we can compute the number of ways to climb n steps by simply
creating a code that generates the nth Fibonacci number such as below.
def
countPaths_fibo(number_of_steps):
if number_of_steps == 0:
return 1
elif number_of_steps == 1:
return 1
If there
are 0 steps or 1 step, then there is only 1 way to climb either staircase.
else:
f_nminus1, f_n=1,1
We
designate f_n as the
last term in the Fibonacci sequence thus far, and f_nminus1 as the second-to-last
term.
for i in range(number_of_steps-1):
We
repeat the following instructions (number_of_steps -1) times.
f_nminus1 = f_nminus1+f_n
f_nminus1,f_n = f_n,f_nminus1
return f_n
These instructions return
the next term in the sequence by reassigning to f_n the
value of the 2 previous terms.
The advantage of
analyzing the mathematics behind the task is that to run the original script
using bitwise operators requires much more time as the number of steps
increase. Because the number of
sequences that have to be checked by the bitwise logical operator increases at
an exponential rate (2^n), the student may have to wait several minutes before
receiving the results of the program when asked to calculate how many ways to
climb 100 steps. This example
illustrates how mathematical understanding enhances programming skills by
helping students create more efficient scripts to accomplish a given task.
Next, we see how creating
different algorithms to solve a given problem can reveal quite interesting
connections among various ideas in mathematics.
We now approach the task
of calculating the number of possible ways to climb 100 steps in a completely
different manner. First let’s tackle the
question of how many possible ways there are to climb 10 steps. Since we can only use “one-steps” (ones) and
“two-steps” (twos), we could climb 10 steps by using 10 ones. We could also climb 10 steps by using 8 ones
and 1 two. Because we can skip a step at
any point, there are there are C(9,1) different ways to climb 10 steps using 8
ones and 1 two. C(9,1) represents the
number of combinations of 1 object from a set of 9 objects. Next, we could climb 10 steps by using 6 ones
and 2 twos, but there are C(8,2) different ways to climb 10 steps using 6 ones
and 2 twos. We can continue in this way
until we exhaust all the different ways to climb 10 steps.
10 ones ⇒ There are C(10,0) ways to climb 10 steps.
8 ones and 1 two ⇒ There
are C(9,1) ways to climb 10 steps.
6 ones and 2 twos ⇒ There are C(8,2) ways to climb 10 steps.
4 ones and 3 twos ⇒ There are C(7,3) ways to climb 10 steps.
2 ones and 4 twos ⇒ There are C(6,4) ways to climb 10 steps.
5 twos ⇒ There are C(5,5) ways to climb 10 steps.
Thus, the number of
possible ways to climb 10 steps = C(10,0) + C(9,1) + C(8,2) + C(7,3) + C(6,4) +
C(5,5).
Suppose there are 11
steps overall. Then the number of
possible ways to climb 11 steps would be: C(11,0) + C(10,1) + C(9,2) + C(8,3) +
C(7,4) + C(6,5).
Notice that for each
term, C(n,r), (n+r) is equal to the
total number of steps. This lends itself
nicely to an algorithm. First we must
define functions for the factorial of a number and combinations of r objects from a set of n objects. Then we need to distinguish between whether
the number of steps is even or odd. The
script follows:
def
numberPaths(number_of_steps):
We are
defining a function called numberPaths which takes the number of steps (number_of_steps) as the input value
and returns the number of possible ways there are to climb number_of_steps steps if you are
allowed to skip steps but no more than 1 step at a time.
def factorial(n):
if n == 0:
return 1
This is the
base case of the recursive function to find the factorial of a number, n.
else:
return n * factorial(n-1)
This is
the recursive part of the function that calls the function itself with factorial(n-1).
def combination(n,r):
return
int((factorial(n)/(factorial(r)*factorial(n-r))))
This is
the definition to find the number of combinations of r objects from a set of n objects.
count = 0
We set
the counter count at 0.
if number_of_steps %2==0:
for i in range (int(number_of_steps/2+1)):
combos = combination(number_of_steps -i,i)
count = count + combos
Recall
that range(j) gives us a list of numbers from 0 through (j-1). Thus, this section states that if number_of_steps is an even number,
then we will add to count:
C(number_of_steps,0)
+ C(number_of_steps -1,1) + C(number_of_steps -2,2) + … + C(number_of_steps /2,
number_of_steps /2).
For
example, if number_of_steps is equal to 6, then we will add to the count: C(6,0)+C(5,1)+C(4,2)+C(3,3)
since the range(6/2+1)=[0,1,2,3].
else:
for i in range (int((number_of_steps +1)/2)):
combos = combination(number_of_steps
-i,i)
count = count + combos
Similarly
for odd numbers, we add to count:
C(number_of_steps,0)
+ C(number_of_steps -1,1) + …
+ C([number_of_steps
-(number_of_steps +1)/2-1],[(number_of_steps+1)/2-1]).
For
example, if k is equal to 7, then we will add to the counter:
C(7,0) +
C(6,1) + C(5,2) + C(4,3) since the range ((7+1)/2) = [0,1,2,3].
return int(count)
The final step is to
return count which is now equal to the total number of
ways to climb number_of_steps steps.
If we compare the results
from the previous algorithm with this one, we see that the sum of the number of
combinations for which (n+r) is a constant is equal to a term of the Fibonacci
sequence! Let’s examine why this is so.
When teaching
combinations many mathematics teachers show students the relationship between
Pascal’s triangle and the combinations of r
objects from a set of n objects.
Pascal’s triangle starts by writing the number 1 at
the top which is considered row 0. Then,
to construct the terms in the row below, add the number above and to the left
with the number above and to the right to find the new value. If there is not a
number above either to the right or to the left, then substitute a zero in its
place. Rows 0 through 7 of Pascal’s
triangle are shown below:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
How is this related to
combinations? If we consider the
left-most entry in each row as part of column 0, an entry to the right as part
of column 1, and so on, then each entry in Pascal’s triangle represents C(n,r)
where n is the row number and r is the column number. See below:
C(0,0)
C(1,0) C(1,1)
C(2,0) C(2,1) C(2,2)
C(3,0) C(3,1) C(3,2) C(3,3)
C(4,0) C(4,1) C(4,2) C(4,3) C(4,4)
C(5,0) C(5,1) C(5,2) C(5,3) C(5,4) C(5,5)
C(6,0) C(6,1) C(6,2) C(6,3) C(6,4) C(6,5) C(6,6)
C(7,0) C(7,1) C(7,2) C(7,3) C(7,4) C(7,5) C(7,6) C(7,7)
Thus, we see that
C(n,r-1) + C(n,r) = C(n+1,r) according
to how the entries of Pascal’s triangle are calculated.
Now we go back to the
question sparked by the two different algorithms for finding the number of ways
to climb 100 steps: Why is it that the
sum of the number of combinations for which (n+r) is a constant is equal to a
term of the Fibonacci sequence? Ron
Knott elegantly explains this relationship between the Fibonacci sequence and
Pascal’s triangle. (http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html#pascal)
Let’s rewrite Pascal’s triangle so that it is left-justified and examine the
sum of the diagonals, three of which are highlighted below. We see the Fibonacci sequence emerges!
1
|
||||||||
1
|
1
|
|||||||
1
|
2
|
1
|
Diagonal Sum = 8
|
Diagonal Sum = 13
|
||||
1
|
3
|
3
|
1
|
Diagonal Sum = 21
|
||||
1
|
4
|
6
|
4
|
1
|
||||
1
|
5
|
10
|
10
|
5
|
1
|
|||
1
|
6
|
15
|
20
|
15
|
6
|
1
|
||
1
|
7
|
21
|
35
|
35
|
21
|
7
|
1
|
|
1
|
8
|
28
|
56
|
70
|
56
|
28
|
8
|
1
|
Next
we rewrite the entries of the left-justified Pascal’s triangle with the
combinations of r objects from a set
of n object
C(0,0)
|
||||||||
C(1,0)
|
C(1,1)
|
|||||||
C(2,0)
|
C(2,1)
|
C(2,2)
|
n+r=5
|
n+r=6
|
||||
C(3,0)
|
C(3,1)
|
C(3,2)
|
C(3,3)
|
n+r=7
|
||||
C(4,0)
|
C(4,1)
|
C(4,2)
|
C(4,3)
|
C(4,4)
|
||||
C(5,0)
|
C(5,1)
|
C(5,2)
|
C(5,3)
|
C(5,4)
|
C(5,5)
|
|||
C(6,0)
|
C(6,1)
|
C(6,2)
|
C(6,3)
|
C(6,4)
|
C(6,5)
|
C(6,6)
|
||
C(7,0)
|
C(7,1)
|
C(7,2)
|
C(7,3)
|
C(7,4)
|
C(7,5)
|
C(7,6)
|
C(7,7)
|
|
C(8,0)
|
C(8,1)
|
C(8,2)
|
C(8,3)
|
C(8,4)
|
C(8,5)
|
C(8,6)
|
C(8,7)
|
C(8,8)
|
As
expected, the terms in the diagonal whose sum is a term of the Fibonacci
sequence contains combinations for which (n+r) is a constant. Note that in this Pascal’s triangle, each
entry is the sum of the number directly above and the number above and to the
left (since we left-justified the columns.)
Thus:
C(7,0)=C(6,0)
C(6,1)=C(5,1) + C(5,0)
C(5,2)=C(4,2) + C(4,1)
C(4,3)=C(3,3) + C(3,2)
C(6,1)=C(5,1) + C(5,0)
C(5,2)=C(4,2) + C(4,1)
C(4,3)=C(3,3) + C(3,2)
If
we set Fk as the kth term of the Fibonacci sequence, and Fk-1
and Fk-2 as the (k-1)th and (k-2)th terms of the Fibonacci sequence,
respectively, we see that the sum of the terms in the blue diagonal (Fk)
is equal to the sum of the terms in the yellow diagonal (Fk-1) plus
the sum of the terms in the green diagonal (Fk-2). Thus, we see why the sum of the number of
combinations for which (n+r) is a constant, k results in the kth term of the
Fibonacci sequence.
Who
would have imagined all of these mathematical connections when first
encountering the question of how many ways there are to climb 100 steps if
you’re allowed to skip steps but no more than 1 at a time? Tackling this problem through programming using
different algorithms led to a truly rich discussion of the connections among
combinations, Pascal’s triangle, and the Fibonacci sequence.
Comments
Post a Comment