#!/usr/local/perl5.8/bin/perl -w

use strict;
use Data::Dumper;


my %balls;
# at the start they might all be heavy or light
my @might_be_heavy;
my @might_be_light;
# and we don't know if any of them are normal
my @normal_balls;


for (0..9) {

    %balls = initialize_balls();
    # at the start they might all be heavy or light
    @might_be_heavy = keys %balls;
    @might_be_light = keys %balls;
    # and we don't know if any of them are normal
    @normal_balls = ();

    #map {print "$_ -> $balls{$_}\n"} keys %balls;

    my $oddball;
    my $weighing = 0;
    while (1) {
        last if ($oddball = pick_a_winner(\@normal_balls));
        $weighing++;
        #print "Starting round $weighing\n";
        my ($leftside, $rightside, $unused) = pick_balls(\@might_be_he
+avy, \@might_be_light, \@normal_balls);
        check_ball_heft($leftside, $rightside, $unused);
        
        #print Dumper(\@might_be_heavy);
        #print Dumper(\@might_be_light);
        #print Dumper(\@normal_balls);

    }
    print "Ball $oddball is the odd ball.  Took $weighing weighings.\n
+";
}

# subs

sub initialize_balls {
    my %balls = map {$_, 1} 1..12;
    my $num = int( rand 12 ) + 1; 
    my $adj = .1 * (int( rand 2 ) ? 1 : -1);
    $balls{$num} += $adj;
    return %balls;
}

sub check_ball_heft {
    my ($left, $right, $unused) = @_;
    die "Both sides must have the same number of balls." unless (scala
+r keys %{$left} == scalar keys %{$right});
    if (heft([values %{$left}]) > heft([values %{$right}])) {
        #print "Left is heavier.\n";
        record_results([keys %{$left}], [keys %{$right}]);
        i_am_normal([keys %{$unused}]);
    } elsif (heft([values %{$left}]) < heft([values %{$right}])) {
        #print "Right is heavier.\n";
        record_results([keys %{$right}], [keys %{$left}]);
        i_am_normal([keys %{$unused}]);
    } else {
        #print "They are the same.\n";
        i_am_normal([keys %{$left}, keys %{$right}]);
    }

}

sub record_results {
    my ($heavy_balls, $light_balls) = @_;
    # remove lighter side balls from @might_be_heavy
    # and heavier side balls from @might_be_light
    foreach my $heavy_ball (@{$heavy_balls}) {
        @might_be_light = grep {$_ != $heavy_ball} @might_be_light;
    }
    foreach my $light_ball (@{$light_balls}) {
        @might_be_heavy = grep {$_ != $light_ball} @might_be_heavy;
    }

}


sub i_am_normal {
    my ($normal_balls) = @_;
    # add all these balls to @normal_balls and remove them from heavy 
+or light
    foreach my $normal_ball (@{$normal_balls}) {
        unshift @normal_balls, $normal_ball unless (grep {$_ == $norma
+l_ball} @normal_balls);
        @might_be_heavy = grep {$_ != $normal_ball} @might_be_heavy;
        @might_be_light = grep {$_ != $normal_ball} @might_be_light;
    }
}

sub heft {
    my ($balls) = @_;
    my $heft = 0;
    foreach my $ball (@{$balls}) {
        $heft += $ball;
    }
    return $heft;
}

sub pick_balls {
    my ($maybe_heavy, $maybe_light, $normal) = @_;
    my $left;
    my $right;
    my %unused = %balls;

    # randomly
    my $balls_to_weigh = int(rand 5) + 1;
    for (1..$balls_to_weigh) {
        my $left_ball = (keys %unused)[int(rand(scalar keys %unused)-1
+) + 1];
        $left->{$left_ball} = $unused{$left_ball};
        delete $unused{$left_ball};
        my $right_ball = (keys %unused)[int(rand(scalar keys %unused)-
+1) + 1];
        $right->{$right_ball} = $unused{$right_ball};
        delete $unused{$right_ball};
    }


    return $left, $right, \%unused;
}

sub pick_a_winner {
    my ($normal) = @_;
    # if there are 11 normal balls, we know which is the oddball.
    if (scalar @{$normal} == 11) {
        my $oddball;
        for my $starting_ball (1..12) {
            $oddball = $starting_ball unless grep {$_ == $starting_bal
+l} @{$normal};
        }
        return $oddball;
    }
    return;
}
[download]