Combinatorics of cardgame hand evaluation for runs, with wildcards and duplicates

Question

Working on a rummy style game with several twists:

Using two 5 suite decks instead of one 4 suite deck (116 cards total).
Suites run from 3 to King and each deck has 3 jokers (so no 2 and no Ace).
11 rounds, first round each player has 3 cards, final round each player has 13 cards.
Besides Jokers being wild, each card value takes a turn being wild and this corresponds to the number of cards in your hand.
So round one 3's are wild round two 4's are wild ... round 11 Kings are wild (Kings have a numeric value of 13).

The goal is to lay down all your cards. Once someone has 'gone out'(laid down all cards) remaining players have one turn to also lay down all cards or as many valid sets/runs as they can. You gain points for whatever cards are left in your hand.

Players can only lay cards down in sets or runs that have a minimum of 3 cards in them, i.e set: {3:c, 3:d, 3:h}, run: {3:c, 4:c, 5:c}. There are also rounds where you have to get a set/run with more then 3 cards because the number of cards in hand is not evenly divisible by 3.

To start hand evaluation I split the cards into these structures:

var suites = {
    'clubs' : [],
    'diamonds' : [],
    'hearts' : [],
    'spades' : [],
    'stars' : []
};
var wilds = [];
var buckets = {
    3 : [],
    4 : [],
    5 : [],
    6 : [],
    7 : [],
    8 : [],
    9 : [],
    10 : [],
    11 : [],
    12 : [],
    13 : []
};
//can have more then one run/set so these are used to hold valid runs/sets
var runs = [];
var sets = [];
var r_num = -1; //starts at -1 so ++ will give 0 index
var s_num = -1;

And then delete any suites/buckets that don't have any cards in them.
Set evaluation is pretty straight forward but run evaluation is... not so straight forward.

I've come up with this range based run evaluation

    for (var s in suites){
        if(suites.hasOwnProperty(s)){
            var suite_length = suites[s].length;
            if(suite_length >= 2){ //only evaluate suits with at least 2 cards in them
                var range = suites[s][suite_length - 1].value - suites[s][0].value;
                r_num++;
                runs[r_num] = [];

                if( (range - 1) >= wilds.length && (range - 1) == suite_length){
                    suites[s].forEach(function(card){ //large range needs several wilds
                        runs[r_num].push(card);
                    });
                    while(runs[r_num].length <= (range + 1) && wilds.length != 0){
                        runs[r_num].push(wilds.pop());
                    }
               }else if(range == 1 && wilds.length >= 1){ //needs one wild
                    suites[s].forEach(function(card){
                        runs[r_num].push(card);
                    });
                    runs[r_num].push(wilds.pop()); 
                }else if( range == suite_length && wilds.length >= 1){ //also needs one wild
                    suites[s].forEach(function(card){
                        runs[r_num].push(card);
                    });
                    runs[r_num].push(wilds.pop());
                }else if( (range + 1) == suite_length){ //perfect run
                    suites[s].forEach(function(card){
                        runs[r_num].push(card);
                    });
                }
            }
        }
    } 
};

This works for a lot of cases but it struggles with duplicates in the suite. One of the toughest cases I've run into while play-testing it is along the following lines:
{3:clubs, wild, 3:spades, 4:clubs, 5:clubs, 6:clubs, 6:clubs 7:clubs, 8:clubs, 10:spades, 10:hearts, wild}

So 12 cards in hand and a valid lay down can be formed: which would look like this:
sets: [{3:c, 3:s, wild},{10:s, 10:h, wild}]
runs: [{4:c, 5:c, 6:c}, {6:c, 7:c, 8:c}]

Unfortunately I end up with something along these lines:
sets: [{6:c, 6:c, wild}, {10:s, 10:h, wild}]
runs: [{3:c,4:c,5:c}]
OR (depending on if I evaluate for sets or runs first)
sets: [{10:s, 10:h, wild, wild}]
runs: [{3:c, 4:c, 5:c, 6:c, 7:c, 8:c}]
with the other cards left over.

I also run into issues in early rounds when I have hands like this:
{6:h, 7:h, 7:h, 8:h}
The above is an issue when trying to lay down a partial hand.
{6:h, 7:h, 8:h} is a valid run in partial hand situations and the player would only be left with 7 points. But because I don't get rid of duplicates it doesn't evaluate this as a possible run and the player is left with all the points(28).

My question is: Is there a better way/algorithm for doing this entire process?

My current thoughts for solving this are kinda depressing as they involve lots of case/if statements for specific hand lengths/game situations/suite lengths. Where sometime I remove duplicates sometimes I don't sometimes I split the suite sometimes I don't... Lots of headaches basically where I'm not sure that I've covered all possible hands/partial lay down situations.

Answer 1

This is a fully functioning hand evaluator (although there is one part that still needs optimising for efficiency). It uses recursion to check all possible combinations, and returns the one that has the lowest leftover value.

The cards are stored as a 5 by 11 matrix, with values of 0, 1 or 2 representing the number of cards of that type, like this:

    3 4 5 6 w 8 9 T J Q K
CLB 1,0,0,0,2,0,1,0,0,0,0 
DMD 0,0,1,0,1,0,1,0,0,0,0 
HRT 0,0,0,0,0,0,1,1,1,0,0 
SPD 0,1,0,0,1,0,0,0,0,0,0 
STR 0,0,0,0,0,0,0,0,0,0,0 
    jokers: 1   value: 93  

In this representation, a run is a horizontal sequence of non-zeros, and a set is a vertical line that adds up to 3 or more.

