#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

# Read list of animals/occurrences into @T
my @T;
my $ttl=0;
while (<DATA>) {
    next if /^\s*$/;
    my ($animal, $occurrences) = split /\s+/, $_;
    $ttl += $occurrences;
    my $t = bless [ $animal, $occurrences ], "Animal";
    insert( $t );
}
print "Total occurrences: $ttl\n";

# Turn it into a huffman tree
while (@T > 1) {
    my $L = shift @T;
    my $R = shift @T;
    my $t = bless [ [$L, $R], $L->[1]+$R->[1] ], "Question";
    insert( $t );
}
#print Dumper($T[0]);

my $avg = compute_avg_num_guesses($T[0]) / $ttl;
print "Avg: $avg\n";

sub compute_avg_num_guesses {
    my $t = shift;
    my $question_depth = shift // 0;
    if (ref $t eq "Animal") {
        my $num_questions = $t->[1] * $question_depth;
        print "Animal: $t->[0], depth $question_depth * occurrences $t->[1] ==> $num_questions\n";
        return $num_questions;
    }
    else {
        my $sum_questions = compute_avg_num_guesses($t->[0][0], $question_depth+1);
        $sum_questions += compute_avg_num_guesses($t->[0][1], $question_depth+1);
        return $sum_questions;
    }
}

sub insert {
    # Inserting in order simplifies the conversion into a huffman tree...
    my $t = shift;
    push @T, $t;
    my $idx = $#T;
    while ($idx) {
        ($T[$idx],$T[$idx-1]) = ($T[$idx-1],$T[$idx]) if $T[$idx][1] < $T[$idx-1][1];
        --$idx;
    }
}

__DATA__
fish 150
horse 62
dog 85
cat 91
frog 28
axolotl 1
gerbil 3
hamster 5
ocelot 5
platypus 3
seal 18
badger 17
walrus 15
wolf 55
wolverine 22
sheep 60
cow 75
unicorn 1
pegasus 1