MarkDunne/33-questions

Why not use Huffman's Coding?

swayam18 opened this issue · 0 comments

Given the question of mutability and the difficulty of coming up with these questions, should we instead use Hoffman's encoding to produce the bits from yes/no questions?

To the uninitiated, Hoffman's coding allows you to take into account the probability of something being true, giving us a lot of flexibility over the questions!

For example, assume that there are 4 people in the world: 2 red heads, 1 blond and 1 brunette.

The following questions can then uniquely identify each person:
Are you a red head?
Are you blond?

Here is why: The probability breakdown is as follows:

Red Head: 50%
Blonde: 25%
Brunette: 25%

If their answer is yes to the first question, assign a '1' as the first bit and the second bit as 0 for the first redhead and 1 for the second red head (Doesn't matter as long as they are unique)!. The trick here is to ignore the answer to the second question

If no, assign 0 as the first bit and 1 as their second if they are a brunette, and 0 otherwise.

Ultimately, we have:

00: Blonde
01: Brunette
10: Redhead 1
11: Readhead 2