Enumerative Combinatorics: "Climbing Stairs" Challenge


#1

Over this weekend, with some feedback provided by the GitHub code collections, I have developed the Javascript program to solve one of the advanced Recursion challenges listed in Ch. 9 “Algorithm Challenges The Dojo Collection”. The 2nd and 3rd additional tasks are not solved yet…

One of the challenges I had is to implement a recursive approach in the main function Dojo_Stairs_Exersizes(num), so “for” loops were used to produce the “footstep configurations” before array is being passed to a recursion function MakeCombo(arr).

Any suggestions or comments are welcomed, if you think this problem can be solved differently or more efficiently… Can we solve this problem only recursively?

“Climbing Stairs”

Given:
Speros walks the stairs at the Dojo multiple times every day. Often he takes 2 stairs at a time, to work his quadriceps; he’s just that way. Other days he mixes it up: with every footstep, he randomly chooses to take 1 stair or 2. You are given an integer representing the total number of stairs. Determine all ways to walk the stairs. Given 4 , return [[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]] . Solve recursively with no loops. And don’t forget to get yourself some exercise during the bootcamp, as well.

Second: assuming you always start with a left foot, return only those ways that end with a right step . So, given 4 , you should return [[1,1,1,1], [2,2]] .

Third: instead of only returning those that end with a right step, only return those where the total number of steps climbed with left foot equal those climbed with right. So, given 4 , you should return [[1,1,1,1], [1,2,1], [2,2]] .

//This function configures footstep configurations with a given integer representing the total number of stairs...
//NOTE: This method is imited to a maximum of 2 stairs footsteps only. 

function Dojo_Stairs_Exersizes(num){
    if (isNaN(num) || (num === String(num)) || (num == undefined)){
			return "Invalid Number Input";			
		}    
    if (num <= 1){
        return false;
    }
    var Exersize = [];  
    var combinations = function (val, arr){
        let temp = val;
        let doubles = 1;
        let _RESULT = [];
        let arrAfter = [];
        for (var i = 1; i <= temp; i++){
            arr.push(1);
        }       
        _RESULT = _RESULT.concat(ComboMaker(arr));
        for (var k = 1; k <= Math.floor(val/2); k++){
            for (var j = 1; j <= doubles; j++)
            {
                arrAfter.push(2);
            }          
            _RESULT = _RESULT.concat(ComboMaker(arr.slice(0, temp - (1 + arrAfter.length)).concat(arrAfter)));
            temp--;
            doubles++;
            arrAfter = [];
        }
        return _RESULT;            
    };
    return combinations(num, Exersize);    
}

//This recursive method is very powerful and it is designed to produce ALL possible combinations 
//of ANY given values in a valid array of ANY size greater than 1, regardless if the values are repeated or not; 

function ComboMaker(arr) {
    if (!Array.isArray(arr)){
        throw Error;
    }
    var _OUTPUT = new Array();
    if (arr.length === 1) {
        _OUTPUT.push(arr);        
        return _OUTPUT;
    }
    for (var i = 0; i < arr.length; i++) {
        var arrBefore = [arr[i]];
        var arrAfter = arr.slice(0, i).concat(arr.slice(i + 1));
        if (arrBefore[0] !== arrAfter[i]){               
            var Combo =  ComboMaker(arrAfter);       
            for (var j = 0; j < Combo.length; j++){           
                _OUTPUT.push(arrBefore.concat(Combo[j]));                 
            }
        }
    }
    return _OUTPUT;
}

console.log(Dojo_Stairs_Exersizes(14)); //Produces the total of 609 combinations for 14 stairs only...