Blowing Down The House (solution)
by David Turner with suggestions from Andrew Lin
The block of data is Huffman-encoded with a 3-ary tree generated from the provided frequency table. When three items are to be encoded at the same level of the tree, the least-frequent gets a zero and the most-frequent gets a 2.
The resulting Huffman code is:
| [space] | 10 |
| A | 010 |
| B | 122 |
| C | 221 |
| D | 111 |
| E | 00 |
| F | 121 |
| G | 011 |
| H | 200 |
| I | 012 |
| J | 1102 |
| K | 2021 |
| L | 212 |
| M | 210 |
| N | 220 |
| O | 222 |
| P | 120 |
| Q | 11000 |
| R | 02 |
| S | 211 |
| T | 201 |
| U | 112 |
| V | 1101 |
| W | 2022 |
| X | 11001 |
| Y | 2020 |
| Z | 11002 |
The decoded data reads:
REENCODE THIS STRING OPTIMALLY THEN DECODE USING THE ORIGINAL CODE YOUR ANSWER WILL APPEAR FOLLOWED BY GIBBERISH WHEN OPTIMIZING INCLUDE THE FOLLOWING PADDING BOXTOP CLAMPS CLAY DAN DRILL DUMP DUNK FAMILY FEVER FLAY FLUB GRAMMAR GRAMPS GROW GUNK HIGHWAY HIM HUMPS HUNT JACK JAY JOKER JOVIAL JUMPER JUNK KISMET LOUSE MAJOR MAST MAZE NEON NEST NOSE PLANTS PLOTS PUSHED QUICK RAFFLE ROAD SLIM SLOT SO STOOP STUMPED SWANK THEOREM THINK THUMP UNDERWHELM VIKING VIXEN WARP WHAMMY WHIG WHISKEY ZACK
This has the following frequencies:
| [space] | 78 |
| A | 28 |
| B | 5 |
| C | 9 |
| D | 16 |
| E | 34 |
| F | 8 |
| G | 14 |
| H | 19 |
| I | 29 |
| J | 7 |
| K | 12 |
| L | 25 |
| M | 22 |
| N | 26 |
| O | 27 |
| P | 18 |
| Q | 1 |
| R | 21 |
| S | 23 |
| T | 20 |
| U | 17 |
| V | 4 |
| W | 13 |
| X | 2 |
| Y | 10 |
| Z | 3 |
The optimal Huffman code is then:
| [space] | 21 |
| A | 222 |
| B | 1011 |
| C | 2012 |
| D | 102 |
| E | 01 |
| F | 2011 |
| G | 100 |
| H | 112 |
| I | 00 |
| J | 2010 |
| K | 021 |
| L | 202 |
| M | 122 |
| N | 220 |
| O | 221 |
| P | 111 |
| Q | 10120 |
| R | 121 |
| S | 200 |
| T | 120 |
| U | 110 |
| V | 1010 |
| W | 022 |
| X | 10121 |
| Y | 020 |
| Z | 10122 |
Encoding with the optimal tree and then decoding with the original generates the answer, FABRIC, followed by garbage.