I know you said you want to keep the memory footprint as small as possible, but there is one quite memory efficient lookup table optimization which I've seen used in some poker hand evaluators and I have used it myself. If you're doing heavy poker simulations and need the best possible performance, you might wanna consider this. Though I admit in this case the difference isn't that big because testing for a straight draw isn't very expensive operation, but the same principle can be used for pretty much every type of hand evaluation in poker programming.
The idea is that we create a kind of a hash function that has the following properties:
1) calculates a unique value for each different set of card ranks
2) is symmetric in the sense that it doesn't depend on the order of the cards
The purpose of this is to reduce the number of elements needed in the lookup table.
A neat way of doing this is to assign a prime number to each rank (2->2, 3->3, 4->5, 5->7, 6->11, 7->13, 8->17, 9->19, T->23, J->29, Q->31, K->37, A->41), and then calculate the product of the primes. For example if the cards are 39TJQQ, then the hash is 36536259.
To create the lookup table you go through all the possible combinations of ranks, and use some simple algorithm to determine whether they form a straight draw. For each combination you also calculate the hash value and then store the results in a map where Key is the hash and Value is the result of the straight draw check. If the maximum number of cards is small (4 or less) then even a linear array might be feasible.
To use the lookup table you first calculate the hash for the particular set of cards and then read the corresponding value from the map.
Here's an example in C++. I don't guarantee that it's working correctly and it could probably be optimized a lot by using a sorted array and binary search instead of hash_map. hash_map is kinda slow for this purpose.
#include <iostream>
#include <vector>
#include <hash_map>
#include <numeric>
using namespace std;
const int MAXCARDS = 9;
stdext::hash_map<long long, bool> lookup;
//"Hash function" that is unique for a each set of card ranks, and also
//symmetric so that the order of cards doesn't matter.
long long hash(const vector<int>& cards)
{
static const int primes[52] = {
2,3,5,7,11,13,17,19,23,29,31,37,41,
2,3,5,7,11,13,17,19,23,29,31,37,41,
2,3,5,7,11,13,17,19,23,29,31,37,41,
2,3,5,7,11,13,17,19,23,29,31,37,41
};
long long res=1;
for(vector<int>::const_iterator i=cards.begin();i!=cards.end();i++)
res *= primes[*i];
return res;
}
//Tests whether there is a straight draw (assuming there is no
//straight). Only used for filling the lookup table.
bool is_draw_slow(const vector<int>& cards)
{
int ranks[14];
memset(ranks,0,14*sizeof(int));
for(vector<int>::const_iterator i=cards.begin();i!=cards.end();i++)
ranks[ *i % 13 + 1 ] = 1;
ranks[0]=ranks[13]; //ace counts also as 1
int count = ranks[0]+ranks[1]+ranks[2]+ranks[3];
for(int i=0; i<=9; i++) {
count += ranks[i+4];
if(count==4)
return true;
count -= ranks[i];
}
return false;
};
void create_lookup_helper(vector<int>& cards, int idx)
{
for(;cards[idx]<13;cards[idx]++) {
if(idx==cards.size()-1)
lookup[hash(cards)] = is_draw_slow(cards);
else {
cards[idx+1] = cards[idx];
create_lookup_helper(cards,idx+1);
}
}
}
void create_lookup()
{
for(int i=1;i<=MAXCARDS;i++) {
vector<int> cards(i);
create_lookup_helper(cards,0);
}
}
//Test for a draw using the lookup table
bool is_draw(const vector<int>& cards)
{
return lookup[hash(cards)];
};
int main(int argc, char* argv[])
{
create_lookup();
cout<<lookup.size()<<endl; //497419
int cards1[] = {1,2,3,4};
int cards2[] = {0,1,2,7,12};
int cards3[] = {3,16,29,42,4,17,30,43};
cout << is_draw(vector<int>(cards1,cards1+4)) <<endl; //true
cout << is_draw(vector<int>(cards2,cards2+5)) <<endl; //true
cout << is_draw(vector<int>(cards3,cards3+8)) <<endl; //false
}