The function works recursively by searching a meld, creating a copy of the hand, removing the meld from the copy, and then calling itself on the copy.

(As it is, the recursion is run from the beginning of the matrix; with a better algorithm to permutate through shorter parts of a long meld, the recursion can be run from the current point, thus avoiding checking combinations twice.)

The example generates and evaluates a random hand of 13 cards with kings wild. By un-commenting the code at the bottom, you can enter specific hands to check. (All code after the array clone function is just to run the example and output to the console).

// OBJECT HAND CONSTRUCTOR

function Hand(cards, jokers, round, wilds) {
    this.cards = clone(cards);
    this.jokers = jokers;
    this.wilds = wilds || 0;
    this.round = round;
    this.melds = [];
    this.value = this.leftoverValue();
}

// FIND MELDS AFTER CURRENT POINT

Hand.prototype.findMelds = function(suit, number, multi) {

    if (suit == undefined || number == undefined || multi == undefined) {
        // NOT A RECURSION
        suit = number = multi = 0;
        this.convertWilds();
    }

    // START WITH ONLY JOKERS AS OPTIMAL COMBINATION
    if (this.jokers > 2) {
        for (i = 0; i < this.jokers; i++) {
            this.melds.push({s:-1, n:-1, m:-1});
        }
    this.value -= 25 * this.jokers - (22 - round) * (this.jokers < this.wilds ? this.jokers : this.wilds);
    }

    // SEARCH UNTIL END OR FULL LAY-DOWN
    while (this.value > 0) {

        // FIND NEXT CARD IN MATRIX
        while (this.cards[suit][number] <= multi) {
            multi = 0;
            if (++number > 10) {
                number = 0;
                if (++suit > 4) return;
            }
        }

        for (var type = 0; type < 2; type++) {
            // FIND MELD AT CURRENT POINT
            var meld = type ? this.findSet(suit, number, multi) : this.findRun(suit, number, multi);

            // TRY DIFFERENT LENGTHS OF LONG MELD
            // (to be improved: try permutations with jokers of each length)
            for (var len = 3; len <= meld.length; len++) {

                // CREATE COPY OF HAND AND REMOVE CURRENT MELD
                var test = new Hand(this.cards, this.jokers, this.round, this.wilds);
                test.removeCards(meld.slice(0, len));

                // RECURSION ON THE COPY
                // test.findMelds(suit, number, multi); // USE ONLY WITH MELD PERMUTATION ALGORITHM
                test.findMelds(0,0,0);                 // RESULT OK, BUT MAY CHECK THINGS MULTIPLE TIMES

                // BETTER COMBINATION FOUND
                if (test.value < this.value) {
                    this.value = test.value;
                    while (this.melds.length) this.melds.pop();
                    for (var i = 0; i < len; i++) {
                        // ADD CURRENT MELD (DON'T DESTROY YET)
                        this.melds.push(meld[i]);
                    }
                    // ADD MELDS FOUND THROUGH RECURSION
                    while (test.melds.length) this.melds.push(test.melds.shift());
                }
            }
        }
        multi++;
    }
}

// CHECK IF CARD IS START OF SET

Hand.prototype.findSet = function(s, n, m) {
    var set = [];
    while (s < 5) {
        while (m < this.cards[s][n]) {
            set.push({s:s, n:n, m:m++});
        }
        m = 0; s++;
    }

    // ADD JOKERS
    for (i = 0; i < this.jokers; i++) {
        set.push({s:-1, n:-1, m:-1});
    }
    return set;
}

// CHECK IF CARD IS START OF RUN

Hand.prototype.findRun = function(s, n, m) {
    var run = [], jokers = this.jokers;
    while (n < 11) {
        if (this.cards[s][n] > m) {
            run.push({s:s, n:n, m:m});
        } else if (jokers > 0) {
            run.push({s:-1, n:-1, m:-1});
            jokers--;
        }
        else break;
        m = 0; n++;
    }

    // ADD JOKERS (TRAILING OR LEADING)
    while (jokers-- > 0 && run.length < 11) {
        if (n++ < 11) run.push({s:-1, n:-1, m:-1});
        else run.unshift({s:-1, n:-1, m:-1});
    }
    return run;
}

// REMOVE ARRAY OF CARDS FROM HAND: [{s:x, n:y} ... ]

Hand.prototype.removeCards = function(cards) {
    for (var i = 0; i < cards.length; i++) {
        if (cards[i].s >= 0) {
            this.cards[cards[i].s][cards[i].n]--;
        } else this.jokers--;
    }
    this.value = this.leftoverValue();
}

// GET VALUE OF LEFTOVER CARDS

Hand.prototype.leftoverValue = function() {
    var leftover = 0;
    for (var i = 0; i < 5; i++) {
        for (var j = 0; j < 11; j++) {
            leftover += this.cards[i][j] * (j + 3) // cards count from 0 vs 3
        }
    }
    return leftover + 25 * this.jokers - (22 - round) * (this.jokers < this.wilds ? this.jokers : this.wilds);
}

// CONVERT WILDCARDS TO JOKERS

Hand.prototype.convertWilds = function() {
    for (var i = 0; i < 5; i++) {
        while (this.cards[i][this.round] > 0) {
            this.cards[i][this.round]--;
            this.jokers++; this.wilds++;
        }
    }
    this.value = this.leftoverValue();
}

// UTILS: 2D ARRAY DEEP-COPIER

