3
\$\begingroup\$

I have a JavaScript function that takes in a user number (total amount placed on a betting table in denominations of 50) and returns an Array of the optimum chips (lowest # required) to form each stack.

My function works, the correct array for each value tested is output - but since this should be running on the client browser with a fast response time for smooth UI I feel like the code is not optimised.

Is there a better, more efficient (+ mathematically solid) way of computing the same output?

Any suggestions would be appreciated.

//number will be validated before running through function to make sure it has a factor of 50.

function chipStack(number) { 
    var k = 0; //1k chip
    var f = 0; //500 chip
    var t = 0; //300 chip
    var o = 0; //100 chip
    var fi = 0; // 50 chip

    k = Math.floor(number / 1000);
    var number2 = number % 1000

    if (number2 === 0) {
        return [k, f, t, o, fi];
    } else {
        f = Math.floor(number2 / 500)
        var number3 = number2 % 500
    }

    if (number3 === 0) {
        return [k, f, t, o, fi];
    } else {
        t = Math.floor(number3 / 300)
        var number4 = number3 % 300
    }

    if (number4 === 0) {
        return [k, f, t, o, fi];
    } else {
        o = Math.floor(number4 / 100)
        var number5 = number4 % 100
    }

    if (number5 === 0) {
        return [k, f, t, o, fi];
    } else {
        fi = Math.floor(number5 / 50)
        var number6 = number5 % 50
    }

    if (number6 === 0) {
        return [k, f, t, o, fi];
    } else {
        return "Something isn't right " + number6;
    }
}
\$\endgroup\$
  • \$\begingroup\$ I guess you could write the code to look more compact, but inlined as it is here should execute fast. \$\endgroup\$ – TonyWilk Mar 20 '14 at 17:31
  • \$\begingroup\$ There won't be performance problems, but there are several poor programming practices in that code (else after return, var inside conditional code, etc). \$\endgroup\$ – Pointy Mar 20 '14 at 17:33
2
\$\begingroup\$

You could compress the code as follows. It doesn't check for early exit conditions, but since it's running on the front-end anyway, i.e. not at high volumes, the performance won't be noticeably degraded.

function chipStack(n){
    var chipValues = [1000,500,300,100,50];
    var stack = [];
    chipValues.forEach(function(e,i){
        stack.push(Math.floor(n / e));
        n -= (stack[stack.length-1] * e);
    })
    return stack;
}
\$\endgroup\$
1
\$\begingroup\$

Since you asked for mathematical background…

In general, the Change-making problem is a knapsack problem, which is NP-hard. However, for sane sets of currency denominations, a simple greedy algorithm works.

For your set of denominations, { 1000, 500, 300, 100, 50 }, the greedy algorithm applies. (There is, however, an amount with two optimal solutions: 600 = 500 + 100 = 300 + 300.) Therefore, your greedy algorithm and @MartVandeVen's simplified implementation of it will work.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.