Staircase Problem Code Body

staircase.js

//Let us make a table of factorials as I feel they're
//going to be really useful.
var maxNStored = 1;
var storedFactorials = [1n, 1n]
function getFactorial(n){
    //We can say that if n is not in our stored factors, no other factorials
    //are in there. Don't worry, we can't fill that stored factorial list
    //up too big as factorials get big FAST.
    if(n > maxNStored){
        let factorial = storedFactorials[maxNStored];
        for(let i = maxNStored + 1; i <= n; ++i){
            factorial *= BigInt(i);
            storedFactorials.push(factorial);
        }
        maxNStored = n;
    }
    return storedFactorials[n];
}

//The factorial if you divide m! out n! in this case we are better off without
//using recursion as we can define the factorial with a straight for loop.
//We can also sneak in the other divisors 
function factorialQuotient(n, m){
    let factorial = 1n;
    for(let factor = n; factor > m; factor--){
        factorial *= BigInt(factor);
    }

    return factorial;
}

function getUniqueCombinationCountOf(a, b, c){
    //The number of ways we could combine these if a, b and c were
    //all distinguishable would just be a + b + c.
    //but a, b and c are all distinguishable
    //but if they are indistinguishable, you want to throw
    //two cominations that are the same out.
    //So, you have (a + b + c)! for the base value,
    //you are choosing all of them, so (n - r)! = 1
    //and then you remove duplicates of subcombinations
    //of a, b, c or a!, b!, c! or...
    //(a + b + c)! / (a!*b!*c!);
    //Unfortunately, a + b + c could be a HUGE number,
    //factorials grow FAST, so we should divide out c
    //ahead of time.
    let sortedABCCount = [a, b, c].sort();
    const smallestFactorial1 = getFactorial(sortedABCCount[0]);
    const smallestFactorial2 = getFactorial(sortedABCCount[1]);
    return factorialQuotient((a + b + c), sortedABCCount[2]) / (smallestFactorial1 * smallestFactorial2);
}

var prevPermutations = {};
function stepPerms(n){
    //Before we do anything, check if we have already encountered this
    //staircase before, if so, we can just return that number as two staircases
    //with the same number of stairs will have the same number of combinations
    if(n in prevPermutations){
        return prevPermutations[n];
    }    
    
    //
    //The first thing to note is that we are looking for all
    //a, b and c such that a + 2 * b + 3 * c = n stairs
    //and then get all permutations and combinations of a set of
    //a 1s, b 2s, and c 3s. I can tell we will need another function
    //that computes this.
    //
    //In the meanwhile, we can just walk through values, b and c
    //such that their sum is less then or equal to n.
    //then a is just n - 2 * b + 3 * c.
    //To keep the number low, ever time we sum, we modulo
    //At the end, or if the number if the sum will exceed MAX_SAFE_INTEGER
    //To avoid overflow.
    //Also, JS now supports BigInt, so... HAHAHAHA!!!
    let sum = 0n;
    const modNum = BigInt(10000000007);

    //We will run over c first because it will create the shortest outer loop
    const maxC = Math.floor(n / 3.0);
    for(let c = 0; c <= maxC; ++c){
        const cTimes3 = c * 3;
        const maxB = Math.floor((n - cTimes3) / 2.0);
        for(let b = 0; b <= maxB; ++b){
            const bTimes2 = b * 2;
            const a = n - cTimes3 - bTimes2;

            //Always check to see if we are going over the max safe JS integer
            //to avoid overflow. Luckily, because our answer is modulo,
            //we can apply modulo to our sum as we go.
            const comboCountOfABC = getUniqueCombinationCountOf(a, b, c);
            if(BigInt(sum + comboCountOfABC) >= Number.MAX_SAFE_INTEGER){
                sum += ((sum % modNum) + comboCountOfABC);
            }
            else{
                sum += comboCountOfABC;
            }
        }
    }

    //When we are done, always apply the modulo again to stay within
    //the requirements of the function and store the result so we do
    //not have to compute it again.
    prevPermutations[n] = sum % modNum;
    return prevPermutations[n];
}