function clone(a) {
    var b = [];
    for (var i = 0; i < a.length; i++) {
        b[i] = a[i].slice();
    }
    return b;
}

/* ******************************************************************************** */

// UTILS: SHOW HAND IN CONSOLE

function showHand(c, j, r, v) {
    var num = "    3 4 5 6 7 8 9 T J Q K";
    console.log(num.slice(0, 2*r+4) + "w" + num.slice(2*r+5));
    for (var i = 0; i < 5; i++) {
        console.log(["CLB ","DMD ","HRT ","SPD ","STR "][i] + c[i]);
    }
    console.log("    jokers: " + j + "  value: " + v);
}

// UTILS: SHOW RESULT IN CONSOLE

function showResult(m, v) {
    if (m.length == 0) console.log("no melds found");
    while (m.length) {
        var c = m.shift();
        if (c.s == -1) console.log("joker *");
        else console.log(["clubs","dmnds","heart","spade","stars"][c.s] + " " + "3456789TJQK".charAt(c.n));
    }
    console.log("leftover value: " + v);
}

// TEST DATA: CREATE ARRAY OF ALL CARDS TO DRAW FROM

var pack = [{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1}];
for (var i = 0; i < 5 ; i++) {
    for (var j = 0; j < 11; j++) {
        pack.push({s:i, n:j}, {s:i, n:j});
    }
}

// TEST DATA: CREATE 2D ARRAY TO STORE CARDS

var matrix = [];
var jokers = 0;
var round = 10; // count from zero

for (var i = 0; i < 5; i++) {
    matrix[i] = [];
    for (var j = 0; j < 11; j++) {
        matrix[i][j] = 0;
    }
}

// TEST DATA: DRAW CARDS AND FILL 2D ARRAY

for (i = 0; i < round + 3; i++)
{
    var j = Math.floor(Math.random() * pack.length);
    var pick = pack[j];
    pack[j] = pack.pop();
    if (pick.s > -1) matrix[pick.s][pick.n]++;
    else jokers++;
}

// USE THIS TO TEST SPECIFIC HANDS

// round = 10; // count from zero
// matrix = [[0,0,0,0,0,1,0,0,0,0,0],
//           [0,0,0,0,0,1,0,0,0,0,0],
//           [0,0,0,0,0,1,1,1,0,0,0],
//           [0,0,0,0,0,1,0,0,0,0,0],
//           [0,0,0,0,0,1,0,0,0,0,0]];
// jokers = 1;

// CREATE INSTANCE OF HAND OBJECT, EVALUATE AND SHOW RESULT

var x = new Hand(matrix, jokers, round); // no wilds parameter: automatic conversion
showHand(x.cards, x.jokers, x.round, x.value);
x.findMelds();
showResult(x.melds, x.value);

This is an optimised version. The recursions for sets now run from the current point, the recursions for runs still run from 0,0.
Optimising the findSets function to the point where all recursions could be run from the current point would add complications that I think would undo any possible speed gain.
The findRuns and findSets functions now return an array of variations of the runs and sets; this also solves a problem with leading jokers in runs.
The "multi" variable has also been removed, since it was only needed in one particular case which is also solved by running the recursions for sets from 0,0.

// CODE FOR SECOND VERSION REMOVED BECAUSE OF ANSWER LENGTH CONSTRAINTS

Actually, the theoretically "optimised" version proved to be faster only for hands with multiple double cards, and much slower for simple hands, so I decided to make a hybrid version. This is 10% faster than both previous algorithms, for hands of any complexity.
One caveat is that it adds leading jokers in runs to the end of the run for code simplicity, so a *QK run will be displayed as QK*.

// OBJECT HAND CONSTRUCTOR

function Hand(cards, jokers, round, wilds) {
    this.cards = clone(cards);
    this.jokers = jokers;
    this.wilds = wilds || 0;
    this.round = round;
    this.melds = [];
    this.value = this.leftoverValue();
}

// FIND MELDS AFTER CURRENT POINT

Hand.prototype.findMelds = function(suit, number) {

    if (suit == undefined || number == undefined) {
        // NOT A RECURSION: CONVERT WILDS TO JOKERS
        suit = number = 0;
        this.convertWilds();
    }

    // START WITH ONLY JOKERS AS OPTIMAL COMBINATION
    if (this.jokers > 2) {
        for (var i = 0; i < this.jokers; i++) {
            this.melds.push({s:-1, n:-1});
        }
        this.value -= 25 * this.jokers - (22 - round) * (this.jokers < this.wilds ? this.jokers : this.wilds);
    }

    // SEARCH UNTIL END OR FULL LAY-DOWN
    while (this.value > 0) {

        // FIND NEXT CARD IN MATRIX
        while (number > 10 || this.cards[suit][number] == 0) {
            if (++number > 10) {
                number = 0;
                if (++suit > 4) return;
            }
        }

        // FIND RUNS OR SETS STARTING AT CURRENT POINT
        for (var meldType = 0; meldType < 2; meldType++) {

            var meld = meldType ? this.findSet(suit, number) : this.findRun(suit, number);

            // TRY DIFFERENT LENGTHS OF LONG MELD
            for (var len = 3; len <= meld.length; len++) {

                // CREATE COPY OF HAND AND REMOVE CURRENT MELD
                var test = new Hand(this.cards, this.jokers, this.round, this.wilds);
                test.removeCards(meld.slice(0, len));

                // RECURSION ON THE COPY
                meldType ? test.findMelds(suit, number) : test.findMelds(0, 0);

                // BETTER COMBINATION FOUND
                if (test.value < this.value) {
                    this.value = test.value;
                    // REPLACE BEST COMBINATION BY CURRENT MELD + MELDS FOUND THROUGH RECURSION
                    this.melds.length = 0;
                    this.melds = [].concat(meld.slice(0, len), test.melds);
                }
            }
        }
        number++;
    }
}

