Page 1 of 2
Unique patterns
Posted: Sun Sep 09, 2007 11:26 am
by Zacariaz
Im not sure if this belongs under programing, but i think so.
this concerns altering two or more simular, patters into one uniques one, discribing all of the.
fx.
you draw tre cards from a deck of cards, they may turn out to be:
(A = ace, K = king, Q = queen, J = jack, T = 10, H = hearts, S = spades, D = diamonds and C = clubs)
AS 2D 7C
non if a had drawn
2D 7C AS
instead, it would still be the same.
Now there is 6 possible combinations in this example:
AS 2D 7C
AS 7C 2D
2D 7C AS
2D AS 7C
7C 2D AS
7C AS 2D
what i want is to combine these hands into a single unique pattern from which i can determine which cards im holding.
eg.
if i draw:
7C 2D AS
i get a pattern in return and if i draw:
AS 2D 7C
I get the same patter.
I actually think this is possible, however it may be to complex.
If possible i want to follow a few single rules:
1. no predefinitions.
2. sorting the cards or simular is not what i had in mind.
3. the value and suit of any card can be contained in 6 bits spaces and we hold 3 cards, 3*6 = 18 and there is 6 combinations, 6*18 = 108 bits in total as the maximum space this unique patter can take up. I would definently prefer no more that 32 bits, which i think will be problematic, allso i might allso want patters of 4, 5, 6 cards or more.
Some sort of binary manipulation as a solution would be cool, but its probably not the right way to go about the problem.
What i need is a generel solution if anyone can offer it.
Please give your thoughs on this.
ps.
This has been really hard for me 2 explain, so please, if theres something you dont understand, dont tease me, but ask your question instead.
Thanks
Posted: Sun Sep 09, 2007 1:55 pm
by Alboin
What about sorting the cards before comparing them? After sorting them numerically and or alphabetically, they would all be the same in order.
Posted: Sun Sep 09, 2007 1:58 pm
by Zacariaz
yes that would be posible but i was hoping for another solution.
I by the way just did the math.
In a 32 bit integer you can hold one of the unique pattern discribing 9 cards = 52*51*50*49*48*47*46*45*44 / 9! = 3679075400 combinations = 32 bits
but after that youll have to use ull's, if thats even enough...
Posted: Sun Sep 09, 2007 8:46 pm
by Kevin McGuire
Code: Select all
typedef struct
{
uint8_t id[7];
} HAND_IDENTIFIER;
#define CARDNUM(num) (num-1)
#define ACE 0
#define JACK 10
#define QUEEN 11
#define KING 12
#define SPADES 1
#define DIAMONDS 2
#define CLUBS 3
#define HEARTS 4
#define CARDID(card, suit) (card * suit)
void setCardHandPattern(HAND_IDENTIFIER *id, uint32_t cardID)
{
id.id[cardID/8] |= (1<<(cardID%8));
}
HAND_IDENTIFIER handID1, handID2;
setCardHandPattern(&handID1, CARDID(ACE, SPADES));
setCardHandPattern(&handID1, CARDID(JACK, SPADES));
setCardHandPattern(&handID1, CARDID(CARDNUM(2), HEARTS));
setCardHandPattern(&handID1, CARDID(CARDNUM(8), DIAMONDS));
setCardHandPattern(&handID2, CARDID(CARDNUM(8), DIAMONDS));
setCardHandPattern(&handID2, CARDID(ACE, SPADES));
setCardHandPattern(&handID2, CARDID(CARDNUM(2), HEARTS));
setCardHandPattern(&handID2, CARDID(JACK, SPADES));
handID1 == handID2
I have not tested any of it, but the concept should work most definitely.
Posted: Sun Sep 09, 2007 10:37 pm
by Zacariaz
im of to bed, havent slept for ages, but i definently look it over tomorrow, ty very much.
Posted: Mon Sep 10, 2007 1:18 am
by Zekrazey1
Kevin:
Teensy thing: suits from 0 to 3 and CARDID(card,suit) = 13 * suit + card
Zacariaz:
Perhaps you could try commutative functions? e.g. if you had two cards, c1, c2, you could form an id with c1 + c2, c1 * c2. For 3 cards you could form an id with c1 + c2 + c3, c1*c2 + c2*c3 + c3*c1, c1*c2*c3.
Posted: Mon Sep 10, 2007 3:27 am
by Kevin McGuire
overflow
Posted: Mon Sep 10, 2007 3:30 am
by Combuster
you could use bitfields to denote the cards you have - you only need two ints for that (64 bits for 52 cards, room for 12 jokers
)
Posted: Mon Sep 10, 2007 3:41 am
by Zekrazey1
Combuster wrote:
you could use bitfields to denote the cards you have - you only need two ints for that (64 bits for 52 cards, room for 12 jokers Very Happy)
Already suggested :p.
Kevin wrote:
overflow
Confused, me :p. Explain?
52 * 52 * 52 < (2^6)^3, i.e. < 18 bits.
Posted: Mon Sep 10, 2007 3:44 am
by Kevin McGuire
Combuster wrote:you could use bitfields to denote the cards you have - you only need two ints for that (64 bits for 52 cards, room for 12 jokers
)
Yeah. You only really need seven bytes if I am not mistaken (but could be).
I just did my card index math wrong above, but it does exactly what you say.
Also, I like the Read-Copy-Update.
overflow
My brain overflowed. (Did the math wrong way up above, Was late.)
Posted: Mon Sep 10, 2007 4:08 am
by Combuster
Also, I like the Read-Copy-Update.
The other thread?
Posted: Mon Sep 10, 2007 7:21 am
by Kevin McGuire
52 * 51 * 50 is the answer, let me get home from work and I will do the rest.
Posted: Mon Sep 10, 2007 8:37 am
by Kevin McGuire
There is an even more efficient way to do this.. I just have to think about it longer but I know there is because I can feel it. The problem with this algorithm below is it is still using a calculation that supports repeating symbols in the combination like: ABACD instead of non-repeating. Then further down is non-repeating with the order not holding any value.
52 ^ 3 = repeating
52 * 51 * 50 = non-repeating
.... not thought up one for order not being important ..
Code: Select all
#include <stdint.h>
#include <stdio.h>
typedef uint8_t CARD;
uint32_t getHandId(CARD a, CARD b, CARD c)
{
uint32_t x, k, v[] = { a + b * 52 + c * (52 * 52),
a + c * 52 + b * (52 * 52),
b + a * 52 + c * (52 * 52),
b + c * 52 + a * (52 * 52),
c + a * 52 + b * (52 * 52),
c + b * 52 + a * (52 * 52)
};
for(x = 0, k = 0xffffffff; x < 6; ++x)
{
if(v[x] < k)
{
k = v[x];
}
}
return k;
}
int main(int argc, char *argv[])
{
printf("handID:%u\n", getHandId(24, 0, 34));
printf("handID:%u\n", getHandId(24, 34, 0));
return 1;
}
Posted: Mon Sep 10, 2007 8:45 am
by Kevin McGuire
Zekrazey1 wrote:Kevin:
Teensy thing: suits from 0 to 3 and CARDID(card,suit) = 13 * suit + card
Zacariaz:
Perhaps you could try commutative functions? e.g. if you had two cards, c1, c2, you could form an id with c1 + c2, c1 * c2. For 3 cards you could form an id with c1 + c2 + c3, c1*c2 + c2*c3 + c3*c1, c1*c2*c3.
Damn. You were right.
a*b*c = id.
Posted: Mon Sep 10, 2007 9:10 am
by Zekrazey1
You need 3 equations, otherwise two different sets of cards may have the same id.
e.g. with just 1 equation: 2 x 3 x 4 = 8 x 3 x 1
So the full thing would be
id = triple(i, j, k) = triple(c1 + c2 + c3, c1*c2 + c2*c3 + c3*c1, c1*c2*c3).
That would take about 36 or so bits if you wanted to concatenate them all together. To get the original numbers back, you can re-arrange those 3 equations to get:
x^3 - i*x^2 + j*x - k = 0
and solve for x.
[edit]
Or, we could get to the same thing another way. If we want an equation that yields c1, c2 & c3 when solved, we might look at an equation with c1, c2 & c3 as roots, i.e. (x - c1)*(x - c2)*(x - c3) = 0. The resulting coefficients of this polynomial are the same regardless of the order of c1, c2 & c3, so we can use them to id the set of all permutations of c1, c2, & c3. It's more obvious how this generalises to more cards. With n cards, we're looking at the polynomial resulting from (x - c1) * (x - c2) * ... * (x - cn).
Sorting and then comparing is still easier though
.