11) Climbing Stairs

I paired with Russell again and A wild Fibonnacci sequence appeared! The leetcode exercise we paired on was called climbing stairs, and it was one of the more unreasonably tricky (not specifically difficult; more like duplicitous) ones.

The idea is that you have a staircase with n stairs, and you can take them one or two at a time. I picked this exercise for the sole reason that Russell is a competitive stair climber. I’m serious. Before talking to him, I hadn’t known it was a sport.

The exercise wants us to return the number of valid, unique sequences of one or two step sequences that will get us exactly to the final stair.

Here is the pseudocode I worked through prior to coding:

    // dynamically find what the output for n would be for every additional step in n, evaluate recursively some function
    // climb stairs, continue until we reach
    // assumption n=3
    // 1, 1, 1
    // 2, 1
    // 1, 2
    // n = 4
    // 2, 2
    // 1, 1, 1, 1
    // 1, 1, 2
    // 2, 1, 1
    // 1, 2, 1
    // should return 5
 
    // n = 1
    // 1
    // return 1
 
    // even odd
    // % 
 
    // 1 -> 1
    // 2, 2
    // 3 -> 3
    // 4 -> 5
    // 5 -> 8
 
    // n=5
    // 1, 1, 1, 1, 1
    // 1, 1, 1, 2
    // 1, 1, 2, 1
    // 1, 2, 1, 1
    // 2, 1, 1, 1
    // 1, 2, 2
    // 2, 1, 2
    // 2, 2, 1
 
    // assumption the only way to get where you are is from an existing pathway that we've added to our sum in one of the past 2n's
 
    // If there are no previous values, create an object - > {1: 1, 2: 2} default value
    // if the current value has no previous value, I want to use the past 2 values to generate and save it to the object
    // if there aren't 2 previous past values <- this won't happen because of default value passed into extra argument
    // if know what the original opassed in value is that's separate from this interative progress through all the values UP to that point,
    // if the iterative value is the same as the passed in value, then I will return things the same way
    // base case vs. enter another recursive case

I had a sort of horrifying (despite it being a mock interview) moment where my brain felt like a completely empty space. Russell suggested that I work through each possible input to see if I could find a pattern. This ended up being a big hint, as the outputs were the fibonacci sequence. I didn’t totally believe it, so I tried to reason as to why this might be. Maybe it’s intuitive to someone else, but to me this seemed strange.

The explanation is that for each n value, there are only two ways to get there with the current configuration of stair-movements - you can get there from n-1 or from n-2.

Why

…Okay actually, I’m really not sure why this is the case still. I had to figure it out here if you’re curious or confused
My confusion lies here: if you combine the number of valid movement to n-1, aren’t most of them in common with n-2?)
I thought about it for awhile (I asked ChatGPT), and because n-2 must always take a 2-step move to arrive at n and n-1 must always take a 1-step move to arrive at n, there is no overlap. Each pathway that arrives at n-1 must have at least a slight variation from a pathway that arrives at n-2, otherwise, well, it would arrive at n-2 instead of n-1.
It’s tricky because many of the variations between the two probably are quite slight. In my opinion, understanding why this situation resolves to the Fibonacci sequence is much less intuitive than writing the Fibonacci sequence.

This is what I arrived at after 40 minutes with some major hints from Russell. I also had practiced A) Dynamically Programming Fibonnacci before as an introduction to Dynamic programming. I hadn’t really gotten it down pat, but I think that not being completely fresh to the idea really helped.

var climbStairs = function(n) {
 
    let initial = new Map()
    initial.set(1, 1)
    initial.set(2, 2)
    //
 
    // recursive case
    // setting new values
 
    let climbStairsRecursively = function(n){
 
        // I would start where n = 3
        // what I'm doing is starting with the final value
 
        if (initial.has(n)){
            return initial.get(n)
        }
 
        if (initial.has(n-1)){
            return initial.get(n-1) + initial.get(n-2)
        } else {
            initial.set(n-1, climbStairsRecursively(n-1))
            return initial.get(n-1) + initial.get(n-2)
        }
    }
 
    return climbStairsRecursively(n)

Russell pointed out that by reversing the conditional and checking for what we DON’T have, we can simplify things, but that we could simplify even farther by just calculating n

 
var climbStairs = function(n) {
 
    let initial = new Map()
    initial.set(1, 1)
    initial.set(2, 2)
 
    let climbStairsRecursively = function(n){
        if (initial.has(n)) return initial.get(n)
 
        initial.set(n, climbStairsRecursively(n-1) + climbStairsRecursively(n-2))
 
        return initial.get(n)
    }
 
    return climbStairsRecursively(n)
};
 

Things I learned

• typos are a real - I misspelled initial a few times, which was an unhelpful var name anyway
• avoid picking difficult to type variable names like initial
• working through example cases is a great thing to do if little else occurs to me. A lot of inspiration struck at this moment. More on that:

Walking Through Example Cases

This might point towards the most difficult part about encountering novel, strange coding puzzles. Somewhere, somehow - I don’t know who put it there - there’s this expectation that you have a stroke of inspiration about how to solve a puzzle. Sometimes I do! Sometimes I have a hunch about what to do. But sometimes there is very little. Or the hunches lead me in the wrong direction.

This sort of approach of “what’s a clever way to do this”, well, it can work sometimes I think. But, it can’t really be relied on.

You know what can be relied on? Doing it manually. I think it’s easy to forget that programming replaces manual operations. Well, it can be hard to replace manual operations if you’re not familiar with them. Eloquence, brevity and abstraction are difficult to arrive at unless there is some ugly, long-winded phrase of axioms to improve upon. In other words, the act of improving nothing is infinitely harder than improving something.

So writing out the expected outcome for a single case seemed like a great exercise. I got to see what my brain did, and abstract. I also got to observe (even if Russell sort of handed them to me) patterns, like the Fibonacci sequence.