// FIND RUN STARTING WITH CURRENT CARD

Hand.prototype.findRun = function(s, n) {
    var run = [], jokers = this.jokers;
    while (n < 11) {
        if (this.cards[s][n] > 0) {
            run.push({s:s, n:n});
        } else if (jokers > 0) {
            run.push({s:-1, n:-1});
            jokers--;
        }
        else break;
        n++;
    }

    // ADD LEADING JOKERS (ADDED TO END FOR CODE SIMPLICITY)
    while (jokers-- > 0) {
        run.push({s:-1, n:-1});
    }
    return run;
}

// FIND SET STARTING WITH CURRENT CARD

Hand.prototype.findSet = function(s, n) {
    var set = [];
    while (s < 5) {
        for (var i = 0; i < this.cards[s][n]; i++) {
            set.push({s:s, n:n});
        }
        s++;
    }

    // ADD JOKERS
    for (var i = 0; i < this.jokers; i++) {
        set.push({s:-1, n:-1});
    }
    return set;
}

// REMOVE ARRAY OF CARDS FROM HAND

Hand.prototype.removeCards = function(cards) {
    for (var i = 0; i < cards.length; i++) {
        if (cards[i].s >= 0) {
            this.cards[cards[i].s][cards[i].n]--;
        } else this.jokers--;
    }
    this.value = this.leftoverValue();
}

// GET VALUE OF LEFTOVER CARDS

Hand.prototype.leftoverValue = function() {
    var leftover = 0;
    for (var i = 0; i < 5; i++) {
        for (var j = 0; j < 11; j++) {
            leftover += this.cards[i][j] * (j + 3) // cards count from 0 vs 3
        }
    }
    return leftover + 25 * this.jokers - (22 - round) * (this.jokers < this.wilds ? this.jokers : this.wilds);
}

// CONVERT WILDCARDS TO JOKERS

Hand.prototype.convertWilds = function() {
    for (var i = 0; i < 5; i++) {
        while (this.cards[i][this.round] > 0) {
            this.cards[i][this.round]--;
            this.jokers++; this.wilds++;
        }
    }
    this.value = this.leftoverValue();
}

// UTILS: 2D ARRAY DEEP-COPIER

function clone(a) {
    var b = [];
    for (var i = 0; i < a.length; i++) {
        b[i] = a[i].slice();
    }
    return b;
}

// UTILS: SHOW HAND IN CONSOLE

function showHand(c, j, r, v) {
    var num = "    3 4 5 6 7 8 9 T J Q K";
    console.log(num.slice(0, 2*r+4) + "w" + num.slice(2*r+5));
    for (var i = 0; i < 5; i++) {
        console.log(["CLB ","DMD ","HRT ","SPD ","STR "][i] + c[i]);
    }
    console.log("    jokers: " + j + "  value: " + v);
}

// UTILS: SHOW RESULT IN CONSOLE

function showResult(m, v) {
    if (m.length == 0) console.log("no melds found");
    while (m.length) {
        var c = m.shift();
        if (c.s == -1) console.log("joker *");
        else console.log(["clubs","dmnds","heart","spade","stars"][c.s] + " " + "3456789TJQK".charAt(c.n));
    }
    console.log("leftover value: " + v);
}

// TEST DATA: CREATE ARRAY OF ALL CARDS TO DRAW FROM

var pack = [{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1}];
for (var i = 0; i < 5 ; i++) {
    for (var j = 0; j < 11; j++) {
        pack.push({s:i, n:j}, {s:i, n:j});
    }
}

// TEST DATA: CREATE 2D ARRAY TO STORE CARDS

var matrix = [];
var jokers = 0;
var round = 10; // count from zero

for (var i = 0; i < 5; i++) {
    matrix[i] = [];
    for (var j = 0; j < 11; j++) {
        matrix[i][j] = 0;
    }
}

// TEST DATA: DRAW CARDS AND FILL 2D ARRAY

for (i = 0; i < round + 3; i++)
{
    var j = Math.floor(Math.random() * pack.length);
    var pick = pack[j];
    pack[j] = pack.pop();
    if (pick.s > -1) matrix[pick.s][pick.n]++;
    else jokers++;
}

// USE THIS TO TEST SPECIFIC HANDS

// round = 10; // count from zero
// matrix = [[0,0,0,0,0,1,0,0,0,0,0],
//           [0,0,0,0,0,2,1,1,0,0,0],
//           [0,0,0,1,1,2,0,0,0,0,0],
//           [0,0,0,0,0,1,0,0,0,0,0],
//           [0,0,0,0,0,0,0,0,0,0,0]];
// jokers = 1;

// CREATE INSTANCE OF HAND OBJECT, EVALUATE AND SHOW RESULT


var x = new Hand(matrix, jokers, round); // no wilds parameter: automatic conversion
showHand(x.cards, x.jokers, x.round, x.value);
x.findMelds();
showResult(x.melds, x.value);

The previous versions aren't optimal in that they check some combinations multiple times. While trying to find the best way to make sure every option is checked just once, I realised that the different nature of runs and sets requires two different approaches, and finding sets doesn't require recursion. In the end, this is the optimal strategy:

