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;         }     }

Comments

Post a Comment

Popular posts from this blog

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

i'm implementing inapp billing in android app. works well, however, i'm trying decouple broadcast receiver activity manifest. suggestion in android's trivialdrive sample: // important: dynamically register broadcast messages updated purchases. // register receiver here instead of <receiver> in manifest // because call getpurchases() @ startup, therefore can ignore // broadcasts sent while app isn't running. // note: registering listener in activity bad idea, done here // because sample. regardless, receiver must registered after // iabhelper setup, before first call getpurchases(). currently there's class extends broadcastreceiver : public class iabbroadcastreceiver extends broadcastreceiver { /** * intent action receiver should filter for. */ public static final string action = "com.android.vending.billing.purchases_updated"; private final iabbroadcastlistener mlistener; public iabbroadcastreceiver(iabbroadcastlistener listener) { m...
Read more

python Tkinter Capturing keyboard events save as one single string -

is possible store keyboard events 1 string? code below stores 1 char , prints it. card reader or bar code reader, contains collection of character/ string not 1 character @ time. goal save char pressed text variable. from tkinter import * root = tk() def key(event): text= event.char text+= event.char print ("pressed", text) def callback(event): frame.focus_set() print ("clicked at", event.x, event.y) frame = frame(root, width=100, height=100) frame.bind("<key>", key) frame.bind("<button-1>", callback) frame.pack() root.mainloop() currently, creating text variable , everytime key() function gets called, , text stores last character typed. you can define text module level variable , , use module level text inside key function - text = '' def key(event): global text text+= event.char print("pressed", text)
Read more

sql server - Why does Linq-to-SQL add unnecessary COUNT()? -

here tables: create table customer ( cid int primary key, name varchar(32) ) create table ord ( oid int primary key, cid int foreign key references customer, address varchar(20) ) here's linq-to-sql statement: var aaa = c in db.customer select new { c, o = c.ord.tolist() }; and here's inexplicable query generated linq-to-sql: select [t0].[cid] [cid], [t0].[name] [name], [t1].[oid] [oid], [t1].[cid] [cid2], [t1].[address] [address], (select count(*) [dbo].[ord] [t2] [t2].[cid] = [t0].[cid]) [value] [dbo].[customer] [t0] left outer join [dbo].[ord] [t1] on [t1].[cid] = [t0].[cid] order [t0].[cid], [t1].[oid] i want understand how rid of count(*) part. it's entirely uncalled for! linq needs count(*) in order determine number of entries returned o = c.ord.tolist() .
Read more