読者です 読者をやめる 読者になる 読者になる

キミならどう書く 油売り算

d.y.d.さんで見かけた

こういうパズル系のプログラムは苦手なんですが、がんばって挑戦してみました。
問題が微妙に分からなかったのですが、他の方と同じ答えが出ているので、たぶんできたと言えば出きたっぽいですが、あらかじめ発見できる深さが分かってないとかなり無駄に動くと言う……ダメな感じです。
夜中に他の方のを見てます。

use strict;

my $MAX = 1000; # 最大深さ
my $SUCCESS = 1;
my $FAILURE = 2;

abura(10, 7, 3);

# 成功?
sub is_goal
{
    my $data = shift;
    my $count = 0;
    
    foreach my $c (@$data) {
        $count += $c->{cur};
    }
    return $$data[0]->{cur} == $count / 2 ? 1:0;
}

# あぶら
sub abura
{
    my $a = shift;
    my $name = ord('A');
    my @data = ({name => chr($name), max => $a, cur => $a});
    while (my $arg = shift) {
        push(@data, {name => chr(++$name), max => $arg, cur => 0});
    }
    for (my $i = 1; $i < $MAX; $i++) {
        my @retqueue = ();
        if (simulate($i, 0, \@data, \@retqueue) == $SUCCESS) {
            # 方法が発見されたので実行する
            print "初期値 -> ";
            foreach my $c (@data) {
                print "$c->{name}=$c->{cur}/$c->{max} ";
            }
            print "\n";
            while (my $fn = pop(@retqueue)) {
                &$fn(1); # 表示
                &$fn(0); # 実行
                print " => ";
                foreach my $c (@data) {
                    print "$c->{name}=$c->{cur}/$c->{max} ";
                }
                print "\n";
            }
            exit; # end
        }
    }
    print "深さ$MAX以内では方法が見つかりませんでした\n";
}

# ありえるパターンを取得
sub get_pattern
{
    my $data = shift;
    my @pattern = ();
    
    foreach my $ci (@$data) {
        my $cur_name = $ci->{name};
        foreach my $cj (@$data) {
            if (($cur_name ne $cj->{name})
                and (($cj->{max} > $cj->{cur}) and $ci->{cur} != 0))
            {
                my $nsyou = $cj->{max} - $cj->{cur} > $ci->{cur} 
                                ? $ci->{cur}:$cj->{max} - $cj->{cur};
                push(@pattern, 
                    sub {
                        my $trace = shift;
                        if ($trace) {
                            print "-> ".$ci->{name}."から".$cj->{name}."へ$nsyou升移す";
                        } else {
                            $cj->{cur} += $nsyou;
                            $ci->{cur} -= $nsyou; 
                        }
                    }
                );
            }
        }
    }
    
    return @pattern;
}

# 深さmaxdpまで深さ優先でシュミレートー
sub simulate
{
    my($maxdp, $dp, $data, $retqueue) = @_;
    return $FAILURE if ($dp > $maxdp);
    
    foreach my $fn (get_pattern($data)) {
        my @copy = ();
        for (my $i = 0; $i < @$data; ++$i) { 
            $copy[$i] = $$data[$i]->{cur};
        }
        &$fn(0);
        if (is_goal($data)) {
            push(@$retqueue, $fn);
            return $SUCCESS;
        }
        my $ret = simulate($maxdp, $dp + 1, $data, $retqueue);
        for (my $i = 0; $i < @copy; $i++) {
            $$data[$i]->{cur} = $copy[$i];
        }
        if ($ret == $SUCCESS) {
            push(@$retqueue, $fn);
            return $SUCCESS;
        }
    }
    
    return $FAILURE;
}


初期値 -> A=10/10 B=0/7 C=0/3

  • > AからBへ7升移す => A=3/10 B=7/7 C=0/3
  • > BからCへ3升移す => A=3/10 B=4/7 C=3/3
  • > CからAへ3升移す => A=6/10 B=4/7 C=0/3
  • > BからCへ3升移す => A=6/10 B=1/7 C=3/3
  • > CからAへ3升移す => A=9/10 B=1/7 C=0/3
  • > BからCへ1升移す => A=9/10 B=0/7 C=1/3
  • > AからBへ7升移す => A=2/10 B=7/7 C=1/3
  • > BからCへ2升移す => A=2/10 B=5/7 C=3/3
  • > CからAへ3升移す => A=5/10 B=5/7 C=0/3