• Find runs first; use jokers only if necessary.
• When a run is found, recurse on a copy of the hand, then continue finding runs.
• When no more runs can be found, switch to finding sets.
• Use all available complete sets without jokers.
• While jokers are available, complete the most valuable one or two-card set(s).
• Add left-over jokers.

To my surprise, even though the code for sets is a bit fiddly, this algorithm is more than 10 times faster for complicated hands.

// OBJECT HAND CONSTRUCTOR

function Hand(cards, jokers, round, wilds) {
    this.cards = clone(cards);
    this.jokers = jokers;
    this.wilds = wilds || 0;
    this.round = round;
    this.melds = [];
    this.value = this.leftoverValue();
}

// FIND MELDS FROM CURRENT POINT

Hand.prototype.findMelds = function(suit, number) {

    // IF NOT A RECURSION: CONVERT WILDCARDS TO JOKERS AND START FROM 0,0
    if (suit == undefined || number == undefined) {
        suit = number = 0;
        var noRecursion = true;
        this.convertWilds();
    }

    // FIND CARDS FROM CURRENT POINT UNTIL END OR FULL LAY-DOWN
    while (suit < 5 && this.value > 0) {
        if (this.cards[suit][number] > 0) {

            // FIND RUNS STARTING WITH CURRENT CARD
            var run = this.findRun(suit, number);

            // TRY DIFFERENT LENGTHS OF LONG RUN
            for (var len = 3; len <= run.length; len++) {

                // SKIP LONG RUNS ENDING WITH A JOKER
                if (len > 3 && run[len - 1].s == -1) continue;

                // CREATE COPY OF HAND, REMOVE RUN AND START RECURSION
                var test = new Hand(this.cards, this.jokers, this.round, this.wilds);
                test.removeCards(run.slice(0, len));
                test.findMelds(suit, number);

                // SAVE CURRENT RUN AND MELDS FOUND THROUGH RECURSION IF BETTER VALUE IS FOUND
                if (test.value < this.value) {
                    this.value = test.value;
                    this.melds.length = 0;
                    this.melds = [].concat(run.slice(0, len), test.melds);
                }
            }
        }

        // MOVE THROUGH CARD MATRIX
        if (++number > 10) {
            number = 0;
            ++suit;
        }
    }

    // AFTER ALL CARDS HAVE BEEN CHECKED FOR RUNS, CREATE COPY OF HAND AND FIND SETS
    if (this.value > 0) {
        var test = new Hand(this.cards, this.jokers, this.round, this.wilds);
        test.findSets();

        // SAVE SETS IF BETTER VALUE IS FOUND
        if (test.value < this.value) {
            this.value = test.value;
            this.melds.length = 0;
            while (test.melds.length) this.melds.push(test.melds.shift());
        }
    }

    // FIX NO MELDS AND ONE JOKER EXCEPTION
    if (noRecursion && this.melds.length < 3) {
        this.melds.length = 0;
        this.value = this.leftoverValue();
    }
}

// FIND RUN STARTING WITH CURRENT CARD

Hand.prototype.findRun = function(s, n) {
    var run = [], jokers = this.jokers;
    while (n < 11) {
        if (this.cards[s][n] > 0) {
            run.push({s:s, n:n});
        } else if (jokers > 0) {
            run.push({s:-1, n:-1});
            jokers--;
        } else break;
        n++;
    }

    // ADD LEADING JOKERS (AT END FOR CODE SIMPLICITY)
    while (run.length < 3 && jokers--) {
        run.push({s:-1, n:-1});
    }

    // REMOVE UNNECESSARY TRAILING JOKERS
    while (run.length > 3 && run[run.length - 1].s == -1) {
        run.pop();
    }
    return run;
}

// FIND SETS

Hand.prototype.findSets = function() {
    var sets = [[], []], values = [[], []];
    for (var n = 0; n < 11; n++) {
        var set = [], value = 0;
        for (var s = 0; s < 5; s++) {
            for (var i = 0; i < this.cards[s][n]; i++) {
                set.push({s:s, n:n});
                value += n + 3;
            }
        }

        // ADD COMPLETE SET TO MELDS, OR INCOMPLETE SET TO CANDIDATES TO RECEIVE JOKERS
        if (set.length >= 3) {
            this.addToMelds(set);
        }
        else if (set.length > 0) {
            // STORE ONE-CARD SETS IN sets[0] AND TWO-CARD SETS IN sets[1]
            sets[set.length - 1].push(set);
            values[set.length - 1].push(value);
        }
    }

    // IF TWO JOKERS ARE AVAILABLE: COMPLETE MOST VALUABLE TWO-CARD SET OR ONE-CARD SET(S)
    while (this.jokers > 1 && sets[0].length > 0) {
        var select = values[0][sets[0].length - 1];
        for (var i = sets[1].length - 1; i >= 0 && i > sets[1].length - 3; i--) {
            select -= values[1][i];
        }
        if (select > 0) {
            set = sets[0].pop(); values[0].pop();
            set.push({s:-1, n:-1}, {s:-1, n:-1});
            this.addToMelds(set);
        } else {
            for (var i = 0; i < 2 && sets[1].length > 0; i++) {
                set = sets[1].pop(); values[1].pop();
                set.push({s:-1, n:-1});
                this.addToMelds(set);
            }
        }
    }

    // IF JOKER IS AVAILABLE: COMPLETE MOST VALUABLE TWO-CARD SET
    while (this.jokers > 0 && sets[1].length > 0) {
        set = sets[1].pop();
        set.push({s:-1, n:-1});
        this.addToMelds(set);
    }

    // ADD LEFT-OVER JOKERS
    while (this.jokers > 0) {
        this.addToMelds([{s:-1, n:-1}]);
    }
}

