|
|
| Author |
Message |
Occulis
RealPoor Jedi
Joined: 11 Oct 2002
Posts: 13293
Location: Moral Relativity Central
|
 Posted: 10/13/05 - 10:10 Post subject: Fun programming task
|
|
|
Let's say a card from a deck has the values 0-51.
There are 52 cards in the deck, numbered 0-51.
Find a way to store the state of the deck with 32 bytes or less.
The closest I can get is about 40 bytes (6 bits per card).
Here are some hints:
Suit (0-3) only takes 2 bits
"Face" value (0-12) is 4 bits
I know I did this 8 years ago but don't remember how. 
|
|
|
Back to top
|
|
|
|
 |
sinrakin
RealPoor Master of Posts
Joined: 11 Oct 2002
Posts: 7044
|
|
Posted: 10/13/05 - 11:02 Post subject:
|
|
|
I'd say use the fact that as you learn the deck it takes fewer and fewer bits to specify the remaining cards.
So your array is a string of numbers of each card in the deck in order, but instead of representing the ordinal number of the card (0-51), it represents the ordinal number of the card taken from the set of remaining cards that haven't yet been put into the deck. I.E. You start with an ordered set of 52 cards and remove cards from it to place into the deck. "14" doesn't mean "card 14", it means "the fourteenth card which is still remaining in the ordered set of unallocated cards".
So the first 21 cards take 6 bits each to specify. But once you're down to only 31 cards left, you can start specifying cards with 5 bits. With 15 cards left, you can start using 4 bits. When you only have 7 cards left unaccounted for, you can use 3 bits, etc.
So you end up with:
33-52 cards remaining: 20 cards times 6 bits = 120 bits
17-32 cards remaining: 16 cards times 5 bits = 80 bits
9-16 cards remaining: 8 cards times 4 bits = 32 bits
5-8 cards remaining: 4 cards times 3 bits = 12 bits
3-4 cards remaining: 2 cards times 2 bits = 4 bits
2 cards remaining: 1 card times 1 bit = 1 bit
total is 249 bits, or 31 bytes and 1 bits
when only 1 card is remaining it's obviously the one that's left, so you don't have to specify it.
Actually, you could compress it still further, so that it would sometimes be less than 249 bits, but you'd still have a worst case of 249 bits. Consider the case when you have 3 cards left, 0-2. The first card requires two bits to specify; the second card requires one bit (and the last doesn't need to be specified). So bit sequence 000 means the card sequence is 0:1:2. 001 means 0:2:1. 100 means 2:0:1 and 101 means 2:1:0. But the leading two bit sequence 11 is never used, since there is no card 3. So you could adopt the convention that if the high bit is set, it means the first card is card 2, and the second bit determines the second card. Then you'd have:
000 = 0:1:2
001 = 0:2:1
010 = 1:0:2
011 = 1:2:0
10 = 2:0:1
11 = 2:1:0
For an average of 16/6 = 2 2/3 bits to specify the three card deck. I suppose this is standard compression theory; I've never done much with that. I imagine you could imply that technique all the way up the line as the number of cards left to specify is less than the bits you need to represent them.
|
|
|
Back to top
|
|
|
|
|
Occulis
RealPoor Jedi
Joined: 11 Oct 2002
Posts: 13293
Location: Moral Relativity Central
|
|
Posted: 10/13/05 - 12:02 Post subject:
|
|
|
|
Yeah, that's as good as I can get, too. Good job Sinkypoo!
|
|
|
Back to top
|
|
|
|
|
Frostkiss
RealPoor Guru
Joined: 20 Oct 2002
Posts: 2018
|
|
Posted: 10/13/05 - 12:18 Post subject: Customs
|
|
|
|
wrong button :-/
|
|
|
Back to top
|
|
|
|
|
sinrakin
RealPoor Master of Posts
Joined: 11 Oct 2002
Posts: 7044
|
|
Posted: 10/13/05 - 13:50 Post subject:
|
|
|
OK I wasted way too much time thinking about this. But technically, the absolute minimum number of bits that will always specify the state of the deck (without relying on a lucky arrangment that can be compressed) is given by the equation: log2(52!).
since the total number of states of the deck is 52!, and the number of bits to specify a number that big is log base 2 of the number. Quick approximation says that's in the neighborhood of 226 bits instead of 249, or 29 bytes. I assume the time and space for an implementation that could encode it that densely must go up dramatically. But theoretically, you could do it in less than 32 bytes. Possibly at the expense of more bytes of static table memory than there are atoms in the universe 
Anyway, it's nice to have a lower bound that you know you can't possibly do better than, and how close you are to it. If someone tells you he has an algorithm to encode the state of a deck of cards in 28 bytes, you can tell him he's lying, because it's theoretically impossible.
|
|
|
Back to top
|
|
|
|
|
Maldek
RealPoor Guru
Joined: 16 Oct 2002
Posts: 2089
|
|
Posted: 10/13/05 - 15:18 Post subject:
|
|
|
|
you guys ever play 52-pickup?
|
|
|
Back to top
|
|
|
|
|
|
|
