麻雀の待ち判定2

うまい解き方をしてる人がいた。

http://d.hatena.ne.jp/zorio/20100403/1270303319



perl に翻訳して、多少味付け。

アルゴリズムって大切だなぁ。。

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");
}