loading...

re: A common recursion interview challenge VIEW POST

FULL DISCUSSION
 

Thanks for the article! This was a fun challenge. I'm not the best with vanilla javascript, so all critiques welcomed.

Here's what I came up with:

const ChangeCalculator = function() {
    const values = {
        quarter: 25,
        dime: 10,
        nickel: 5,
        penny: 1
    };

    let allowedCoins, allowedCoinsTemp, amountLeft, solutions, solutionIndex;

    /**
     * Add a single solution to the solutions array
     * using the allowed coins.
     * @return {ChangeCalculator}
     */
    this.addSolution = () => {
        // Order is important here. Highest to lowest denomination.
        ['quarter', 'dime', 'nickel', 'penny'].forEach((coin) => {
            if (allowedCoinsTemp[coin] > 0 && amountLeft >= values[coin]) {
                amountLeft -= values[coin];
                allowedCoinsTemp[coin]--;
                solutions[solutionIndex][coin]++;
                return this.addSolution();
            }
        });

        // Base case (amountLeft == 0)
        return this;
    };

    /**
     * Calculate all solutions to make change for a given amount of cents
     * @param  {int} cents
     * @return {array}
     */
    this.calculate = (cents) => {
        this.resetSolutions();
        this.setMaxCoins(cents);

        do {
            this.nextSolution(cents)
                .addSolution()
                .setAllowedCoins();
        } while (solutions[solutionIndex].penny != cents);

        // return solutions; If you want to see all the solutions, 
        // but the problem requested number of ways.
        return solutions.length;
    };

    /**
    * Prepare to calculate the next solution
    * @param  {int} cents
    * @return {ChangeCalculator}
    */
    this.nextSolution = (cents) => {
        solutionIndex++;
        amountLeft = cents;
        solutions.push({
            quarter: 0,
            dime: 0,
            nickel: 0,
            penny: 0
        });

        return this;
    };

    /**
     * Reset the solutions variables before doing calculations
     * @param {int} cents
     */
    this.resetSolutions = () => {
        solutionIndex = -1;
        solutions = [];
    };

    /**
     * Set the number of each coin that may be used.
     */
    this.setAllowedCoins = () => {
        if(allowedCoins.quarter > 0) {
            allowedCoins.quarter--;
        } else if (allowedCoins.dime > 0) {
            allowedCoins.dime--;
        } else if (allowedCoins.nickel > 0) {
            allowedCoins.nickel--;
        }

        allowedCoinsTemp = Object.assign({}, allowedCoins);
    };

    /**
     * Set the maximum amount of each coin type that may be used.
     * @param {int} cents
     */
    this.setMaxCoins = (cents) => {
        allowedCoins = {
            quarter: Math.floor(cents / values.quarter),
            dime: Math.floor(cents / values.dime),
            nickel: Math.floor(cents / values.nickel),
            penny: cents
        };

        allowedCoinsTemp = Object.assign({}, allowedCoins);
    };
};

To run it:

const calculator = new ChangeCalculator();
const solutions = calculator.calculate(42);
console.log(solutions);
Code of Conduct Report abuse