The problem
counts maps each letter to how often it appears in a text. A letter can be any string, such as 'a' or a whole word. Return a dict that gives each letter a code: a non-empty string of '0' and '1'. The codes must be prefix-free (no code is the start of another), and the total number of bits, sum(counts[x] * len(code[x])), must be as small as possible.
huffman({'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45})
# for example {'f': '0', 'c': '100', 'd': '101',
# 'a': '1100', 'b': '1101', 'e': '111'}: 224 bits
When counts are equal, several sets of codes are equally good; any of them is accepted. The tests check the letters, that every code is made of 0 and 1, that no code starts another, and the total number of bits. With only one letter, give it the code '0'. Every count is at least 1.
Limits
- Up to 50,000 letters. Aim for O(k log k) for k letters.
Builds on GRDY-4 Huffman coding.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Two letters | Not run | |
| 3 | One letter | Not run | |
| 4 | All equal | Not run | |
| 5 | Doubling counts | Not run | |
| 6 | Codes must not start each other | Not run | |
| 7 | Words as letters | Not run | |
| 8 | 50,000 letters | Not run |