TL;DR

On with TASK #2 from the Perl Weekly Challenge #112. Enjoy!

The 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
    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

The questions

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…

The solution

Algorithm first:

• 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 reminds me of something…

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 🙄