Task — Climb stairs

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.

Examples

Example 1
Input: $n = 3
Output: 3
    Option 1: 1 step + 1 step + 1 step
    Option 2: 1 step + 2 steps
    Option 3: 2 steps + 1 step

Example 2
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

Analysis

The easiest way to this - in my opinion - is recursion.

So we try 1 step and then 2 steps from where we've already go to and if:

• we've arrived at the top, we record that and keep looking, or
• we're not there yet, we take another step or two, or
• we've overshot we give up and try the next combination.

The standard new house in the UK - including mine - has 13 steps from the ground (US first) floor to the first (US second) floor, and there are 377 ways of doing that. I've only shown a few of them in the examples.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-05-10
use utf8;     # Week 112 - task 2 - Climb stairs
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

my ($options);

climb_stairs(4);
climb_stairs(8);
climb_stairs(13);

sub climb_stairs {
    
    my ($landing, $n);
    
    # initialise
    $landing = $_[0];
    $options = '';
    climb($landing, '   ');
    
    say qq[\nInput:  $landing stairs];
    $n = $options =~ y|\n|\n|;
    say qq[Output: $n options:\n$options];
}

sub climb {
    
    my ($stairs_left, $so_far, $j);
    
    ($stairs_left, $so_far) = @_;
    
    # arrived
    if ($stairs_left == 0) {
        $options .= substr($so_far, 0, -2) . qq[\n];
        return;
        
    # overshot
    } elsif ($stairs_left < 0) {
        return;
        
    # not there yet 
    } else {
        for $j (1 .. 2) {
            climb($stairs_left - $j, $so_far . qq[$j + ]);
        }
    }
}

19 lines of code

I completed this challenge after the closing date
and it has not been submitted to GitHub

Output

Input:  4 stairs
Output: 5 options:
   1 + 1 + 1 + 1 
   1 + 1 + 2 
   1 + 2 + 1 
   2 + 1 + 1 
   2 + 2 


Input:  8 stairs
Output: 34 options:
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 
   1 + 1 + 1 + 1 + 1 + 1 + 2 
   1 + 1 + 1 + 1 + 1 + 2 + 1 
   1 + 1 + 1 + 1 + 2 + 1 + 1 
   1 + 1 + 1 + 1 + 2 + 2 
   1 + 1 + 1 + 2 + 1 + 1 + 1 
   1 + 1 + 1 + 2 + 1 + 2 
   1 + 1 + 1 + 2 + 2 + 1 
   1 + 1 + 2 + 1 + 1 + 1 + 1 
   1 + 1 + 2 + 1 + 1 + 2 
   1 + 1 + 2 + 1 + 2 + 1 
   1 + 1 + 2 + 2 + 1 + 1 
   1 + 1 + 2 + 2 + 2 
   1 + 2 + 1 + 1 + 1 + 1 + 1 
   1 + 2 + 1 + 1 + 1 + 2 
   1 + 2 + 1 + 1 + 2 + 1 
   1 + 2 + 1 + 2 + 1 + 1 
   1 + 2 + 1 + 2 + 2 
   1 + 2 + 2 + 1 + 1 + 1 
   1 + 2 + 2 + 1 + 2 
   1 + 2 + 2 + 2 + 1 
   2 + 1 + 1 + 1 + 1 + 1 + 1 
   2 + 1 + 1 + 1 + 1 + 2 
   2 + 1 + 1 + 1 + 2 + 1 
   2 + 1 + 1 + 2 + 1 + 1 
   2 + 1 + 1 + 2 + 2 
   2 + 1 + 2 + 1 + 1 + 1 
   2 + 1 + 2 + 1 + 2 
   2 + 1 + 2 + 2 + 1 
   2 + 2 + 1 + 1 + 1 + 1 
   2 + 2 + 1 + 1 + 2 
   2 + 2 + 1 + 2 + 1 
   2 + 2 + 2 + 1 + 1 
   2 + 2 + 2 + 2 


Input:  13 stairs
Output: 377 options:
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 2 
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 1 
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 + 1 
   1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 + 2 
   and so on, ending with:
   2 + 2 + 2 + 2 + 2 + 1 + 2 
   2 + 2 + 2 + 2 + 2 + 2 + 1