Davis’ Staircase

Find all combinations around three numbers that sums n

Problem Statement

David has a number of staircases and he likes to climb each staircase in 1,2 and 3 steps at a time. Being a very precocious child, he wonders how many ways there are to reach the top of their staircase.

Given the respective heights for each of the s staircases in his house, find and print the number of ways he can climb each staircase.

Example, find all ways David can climb each staircase

Considerations

The secret to solve any given problem is to find the real problem and ignore everything else.

There are details they are not relevant for the algorithm to solve.

Relevant details

1. climb each staircase in 1,2 and 3 steps at a time
2. how many ways there are to reach the top
3. Given the respective heights for each of the s staircases

Decompose the problem

Given the height n of the one staircase. Davis could climb using 1,2, 3 steps at a time. Let’s rephrase the just mentioned statements so could build an algorithm around it.

So, we are asked, to find all the combinations (recursion) possible around three numbers (1,2,3). Each of this combinations must meet certain criteria, their sum must be equal to the given height n .

All combinations that sums 5

Google Bard

Now more than ever I understand why Google was hesitating to release Generative AI technology given the Google search was way more accurate than any state of the art Gen AI tool. Anyway I love Google Bard since it helps me as a companion to solve problems besides its lacks in accuracy. In the resources section I left my conversation with Google Bard (Maybe my prompts were not good enough to make myself clear and that is why Bard couldn’t understand my problem better).

Combinations vs Permutations

In a combination, the elements of the subset can be listed in any order. In a permutation, the elements of the subset are listed in a specific order

Here’s an easy way to remember: permutation sounds complicated, doesn’t it? And it is. With permutations, every little detail matters. Alice, Bob and Charlie is different from Charlie, Bob and Alice (insert your friends’ names here).

Combinations, on the other hand, are pretty easy going. The details don’t matter. Alice, Bob and Charlie is the same as Charlie, Bob and Alice.

Thanks to BetterExplain and TeachTarget for this definitions.

The algorithms

There are several algorithms which can used to find all the possible combinations around three particular numbers.

Brute force (On²)

The simplest one. It will find all the combinations around three numbers with no restrictions. This could be very inefficient since it generate all possible combinations that are not relevant for the problem to be solved.

Backtracking

More efficient than brute force. It will start with an empty list, the adds one of the three numbers one by one. It backtracks whenever one combination is not meeting the criteria.

Dynamic programming

This is the fastest and more optimal choice to find all the combinations around (1,2,3) that meets that criteria sum(combination) = n .

The implementation

1. The first line checks if the height is negative. If it is, the function returns 0.
2. The second line checks if the height is less than 1. If it is, the function returns 1.
3. The third line checks if the computation for the given height has been performed before. If it has not been performed, the function recursively calls itself to compute the number of step permutations for the height-1, height-2, and height-3step pyramids. The function then stores the result in the memo map.
4. The fourth line returns the value from the memo map.

Backtracking with caching

Resources

I couldn’t get Google Bard to get me a correct answer here but it was quite nice and helpful to wrap my mind around the problem

What is combination and permutation? | Definition from TechTarget

Easy Permutations and Combinations