comment on

my girlfriend told me the following riddle:

there was a king with a beautiful daughter who he wanted to marry off to someone worthy. so he said that anyone who could solve the riddle could marry his daughter. anyone who tried but failed would be beheaded. the riddle was about 12 pearls. one was real and the others were fake. the only difference between them was that the real one was a grain diffent in weight (you don't know if it's heavier or lighter). given a balance and three attempts, figure out which one is the real pearl and tell whether it is heavier or lighter.

after beating my head against a wall for a few hours i came up with the following solution:

step 1: weigh 1-4 against 5-8. if they weigh the same, we know the real one's in 9-12 and proceed to 2a otherwise proceed to step 2b. step 2a : weigh 9-11 against 1-3. if they're the same, we know it's 12. weigh 12 against any of the others to determine if it's lighter or heavier then you're done. if 9-11 was heavier than 1-3, you know that the real one is heavy. weigh 9 against 10. if they're equal 11 is the real one. otherwise, the heavier of 9 and 10 is the real one. step 2b: weigh 1,2,5,6 against 9,10,3,7. (assume 1,2,3,4 was heavier than 5,6,7,8 in step 1. the technique is symmetric; i'll leave it as an exercise to the reader to work out how to do it if it was lighter) if 1,2,3,6 is heavier than we know that either 1 or 2 is heavy or 7 was light. if 1,2,5,6 was lighter, we know that 5 or 6 was light or 3 was heavy. if they were the same, we know that 4 was heavy or 8 was light (test either one against a known fake and you're done). in the case of (1,2) heavy or 7 light, weigh 1,7 against X,X (X is any known fake). if 1,7 is heavier, 1 is the heavy pearl; if lighter, 7 is the light pearl; if the same, 2 is the heavy pearl. same idea if (5,6) light or 3 heavy: just test 5,3 against X,X

which is really complicated and i don't think explains it that clearly. to both make sure i'd figured it out and to explain it more fully, i wrote some perl code:

#!/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" ) . ". fou
+nd in $test_counter tests.\n";
}
[download]

that's functional, demonstrates that it works, and is relatively easy to read but was not written for brevity.

so the golf is to recode the find_pearl sub. as the comments say, it gets passed a list of 12 weights and must return the index of the one that is different and whether it is lighter or heavier. you have access to the weigh() subroutine which takes references to two arrays and tells you which was heavier. weigh() is the only way that you're allowed to examine the weights themselves. any other testing of the contents of the list by any means is grounds for disqualification. naturally, you can't exceed the 3 test limit either.

solutions don't have to run under strict (10 stroke bonus if it does though).

the weights aren't restricted to the 0,1,2 that i use in the example code. this shouldn't matter though since you can only access them through weigh().

i'm thinking that with the symmetric nature of the algorithm, a good strategy may be generating code on the fly and eval()ing it. good luck.

update: by popular request, added <readmore> tags.

anders pearson

In reply to (GOLF) pearls and perl by thraxil

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:
	&		`&`
	<		`<`
	>		`>`
	[		`[`
	]		`]`

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.