Combinatorics of cardgame hand evaluation for runs, with wildcards and duplicates
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 CONSTRAINTSActually, 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);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