// ADD SET TO MELDS

Hand.prototype.addToMelds = function(set) {
    this.removeCards(set);
while (set.length) this.melds.push(set.shift());
}

// REMOVE ARRAY OF CARDS FROM HAND

Hand.prototype.removeCards = function(cards) {
    for (var i = 0; i < cards.length; i++) {
        if (cards[i].s >= 0) {
            this.cards[cards[i].s][cards[i].n]--;
        } else this.jokers--;
    }
    this.value = this.leftoverValue();
}

// GET VALUE OF LEFTOVER CARDS

Hand.prototype.leftoverValue = function() {
    var leftover = 0;
    for (var i = 0; i < 5; i++) {
        for (var j = 0; j < 11; j++) {
            leftover += this.cards[i][j] * (j + 3) // cards count from 0 vs 3
        }
    }
    return leftover + 25 * this.jokers - (22 - round) * (this.jokers < this.wilds ? this.jokers : this.wilds);
}

// CONVERT WILDCARDS TO JOKERS

Hand.prototype.convertWilds = function() {
    for (var i = 0; i < 5; i++) {
        while (this.cards[i][this.round] > 0) {
	this.cards[i][this.round]--;
            this.jokers++; this.wilds++;
        }
    }
    this.value = this.leftoverValue();
}

// UTILS: 2D ARRAY DEEP-COPIER

function clone(a) {
    var b = [];
    for (var i = 0; i < a.length; i++) {
        b[i] = a[i].slice();
    }
    return b;
}

// UTILS: SHOW HAND IN CONSOLE

function showHand(c, j, r, v) {
    var num = "    3 4 5 6 7 8 9 T J Q K";
    console.log(num.slice(0, 2*r+4) + "w" + num.slice(2*r+5));
    for (var i = 0; i < 5; i++) {
        console.log(["CLB ","DMD ","HRT ","SPD ","STR "][i] + c[i]);
    }
    console.log("    jokers: " + j + "  value: " + v);
}

// UTILS: SHOW RESULT IN CONSOLE

function showResult(m, v) {
    if (m.length == 0) console.log("no melds found");
    while (m.length) {
        var c = m.shift();
        if (c.s == -1) console.log("joker *");
        else console.log(["clubs","dmnds","heart","spade","stars"][c.s] + " " + "3456789TJQK".charAt(c.n));
    }
    console.log("leftover value: " + v);
}

// TEST DATA: CREATE ARRAY OF ALL CARDS TO DRAW FROM

var pack = [{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1},{s:-1,n:-1}];
for (var i = 0; i < 5 ; i++) {
    for (var j = 0; j < 11; j++) {
        pack.push({s:i, n:j}, {s:i, n:j});
    }
}

// TEST DATA: CREATE 2D ARRAY TO STORE CARDS

var matrix = [];
for (var i = 0; i < 5; i++) {
    matrix[i] = [];
    for (var j = 0; j < 11; j++) {
        matrix[i][j] = 0;
    }
}

// TEST DATA: DRAW CARDS AND FILL 2D ARRAY

var round = 10; // count from zero
var jokers = 0;
for (i = 0; i < round + 3; i++)
{
    var j = Math.floor(Math.random() * pack.length);
    var pick = pack[j];
    pack[j] = pack.pop();
    if (pick.s > -1) matrix[pick.s][pick.n]++;
    else jokers++;
}

// USE THIS TO TEST SPECIFIC HANDS

// round = 10; // count from zero
// matrix = [[0,0,0,0,0,1,0,0,0,0,1],
//           [0,0,0,0,0,1,0,0,0,0,0],
//           [0,1,0,0,1,2,0,0,0,0,0],
//           [0,0,0,0,0,2,1,0,0,1,1],
//           [0,0,0,0,0,0,0,0,0,0,0]];
// jokers = 1;

// CREATE INSTANCE OF HAND OBJECT, EVALUATE AND SHOW RESULT


var x = new Hand(matrix, jokers, round); // CALL WITHOUT FOURTH (WILDS) PARAMETER
showHand(x.cards, x.jokers, x.round, x.value);
x.findMelds();                           // CALL WITHOUT PARAMETERS TO INITIATE EVALUATION
showResult(x.melds, x.value);

Answer 2

This is a combinatorial optimization problem. Your algorithm produces only one solution. This is called a "greedy algorithm". For most problems there is no greedy algorithm which can guarantee an optimal solution. This seems to be also the case for your problem.

So if you want to improve the results you should produce several or even all possible solutions and choose the best one. With an effective approach and proper pruning of the search tree it should be possible to always find the optimal solution for your problem size.

A good idea might be to split the generation of a solution into a "starting phase" (creating runs and sets with the minimal size of 3) and then a "filling up phase" (where the remaining cards are added to existing runs and sets).

With each non-assigned card (at the beginning all cards are non-assigned) you have several possible "moves". In the starting phase these might be of the follwing types: skip, start a run or start a set. In the "filling up phase" the moves might be: skip, add to a run, add to set (there can be several possibilites of adding a card to a run).

For pruning the following rules will be helpful, since they will not influence the best found value of a solution:

• do not use a wild card instead of a non-assigned card.
• do not start a new set of the same rank as an existing one.

I am not so familiar with JavaScript, so here is a solution with Python (maybe you can use the one or other idea):

