うまい解き方をしてる人がいた。
http://d.hatena.ne.jp/zorio/20100403/1270303319perl に翻訳して、多少味付け。
アルゴリズムって大切だなぁ。。
use strict;
use warnings;
sub get_mentsu {
my ($is_atama, $is_machi, $req, $tehai, $has_atama, $has_machi, $offset) = @_;
if (@$tehai < @$req || ($is_atama && $has_atama) || ($is_machi && $has_machi)) {
return;
}
my $init = 1;
my $ret = "";
foreach my $i (0..(@$req-1)) {
if ((!defined $tehai->[$i]) || $tehai->[$i] < $req->[$i]) {
return;
} else {
if ($init) {
my @w = @$tehai;
$tehai = \@w;
$init = 0;
}
$tehai->[$i] -= $req->[$i];
foreach (1..$req->[$i]) {
$ret .= $i + $offset;
}
}
}
if ($is_machi) {
$ret = "[$ret]";
} else {
$ret = "($ret)";
}
return $tehai, $ret, $is_atama || $has_atama, $is_machi || $has_machi;
}
my @mentsu_pattern;
# 頭待ち
push @mentsu_pattern, sub { get_mentsu(1, 1, [1], @_) };
# 頭
push @mentsu_pattern, sub { get_mentsu(1, 0, [2], @_) };
# 刻子待ち
push @mentsu_pattern, sub { get_mentsu(0, 1, [2], @_) };
# 刻子
push @mentsu_pattern, sub { get_mentsu(0, 0, [3], @_) };
# カンチャン待ち
push @mentsu_pattern, sub { get_mentsu(0, 1, [1,0,1], @_) };
# 順子待ち
push @mentsu_pattern, sub { get_mentsu(0, 1, [1,1], @_) };
# 順子
push @mentsu_pattern, sub { get_mentsu(0, 0, [1,1,1], @_) };
sub search {
my ($tehai, $index, $offset, $current, $ret, $has_atama, $has_machi) = @_;
my $start = $index;
while (!$tehai->[0]) {
shift @$tehai;
$offset++;
$start = 0;
if (@$tehai == 0) {
push @$ret, $current;
return;
}
}
foreach my $i ($start..$#mentsu_pattern) {
my ($t, $r, $a, $m) = $mentsu_pattern[$i]->($tehai, $has_atama, $has_machi, $offset);
if (defined $t) {
search($t, $i, $offset, $current.$r, $ret, $a, $m);
}
}
}
sub main {
my $input = shift;
print "$input\n";
my @values = split //, $input;
my @tehai;
foreach my $v (@values) {
if (defined $tehai[$v]) {
$tehai[$v]++;
} else {
$tehai[$v] = 1;
}
}
shift @tehai;
my @ret;
search(\@tehai, 0, 1, "", \@ret);
foreach my $r (@ret) {
print "$r\n";
}
}
if (@ARGV) {
main($ARGV[0]);
} else {
main("1112224588899");
main("1122335556799");
main("1112223335559");
main("1223344888999");
main("1112345678999");
}
