ETOOBUSY 🚀 minimal blogging for the impatient
PWC112 - Climb Stairs
On with TASK #2 from the Perl Weekly Challenge #112. Enjoy!
You are given
$nsteps 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.
Input: $n = 3 Output: 3 Option 1: 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
I remember a story about a child - aged about 10 around year 1180 - called Leonardo that was often sent to buy some bread, and had to climb some stairs every day to go back home. He decided that each day he wanted to take a different pattern, either 1 or 2 steps at a time, and wanted to figure out how many different ways he could do this before having to repeat a climbing pattern.
So my question is… is this somehow related to his problem? You know, I have the blessing of forgetting…
- For each element, you can take 1 step or 2, but only
- If there are 2 steps or more,
- Because 1 step has 1 allowed move only.
- On each alternative, you just sum recurrently,
- Neither choice being the preferred.
- All you have to do is
- Continue along the
- Course down to no steps left.
- I guess we’re ready now!
It seems that Leonardo had to climb $42$ steps to come back home from the bakery, and he calculated that it would take $433494437$ days to be forced again on the same pattern… which is more than one million years. Enough!
This also seems to be one of the first cases of off-by-one error but it was not the child’s fault…
The solution can be found here.
Update You might not find any reference in history about a Leonardo being sent to buy bread etc. and this is no coincidence - it was just my invention to give some flavor to the topic 🙄