# trying to solve
# http://stackoverflow.com/questions/31615597/combinatorics-of-cardgame-hand-evaluation-for-runs-with-wildcards-and-duplicate

import copy

CLUBS, DIAMONDS, HEARTS, SPADES, STARS = range(5)
WILD = 0

testHand = [(CLUBS,3), WILD, (SPADES,3), (CLUBS,4), (CLUBS,5), (CLUBS,6), (CLUBS,6), (CLUBS,7), (CLUBS,8), (SPADES,10), (HEARTS,10), WILD]

def nextInRun(card):
    if card[1] == 13:
        raise ValueError("cannot determine next card in run for %s" % str(card))
    return (card[0],card[1]+1)

def prevInRun(card):
    if card[1] == 3:
        raise ValueError("cannot determine previous card in run for %s" % str(card))
    return (card[0],card[1]-1)

def fit2Set(card1, card2):
    return card1 == WILD or card2 == WILD or card1[1] == card2[1]

START_RUN, START_SET = range(2)

def removeCard(hand, card, startIdx=None):
    hand = copy.deepcopy(hand)
    if startIdx != None and hand.index(card) < startIdx:
        startIdx -= 1
    hand.remove(card)
    return ((hand, startIdx) if startIdx != None else hand)

def startMoves(handr1,card1,startIdx):
    if card1 == WILD:
        #print "trying to start run with 1 WILD card"
        for card2 in set(handr1):
            handr2,startIdx = removeCard(handr1, card2, startIdx)
            if card2 == WILD:
                #print "trying to start run with 2 WILD cards"
                for card3 in set(handr2):
                    handr3,startIdx = removeCard(handr2, card3, startIdx)
                    if card3 == WILD:
                        yield (START_RUN, 3*[WILD], handr3, startIdx)
                    else:
                        try:
                            card2v = prevInRun(card3)
                            card1v = prevInRun(card2v)
                            yield (START_RUN, [card1,card2,card3], handr3, startIdx)
                        except ValueError:
                            pass
            else:
                #print "trying to start run with WILD card and %s" % str(card2)
                try:
                    card1v = prevInRun(card2)
                    card3 = nextInRun(card2)
                    #print "card3 = %s, handr2 = %s" % (str(card3),str(handr2))
                    canContinueRun = card3 in handr2
                    if not canContinueRun and WILD in handr2:
                        card3 = WILD
                        canContinueRun = True
                    if canContinueRun:
                        handr3,startIdx = removeCard(handr2, card3, startIdx)
                        yield (START_RUN, [card1,card2,card3], handr3, startIdx)
                except ValueError:
                    pass
        return # no need to start a set with a WILD
    else:
        try:
            card2v = card2 = nextInRun(card1)
            canContinueRun = card2 in handr1
            #print "card2 = %s, handr1 = %s" % (str(card2),str(handr1))
            if not canContinueRun and WILD in handr1:
                card2v = card2
                card2 = WILD
                canContinueRun = True
            if canContinueRun:
                handr2,startIdx = removeCard(handr1, card2, startIdx)
                card3 = nextInRun(card2v)
                canContinueRun = card3 in handr2
                #print "card3 = %s, handr2 = %s" % (str(card3),str(handr2))
                if not canContinueRun and WILD in handr2:
                    card3 = WILD
                    canContinueRun = True
                if canContinueRun:
                    handr3,startIdx = removeCard(handr2, card3, startIdx)
                    yield (START_RUN, [card1,card2,card3], handr3, startIdx)
        except ValueError:
            pass
        handrs = copy.deepcopy(handr1)
        for card2 in set(handr1):
            handrs.remove(card2)
            if not fit2Set(card1,card2):
                continue
            handr2,startIdx = removeCard(handr1, card2, startIdx)
            for card3 in set(handrs):
                if not fit2Set(card1,card3):
                    continue
                handr3,startIdx = removeCard(handr2, card3, startIdx)
                yield (START_SET, [card1,card2,card3], handr3, startIdx)

def startings(hand,startIdx=0,runs=[],sets=[]):
    #print "get startings for\n hand = %s\n startIdx = %d\n runs = %s\n sets = %s" % (str(hand),startIdx,str(runs),str(sets))
    if len(hand) == 0 or startIdx >= len(hand):
        yield copy.deepcopy(hand),copy.deepcopy(runs),copy.deepcopy(sets)
        return
    card = hand[startIdx]
    while hand.index(card) < startIdx:
        startIdx += 1 # do not try to start with the same card twice here
        if startIdx >= len(hand):
            yield copy.deepcopy(hand),copy.deepcopy(runs),copy.deepcopy(sets)
            return
        card = hand[startIdx]
    #print " actual startIdx = %d" % startIdx
    handr = removeCard(hand, card)
    for move in startMoves(handr, card, startIdx):
        if move[0] == START_RUN:
            runs2 = copy.deepcopy(runs)
            runs2.append(move[1])
            for starting in startings(move[2], move[3], runs2, sets):
                yield starting
        elif move[0] == START_SET:
            sets2 = copy.deepcopy(sets)
            sets2.append(move[1])
            for starting in startings(move[2], move[3], runs, sets2):
                yield starting
    for h,r,s in startings(hand, startIdx+1, runs, sets):
        yield h,r,s

