Limbic~Region:

Here's kind of what I was thinking. The Huffman tree keeps the most common animals (fish, dog, cat) at the top of the tree with few questions, and the unusual critters (unicorn, pegasus, axolotl) at the bottom of the tree.

Is this something along the lines of what you're after?

#!/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], $quest
+ion_depth+1);
        $sum_questions += compute_avg_num_guesses($t->[0][1], $questio
+n_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

[download]

Running it gives me:

$ perl huffman.pl
Total occurrences: 697
Animal: walrus, depth 5 * occurrences 15 ==> 75
Animal: badger, depth 5 * occurrences 17 ==> 85
Animal: seal, depth 5 * occurrences 18 ==> 90
Animal: pegasus, depth 8 * occurrences 1 ==> 8
Animal: axolotl, depth 9 * occurrences 1 ==> 9
Animal: unicorn, depth 9 * occurrences 1 ==> 9
Animal: hamster, depth 7 * occurrences 5 ==> 35
Animal: ocelot, depth 7 * occurrences 5 ==> 35
Animal: gerbil, depth 8 * occurrences 3 ==> 24
Animal: platypus, depth 8 * occurrences 3 ==> 24
Animal: cow, depth 3 * occurrences 75 ==> 225
Animal: fish, depth 2 * occurrences 150 ==> 300
Animal: dog, depth 3 * occurrences 85 ==> 255
Animal: cat, depth 3 * occurrences 91 ==> 273
Animal: wolverine, depth 5 * occurrences 22 ==> 110
Animal: frog, depth 5 * occurrences 28 ==> 140
Animal: wolf, depth 4 * occurrences 55 ==> 220
Animal: sheep, depth 4 * occurrences 60 ==> 240
Animal: horse, depth 4 * occurrences 62 ==> 248
Avg: 3.45050215208034

[download]

So if I haven't screwed up, it looks like given the stated distributions and guesses, that you'd need 3.45 guesses on average.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

In reply to Re^3: Challenge: Optimal Animals/Pangolins Strategy by roboticus
in thread Challenge: Optimal Animals/Pangolins Strategy by Limbic~Region

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.