Algorithm to find optimal groups in 2D array -

i have deck of 24 cards - 8 red, 8 blue , 8 yellow cards.

red    |1|2|3|4|5|6|7|8| yellow |1|2|3|4|5|6|7|8| blue   |1|2|3|4|5|6|7|8| 

i can take 3 of cards (same numbers, straight, straigh flush), whereas each of type scored differently. question is, how calculate maximal possible score (find optimal groups) game in progress, cards missing. example:

red    |1|2|3|4|5|6|7|8| yellow |1|2|3| |5| |7|8| blue   |1|2| |4|5|6| |8| 

---

the score three-of-a-kind is:

1-1-1    20   2-2-2    30   3-3-3    40   4-4-4    50   5-5-5    60   6-6-6    70   7-7-7    80   8-8-8    90   

the score straight is:

1-2-3    10   2-3-4    20   3-4-5    30   4-5-6    40   5-6-7    50   6-7-8    60   

the score straight flush is:

1-2-3    50   2-3-4    60   3-4-5    70   4-5-6    80   5-6-7    90   6-7-8   100  

a solution recursively tries every combination go this:

start looking @ combinations have red 8 highest card: three-of-a-kind r8-y8-b8, straight flush r6-r7-r8, , every possible straight *6-*7-r8. each of these, remove cards set, , recurse check combinations yellow 8, blue 8, red 7, yellow 7, blue 7, red 6 ... until you've checked except 2's , 1's; add three-of-a-kind 2-2-2 , 1-1-1 if available. @ each step, check recursion returns maximum score, , return maximum.

---

let's @ happens in each of these steps. we're looking @ combinations red 8; have available cards like:

red    ...|6|7|8| yellow ...|6| |8| blue   ...| |7|8| 

first, use three-of-a-kind r8-y8-b8, if possible. create copy of available cards, remove 8's, , recurse straight 7's:

score = 90 + max_score(cards_copy, next = red 7) 

(trying three-of-a-kind should done when current card red, avoid duplicate solutions.)

then, use straight flush r6-r7-r8, if possible. create copy of available cards, remove r6, r7 , r8, , recurse yellow 8:

score = 100 + max_score(cards_copy, next = yellow 8) 

then, use every possible non-flush straight containing red 8; in example, r6-b7-r8, y6-r7-r8 , y6-b7-r8 (there nine). each of these, create copy of available cards, remove 3 cards , recurse yellow 8:

score = 60 + max_score(cards_copy, next = yellow 8) 

then, finally, recurse without using red 8: create copy of available cards, remove red 8 , recurse yellow 8:

score = max_score(cards_copy, next = yellow 8) 

you calculate of these options has greatest score (with score returned recursion added), , return maximum score.

---

a quick test in javascript shows full set of 24 cards, algorithm goes through 30 million recursions find maximum score 560, , becomes quite slow. however, 3 higher-value cards have been removed, number of recursions falls below 1 million , takes around 1 second, , 6 higher-value cards removed, falls below 20,000 , returns instantly.

for almost-complete sets, pre-compute maximum scores, , calculate score once number of cards have been removed. lot of sets duplicates anyway; removing r6-r7-r8 result in same maximum score removing y6-y7-y8; removing r6-y7-b8 duplicate of removing b6-y7-r8... first change input canonical version, , pre-computed score. e.g. using pre-computed scores sets 3 or 6 cards removed require storing 45,340 scores.

---

as code example, here's javascript code tested algorithm with:

function clone(array) {                                   // copy 2-dimensional array      var copy = [];      array.foreach(function(item) {copy.push(item.slice())});      return copy;  }  function max_score(cards, suit, rank) {      suit = suit || 0; rank = rank || 7;                             // start @ red 8      var max = 0;      if (rank < 2) {                               // try 3-of-a-kind rank 1 , 2          if (cards[0][0] && cards[1][0] && cards[2][0]) max += 20;          if (cards[0][1] && cards[1][1] && cards[2][1]) max += 30;          return max;      }      var next_rank = suit == 2 ? rank - 1: rank;      var next_suit = (suit + 1) % 3;      max = max_score(clone(cards), next_suit, next_rank);    // try skipping card      if (! cards[suit][rank]) return max;      if (suit == 0 && cards[1][rank] && cards[2][rank]) {           // try 3-of-a-kind          var score = rank * 10 + 20 + max_score(clone(cards), 0, rank - 1);          if (score > max) max = score;      }      (var = 0; < 3; i++) {                       // try possible straights          if (! cards[i][rank - 2]) continue;          (var j = 0; j < 3; j++) {              if (! cards[j][rank - 1]) continue;              var copy = clone(cards);              copy[j][rank - 1] = 0; copy[i][rank - 2] = 0;              var score = rank * 10 - 10 + max_score(copy, next_suit, next_rank);              if (i == suit && j == suit) score += 40;    // straight straight flush              if (score > max) max = score;          }      }      return max;  }  document.write(max_score([[1,1,1,1,1,0,1,1], [1,1,1,1,1,1,1,0], [1,1,1,0,1,1,1,1]]));

an obvious way speed algorithm use 24-bit pattern instead of 3x8 bit array represent cards; way array cloning no longer necessary, , of code turned bit manipulation. in javascript, it's 8 times faster:

function max_score(cards, suit, rank) {      suit = suit || 0; rank = rank || 7;                             // start @ red 8      var max = 0;      if (rank < 2) {                               // try 3-of-a-kind rank 1 , 2          if ((cards &  65793) ==  65793) max += 20;     // 65793 = rank 1 of suits          if ((cards & 131586) == 131586) max += 30;    // 131586 = rank 2 of suits          return max;      }      var next_rank = suit == 2 ? rank - 1: rank;      var next_suit = (suit + 1) % 3;      var this_card = 1 << rank << suit * 8;      max = max_score(cards, next_suit, next_rank);           // try skipping card      if (! (cards & this_card)) return max;      if (suit == 0 && cards & this_card << 8 && cards & this_card << 16) { // try 3oak          var score = rank * 10 + 20 + max_score(cards, 0, rank - 1);          if (score > max) max = score;      }      (var = 0; < 3; i++) {                       // try possible straights          var mid_card = 1 << rank - 1 << * 8;          if (! (cards & mid_card)) continue;          (var j = 0; j < 3; j++) {              var low_card = 1 << rank - 2 << j * 8;              if (! (cards & low_card)) continue;              var cards_copy = cards - mid_card - low_card;              var score = rank * 10 - 10 + max_score(cards_copy, next_suit, next_rank);              if (i == suit && j == suit) score += 40;    // straight straight flush              if (score > max) max = score;          }      }      return max;  }  document.write(max_score(parseint("111101110111111111011111", 2)));  //                                 b       y       r  //                                 876543218765432187654321

the speed almost-complete sets can further improved using observation if straight flush 3 suits can be made current rank, best option. reduces number of recursions drastically, because 9 cards can skipped @ once. check should added after trying 3-of-a-kind rank 1 , 2:

    if (suit == 0) {                              // try straight flush suits         var flush3 = 460551 << rank - 2;     // 460551 = rank 1, 2 , 3 of suits         if ((cards & flush3) == flush3) {             max = rank * 30 + 90;             if (rank > 2) max += max_score(cards - flush3, 0, rank - 3);             return max;         }     }