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

131–140 of 149 posts

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

#131

Post by marcan_42 »

Too wrote: post #126
steve_musk wrote: post #124

Earlier quoted context omitted.

Well it’s easy to do with two people because the first person can just guess the color of the second, since we are allowed one wrong guess. I don’t see how this can be extended.

You can extend to three people if the first "guess" indicates if nr 2 and 3 have the same color or not. But doesn't go further because after the first all guesses must be 100% correct and can't be used for communicating additional information.

It does extend. It's just an XOR/parity trick. The last person shouts out the XOR of all the previous colors (if you prefer: whether the number of visible white hats is even or odd). From there, every other subsequent person knows their color by XORing the hats they see together with the guesses made so far.

For example, the second to last person knows their hat is black (0) if the last person's guess matches the XOR of the hats they see - if it doesn't, their hat flipped it, and thus is white (1). And so on and so forth. Your hat color is everything you see and everything that was said XORed together.

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

#132

Post by TekMol »

huftis wrote: post #120
TekMol wrote: post #118

Earlier quoted context omitted.

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

Damn, you are right! I wonder why the first two instances of this puzzle I googled included that info.

Still, it's not 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

#133

Post by syrrim »

nightcracker wrote: post #37

It is possible to do this in O(1) memory, for arbitrary sized collections, efficiently. The first trick is to make a function that can calculate the nth set with k elements from some universe U (in this case U = {0..2^5-1} without order (no duplicates) directly. This is done using the https://en.wikipedia.org/wiki/Combinatorial_number_system . This is very efficient. Then, to encode duplicates you use the stars and b…

This seems obviously wrong, though I admittedly don't know the stars and bars trick. Lets say you wanted to store a number a in [0,k), for arbitrarily large k. All you would need to so is encode your value as 0 repeated a times, and 1 repeated k-a times. Because you can store arbitrary integers below k with this method, you would need at least log(k) space. If k can be arbitrarily large, you would require unbounded space.

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

#134

Post by andromeduck »

joshuak wrote: post #95
andromeduck wrote: post #91

Earlier quoted context omitted.

Saving space in data structures that use buckets such as hash tables. I actually discovered this in a paper on hash tables that kind of just mentioned that it was a thing but I had a harder time finding out exactly how it was done.

Any chance you can remember which paper?

https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

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

#135

Post by andromeduck »

pm215 wrote: post #130
andromeduck wrote: post #91

Earlier quoted context omitted.

Saving space in data structures that use buckets such as hash tables. I actually discovered this in a paper on hash tables that kind of just mentioned that it was a thing but I had a harder time finding out exactly how it was done.

Perhaps you could mention the motivation for the trick in the readme? My initial reaction was "either this is an april-fools style joke, or it's a cute but pointless trick", and it wasn't til I got to the bottom of the HN comments that I found an explanation of why it would be worth knowing...

done :)

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

#136

Post by YesThatTom2 »

Which reminds of of this old programming joke:

While developing a CAD system we saved a lot of RAM compared to our competitor's product. They were storing each (X1,Y1)(X2,Y2) as four integers. We figured out how to the same thing in just 16-bits.

Yes, you guessed it (wait for it....) we could fit a edge in word-wise!

(Disclaimer: I didn't say it was a GOOD joke!)

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

#137

Post by majewsky »

chungy wrote: post #75
andromeduck wrote: post #36

Earlier quoted context omitted.

Is there a way to make it work with just make? I'm way too used to just typing make at this point and it's not too much work to just copy the same makefile everywhere.

echo "all: main" > Makefile make

No need create a Makefile.

  make main
is enough.

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

#138

Post by huftis »

TekMol wrote: post #132
huftis wrote: post #120

Earlier quoted context omitted.

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

Damn, you are right! I wonder why the first two instances of this puzzle I googled included that info. Still, it's not about encoding "9 bits of information in 1 bit".

You’re of course right about this not being encoding ‘9 bits of information in 1 bit’. That would be impossible; to encode 9 (arbitrary) bits of information, you need 9 bits.

On the other hand, you must encode information on the colour of 9 hats, and only the last person in the line is free to provide some information. He can’t possibly know the colour of his own hat, so he can only guess – or use his turn to provide 1 bit of information to the rest of the group (while the other people have to shout out their correct hat colour). The difficulty lies in figuring out why the puzzle as stated does not need you to encode 9 bits using 1 bit …

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

#139

Post by huftis »

marcan_42 wrote: post #131
Too wrote: post #126

Earlier quoted context omitted.

You can extend to three people if the first "guess" indicates if nr 2 and 3 have the same color or not. But doesn't go further because after the first all guesses must be 100% correct and can't be used for communicating additional information.

It does extend. It's just an XOR/parity trick. The last person shouts out the XOR of all the previous colors (if you prefer: whether the number of visible white hats is even or odd). From there, every other subsequent person knows their color by XORing the hats they see together with the guesses made so far. For example, the second to last person knows their hat is black (0) if the last person's guess matches the XOR…

That’s correct. Or, to explain in (slightly) more non-mathematical terms: The last person (‘person 10’) shouts out (e.g.) ‘white’ if the number of white hats in front of him is an odd number (1, 3, 5, 7, 9) and ‘black’ otherwise. Let’s say he shouted ‘white’. The person in front of him looks at the people in front him. If it’s still an odd number of white hats, his must obviously be black; otherwise it must be white.

If his hat is black, his shouts out ‘black’, and the person in front of him knows that the rest of the line (8 people) must still have an odd number of white hats, and he applies the exact same logic. But if the hat of person 9 was white, he would shout out ‘white’, and person 8 would know that the rest of the line (including himself) should now have an even number of white hats.

So, basically the rule is: Define ‘the rest of the line’ to mean the people who have not yet shouted out a colour. When the first person (person 10) shouts out ‘white’, this means that ‘the rest of the line’ has an odd number of white hats (parity: odd). Whenever someone shouts out ‘white’, the parity (even/odd) of ‘the rest of the line’ is flipped.

Using this, each person only has to count the number of white hats of the people in front of them and observe if it is even or odd. If it matches the parity of ‘the rest of the line’, the person’s hat is black, otherwise it’s white. (This also works for the person in front of the line (person 1). He sees no (or 0) white hats, i.e. he sees an even number of white hats.)

Post reply on HN