Unique patterns

[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

[Alboin]

What about sorting the cards before comparing them? After sorting them numerically and or alphabetically, they would all be the same in order.

[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...

[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.

[Zacariaz]

im of to bed, havent slept for ages, but i definently look it over tomorrow, ty very much.

[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.

[Kevin McGuire]

overflow

[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 )

[Zekrazey1]

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.

overflow

Confused, me :p. Explain?

52 * 52 * 52 < (2^6)^3, i.e. < 18 bits.

[Kevin McGuire]

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.)

[Combuster]

Also, I like the Read-Copy-Update.

The other thread?

[Kevin McGuire]

52 * 51 * 50 is the answer, let me get home from work and I will do the rest.

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

Opps. I just realized this is basically what Alboin was saying to do.

[Kevin McGuire]

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.

[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 .