#!/usr/bin/perl -wT
use strict;

my $test_counter = 0;

my @pearls = (1,1,1,1,1,1,1,1,1,1,1,1);

# exhaustively test it.
foreach my $n (0..11) {
    my @test = @pearls;

    # make pearl n light
    $test[$n] = 0;
    $test_counter = 0;
    &answer(&find_pearl(@test));

    # make pearl n heavy
    $test[$n] = 2;
    $test_counter = 0;
    &answer(&find_pearl(@test));
}



# pass in an array of pearl weights
# 11 must be the same. returns the index
# of the pearl that is different and 
# a 0 if it was lighter than the rest or
# a 1 if it was heavier than the rest.
# only accesses the elements of the array
# via the weigh subroutine (which it may only call
# 3 times).

sub find_pearl {
    my @p = @_;

    my @g1 = @p[0..3];
    my @g2 = @p[4..7];
    my @g3 = @p[8..11];
    my $weigh1 = &weigh(\@g1,\@g2);
    if($weigh1 == 0) {
	# equal
	my $w2 = &weigh([@p[0..2]],[@p[8..10]]);
	if($w2 == 0) {
	    # #12 is the real one
	    my $w3 = &weigh([$p[0]],[$p[11]]);
	    if($w3 > 0) {
		return (11,0);
	    } else {
		return (11,1);
	    }
	} elsif ($w2 < 0) {
	    # heavy one in 8-10
	    my $w3 = &weigh([$p[8]],[$p[9]]);
	    if($w3 == 0) {
		return (10,1);
	    } elsif ($w3 < 0) {
		return (9,1);
	    } else {
		return (8,1);
	    }
	} else {
	    # light one in 8-10
	    my $w3 = &weigh([$p[8]],[$p[9]]);
	    
	    if($w3 == 0) {
		return (11,0);
	    } elsif ($w3 < 0) {
		return (8,0);
	    } else {
		return (9,0);
	    }
	}
    } elsif ($weigh1 < 0) {
	# light in 0-3 or heavy in 4-7
	my $w2 = &weigh([$p[4],$p[5],$p[0],$p[1]],
			[$p[8],$p[9],$p[6],$p[2]]);
	if($w2 == 0) {
	    # either 3 is light or 7 is heavy
	    my $w3 = &weigh([$p[0]],[$p[3]]);
	    if($w3 == 0) {
		return (7,1);
	    } elsif ($w3 < 0) {
		die "should not be possible";
	    } else {
		return (3,0);
	    }
	} elsif ($w2 < 0) {
	    # 0 or 1 is light or 6 is heavy
	    my $w3 = &weigh([$p[0]],[$p[1]]);
	    if($w3 == 0) {
		return (6,1);
	    } elsif ($w3 < 0) {
		return (0,0);
	    } else {
		return (1,0);
	    }
	} else {
	    # 4 or 5 is heavy or 2 is light
	    my $w3 = &weigh([$p[4]],[$p[5]]);
	    if($w3 == 0) {
		return (2,0);
	    } elsif ($w3 < 0) {
		return (5,1);
	    } else {
		return (4,1);
	    }
	}
    } else {
	# heavy in 0-3 or light in 4-7
	my $w2 = &weigh([$p[0],$p[1],$p[4],$p[5]],
			[$p[8],$p[9],$p[2],$p[6]]);
	if($w2 == 0) {
	    # 3 heavy or 7 light
	    my $w3 = &weigh([$p[3]],[$p[0]]);
	    if($w3 == 0) {
		return (7,0);
	    } elsif ($w3 < 0) {
		die "should not be possible";
	    } else {
		return (3,1);
	    }
	} elsif ($w2 < 0) {
	    # 4 or 5 light or 2 heavy
	    my $w3 = &weigh([$p[4]],[$p[5]]);
	    if($w3 == 0) {
		return (2,1);
	    } elsif ($w3 < 0) {
		return (4,0);
	    } else {
		return (5,0);
	    }
	} else {
	    # 0 or 1 heavy or 6 light
	    my $w3 = &weigh([$p[0]],[$p[1]]);
	    if($w3 == 0) {
		return (6,0);
	    } elsif ($w3 < 0) {
		return (1,1);
	    } else {
		return (0,1);
	    }
	}
    }
}

# pass it references to two arrays of weights
# returns -1 if the first array is lighter,
# 0 if they're the same or 1 if the first is
# heavier. increments $test_counter.

sub weigh {
    my $group1 = shift;
    my $group2 = shift;

    my $weight1 = 0;
    my $weight2 = 0;

    foreach my $pearl (@{$group1}) {
	$weight1 += $pearl;
    }

    foreach my $pearl (@{$group2}) {
	$weight2 += $pearl;
    }
    $test_counter++;
    return $weight1 <=> $weight2;
}

sub answer {
    my ($num,$weight) = @_;
    print "pearl #$num was " . ($weight ? "heavy" : "light" ) . ". found in $test_counter tests.\n";
}