def runExtensions(run,handSet):
    if set(run) == set([WILD]): # run consists only of WILD cards
        for card in handSet:
            yield card
    else:
        runUnique = list(set(run))
        runUnique.sort()
        cardv = runUnique[0] if runUnique[0] != WILD else runUnique[1]
        idx = run.index(cardv)
        lastCardVal = cardv
        while idx < len(run)-1:
            lastCardVal = nextInRun(lastCardVal)
            idx += 1
        try:
            nextCardVal = nextInRun(lastCardVal)
            if nextCardVal in handSet:
                yield nextCardVal
                return
            if WILD in handSet:
                yield WILD
        except ValueError:
            pass
    
def fillings(hand, runs, sets):
    if len(runs) > 0:
        run1 = runs[0]
        noExtensionFound = True
        usedWildExtension = False
        for runExtension in runExtensions(run1,set(hand)):
            noExtensionFound = False
            run1e = copy.deepcopy(run1)
            run1e.append(runExtension)
            handr = removeCard(hand, runExtension)
            runse = [run1e] + copy.deepcopy(runs[1:])
            for filling in fillings(handr, runse, sets):
                yield filling
            if runExtension == WILD:
                usedWildExtension = True
            # when extending with WILD: also try without extending the first run; WILD card could be needed in another run
        if noExtensionFound or usedWildExtension and len(runs) > 1:
            for h,r,s in fillings(hand, copy.deepcopy(runs[1:]), sets):
                r = [run1] + r
                yield h,r,s
        return
    handr = copy.deepcopy(hand)
    setse = copy.deepcopy(sets)
    for card in hand:
        for set_i in setse:
            if fit2Set(card, set_i[0]):
                handr.remove(card)
                set_i.append(card)
                break
    yield handr,[],setse

def valueCard(card):
    if card == WILD:
        return 20
    return card[1]

def value(hand):
    return sum([valueCard(card) for card in hand])

def strRepSuit(suit):
    if suit == CLUBS:
        return 'clubs'
    if suit == DIAMONDS:
        return 'diamonds'
    if suit == HEARTS:
        return 'hearts'
    if suit == SPADES:
        return 'spades'
    if suit == STARS:
        return 'stars'

def strRepCard(card):
    if card == WILD:
        return 'WILD'
    return '%s%d' % (strRepSuit(card[0]), card[1])

def strRepCardSuit(card):
    if card == WILD:
        return 'WILD'
    return strRepSuit(card[0])

def strRepVal(card):
    if card == WILD:
        return 'WILD'
    return '%d' % card[1]

def strRepRun(run):
    setRun = set(run)
    if setRun == set([WILD]):
        return '%d * %s' % (len(run),strRepCard(run[0]))
    runUnique = list(setRun)
    suit = (runUnique[0] if runUnique[0] != WILD else runUnique[1])[0]
    return '%s %s' % (strRepSuit(suit), ','.join([strRepVal(card) for card in run]))

def strRepSet(set_):
    setUnique = list(set(set_))
    val = (setUnique[0] if setUnique[0] != WILD else setUnique[1])[1]
    return '%d %s' % (val, ','.join([strRepCardSuit(card) for card in set_]))

def strRepSol(hand,runs,sets):
    return ' runs: %s\n sets: %s\n hand: %s\n hand value: %d' % ('; '.join([strRepRun(run) for run in runs]), '; '.join([strRepSet(set_) for set_ in sets]), ','.join([strRepCard(card) for card in hand]), value(hand))

def optimizeHand(hand):
    lowestHandValue = value(hand)
    bestSolution = hand,[],[]
    for handr,runs,sets in startings(hand):
        #print "starting with\n runs = %s\n sets = %s\n handr = %s" % (str(runs),str(sets),str(handr))
        if len(runs) == 0 and len(sets) == 0:
            continue
        if len(handr) == 0:
            print "solution generated without filling"
            lowestHandValue = 0
            bestSolution = [],runs,sets
            break
        for solution in fillings(handr,runs,sets):
            handValue = value(solution[0])
            if handValue < lowestHandValue:
                lowestHandValue = handValue
                bestSolution = solution
                print "solution improved:\n%s" % strRepSol(bestSolution[0], bestSolution[1], bestSolution[2])
                if lowestHandValue == 0:
                    break
        if lowestHandValue == 0:
            break
    print "best solution:\n%s" % strRepSol(bestSolution[0], bestSolution[1], bestSolution[2])
    #return lowestHandValue, bestSolution

Now letting the code work on your example we get the following output:

>>> optimizeHand(testHand)
solution improved:
 runs: clubs 3,4,5,6; spaded WILD,WILD,10; clubs 6,7,8
 sets: 
 hand: spaded3,hearts10
 hand value: 13
solution improved:
 runs: clubs 3,4,5,6; clubs WILD,7,8
 sets: 10 spaded,WILD,hearts
 hand: spaded3,clubs6
 hand value: 9
solution improved:
 runs: clubs 3,4,5,6; clubs WILD,6,7,8
 sets: 10 spaded,WILD,hearts
 hand: spaded3
 hand value: 3
solution generated without filling
best solution:
 runs: clubs 4,5,6; clubs 6,7,8
 sets: 3 clubs,WILD,spaded; 10 spaded,WILD,hearts
 hand: 
 hand value: 0

Execution time is about 0.1s on my computer.

The above code finds also other wicked solutions:

>>> optimizeHand([WILD,WILD,(CLUBS,3)])
 ...
 runs: clubs 3,WILD,WILD
 
>>> optimizeHand([WILD,WILD,(CLUBS,13)])
 ...
 runs: clubs WILD,WILD,13

>>> optimizeHand([WILD,WILD,(CLUBS,13),(CLUBS,11)])
 ...
 runs: clubs WILD,11,WILD,13