Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: How to store a set of four 5-bit values in one 16-bit value

github.com

Post reply on HN
Print view View original

111–120 of 149 posts

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#111

Post by hinkley »

lostatseajoshua wrote: post #106

Can someone explain this in very simple terms without math? An ELI5 example. Thank you.

If you’re playing Yahtzee or cards it doesn’t matter what order you get the dice/cards. It just matters if you got them at all.

If you have two values, you can arrange them two ways. Three values you can arrange six ways. Four values you can arrange 20 ways. 0-20 takes a little over four bits to represent.

If you have a set, you don’t care about order. So if you save the data without an order to it, it takes a little less space to hold it. About four bits worth.

With five values you can save almost seven bits (120) and with six it’s over 9 bits (720).

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#112

Post by mturmon »

yorwba wrote: post #76
mturmon wrote: post #62

Earlier quoted context omitted.

His math is right. The factorial already took care of the fact that order does not matter. If you want to optimize storage of duplicates, you still have to store the number of duplicate numbers, and you are back where you started.

The factorial is taking too much care of the fact that order does not matter. If I wanted to store four 1-bit numbers, ajkjk's math would suggest that I need log2(2^4/4!) = -0.58, i.e. a negative number of bits. You can't just divide by 4! because not all combinations of 4 numbers have 4! unique permutations. > If you want to optimize storage of duplicates, you still have to store the number of duplicate numbers, and…

You’re right, correction appreciated.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#113

Post by shaklee3 »

utopcell wrote: post #97

For completeness: The number of possible sets that include 4 numbers from the range [0..15] is (16+4-1) choose 4, or 3876. Let's assume that our set is (a, b, c, d). It is ordered, therefore a Consider all possible numbers that may be in our set, laid out in order. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 For each element in the set, we mark its position in this order by placing a marker to the left of the corresponding…

Thanks. That was really helpful.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#114

Post by hinkley »

barrkel wrote: post #10

The fact that it's using lookup tables to store the mapping between the set of numbers and the encoded 16-bit number makes it less interesting; it basically just enumerates the set of all possible combinations of numbers, and uses the ordinal as the encoding. A directly calculated scheme without a lookup would be niftier, though I suspect in practice the way it steals bits from redundancy of duplicates it wouldn't be…

It does seem like it should be calculable without the lookup table. Something with modular math perhaps.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#115

Post by huftis »

This reminds me of the following old puzzle.

Ten people are standing in a line. Each person is wearing a black or a white hat and can only see the colours of the hats of the people in front of them. The goal is to guess the colour of one’s own hat. First, the last person in the line shouts out their guess (‘black’ or ‘white’), then the person in front of them shouts out their guess, etc. No other form of communication is allowed (no clapping, no touching, no texting – and no tricks involving, e.g., encoding information in the delay between it being ‘your turn’ and actually shouting out your guess). The group ‘wins’ if at most one person guesses wrong.

The group is allowed to discuss a strategy before taking part in this puzzle (i.e., before being given their hats). Which strategy should they choose to maximise the chance of winning?

They’re only allowed one wrong guess, so this is basically trying to encode 9 bits of information in 1 bit. And here the ordering of the bits actually matters. Still, it’s possible to choose a strategy which gives the group 100% chance of winning! Good luck trying to solve this one. :)

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#116

Post by steve_musk »

huftis wrote: post #115

This reminds me of the following old puzzle. Ten people are standing in a line. Each person is wearing a black or a white hat and can only see the colours of the hats of the people in front of them. The goal is to guess the colour of one’s own hat. First, the last person in the line shouts out their guess (‘black’ or ‘white’), then the person in front of them shouts out their guess, etc. No other form of communicatio…

Seems impossible to me.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#117

Post by Robin_Message »

steve_musk wrote: post #116
huftis wrote: post #115

This reminds me of the following old puzzle. Ten people are standing in a line. Each person is wearing a black or a white hat and can only see the colours of the hats of the people in front of them. The goal is to guess the colour of one’s own hat. First, the last person in the line shouts out their guess (‘black’ or ‘white’), then the person in front of them shouts out their guess, etc. No other form of communicatio…

Seems impossible to me.

Try doing it with just two people. Then extend the concept somehow. All the details of the puzzle are important.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#118

Post by TekMol »

steve_musk wrote: post #116
huftis wrote: post #115

This reminds me of the following old puzzle. Ten people are standing in a line. Each person is wearing a black or a white hat and can only see the colours of the hats of the people in front of them. The goal is to guess the colour of one’s own hat. First, the last person in the line shouts out their guess (‘black’ or ‘white’), then the person in front of them shouts out their guess, etc. No other form of communicatio…

Seems impossible to me.

The way huftis stated it, it is indeed impossible.

In the popular, solvable version of the puzzle, the group also gets the information if each guess was wrong or right. It's not at all about encoding "9 bits of information in 1 bit".

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#119

Post by bubblethink »

pishpash wrote: post #86
yorwba wrote: post #60

Earlier quoted context omitted.

Are you sure you don't mean log2((32*31*30*29)/(4*3*2*1) + (32*31*30)/(3*2*1) + (32*31)/(2*1) + 32/1) = 15.34 using the number of sets of values from {0, 2^5-1} with at most 4 elements? If on the other hand you want to store exactly 4 values, possibly with duplicates (while still ignoring order), you need to count multisets ( https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul... ) log2( (35*34*33*32)/(4*3*2…

The second answer, 15.676, is the correct one. It can also be arrived at by: log2(32C4 + 32C3 * 3 + 32C2 * 3 + 32C1)

I followed the original link as well as this calculation. Why not use this to map them directly (instead of breaking it into 12 bits and 4 bits) ? We'll just have some unused headroom in 16 bits. This would seem more natural than thinking of the 12 + 4 solution.

Re: Show HN: How to store a set of four 5-bit values in one 16-bit value

#120

Post by huftis »

TekMol wrote: post #118
steve_musk wrote: post #116

Earlier quoted context omitted.

Seems impossible to me.

The way huftis stated it, it is indeed impossible. In the popular, solvable version of the puzzle, the group also gets the information if each guess was wrong or right. It's not at all about encoding "9 bits of information in 1 bit".

No you don’t need information on whether the each guess is right. (And, of course, if the group is playing it correctly, every guess except possible the first one is correct.)
Post reply on HN