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

Replies are listed 'Best First'.
Re: (GOLF) pearls and perl
by tachyon (Chancellor) on Apr 04, 2002 at 13:17 UTC

    At 224 returns general weight, different pearl weight and index of under/over weight pearl as an array. Runs under strict. Unfortunately if your first two groups of 4 pearls do not weigh the same you need 4 goes...oh well who needs a head. 

    use strict;
my @pearls = (1,1,1,1,1,1,1,1,1,1,2,1);
$, = ",  ";
print perl(@pearls);

#234567890123456789012345678901234567890123456789012345678901234567890
sub perl {
sub w{$"='+';eval"@_"}my@p=@_;@p=w(@p[0..3])==w(@p[4..7])?@p[8..11,0]:
w(@p[0..3])==w(@p[8..11])?@p[4..8]:@p[0..4];$a=pop@p;@p=w(@p[0,1])==$a
*2?@p[2,3]:@p[0,1];@p=(@p[0]==$a)?@p[1]:@p[0];map{$b=$_[$_]!=$a?$_:$b}
0..11;$a,@p,$b
}

    [download]

    cheers

    tachyon

    s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print

[reply]
[d/l]
Re: (GOLF) pearls and perl
by particle (Vicar) on Apr 04, 2002 at 14:10 UTC
    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 2a of your algorithm is not correct. tachyon's right. you'll lose your head--there's an extra weighing here. instead, it should go something like this:

    step 2a : weigh 9 against 10. if they're the same, we know it's 11 or twelve. then weigh 9 against 11. if they're the same, we know it's twelve; if they're different, it's 11 and you're done. if 9 and 10 are different, weigh 9 against 11. if they're the same, it's 10; if they're different, it's 9 and you're done.

    my logic for this bit, which works under strict and warnings, is

    $p[8]==$p[9]?$p[8]==$p[10]?12:11:$p[8]==$p[10]?10:9;

    or, building the return matrix and putting it in a sub:

    do{([9,10],[11,12])[$p[8]==$p[9]]->[$p[8]==$p[10]]}

    which is one char shorter.

    ~Particle ;Þ

[reply]
[d/l]
[select]

      my prose explanation may be unclear but i think it's correct. look closely at the example code. running it gives:

      pearl #0 was light. found in 3 tests.
pearl #0 was heavy. found in 3 tests.
pearl #1 was light. found in 3 tests.
pearl #1 was heavy. found in 3 tests.
pearl #2 was light. found in 3 tests.
pearl #2 was heavy. found in 3 tests.
pearl #3 was light. found in 3 tests.
pearl #3 was heavy. found in 3 tests.
pearl #4 was light. found in 3 tests.
pearl #4 was heavy. found in 3 tests.
pearl #5 was light. found in 3 tests.
pearl #5 was heavy. found in 3 tests.
pearl #6 was light. found in 3 tests.
pearl #6 was heavy. found in 3 tests.
pearl #7 was light. found in 3 tests.
pearl #7 was heavy. found in 3 tests.
pearl #8 was light. found in 3 tests.
pearl #8 was heavy. found in 3 tests.
pearl #9 was light. found in 3 tests.
pearl #9 was heavy. found in 3 tests.
pearl #11 was light. found in 3 tests.
pearl #10 was heavy. found in 3 tests.
pearl #11 was light. found in 3 tests.
pearl #11 was heavy. found in 3 tests.

      if you get to step 2a, you've already used the balance once and you know that the pearl is in 9-12 and therefore 1-8 are all fakes. weighing 1-3 against 9-11 (your second use of the balance) tells you immediately whether it's 12 or one of 9-11 as well as whether it's light or heavy. if you know it's 12 you have to do another weigh (your third) to tell if it's lighter or heavier. if it's one of the other 3, you weigh 9 against 10 (your third). equal means that it's 11 and you know if it's light or heavy from the previous 1-3 vs 9-11 weighing. if you know that it's heavy you take the heavier of the two you just weighed; lighter, you take the lighter of the two.

      is that more clear?

      actually, i think your version of 2a will run into four weighs. take the case where it's 12. first, you've already weighed 1-4 against 5-8 before you get there. then you weigh 9 against 10 (#2). they're the same so you weigh 9 against 11 (#3). you know that it's 12 but don't have any way of knowing if it's heavy or light so your best bet then would be to guess and be happy with a 50/50 chance of losing your head.

      anders pearson

[reply]
        yeah, you're right. my solution ignores the weight... oops! i've bookmarked this thread, i'd like to work on it when i get some time. i'd like to set up an 3d answer matrix, and use code only in the indices (as in (answers)[code]) like i did in my (incorrect) example above.

        ~Particle ;Þ

[reply]
[d/l]
Re: (GOLF) pearls and perl
by jwest (Friar) on Apr 04, 2002 at 16:04 UTC
    My first round of golf, so be gentle... I took a slightly different route to get to the same solution:

    use strict;
my @p = (1,1,1,1,1,1,1,1,2,1,1,1);
print perl(),"\n";

sub perl{sub w{my$h=int(($_[1]-$_[0])/2+$_[0]);$"='+';my$o=eval"@p[$_[
+0]..$h]";
my$t=eval"@p[$h+1..$_[1]]";$o<=>$t?(($o<=>$t)==1?($_[0],$h):($h+1,$_[1
+])):undef;}
my@r=w(w(0,11));my$v=$p[$r[0]]<=>$p[$r[0]+1];$v?($v==1?$r[0]:$r[0]+1):
+$r[1];}

    [download]

    I count this at 237 characters. Hopefully I haven't violated any of the rules...

    --jwest 
    -><- -><- -><- -><- -><-
All things are Perfect
    To every last Flaw
    And bound in accord
         With Eris's Law
 - HBT; The Book of Advice, 1:7
[reply]
[d/l]

      well, it doesn't return anything when the pearl is lighter and it doesn't return whether the pearl found is heavier or lighter. good try though. i'm still examining the code trying to figure out if your overriding of the weighing breaks any rules.

      anders pearson

[reply]
Interesting, but please edit
by RMGir (Prior) on Apr 05, 2002 at 16:40 UTC
    It's an interesting problem, but could you please insert a <readmore> tag before the long blanked out blocks?

    Your post is making the meditations page very hard to read...

    Thanks!
    --
    Mike

    (Edit: I was going to delete this, since I /msg'd the author, but I figure the suggestion is a good one for folks to see in public, in case they don't know about <readmore>)

[reply]

Back to Meditations