use strict;
use warnings;
use Data::Dump qw/pp dd/;



# my @freq = qw/5 7 10 15 20 45/;
# my $sym = "1";
# my @tree = map { [ $_ => $sym++ ] } @freq;

my %freq = (
  ""    => 592,
  "2"   => 74,
  "24"  => 60,
  "246" => 24,
  "247" => 24,
  "248" => 24,
  "249" => 24,
  "25"  => 84,
  "257" => 24,
  "258" => 24,
  "259" => 24,
  "26"  => 84,
  "268" => 24,
  "269" => 24,
  "27"  => 84,
  "279" => 24,
  "28"  => 84,
  "29"  => 60,
  "3"   => 208,
  "35"  => 144,
  "357" => 48,
  "358" => 48,
  "359" => 48,
  "36"  => 192,
  "368" => 48,
  "369" => 48,
  "37"  => 192,
  "379" => 48,
  "38"  => 192,
  "39"  => 144,
  "4"   => 366,
  "46"  => 228,
  "468" => 72,
  "469" => 72,
  "47"  => 300,
  "479" => 72,
  "48"  => 300,
  "49"  => 228,
  "5"   => 524,
  "57"  => 312,
  "579" => 96,
  "58"  => 408,
  "59"  => 312,
  "6"   => 682,
  "68"  => 396,
  "69"  => 396,
  "7"   => 840,
  "79"  => 336,
  "8"   => 830,
  "9"   => 508,
);


my @tree = map { [ $freq{$_} => $_ ] } keys %freq;


#warn pp \@tree;
#exit;

while ( @tree > 1 ) {
    @tree = sort { $a->[0] <=> $b->[0] } @tree;
    my $left  = shift @tree;
    my $right = shift @tree;
    unshift @tree, [  ($left->[0] + $right->[0]) =>  [ $left, $right ] ];
}

#warn pp \@tree;

my %huff;
create_code($tree[0],"");

#warn pp \%huff;

my $avr = 0;
$avr += $freq{$_} * length($huff{$_}) / 10000
    for keys %freq;

my $classic = log(50)/log(2);

my $old=0;
$old += $freq{$_} * length($_) * 8 / 10000
    for keys %freq;

$old += 8/9 ;                              # \n


warn pp {
    "old"          => $old,
    "line"         => $old*9/8 . " bytes",
    "huff average" => $avr ,
    "classic length" => $classic ,
    "huff win"     => $avr/$old*100     ." %",
    "classic win"  => $classic/$old*100 ." %",
}; 


sub create_code {
    my ($node,$code) = @_;
    my $sym  = $node->[1];
    if ( ref $sym ) {
        create_code( $sym->[0], $code."0" );
        create_code( $sym->[1], $code."1" );
    } else {
        $huff{$sym} = $code;
    }
}