Staircase Steps Challenge
Staircase Python Challenge
A child is running up a staircase with N steps, and can hop 1 step, 2 steps or 3 steps at a time.
Write a Python program that prompts the user to enter the number of steps in a staircase. The program should then provide the following information:
1) The total number of possible ways the child can run up the stairs.
2) A breakdown of all the possible combinations to climb the stairs.
For example, a staircase with three steps:
There are 4 ways to climb.
Possible ways:
1 1 1
1 2
2 1
3
Expected Output
Enter the number of steps: 6 Number of ways to climb: 24 All possible ways to climb: [1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 2] [1, 1, 1, 2, 1] [1, 1, 1, 3] [1, 1, 2, 1, 1] [1, 1, 2, 2] [1, 1, 3, 1] [1, 2, 1, 1, 1] [1, 2, 1, 2] [1, 2, 2, 1] [1, 2, 3] [1, 3, 1, 1] [1, 3, 2] [2, 1, 1, 1, 1] [2, 1, 1, 2] [2, 1, 2, 1] [2, 1, 3] [2, 2, 1, 1] [2, 2, 2] [2, 3, 1] [3, 1, 1, 1] [3, 1, 2] [3, 2, 1] [3, 3]
Source Code
## Function to find possible ways to climb the stairs
def find_steps(n, steps):
if n == 0:
return [[]]
if n < 0:
return []
ways = []
for step in steps:
for way in find_steps(n - step, steps):
ways.append([step] + way)
return ways
## Function to count the number of ways found by of ways found by the "find_steps" function
def count_ways(n, steps):
return len(find_steps(n, steps))
steps = [1, 2, 3]
n = int(input("Enter the number of steps: "))
ways = find_steps(n, steps)
print("Number of ways to climb: ", count_ways(n, steps))
print("All possible ways to climb: ")
for way in ways:
print(way)
In this program, "find_steps" is a recursive function that finds all the possible ways to climb the stairs. It does this by subtracting each possible step from the total number of steps until it reaches zero (which means it found a way) or less than zero (which means the way is not possible). The “count_ways” function simply counts the number of ways found by the "find_steps" function. The program then asks the user to input the number of steps and prints out the number of ways and all the possible ways to climb the stairs.
To keep practicing Python, check out other Practity projects
