Data-compression with playing cards


#1

[Permalink]


#2

I can compress playing cards too! It’s lossy, though. You have to scrunch one up in your hand, into a little ball.


#3

I believe this was the basis for the “Solitaire” encryption method designed by Bruce Schneier and featured in Neal Stephenson’s Cryptonomicon.


#4

I have a way. You take a binary document, express it in base 10, add a decimal point in front and make a notch on a stick that far along the stick (assuming the stick is of unit length)

Done!

All of human knowledge reduced to a notch on a stick!

:smiley:


#5

I don’t know where you found that picture, but the thumb is freakin me out!


#6

Where do the playing cards come in?


#7

Hi, I think Bruce Schneier’s method uses the cards to provide a means of encrypting messages written out on paper, while this method stores the data within the cards themselves. This method is also much easier to understand and implement.


#8

You got here first, Brain!


#9

Strip poker, mainly


#10

I hope you have a mighty sharp knife, there. And a damn good ruler.


#11

Obama’s OK, but I bet we could do better.


#12

I wouldn’t categorize it as “compression”, but yeah, you can actually store a lot of data in the state of a deck of cards. There are 52! possible orderings, which means that you can encode slightly more than 225 bits of data with card order. You could add an extra 52 bits if you encode more information in whether the cards are forwards/backwards.


#13

If you divide the deck into 3 groups, you can store a number 2^17 in each register (~131,000) and have an out register for recording the results of adding/subtracting the other two registers. And have a few cards left over to fill in blanks as you go. So now you’re not just encoding messages, but you’re able to do something useful with them and write programs.

You can double the size of each register by representing 1 or 0 as card or NO card in each place, and get up to numbers 2^34 or 17179869184. If you switch to base 3, you can have a card face up or face down, or not there and achieve 3^34, or 1.7x 10^16.

Or if you go to base 5, with card face up, upright, face up upside-down, face down upright, face down upside down (if the cards support this platform), or absent, then you can achieve 5^34 or 5.8x10^23.

Base 7: turn cards sideways. Base 25: turn cards to various discernible degrees, including face up, face down in all clock-face configurations, plus absent.

The point is, you can do a whole lot more than just encode 52 bits. You have a much wider range of possibilities if you get creative with your representational systems.


#14

There are 52! ways to arrange a deck of cards. Any particular arrangement can be seen as the representation of a number written in a variable base system. The rightmost digit is units, and it has 52 possible numerals from 0 to 51. The next digit to the left is 52s, and its possible numerals are 0 to 50. The next digit to the left is (52 x 51)'s, and its possible numerals are 0 to 49. The next digit to the left is (52 x 51 x 50)'s, and its possible numerals are 0 to 48. (To pull this off, number your cards zero to 51; as you use each one, renumber the rest to eliminate the gap.)

Thus, we can encode any integer between 0 and (52! -1) with a deck of cards. That’s ln(52!) / ln(2) bits, which gives us 225 bits free and clear. What sort of message you can wedge into 225 bits is a separate problem than how many bits a deck of playing cards can represent, but with no compression at all, 5 bits a character gives us 26 letters plus a little punctuation, and our 225 bits gets us 45 of these characters.


#15

If you flip over some of the cards you even get 52 more bits (or 10 more letters).


#16

Good point. And then if you use cards with a definite upright versus reversed orientation (like the Most-wanted Iraqi playing cards), that gets you another 52 for 329 bits. (Although you’d have to put them in a box with a definite top-bottom and front-back orientation.) Similarly, 78 card Tarot decks with card orientations are readily available. ln(78!)/ln(2) = 382 bits for card order, +78 for orientation, +78 for face up versus face down = 538 bits.


#17

You assumed it was more than that? Hubris.


#18

Scrunching? Bah! You want lossy compression? I light each card on fire and keep the ashes.

Reconstruction takes a lot of processing time, but I’m pretty sure the data that’s lost isn’t needed by anyone.


#19

But you’d have to communicate which ordering you were starting with (and the bandwidth used for communicating the key has to be taken into consideration when determining compression efficiency). The method outlined assumes both parties know the ordering is the sorted start of a deck of cards, bypassing that communication overhead.

Honestly, reading his description made me feel like I it was loosely associated with Huffman encoding (different, obviously, but recursively adaptive).


#20

I have attempted to code the “Basic implied card method” in MATLAB… (https://dl.dropboxusercontent.com/u/45063757/cardcipher-basic-1p0.m)

It is quite a neat little idea. It would be nice to send a friend a deck of cards, having previously given them an ordered deck (key exchange!), and have them decode your message. But what is the longest message one might send by this method?

I found that by using a frequency-order alphabet and a single space, I can code a message as long as 47 characters of a high-frequency 'e’s, but only 16 charcters of low-frequency 'z’s.

Can a twitter 140 character tweet be sent on a card deck(s)? Depends on the letter frequency. Using a frequency-order alphabet (with a single space at the end), you can get a tweet like the following into three decks of cards:
‘lady macbeth encourages her husband to be more aggressive in pursuing career options’
(thanks to the “Reduced Shakespeare Company” http://www.reducedshakespeare.com/2009/11/tweeting-shakespeare/)

With one deck, you can only get this much: ‘lady macbeth encourages hr’ The deck order looks like this:

messagedeckfrombinary =

 2
 4
 9
12
15
16
20
21
22
24
27
28
30
34
37
39
40
41
44
45
 5
 8
10
11
13
14
18
35
38
43
47
48
52
 1
 6
 7
25
42
49
36
46
51
 3
19
31
32
33
17
50
23
29
26

Thanks,
M.