3

First of all, I'd like to point out that this is server-side Node.js code, not plain client-side Javascript. I don't want to use jQuery but using any native Node.js methods (if there are any potentially useful ones you know) is fine.

This is code for a robot player in a card game. The robot has a hand of cards structured as follows:

[ '9H', '10S', 'KD', '9D', '7D', 'QC', 'JC', '7C' ]

So each of the 8 cards is given as a value+suit string. This can't be changed, as the whole application works with this structure.

Now, the robot has to analyze this hand to search for certain card combinations. For example, it should find any "third kings" (king with at least 2 smaller cards of the same suit), "second tens" (queen with at least 1 smaller card of the same suit) or "third queens".

In the example above, it should come up with: third king of diamonds and third queen of clubs.

I'm looking at implementing a search algorithm to find these combinations, but I'm worried it would be very inefficient. My first idea is to iterate through the array to find all kings, queens and 10s and save this data somewhere, then iterate through it again to count how many other cards of the same suit we have. For example, for the king:

var kingsuits = [];
for(var i=0;i<8;i++){
    if(hand[i].substr(0,1) == "K")
        kingsuits.push(hand[i].substr(-1));
}
//now kingsuits has the suits of all kings, and we can go through our hand again and check how many cards we have in each of these suits...

My question is, is there a more efficient way to accomplish this? The thing is, there are quite a few other combinations that should also be looked for, not just the ones I named as examples above.

Also - perhaps more importantly - if we find a "third king" we don't need to look for a "third queen" or "second 10" at all. There's a clear hierarchy of these combinations, so if we find the first one we don't need to care about the others at all.

Improve this question
1
  • 1
    The "most efficient" way would probably involve a very large table of precomputed values similar to what you see in the fastest poker hand checkers. A very reasonable solution would be to sort the cards by suit/number and then sequentially scan them as one of the answers below describes. Commented Mar 7, 2014 at 15:11

5 Answers 5

Reset to default
3

Use a two-dimensional hashmap or array or some other kind of direct-access data structure, in which it is stored whether (boolean) or how many (int) cards of a particular type are in your hand. For example:

[ '9H', '10S', 'KD', '9D', '7D', 'QC', 'JC', '7C' ]
=>
  | A  K  Q  J  10 9  8  7  6  5  4  3  2
--+--------------------------------------
C | 0  0  1  1  0  0  0  1  0  0  0  0  0
D | 0  1  0  0  0  1  0  0  0  0  0  0  0
H | 0  0  0  0  0  1  0  0  0  0  0  0  0
S | 0  0  0  0  1  0  0  0  0  0  0  0  0

This should allow for quite fast and plain searches in that structure - by looping you can quickly identify that there are multiple nines, and that there are 2 club cards next to the club queen.

It does not really matter whether you choose an object or an array for the spades, and which (suits or values) is the first or second dimension. For the values you will need to use an array to get the defined order, even if the mapping (e.g. A->0, K->1, … 2->12) is unconventional.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

A fast solution would be to first quick sort the hand into suit/number order, i.e.:

[ '9H', '10S', '7D', '9D', 'KD', '7C', 'JC', 'QC' ]

Then do a single pass through the list tracking the longest sequence of cards in a single suit found so far, e.g.:

var lastCard
var currentSequence
var bestSequence

for card in cards:
  if suitOf(card) = suitOf(lastCard) and numberOf(card) = numberOf(lastCard) + 1:
    append to currentSequence
  else:
    if currentSequence better than bestSequence:
      bestSequence = currentSequence
    clear currentSequence

The search can be easily aborted when you find a "best" sequence.

Improve this answer

3 Comments

I don't see how this would work in case of more complicated card combinations if they are needed, because those are just examples? such as the ones where KD, QC, JD, 10S, 9D would be the best hand?
The hand is already sorted by suit/number, only it's in declining order in my example...
@MaunoV. It's easy enough to sort by suit/number to identify the suit-major hands (his custom hands and flushes, for example), and then sort again by number/suit to handle the number-major hands (pairs, straights, etc.).
2

Since there are a lot of unknowns regarding exactly what you are searching for, it could be that simply sorting the cards is sufficient, but you could consider arranging the cards in an object (hash table) for fast lookup of the conditions.

function value(s) {
    return s.substr(0, s.length - 1)
}

function suit(s) {
    return s.substr(-1)
}


function search(arr) {
    var suits = {
        S: {},
        C: {},
        D: {},
        H: {}
    }

    var count = {
        S: 0,
        C: 0,
        D: 0,
        H: 0
    }

    for (var i = 0; i < arr.length; i++) {
        var card = arr[i]
        var s = suit(card)
        var v = value(card)

        suits[s][v] = true
        count[s]++
    }

    // hunt in the structure here
}

This would allow you to fetch third queens for example:

var thirdQueens = ["S", "C", "D", "H"].map(function (s) {
    var hash = suits[s]

    if (hash.Q && count[s] - (hash.K ? 1 : 0) >= 3) {
        return "Q" + s
    }
}).filter(function identity(x) { return x })
Improve this answer

Comments

1

To answer the "more importantly" part of your question, you could create an array of rules, in order of precedence, one function for each rule, and iterate over it. Here is an example with very simple rules:

var hand = [ '9H', '10S', 'KD', '9D', '7D', 'QC', 'JC', '7C' ];

var rules = [
    function(hand) {
        if (hand.indexOf('9H') !== -1) {
            return {
                rule: "Has a 9H",
                cards: [ "9H" ]
            };
        }
    },

    function(hand) {

        if (hand.indexOf('7D') !== -1) {
            return {
                rule: "Has a 7D",
                cards: [ "7D" ]
            };
        }
    }
];

var match = false;

for (var i = 0, len = rules.length; i < len && !match; ++i) {
    match = rules[i](hand);
}

console.log(match);

Once you have this written, you can look at your rules and check for repetition of logic, and start rewriting your rules:

var rules = [
    matchCardFn("9H"),
    matchCardFn("7D")
];

function matchCardFn(matchCard) {
    return function(hand) {
        if (hand.indexOf(matchCard) !== -1) {
            return {
                rule: "Has a " + matchCard,
                cards: [ matchCard ]
            };
        }
    };
}
Improve this answer

2 Comments

Would this work considering the asynchronous nature of Node.js?
Absolutely. The asynchronicity you refer to is relevant only for lengthy "external" processes (e.g. file I/O, database access, network communication…)
1

... and here is how your hashmap can be constructed... I guess anything else had been explained before me.

var input = [ '9H', '10S', 'KD', '9D', '7D', 'QC', 'JC', '7C' ]

var M = [ [], [], [], [] ]

var values = {
  2:  0,
  3:  1,
  4:  2,
  5:  3,
  6:  4,
  7:  5,
  8:  6,
  9:  7,
 10:  8,
  J:  9,
  Q: 10,
  K: 11,
  A: 12,
}

var suits = {
  C: 0,
  D: 1,
  H: 2,
  S: 3,
}

input.forEach(function(x) {
  M[suits[x.slice(-1)]][values[x.slice(0, -1)]] = 1
})
Improve this answer

1 Comment

There is no 1 usually :-)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.