This question already has an answer here:
- Code the Huffman! 7 answers
Write a filter that converts text from standard input to a representation of its Huffman tree on standard output. In as few characters as possible.
- you're free to consider newlines or not
- output format is free, as long as it's some human-readable encoding of a tree. s-exps, ascii-art and .png, all good. RPN, .dot, I'll smile or frown, but that ought to be ok. Program cores and/or raw pointers , no way.
- no canonicalization needed; if the characters are at the right depth, that's good enough.
Sample possible output for "this is an example of a huffman tree" (from wikipedia):
(((e . (n . (o . u))) . (a . (t . m))) . (((i . (x . p)) . (h . s)) . (((r . l) . f) . #\space)))
I can't reproduce all possible valid outputs with human-readable representation combinations in here (the margin is a bit too thin), but what should check is which characters end up at which number of bits:
- 3 bits: a e [space]
- 4 bits: f h i m n s t
- 5 bits: l o p r u x
If [newline] is kept in, it appears appears in the "5 bits" level, but (any) two characters have to drop from there to 6 bits.