Note that the property by which you are defining the Huffman encoding is not entirely obvious from the algorithm, and was not stated in your original node.

Certainly I had no idea what you meant. I had a distinct impression that we were to come up with another tree which could be produced by the same algorithm as the first. I think it would have really helped to have some complex inputs and complex outputs. Or to have a program which could be used to validate things.

Otherwise I guarantee that, for instance, someone will try to get the bonus and (for instance) use a naive recursive algorithm get the wrong result on the case where a-r are weighted 1 each, and S and T get 3. The ouput should be: 

a 1 00000
b 1 00001
c 1 00010
d 1 00011
e 1 00100
f 1 00101
g 1 00110
h 1 00111
i 1 01000
j 1 01001
k 1 01010
l 1 01011
m 1 01100
n 1 01101
o 1 01110
p 1 01111
q 1 1000
r 1 1001
S 3 101
T 3 11

[download]
However a recursive approach will have a hard time figuring out where is globally best to take the penalties of incorrect weights.

In reply to Re (tilly) 5: A Brainteaser -- Huffman with a twist by tilly
in thread A Golf question maybe? Huffman with a twist by demerphq

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.