# ETOOBUSY ðŸš€ minimal blogging for the impatient

# PWC112 - Climb Stairs

**TL;DR**

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

# The challenge

You are given

`$n`

steps to climbWrite 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:

**F**or each element, you can take 1 step or 2, but only**I**f there are 2 steps or more,**B**ecause 1 step has 1 allowed move only.**O**n each alternative, you just sum recurrently,**N**either choice being the preferred.**A**ll you have to do is**C**ontinue along the**C**ourse 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 ðŸ™„