多米诺骨牌

 

多米诺骨牌（DOMINO）

问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：

顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。

现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。

our $Count = 6;
my @up = (1,3,4,5,3,6);
my @down = (2,3,6,1,2,6);
sub swap{
    my @tup = @up;
    my @tdown = @down;

    my @arr = split("",shift);
    my $i = 0;
    my $count =0;
    for(@arr){
        if($_==1){
            my $t = $tup[$i];
            $tup[$i] = $tdown[$i];
            $tdown[$i] = $t;
            $count++;
        }
        $i++;
    }
    my ($sup, $sdown);
    for(@tup){
        $sup+=$_;
    }
    for(@tdown){
        $sdown+=$_;
    }
    return abs($sup - $sdown),$count;
}

sub toBinary{
    my $i = shift;
    return $i if($i<2);
    my $mod = $i%2;
    $i = ($i - $mod)/2;
    return toBinary($i).$mod;
}

sub allp{
    my @result;
    for(0..shift){
        my $t = toBinary($_);
        my $r = "0"x($Count-length($t)).$t;
        push (@result, $r);
    }
    return @result;
}

my ($value, $times) = 100;
my $q;
for(allp(2**$Count-1)){
    my ($tv, $tt) = swap($_);
    if($tv<$value){
        $value = $tv;
        $times = $tt;
        $q = $_;

    }
    elsif($tt<$times and $value == $tv){
        $times = $tt ;
        $q = $_;
    }
}

print "Result !!!\n";
print "$value: $times: $q";