Combinatorics for evaluating manual maps for runs using wildcards and duplicates

Question

Working on a rummy-style game with a few twists:

Using two 5 deck decks instead of one deck of 4 columns (116 cards in total).
Suites work from 3 to the king, and in each deck there are 3 jokers (since there are no 2 and there is no ace).
11 rounds, in the first round each player has 3 cards, in the last round each player has 13 cards.
Besides the fact that Jokers are wild, each card value becomes too wild, and this corresponds to the number of cards in your hand.
So, one round 3 - wild two rounds 4 - wild ... round 11 Kings are wild (kings have a numerical value of 13).

The goal is to stack all of your cards. As soon as someone “leaves” (pawns all the cards), the remaining players have one move to also fold all the cards or as many valid sets / runs as possible. You get points for any cards left in your hand.

Players can only place cards in sets or runs in which there are at least 3 cards, i.e. set: {3:c, 3:d, 3:h} , run: {3:c, 4:c, 5:c} . There are also rounds where you need to get a set / launch with more than 3 cards, because the number of cards in your hand is not evenly divided by 3.

To start a manual assessment, I divided 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 remove all packages / buckets that do not have cards.
Setting up scores is pretty straightforward, but scoring ... is not straightforward.

I came up with a range-based performance assessment

  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 in many cases, but it fights duplicates in the package. One of the most difficult cases that I encountered while testing the game is 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}

Thus, 12 cards can be formed in the hand and a valid box: it will 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 like this:
sets: [{6:c, 6:c, wild}, {10:s, 10:h, wild}]
runs: [{3:c,4:c,5:c}]
OR (depending on whether I will evaluate the kit first or run it)
sets: [{10:s, 10:h, wild, wild}]
runs: [{3:c, 4:c, 5:c, 6:c, 7:c, 8:c}]
with the remaining cards.

I also encounter problems in the early rounds when I have these hands:
{6:h, 7:h, 7:h, 8:h}
The above problem occurs when you try to set aside a partial arm.
{6:h, 7:h, 8:h} - a valid run in situations on the partial side, and the player will be left with only 7 points. But since I am not getting rid of duplicates, he does not evaluate this as a possible run, and the player stays with all the points (28).

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

My current thoughts for solving this problem seem depressing since they include many case/if for specific arm lengths / game situations / packet lengths. Where once I delete duplicates, sometimes I sometimes don’t break the package, sometimes I don’t do this ... There are a lot of headaches mainly where I’m not sure that I covered all possible hands / partial situations.

Answer 1

This is a fully functioning manual evaluator (although there is one part that still needs to be optimized for efficiency). It uses recursion to check all possible combinations and returns the one with the lowest remaining value.

Cards are stored as a 5 by 11 matrix, with values ​​0, 1 or 2 representing the number of cards of this type, for example:

  3 4 5 6 w 8 9 TJQK 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 view, 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, scouring meld, creating a copy of the hand, removing meld from the copy and then invoking itself on the copy.

(Since recursion is performed from the beginning of the matrix, with a better algorithm for shuffling through shorter parts of a long field, recursion can be performed from the current point, which avoids the combination of combinations twice).

In the example, a random hand of 13 cards with wild kings is generated and evaluated. Without commenting on the code below, you can enter specific hands for verification. (All the code after the function of cloning the array is intended 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 TJQK"; 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 (cs == -1) console.log("joker *"); else console.log(["clubs","dmnds","heart","spade","stars"][cs] + " " + "3456789TJQK".charAt(cn)); } 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); 

Run codeHide result

This is an optimized version. Recursions for sets are now executed from the current point, recursions for runs still work from 0.0.
Optimizing the findSets function to the point where all recursions can be performed from the current point will add complexity, which, I think, will cancel any possible increase in speed.
The findRuns and findSets functions now return an array of options and sets; it also solves the problem with leading jokers on the run.
The variable "multi" has also been removed, because it is needed only in one specific case, which is also solved by running recursions for sets of 0,0.

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

Run codeHide result

Actually, the theoretically “optimized” version turned out to be faster only for hands with several dual cards and much slower for simple hands, so I decided to make a hybrid version. This is 10% faster than previous algorithms for hands of any complexity.
One caveat is that it adds leading jokers to the runs at the end of the run for simplicity of code, so the *QK run will display 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 TJQK"; 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 (cs == -1) console.log("joker *"); else console.log(["clubs","dmnds","heart","spade","stars"][cs] + " " + "3456789TJQK".charAt(cn)); } 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); 

Run codeHide result

Previous versions are not optimal, as they check several combinations several times. When trying to find the best way to make sure that each parameter is checked only once, I realized that for the different nature of runs and sets, two different approaches are required, and finding sets does not require recursion. As a result, this is the optimal strategy:

• Search begins first; Use shooters only when necessary.
• When the search is found, make a copy of the copy, then continue the search.
• When there are no more runs found, switch to search sets.
• Use all available kits without jokers.
• While jokers are available, fill out the most valuable set of one or two cards.
• Add eyebrow jokers.

To my surprise, despite the fact that the code for the sets is a little difficult, this algorithm is more complex 10 times faster.

 // 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 TJQK"; 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 (cs == -1) console.log("joker *"); else console.log(["clubs","dmnds","heart","spade","stars"][cs] + " " + "3456789TJQK".charAt(cn)); } 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); 

Run codeHide result

Answer 2

This is combinatorial optimization . Your algorithm creates only one solution. This is called the "greedy algorithm . " For most problems, there is no greedy algorithm that can guarantee an optimal solution. This seems to apply to your issue as well.

So, if you want to improve the results, you must create some or even all possible solutions and choose the best. Thanks to an efficient approach and proper pruning of the search tree, you can always find the best solution for your problem size.

It might be a good idea to split the solution generation into the "initial phase" (creating runs and sets with a minimum size of 3), and then the "filling phase" (where the rest of the cards are added to the existing ones and starts and sets).

With each non-assigned card (at the beginning, all cards are not assigned), you have several possible “moves”. At the initial stage, these can be the following types: skip, start a run, or run a set. In the "filling phase" the moves can be as follows: skip, add to the run, add to the set (there may be several options for adding a card to the move).

The following rules will be useful for trimming, since they will not affect the best solution value found:

• do not use a wild card in place of an unassigned card.
• do not run a new set of the same rank as the existing one.

I am not very familiar with JavaScript, so here is a solution with Python (maybe you can use this or that 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)) 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 that the code is working 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 

The runtime is about 0.1 s on my computer.

The above code finds other evil 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