googleの面接のパズルを颯爽と解いてみた。

とりあえず、(1)から(13)まで番号を振る
(1)(2)(3)(4)と(5)(6)(7)(8)を天秤に乗せる

傾いたら
    残りの(9)-(13)は本物
    (1)(2)(3)(5)(6)と(9)(10)(11)(12)(13)を天秤に載せる
    傾いたら
        ここで偽者が重いか軽いかが判明
        かつ、一回目の結果を考えると、(1)(2)(3) OR (5)(6) のいずれに偽者が含まれるかも判明
        (1)(2)(3)に偽者が含まれるなら
            (1)と(2)を比較。
        (5)(6)に偽者が含まれる
            (5)と(6)を比較
    傾かなかったら
        (4)(7)と(12)(13)を比較
        傾いたら
            偽者が重いか軽いかが分かる。
            かつ、一回目の結果を考えれば、(4)と(7)のどちらが重いか分かるので、判定可能
        傾かなかったら
            (8)が偽者(重いか軽いかは分からず)
傾かなかったら
    残りの(9)-(13)に偽者が含まれる。(1)から(8)は本物
    (1)(2)(3)と(9)(10)(11)を天秤に
    傾いたら
        偽者が重いか軽いかが分かる
        (9)と(10)を天秤に
    傾かなかったら
        (12)(13)のいずれかが偽者
        (1)と(12)を天秤に

#!/usr/bin/perl
use strict;
sub which_is_heavy {
    my ($left, $right) = @_;

    #この辺は本来ならブラックボックス
    my ($left_mass, $right_mass);
    map { $left_mass += $_ } @$left;
    map { $right_mass += $_ } @$right;

    return $left_mass > $right_mass    ? 'left'
            : $left_mass < $right_mass ? 'right'
            :                            'balanced';
}
 
sub get_fake_from_three {
    #偽者が重いか軽いか分かってれば3つのコインから一発で偽者を割り出せるよ関数
    my ($fake, @coins) = @_;
    if ($coins[0] > $coins[1] ) {
        return $fake eq 'heavy' ? 0 : 1;
    }
    elsif ( $coins[0] < $coins[1] ) {
        return $fake eq 'heavy' ? 1 : 0;
    }
    else {
        return 2;
    }
}
 
sub get_fake {
    my @c = @_;
    my $first_result = which_is_heavy( [ @c[0..3] ] ,[ @c[4..7] ] );
    if ($first_result eq 'balanced' ) {
        #0-7は本物
        my $second_result = which_is_heavy( [@c[0..2]], [@c[8..10]] );
        if ($second_result eq 'balanced' ) {
            #11,12が偽者
            my $third_result = which_is_heavy( [ $c[0] ], [ $c[11] ]);
            return $third_result eq 'balanced' ? 12 : 11;
        }
        else {
            #8-10に偽者かつ重いか軽いかが判明
            my $fake = $second_result eq 'left' ? 'light' : 'heavy';
            return 8 + get_fake_from_three($fake, @c[8..10]);
        }
    }
    else {
        #8-12は本物
        my $second_result = which_is_heavy( [$c[0],$c[1],$c[2],$c[4],$c[5]],[@c[8..12]] );
        if ($second_result eq 'balanced' ) {
            my $third_result = which_is_heavy( [$c[3], $c[6]], [@c[8..9]] );
            if ( $third_result eq 'left') {
                return $first_result eq 'left' ? 3 : 6;
            }
            elsif ( $third_result eq 'right' ) {
                return $first_result eq 'left' ? 6 : 3;
            }
            else {
                return 7;
            }
        }
        else {
            my $fake = $second_result eq 'left' ? 'heavy' : 'light';
            if ( ( $fake eq 'heavy' && $first_result eq 'left' )
              || ( $fake ne 'heavy' && $first_result ne 'left' ) ) {
                return get_fake_from_three( $fake, @c[0..2] );
            }
            else {
                if ( $fake eq 'heavy' ) {
                    return $c[4] > $c[5] ? 4 : 5;
                }
                else {
                    return $c[4] > $c[5] ? 5 : 4;
                }
            }
        }
    }
}
 
print get_fake( 3,2,2,2,2,2,2,2,2,2,2,2,2 ) . " will be 0\n";
print get_fake( 2,3,2,2,2,2,2,2,2,2,2,2,2 ) . " will be 1\n";
print get_fake( 2,2,3,2,2,2,2,2,2,2,2,2,2 ) . " will be 2\n";
print get_fake( 2,2,2,3,2,2,2,2,2,2,2,2,2 ) . " will be 3\n";
print get_fake( 2,2,2,2,3,2,2,2,2,2,2,2,2 ) . " will be 4\n";
print get_fake( 2,2,2,2,2,3,2,2,2,2,2,2,2 ) . " will be 5\n";
print get_fake( 2,2,2,2,2,2,3,2,2,2,2,2,2 ) . " will be 6\n";
print get_fake( 2,2,2,2,2,2,2,3,2,2,2,2,2 ) . " will be 7\n";
print get_fake( 2,2,2,2,2,2,2,2,3,2,2,2,2 ) . " will be 8\n";
print get_fake( 2,2,2,2,2,2,2,2,2,3,2,2,2 ) . " will be 9\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,3,2,2 ) . " will be 10\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,2,3,2 ) . " will be 11\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,2,2,3 ) . " will be 12\n";
 
print get_fake( 1,2,2,2,2,2,2,2,2,2,2,2,2 ) . " will be 0\n";
print get_fake( 2,1,2,2,2,2,2,2,2,2,2,2,2 ) . " will be 1\n";
print get_fake( 2,2,1,2,2,2,2,2,2,2,2,2,2 ) . " will be 2\n";
print get_fake( 2,2,2,1,2,2,2,2,2,2,2,2,2 ) . " will be 3\n";
print get_fake( 2,2,2,2,1,2,2,2,2,2,2,2,2 ) . " will be 4\n";
print get_fake( 2,2,2,2,2,1,2,2,2,2,2,2,2 ) . " will be 5\n";
print get_fake( 2,2,2,2,2,2,1,2,2,2,2,2,2 ) . " will be 6\n";
print get_fake( 2,2,2,2,2,2,2,1,2,2,2,2,2 ) . " will be 7\n";
print get_fake( 2,2,2,2,2,2,2,2,1,2,2,2,2 ) . " will be 8\n";
print get_fake( 2,2,2,2,2,2,2,2,2,1,2,2,2 ) . " will be 9\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,1,2,2 ) . " will be 10\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,2,1,2 ) . " will be 11\n";
print get_fake( 2,2,2,2,2,2,2,2,2,2,2,2,1 ) . " will be 12\n";