Sundio - Exercice 2

how_many_ways.ts

namespace Sundio {
    /**
     * Computes how many ways someone can use to climb a given number of stairs by 
     * doing it in groups of two or one stair at time.
     * 
     * @param   stairs  The number of stairs to climb.
     * @returns The number of ways someone can climb the stairs.
     */
    export function howManyWays(stairs: number): number {
        // For known values, return the result directly.
        if (stairs === 2) {
            return 2;
        }
        else if (stairs === 1) {
            return 1;
        }
        else if (stairs === 0) {
            return 0;
        }

        // To reach the last stair we can come from n-1 or n-2 so..
        return howManyWays(stairs-1) + howManyWays(stairs-2);
    }

    /**
     * Computes how many ways someone can use to climb a given number of stairs by 
     * doing it in groups of two or one stair at time.
     * 
     * @param   stairs      The number of stairs to climb.
     * @param   preComputed An array of pre-computed values to reach the stairs.
     * @returns The number of ways someone can climb the stairs.
     */
    export function howManyWaysOptimized(stairs: number, preCoputed: number[] = [0, 1, 2]): number {
        // If we previously computed the value, return it directly.
        if(typeof preCoputed[stairs] !== 'undefined') {
            return preCoputed[stairs]            
        }

        // If we have not computed the value, make the recursive calls to compute it.
        const ways =  howManyWaysOptimized(stairs-1, preCoputed)
                    + howManyWaysOptimized(stairs-2, preCoputed);
        // And cache it.
        preCoputed[stairs] = ways;
        return ways;
    }
}

function getMillis(): number {
    return new Date().getTime();
}

for (let stairs = 0; stairs <= 45; stairs++) {
    console.log('With', stairs, 'stairs.');
    console.log('-----------------------');

    // Unoptimized way
    console.log('Unoptimized way:');
    let mil = getMillis();

    console.log('-> Result:', Sundio.howManyWays(stairs), 'different ways.');

    mil = getMillis() - mil;
    console.log('-> Time spent:', mil, 'ms');

    // Optimized way
    console.log('Optimized way:');
    mil = getMillis();

    console.log('-> Result:', Sundio.howManyWaysOptimized(stairs), 'different ways.');

    mil = getMillis() - mil;
    console.log('-> Time spent:', mil, 'ms');
    console.log('-----------------------');
}