水の移し替えパズル in Perl DouKaku?

A, B, Cの容器があり，それぞれ水が4L, 2L, 10L入っている．ここで次の操作を繰り返す．

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ，残りの容器に移す．」

たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる．くみ上げる前の容器には必ず水が入っているとする．

(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ．

可能ならA=827392L，B=65536L，C=122880Lのときも求めよ．

このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。

とりあえず愚直に。まだだれもperlで投稿してないのでテスト。 3つの要素を比較して１番小さな要素を足していきます。１問目は $VAR1 = { '1' => 3, '3' => 9, '2' => 4 }; $VAR1 = { '1' => 5, '3' => 8, '2' => 3 }; $VAR1 = { '1' => 4, '3' => 7, '2' => 5 }; $VAR1 = { '1' => 6, '3' => 6, '2' => 4 }; 1と3のバケツが6と6になったので　以下略。で　10手２問目は大きすぎるのではしょって ...一番最後 $VAR1 = { '1' => 338603, '3' => 338602, '2' => 338603 }; 827392手みたいです。

see: みんな神すぐる件

use Data::Dumper;

my %hash = (
    1 => 827392,
    2 => 65536,
    3 => 122880,
);

my $calc_cnt = 0;

until ( any_eqv( \%hash ) ) {

    ++$calc_cnt;

    my $mini_key = get_mini_key( \%hash );
    $hash{$mini_key} += 2;

    @other_key = get_other_key($mini_key);
    for (@other_key) {
        $hash{$_} -= 1;
    }
}

print Dumper( \%hash );

$nokori = get_same_val( \%hash );
print "The answer is " . ( $calc_cnt + $nokori );

sub any_eqv {
    my $hash_ref = shift;
    my %hash     = %{$hash_ref};

    if (   $hash{1} == $hash{2}
        or $hash{2} == $hash{3}
        or $hash{3} == $hash{1} )
    {
        return 1;
    }
    else {
        return 0;
    }
}

sub get_mini_key {
    my $hash_ref = shift;
    my %hash     = %{$hash_ref};
    my $mini     = $hash{1};
    my $mini_key;
    for ( 1 .. 3 ) {
        $mini = $hash{$_} xor $mini_key = $_
            if ( $mini >= $hash{$_} );

    }
    return $mini_key;
}

sub get_other_key {

    my $target = shift;
    my $list   = '123';
    $list =~ s/$target//;
    return split( //, $list );
}

sub get_same_val {

    my $hash_ref = shift;
    my %hash     = %{$hash_ref};

    if ( $hash{1} == $hash{2} ) {
        return $hash{1};
    }
    elsif ( $hash{2} == $hash{3} ) {
        return $hash{2};
    }
    elsif ( $hash{3} == $hash{1} ) {
        return $hash{3};
    }
}

IDをはじめて取得してみました。

かなり変態的に。
解が無いもの

”要素の合計が３で割り切れ
且つ　要素が互いに異なるもの”

に対しては　むりぽ　と叫んでdieします。

一問目は　10
二問目は　827392

 (m,n,l)の配列で

m != n !=  l
の時の最短の手法は　一番大きな要素になります。

＊　一番大きな要素を１ずつ削っていくため。

m と　n または
n と l　または
m　と l  が同じ値の時、
同じ値の数値が最短の手法になります。

＊　同じ容器から１ずつ削っていくため。　

m と n　と　l　が同じ値の時
は m = n= l　回が最短の手法です。

＊　任意の２つの容器から１ずつ削っていくため。

@list = sort { $b <=> $a } qw(827392 65536 122880);
die "むりぽ"
    if (!( map { $sum += $_; $sum } @list ) % 3
    and !grep { $_ ne $x xor( $x = $_ ) } @list );

@list = sort { $a <=> $b } @list
    if ( grep { $_ ne $x xor( $x = $_ ) } @list );
print my ($min) = @list;

こっちが正解でつ

@list = sort { $b <=> $a } qw(3 2 1);
my ($s) = grep { $x ne $_ xor $x = $_ } @list;
print $s if ($s);
die "だめぽ"
    if ( ( $list[0] - $list[1] )  
    * ( $list[1] - $list[2] ) 
    * ( $list[0] - $list[2] ) % 3 );
print $list[0] if ( !$s );

DouKaku?

水の移し替えパズル

Posted feedbacks - Perl

Index

Feed

Other

Link

Pathtraq