このブログを検索

ラベル Perl の投稿を表示しています。 すべての投稿を表示
ラベル Perl の投稿を表示しています。 すべての投稿を表示

2019/04/27

「パスワードを暗号化して保存する」ではダメな理由

perlでcgiを作ってみた。

ハッシュアルゴリズムにmd5を使っているが、
md5もはや安全ではないらしい。

このスクリプトはあくまでもハッシュを作ることを実感するためのサンプルである。
実際にはより安全なアルゴリズムに変える必要がある。



ユーザ名とパスワードを登録するcgi

register_pwd.cgi
---
#!/usr/bin/perl

print "Content-type: text/html\n\n";
print "register password";
print '<form action="save_pwd.cgi" method="post">';
print '<p>';
print 'name:<input type="text" name="username" size="20">';
print '</p>';
print '<p>';
print 'password:<input type="text" name="password" size="20">';
print '</p>';
print '<p>';
print '<input type="submit" value="送信"><input type="reset" value="リセット">';
print '</p>';
print '</form>';
---


ユーザ名とパスワードのソルト付きハッシュを保存するcgi

users.txt というファイルに保存する。
すでに同じユーザ名が登録されているかのチェックもする。

ソルトの作り方がアレかもしれないが、
ここもサンプルなので見逃してほしい。


save_pwd.cgi
---
#!/usr/bin/perl

use Digest::MD5 qw(md5 md5_hex);

if ($ENV{'REQUEST_METHOD'} eq 'POST') {
  read(STDIN, $alldata, $ENV{'CONTENT_LENGTH'});
} else {
  $alldata = $ENV{'QUERY_STRING'};
}
foreach $data (split(/&/, $alldata)) {
  ($key, $value) = split(/=/, $data);

  $value =~ s/\+/ /g;
  $value =~ s/%([a-fA-F0-9][a-fA-F0-9])/pack('C', hex($1))/eg;
  $value =~ s/\t//g;

  $in{"$key"} = $value;
}

print "Content-Type: text/html; charset=Shift_JIS\n\n";
print "<html>\n";
print "<head><title>save password</title></head>\n";
print "<body>\n";

$my_user = $in{'username'};
$my_pwd = $in{'password'};

print "<p>username: $my_user</p>\n";
print "<p>password: $my_pwd</p>\n";

$digest = md5_hex($my_pwd);

print "md5 digest:".$digest."<br>";

$num = int(rand(1000000));

$salt = '$1$'.$num.'$';

print '<br>'.$salt.'<br>';

$crypt = crypt($my_pwd, $salt);

print "md5 with salt: ".$crypt."<br>";

print '<br>';

$count = 0;

open (IN, "users.txt");
while(<IN>){
        @tmp_user = split(/,/,$_);
        if (@tmp_user[0] eq $my_user){
                $count++;
        }
}

if ($count > 0 ) {
        print("username ".$my_user." has been already registered.<br>");
}else {
        open (OUT,">> users.txt");
        print OUT $my_user.",".$crypt."\n";
        close (OUT);
        print 'registered<br>';
        print '<a href="/index.html">'.'index.html'.'</a>';
}
print "</body>\n";
print "</html>\n";

exit;
---

パスワード確認cgi
(ログインのイメージ)

kensho_pwd.cgi
---
#!/usr/bin/perl

print "Content-type: text/html\n\n";
print "verify password";
print '<form action="hash_kensho.cgi" method="post">';
print '<p>';
print 'name:<input type="text" name="username" size="20">';
print '</p>';
print '<p>';
print 'password:<input type="text" name="password" size="20">';
print '</p>';
print '<p>';
print '<input type="submit" value="送信"><input type="reset" value="リセット">';
print '</p>';
print '</form>';

exit;
---

ユーザの入力したユーザ名を保存したユーザ名から検索し、
保存されているソルトを付加してハッシュを計算し、保存されているハッシュと比較する

users.txtを読んで、同じユーザ名を探す。

実際はDBを使うなどするのだろうがこれは実験なので。

---
#!/usr/bin/perl

use Digest::MD5 qw(md5 md5_hex);

if ($ENV{'REQUEST_METHOD'} eq 'POST') {
  read(STDIN, $alldata, $ENV{'CONTENT_LENGTH'});
} else {
  $alldata = $ENV{'QUERY_STRING'};
}
foreach $data (split(/&/, $alldata)) {
  ($key, $value) = split(/=/, $data);

  $value =~ s/\+/ /g;
  $value =~ s/%([a-fA-F0-9][a-fA-F0-9])/pack('C', hex($1))/eg;
  $value =~ s/\t//g;

  $in{"$key"} = $value;
}

print "Content-Type: text/html; charset=utf-8\n\n";
print "<html>\n";
print "<head><title>password kensho</title></head>\n";
print "<body>\n";

$my_user = $in{'username'};
$my_pwd = $in{'password'};

print "username: $my_user<br>";
print "password: $my_pwd<br>";

open (IN,"users.txt");
#$record = <IN>;

$count=0;
$tmp_user="";
$tmp_digest="";

while(<IN>){
        @tmp = split(/,/,$_);
        if(@tmp[0] eq $my_user){
                $count++;
                $tmp_user = @tmp[0];
                $tmp_digest = @tmp[1];
        }
}
close (IN);

if($count<1){
        print "unknown username<br>";
        exit;
}

chomp($tmp_digest);


$salt = substr($tmp_digest,0,10);

$crypt = crypt($my_pwd, $salt);

print "md5 with salt: ".$crypt."<br>";
print "saved md5    : ".$tmp_digest."<br>";

if ($tmp_digest eq $crypt ) {
        print "Welcome, ".$my_user." !!<br>";
}else{
        print "Incorrect password<br>";
}

print "</body>\n";
print "</html>\n";

exit;
---

実行例

ユーザ名とパスワードを入力

保存されたソルト付きハッシュ
上に表示されているのは、ソルトなしのハッシュ
$で挟まれているのがソルト。
ハッシュの先頭に付加されるのでそれを含めて保存する。


登録したユーザ名とパスワードを入力する


保存してあるハッシュと一致した。


違うユーザ名で同じパスワードを登録してみる。

jiro, password



ソルトなしのハッシュは、taro, passwordの場合と全く同じ

ソルト付きのハッシュは、同じパスワードから生成したものであっても、
taroのものと異なる。





「暗号化して保存する」と「ハッシュを保存する」は違う。

暗号化したデータは、しかるべき操作をすると元のデータが復号できるが、
ハッシュはできない。

もし悪意あるものがサーバにアクセスしてハッシュを入手したとしても、
できることは、元のデータを推測して、
そのデータのハッシュを計算して比較し、同じであるかどうかを確認することだけである。

ハッシュでできることは、元のデータを復元してそれを入力された値と比較することではない。
比較するのはあくまでもハッシュであり、
サーバ管理者でさえも、ユーザのパスワードが何かはわからないのである。
もしパスワードを暗号化して保存し、それを復号化して比較するのであれば、
サーバ管理者がユーザのパスワードを知ってしまうことになる。

また、もし暗号化されたパスワードを保存しているサーバにアクセスされてしまったら、
高確率で復号化する仕組みにもアクセスされるだろう。

そのことを知らなかったら、「暗号化して保存したってどうせ復号するんだから意味はない」と考えて、平文で保存してしまうのではないだろうか?

だから、「暗号化して保存する」と「ハッシュを保存する」の区別は重要なのである。


・・・と思ったのだが、記事を一回公開してから気づいた。
ハッシュを計算するときに、見ようと思えばユーザのパスワードは知ることができる。

先ほどのperlのスクリプトで、ユーザがフォームに入力したパスワードをprintで表示すればよい。
(実際、している。もちろん、本当に実装するときにそんなことはしないが。)

フォームにパスワードを入力してサーバに送信する前に、ハッシュを計算して、その結果を送信しなければいけないのか?

そんなことは不可能か?

通信が暗号化されていればサーバに到達するまではパスワードは他者に知られないが、

ハッシュ計算時には知ることができる。

それを保存さえしなければいいのか?


またこの時、もしソルトを付加せずに計算したハッシュを保存したらどうなるか。

1万人のユーザのハッシュの中で、同じものが50件あったとすると、
そのパスワードは誰でも思いつくパスワードであると想像でき、元のデータの推測が容易になってしまう。

2019/04/20

パスワードを平文で保存してはいけないならどうやって保存するのか?

あるサービスが「パスワードを平文で保存していた」というニュースに対してある有名な人が「平文で保存するなんてありえない!」と怒っていた。

「平文で保存していた」というニュースは何度か見たことがある。

では、平文で保存してはならないのならば、どうやって保存すればいいのか?

そう聞いたら、多くの人がこう答えるだろう。

「暗号化して保存する」

私もそうだと思っていた。

しかしそれは間違いで、正しくは

「パスワードのハッシュを保存する」

であった。


そういうとおそらく「暗号化もハッシュも同じようなものだ、そんな細かいことはどうでもいい」という人も多いだろう。

でも、そういう、「細かいことはどうでもいい」が積み重なって、「平文でも大丈夫」になってしまうのではないだろうか?

だから、ちょっと「細かいこと」にこだわってみよう。

ハッシュとか、暗号化とか、sha1とかmd5とかいうものの存在は知っていた。

ソフトウェアなどをダウンロードしたときにmd5チェックサムがついていて、
ファイルが壊れていないかを確認することができる、とか、

WEBサーバは、sha1は古いアルゴリズムだから、sha256を使わないといけないとか。


しかし、実際に自分がサーバ管理者やサービス提供者になったとして、
顧客のパスワードを安全に保存するにはどうすればいいかと聞かれたら答えられない。

最近、当たり前のことなのだが、知ってちょっと驚いたことがある。

それは、ハッシュというものは同じ値に対してはだれが計算しても同じ結果になる、
ということだ。


windowsのコマンドプロンプト(またはパワーシェル)で、
ハッシュを計算することができる。

別に何かのアプリなどをインストールする必要はない。

a.txt

というファイルがある。
中身は

あいうえお(改行)

で、文字コードをutf-8で保存した。


PS C:\users\taro\desktop> certutil -hashfile a.txt
SHA1 ハッシュ (対象 a.txt):
471399aeda50586bdc982b558bfde1da642c0fb3
CertUtil: -hashfile コマンドは正常に完了しました。

PS C:\users\taro\desktop> certutil -hashfile a.txt md5
MD5 ハッシュ (対象 a.txt):
0f2f3458c1553eb96d499508dc5184b4
CertUtil: -hashfile コマンドは正常に完了しました。

PS C:\users\taro\desktop> certutil -hashfile a.txt sha256
SHA256 ハッシュ (対象 a.txt):
0007a58ae5789f92155f87d6bc51edd4c9b036277d23154fe06a9daf33d0e514
CertUtil: -hashfile コマンドは正常に完了しました。


sha1(デフォルト)、md5、sha256で計算してみた。


それでは、このファイルを、私がさくらのVPSで使っているcentosのサーバにアップロードし、そこでハッシュを計算してみよう。

centosにもハッシュを計算するコマンドがある。

# sha1sum a.txt
471399aeda50586bdc982b558bfde1da642c0fb3  a.txt

# md5sum a.txt
0f2f3458c1553eb96d499508dc5184b4  a.txt

# sha256sum a.txt
0007a58ae5789f92155f87d6bc51edd4c9b036277d23154fe06a9daf33d0e514  a.txt


結果は全く同じである。

ハッシュというのは元の値に対して、人の目からは無意味である程度長く、元の値を推測も計算することもできないような値を生成する。

それはわかっていた。

しかしもうひとつ肝心なことは、同じアルゴリズム(sha1とかmd5とか)を使用すれば、
同じ値からは同じハッシュ値が生成されるということだ。

そうでなければ、たとえばユーザのパスワードのハッシュ値を保存しても、
ユーザのパスワードが正しいかを検証できない。

当たり前のことであるが。


私もパソコン、スマホ、さまざまなインターネット上のサービスなどを利用していて、
「パスワード」というものを何十個、何百個と設定して使用してきたが、
そのパスワードがテキストで読める状態で保存されているのは見たことがない。
パスワードをメールや郵便物に記載して送付されることはあったが。

あらためて、先ほどのcentosのサーバにパスワードがどのように保存されているかを見てみた。

/etc/shadow

というファイルである。

私は複数のアカウントを作成しているが、そのうちいくつかは異なるアカウントに同じパスワードを設定していた。

たとえば、taroというユーザのパスワードが password、
jiroというユーザのパスワードも password
という感じである。

「同じ値のhash値は誰が計算しても同じ」
ということは、taroとjiroのパスワードから計算したhash値は同じ文字列のはずだ......

しかし、実際には違う文字列であった。

あれ?


調べると、パスワードを保存する際にはhash値をもとの文字列からそのまま計算せず、
「ソルト(塩)」と呼ばれるランダムな値を付加して計算するのだそうだ。

その付加する方法は、文字列としてくっつけるのか、二進数でなんらかの演算をするのかわからないが、とにかくもうひと手間加えて、同じパスワードでも同じハッシュにならないようにする。


同じハッシュ値だからといっても、元の値を知ることは事実上不可能なことにはかわりないが、「複数のアカウントが同じパスワードである」という事実があれば、それらのアカウントに使用されているパスワードは誰もが思いつきそうな単純なパスワードであると推測できる。

また、よく使われそうなパスワード文字列を用意し、そのハッシュ値を計算しておいて、
ハッシュ値同士を比較すれば元の文字列がわかる。(これをレインボーテーブルという)

これらを防ぐために、ソルトというものが使われる。

しかし私はそこでひとつ疑問がわいた。

パスワードは正しい値であることを検証しなければならない。


再訪したユーザが入力したパスワード値にソルトを付加してハッシュ値を計算し、保存されたハッシュ値と同じであるかを比較しなければならない。

ではソルトをハッシュ値と一緒に保存するのか。
それは鍵をかけた金庫の横に鍵を置くようなものだ。

/etc/shadowを見てももちろんソルト値は書かれていない...

調べてみた。

ソルト値の隠し場所があった。

金庫のたとえで言うなら、鍵は金庫の横に置かれてこそいないが、
横にテープで貼り付けるくらいのことしかされていなかった。

ソルト値を使ってパスワードからhashを計算したら、
/etc/shadowに書かれているhash値と一致した。

# cat /etc/shadow | grep hiroshi
hiroshi:$6$9Qpwui9R$jrswaF/U2NRgq7Yhuk2YH7T2POuOYuDq/2eH71KMJkRDNaLxHEa25BLvmAnT3zz.ijxv/e6qUK.cEN24FN.GD0:18005:0:99999:7:::

# perl -e 'print crypt("hiroshidesu", "\$6\$9Qpwui9R");'
$6$9Qpwui9R$jrswaF/U2NRgq7Yhuk2YH7T2POuOYuDq/2eH71KMJkRDNaLxHEa25BLvmAnT3zz.ijxv/e6qUK.cEN24FN.GD0


pythonの例

# python -c 'import crypt; print(crypt.crypt("hiroshidesu", salt="$6$9Qpwui9R"))'
$6$9Qpwui9R$jrswaF/U2NRgq7Yhuk2YH7T2POuOYuDq/2eH71KMJkRDNaLxHEa25BLvmAnT3zz.ijxv/e6qUK.cEN24FN.GD0


そもそも、ハッシュ値で保存するのも、さらにその際にソルトを加えるのも、
サーバにアクセスされてかつサーバの管理アカウントでログインされてしまった場合を想定してのことである。

平文で保存していたのも、サーバにログインされないための対策を十分にしているから、
と考えてのことだろう。


sha512の計算方法とか、saltのかけ方とかはわからないが、
それを使ってますよ、というだけで、パスワードの保存方法というのはそんなに難しいことをしているわけではないというのが、分かった。

ただし、繰り返しになるが、それはあくまでも推測したパスワードからハッシュを計算して一致するかを調べる、ということであって、ハッシュ計算の脆弱性があるとか、ハッシュ値から元の値が算出できるとかいうことではない。


※関連エントリ

https://monqy.blogspot.com/2019/04/blog-post_27.html

2019/03/02

python3をデフォルトにする@centos6

google analyticsがあるcgiがinternal server errorになっていることを報告してきて、
それを直している過程で、

perl (LWP)でやっているスクレイピングが時代遅れ

pythonの2系は時代遅れ

ということを悟ったので、3系(3.6)をインストールした。

2.6とか2.7とかいろいろ入ってしまったのできれいにしようと思ったのだが、
うまく消えないのでとりあえず3系がデフォルトで動くようにした。



# pip install beautifulsoup4
DEPRECATION: Python 2.7 will reach the end of its life on January 1st, 2020. Please upgrade your Python as Python 2.7 won't be maintained after that date. A future version of pip will drop support for Python 2.7.
Requirement already satisfied: beautifulsoup4 in /usr/local/lib/python2.7/site-packages (4.7.1)
Requirement already satisfied: soupsieve>=1.2 in /usr/local/lib/python2.7/site-packages (from beautifulsoup4) (1.8)
Requirement already satisfied: backports.functools-lru-cache; python_version < "3" in /usr/local/lib/python2.7/site-packages (from soupsieve>=1.2->beautifulsoup4) (1.5)
#


beautifulsoupなる便利なものがあると聞いて使ってみようとしたら「まだ2.7なんか使ってんのかよ」と怒られた。


# python --version
Python 2.6.6


python

とだけやると、2.6.6が起動する。

python3.6

とやれば3系が動くようにはなっているが、面倒。

# python3.6
Python 3.6.7 (default, Dec  5 2018, 15:02:16)
[GCC 4.4.7 20120313 (Red Hat 4.4.7-23)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>

"python" はシンボリックリンクなので、
それを3系にリンクしなおせばよい。

# which python
/usr/bin/python

# which python3.6
/usr/bin/python3.6


pipも

# which pip3.6
/usr/bin/pip3.6

# which pip
/usr/local/bin/pip



# ln -s /usr/bin/python3.6 /usr/bin/python
ln: creating symbolic link `/usr/bin/python': ファイルが存在します

現在のリンクを消してから3系へのリンクを作る。

# unlink /usr/bin/python

# ln -s /usr/bin/python3.6 /usr/bin/python



# ln -s /usr/bin/pip3.6 /usr/local/bin/pip
ln: creating symbolic link `/usr/local/bin/pip': ファイルが存在します

pipも同様

# unlink /usr/local/bin/pip
# ln -s /usr/bin/pip3.6 /usr/local/bin/pip




# python
Python 3.6.7 (default, Dec  5 2018, 15:02:16)
[GCC 4.4.7 20120313 (Red Hat 4.4.7-23)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>


# pip -V
pip 9.0.1 from /usr/lib/python3.6/site-packages (python 3.6)


pythonもpipも3系になった。


2015/07/19

mod_perl

googleアドセンスのスコアカードで、私のサイトのあるページの応答速度が0.26秒であった。

200ミリ以下が理想だそうだ。

apacheの不要なモジュールを停めてみたりしたが効果がない。


mod_perlを入れてみる。


yum -y install mod_perl


/etc/httpd/conf.d/perl.conf

で、必要な設定をコメントアウト


LoadModule perl_module modules/mod_perl.so

PerlSwitches -w

PerlSwitches -T

Alias /perl /var/www/perl
<Directory /var/www/perl>
    SetHandler perl-script
    PerlResponseHandler ModPerl::Registry
    PerlOptions +ParseHeaders
    Options +ExecCGI
</Directory>

<Location /perl-status>
    SetHandler perl-script
    PerlResponseHandler Apache2::Status
    Order deny,allow
    Deny from all
    Allow from .example.com
</Location>


httpd再起動。
速くなったように感じるが、アドセンスの評価は変わらず。


2015/04/30

mecab

webサーバも、新しいvpsに移行することにした。

apache + perl がメインである。


mecabを使ったcgiがあるのだが、
perlのmecabがどうしてもインストールできない。

と思ったら、pythonを使ったものになっていたので、
pythonのmecabをインストール

参考
http://d.hatena.ne.jp/mrgoofy33/20110406/1302019908

http://qiita.com/ShingoOikawa/items/175be8a472ec8ed8a707


http://d.hatena.ne.jp/yuboolike/20121207/1354869309


2014/02/09

logをmysqlのテーブルにする

perlで書いたcgiでログ解析をしているのだが、現在持っているログを全部読むとcgiがタイムアウトしてしまう。
件数は13万件弱である。

そこで、毎回毎回テキストを全部読んで数えるのは面倒くさいので、
mysqlにDBとして登録してしまえば、と思ってやってみた。
mysqlは別のことで使ったことがあって、
dbを作ってテーブルを作ってそこにperlでレコードを登録する、
という一連のことはやったことがあった。

それを流用してログを登録していると、エラーが発生した。
それは、シングルクォーテーションがデータ区切りとして認識されてしまうために起きていた。
シングルクォーテーションは二つ続けて書くことでエスケープできるようなので、ログファイルのシングルクォーテーションを探してそのようにした。
そんなにたくさんはないので一個ずつ直した。

今回はそれでいいのだが、ゆくゆくはアクセスがあった時点でそのつどログをdbに書こうと思っている。
このログとはいわゆる「掲示板」のようなCGIで、アクセス数は日に数件程度なのでそれでよいのだ。
でも、シングルクォーテーションがあったらそれを2個にするようにいちいちしなければならないのは、ちょっとイヤだな。

とりあえずできた。
12万件を登録するのはけっこう時間がかかった。30分くらい?
select文でいろいろ検索してみる。一発だ。

2013/07/15

twitterのbotが止まる

twitterのbotが止まっていた。

二つ動かしているのだが、二つとも6/11で止まっている。

tweetするスクリプトを手動で動かすと以下のようなエラーが出てツイートしない。

410: Gone 

同じアカウントを使っているpythonで作ったスクリプトだとツイートする。

これは、Net::Twitterが新しいAPIに対応していないためだろうと、
Net::Twitter::Liteを最新にするが、変わらない。

 検索すると、 Net::Twitter::Lite::WithAPIv1_1 を使うということがわかった。 

useとnewのところを直してうまくいった。


2013/04/14

色対応

できた。
配牌はスペースで区切って指定する。 昨日直したときの修正ミスがあったのでそれもなおす。
use strict;
use warnings;

if($#ARGV < 0){
    print "please specify haipai.\n";
    exit;
}

#my @haipai = sort split / /, shift;
my @haipai = sort @ARGV;

if($#haipai != 12){
    print "please specify 13 pies.\n";
    exit;
}
my @menz;

my %tenpai;

my $menz_count = 0;
my $head_count = 0;
my $tenpai_count = 0;
my $not_menz = 0;

my $select_head = 0;

print "haipai: @haipai\n";

&select_head([@haipai]);

@menz=();
$not_menz = 0;
$head_count = 0;

&select_menz([@haipai],[@menz],"");

#七対子
&chitoi([@haipai]);

# 結果表示
foreach my $name (sort keys %tenpai){
    $tenpai_count++;
    print "$tenpai_count : $name\n";
}


#アタマを選んだ後、メンツを選ぶ
sub select_head{
    my @haipai = @{ $_[0] };

    my ($i, $j);

    $head_count++;

    for($i=0;$i <= $#haipai - 1;$i++){
        for($j=$i+1;$j <= $#haipai;$j++){
            if(&is_menz($haipai[$i],$haipai[$j])==3){
                my $atama = "<".$haipai[$i].$haipai[$j].">";
#               print $atama."\n";

                my @menz;
#選んだ牌を消す
                my @new_haipai = @haipai;
                $new_haipai[$i]="0";
                $new_haipai[$j]="0";

                @new_haipai = grep { $_ ne "0" } @new_haipai;
#残ったパイからメンツを選ぶ
                &select_menz([@new_haipai], [@menz], $atama);
            }
        }
    }
}


sub select_menz{
    my @haipai = @{ $_[0] };
    my @menz = @{ $_[1] };
    my $atama = $_[2];

    my ($i,$j, $k);

# 牌の残りが2枚以下
    if($#haipai < 2){
# アタマあり
        if($head_count > 0) {
#メンツが3個以上
            if($#menz > 1){
#残りの牌がターツかトイツ
                if(&is_menz(@haipai)>0){
                    my @sorted = sort @menz;
                    my $tenpai = $atama.join("",@sorted)."[".join("",@haipai)."]";
                    &tenpai_check($tenpai);
                }
            }
            return;
# アタマなし
        }else{
#メンツが4個以上
            if($#menz > 2){
                my @sorted = sort @menz;
                my $tenpai = $atama.join("",@sorted)."[".join("",@haipai)."]";
                &tenpai_check($tenpai);
            }
            return;
        }
    }


    for($i=0;$i<= $#haipai - 2;$i++){
        for($j=$i+1;$j<= $#haipai - 1;$j++){
            for($k=$j+1;$k<= $#haipai;$k++){

                my @new_menz = @menz;

                if(&is_menz($haipai[$i], $haipai[$j], $haipai[$k]) > 0) {
                    push @new_menz, "(".$haipai[$i].$haipai[$j].$haipai[$k].")";
                }else{
#メンツにならなかったらカウント
                    $not_menz++;
                }
#アタマありの場合非メンツが2つ、なしの場合1つあれば探索中止

                if(($head_count == 0 && $not_menz > 0) ||
                ($head_count > 0  && $not_menz > 1)) {
                    $not_menz = 0;
                    last;
                }else{
#選んだパイを削除
                    my @new_haipai = @haipai;
                    $new_haipai[$i]="0";
                    $new_haipai[$j]="0";
                    $new_haipai[$k]="0";

                    @new_haipai = grep { $_ ne "0" } @new_haipai;

#再帰呼び出しで残り牌からメンツを選ぶ
                    &select_menz([@new_haipai], [@new_menz], $atama);

                }
            }
        }
    }
}

sub chitoi{
    my @haipai = @{ $_[0] };

    my $i = 0;
    my @menz;

    $menz_count = 0;

    while($i<$#haipai){
        if(&is_menz($haipai[$i], $haipai[$i+1]) == 3){
            push @menz,"(".$haipai[$i].$haipai[$i+1].")";
            $menz_count++;
            if($i==$#haipai-2){
                push @menz,"[".$haipai[$#haipai]."]";
            }
            $i+=2;
        }else{
            push @menz,"[".$haipai[$i]."]";
            $i++;
        }
    }

    if($menz_count>5){
        my $tenpai = join("",@menz);
        &tenpai_check($tenpai);
    }
}


#重複した聴牌形をハッシュでチェック
sub tenpai_check{
    my ($tenpai) = @_;
#   print "tenpai check :$tenpai\n";
    $tenpai{$tenpai}++;
}

#余り牌がターツあるいはトイツであるかをチェック
sub amari_check{
    my @haipai = @{ $_[0] };

    if($haipai[0] == $haipai[1]){
        return 1;
    }
    if($haipai[0]+1 == $haipai[1]){
        return 1;
    }
    if($haipai[0]+2 == $haipai[1]){
        return 1;
    }
}

sub is_menz{
    my @pais = @_;

#   print "pais:@pais\n";

    if($#pais == 1){
        if($pais[0] eq $pais[1]){
            return 3;
        } elsif(substr($pais[0],0,1) eq substr($pais[1],0,1) && (substr($pais[0],0,1) ne "x")){
            if(substr($pais[0],1,1)+1 == substr($pais[1],1,1)){
                return 4;
            }elsif(substr($pais[0],1,1)+2 == substr($pais[1],1,1)){
                return 5;
            }else{
                return 0;
            }
        }else{
            return 0;
        }
    }

    if($pais[0] eq $pais[1] && $pais[0] eq $pais[2]){
        return 2;
    }elsif(substr($pais[0],0,1) eq substr($pais[1],0,1) && substr($pais[0],0,1) eq substr($pais[2],0,1) && (substr($pais[0],0,1) ne "x")){
        if(substr($pais[0],1,1)+1 == substr($pais[1],1,1) && substr($pais[0],1,1)+2 == substr($pais[2],1,1)){
            return 1;
        }else{
            return 0;
        }
    }else{
        return 0;
    }
}
実行結果
# perl menx.pl m1 m2 m3 p1 p2 p3 s3 s4 s5 s6 s7 x1 x1
haipai: m1 m2 m3 p1 p2 p3 s3 s4 s5 s6 s7 x1 x1
1 : (m1m2m3)(p1p2p3)(s3s4s5)[s6s7]
2 : (m1m2m3)(p1p2p3)(s5s6s7)[s3s4]

2013/04/13

色対応の検討



麻雀聴牌判定プログラムは、一色限定版である。


だが、一色でできてしまえば、あとは牌が同一あるいは連続であるかを判定するときに色も見ればよい。


簡単そうだが、色をどうやってもたせるべきだろうか?


そもそも私は最初は色つきでやろうとしていたのだが、


調べていくうちに一色限定で判定するというコンテストのようなものを見つけ、


それをまずやってみた。


私が最初にやろうとしたのは、


マンズ: m1, m2 ... m9


ピンズ: p1, p2 ... p9


ソーズ: s1, s2 ... s9


字牌:x1, x2 ... x7


として、比較する時は牌データの1文字目で色を、2文字目で数字を見る、


というものであった。


substr関数を使うとか、正規表現を使うとかすればよいだろう。


クラスを使うのはどうだろうか?


$pai->color で色を、$pai->number で数字にアクセスできれば、


判定がわかりやすく簡単に書けそうだ。


でもこのくらいであれば、上記のフォーマットにして「同じか」「連続しているか」


などをサブルーチンにするだけでよいかもしれない。





2013/04/12

七対子対応



最初は、通常のテンパイ判定を改造して、3つ選ぶのを2枚にして、メンツの数は5つにして・・・とやったのだが、なぜかうまくいかなかった。


配牌はソートしているから隣と同じでなければ即非メンツに判定できることに気づいて、別途作った。


あとはループのさせ方がちょっと変だったのでなおしたら、1秒くらいで判定するようになった。



use strict;
use warnings;

if($#ARGV < 0){
print "please specify haipai.\n";
exit;
}

my @haipai = sort split //, shift;

if($#haipai != 12){
print "please specify 13 pies.\n";
exit;
}
my @menz;

my %tenpai;

my $menz_count = 0;
my $head_count = 0;
my $tenpai_count = 0;
my $not_menz = 0;

my $select_head = 0;

print "haipai: @haipai\n";

&select_head([@haipai]);

@menz=();
$not_menz = 0;
$head_count = 0;

&select_menz([@haipai],[@menz],"");

#七対子
&chitoi([@haipai]);

# 結果表示
foreach my $name (sort keys %tenpai){
$tenpai_count++;
print "$tenpai_count : $name\n";
}


#アタマを選んだ後、メンツを選ぶ
sub select_head{
my @haipai = @{ $_[0] };

my ($i, $j);

$head_count++;

for($i=0;$i <= $#haipai - 1;$i++){
for($j=$i+1;$j <= $#haipai;$j++){
if($haipai[$i] == $haipai[$j]){
# print "$head_count: <".$haipai[$i].$haipai[$j].">\n";
my $atama = "<".$haipai[$i].$haipai[$j].">";
my @menz;
#選んだ牌を消す
my @new_haipai = @haipai;
$new_haipai[$i]=0;
$new_haipai[$j]=0;

@new_haipai = grep { $_ > 0 } @new_haipai;
#残ったパイからメンツを選ぶ
&select_menz([@new_haipai], [@menz], $atama);
}
}
}
}


sub select_menz{
my @haipai = @{ $_[0] };
my @menz = @{ $_[1] };
my $atama = $_[2];

my ($i,$j, $k);

# 牌の残りが2枚以下
if($#haipai < 2){
# アタマあり
if($head_count > 0) {
#メンツが3個以上
if($#menz > 1){
#残りの牌がターツかトイツ
if(&amari_check([@haipai])>0){
my @sorted = sort @menz;
my $tenpai = $atama.join("",@sorted)."[".join("",@haipai)."]";
&tenpai_check($tenpai);
}
}
return;
# アタマなし
}else{
#メンツが4個以上
if($#menz > 2){
my @sorted = sort @menz;
my $tenpai = $atama.join("",@sorted)."[".join("",@haipai)."]";
&tenpai_check($tenpai);
}
return;
}
}


for($i=0;$i<= $#haipai - 2;$i++){
for($j=$i+1;$j<= $#haipai - 1;$j++){
for($k=$j+1;$k<= $#haipai;$k++){

my @new_menz = @menz;

if($haipai[$i]+1 == $haipai[$k]){
$not_menz++;
}elsif(($haipai[$i] == $haipai[$j] && $haipai[$j] == $haipai[$k]) ||
($haipai[$i]+1 == $haipai[$j] && $haipai[$j]+1 == $haipai[$k])){
push @new_menz, "(".$haipai[$i].$haipai[$j].$haipai[$k].")";
}else{
#メンツにならなかったらカウント
$not_menz++;
}
#アタマありの場合非メンツが2つ、なしの場合1つあれば探索中止

if(($head_count == 0 && $not_menz > 0) ||
($head_count > 0 && $not_menz > 1)) {
$not_menz = 0;
last;
}else{
#選んだパイを削除
my @new_haipai = @haipai;
$new_haipai[$i]=0;
$new_haipai[$j]=0;
$new_haipai[$k]=0;

@new_haipai = grep { $_ > 0 } @new_haipai;

#再帰呼び出しで残り牌からメンツを選ぶ
&select_menz([@new_haipai], [@new_menz], $atama);

}
}
}
}
}

sub chitoi{
my @haipai = @{ $_[0] };

my $i = 0;
my @menz;

$menz_count = 0;

while($i<$#haipai){
if($haipai[$i] == $haipai[$i+1]){
push @menz,"(".$haipai[$i].$haipai[$i+1].")";
$menz_count++;
if($i==$#haipai-2){
push @menz,"[".$haipai[$#haipai]."]";
}
$i+=2;
}else{
push @menz,"[".$haipai[$i]."]";
$i++;
}
}

if($menz_count>5){
my $tenpai = join("",@menz);
&tenpai_check($tenpai);
}
}


#重複した聴牌形をハッシュでチェック
sub tenpai_check{
my ($tenpai) = @_;
# print "tenpai check :$tenpai\n";
$tenpai{$tenpai}++;
}

#余り牌がターツあるいはトイツであるかをチェック
sub amari_check{
my @haipai = @{ $_[0] };

if($haipai[0] == $haipai[1]){
return 1;
}
if($haipai[0]+1 == $haipai[1]){
return 1;
}
if($haipai[0]+2 == $haipai[1]){
return 1;
}
}





2013/04/11

テンパイ判定

3秒くらいで結果が出るようになった。

メンツの探索中に非メンツが、アタマありの場合2個、アタマなしの場合1個みつかったら探索を中止する。

本当はこの判断が入っているので最後にメンツの数をチェックする必要はないと思ったのだが、
メンツの数が足りないのに最後まで行く場合がかなりある。

また、中止する場合にlastでループを抜けてよいと思ったのだがそれをやると答えが足りなくなる。


use strict;
use warnings;

if($#ARGV < 0){
print "please specify haipai.\n";
exit;
}

my @haipai = sort split //, shift;

if($#haipai != 12){
print "please specify 13 pies.\n";
exit;
}
my @menz;

my %tenpai;

my $menz_count = 0;
my $head_count = 0;
my $tenpai_count = 0;
my $not_menz = 0;

my $select_head = 0;

print "haipai: @haipai\n";

&select_head([@haipai]);

$head_count = 0;

&select_menz([@haipai],[@menz],"");

# 結果表示
foreach my $name (sort keys %tenpai){
$tenpai_count++;
print "$tenpai_count : $name\n";
}


#アタマを選んだ後、メンツを選ぶ
sub select_head{
my @haipai = @{ $_[0] };

my ($i, $j) = (0, 1);

$head_count++;

while($i <= $#haipai - 1){
if($haipai[$i] == $haipai[$j]){
# print "$head_count: <".$haipai[$i].$haipai[$j].">\n";
my $atama = "<".$haipai[$i].$haipai[$j].">";

my @menz;

#選んだ牌を消す
my @new_haipai = @haipai;
$new_haipai[$i]=0;
$new_haipai[$j]=0;

@new_haipai = grep { $_ > 0 } @new_haipai;

#残ったパイからメンツを選ぶ
&select_menz([@new_haipai], [@menz], $atama);
}

$j++;
if($j>$#haipai){
$i++;
$j=$i+1;
}

}
}


sub select_menz{
my @haipai = @{ $_[0] };
my @menz = @{ $_[1] };
my $atama = $_[2];

my ($i,$j, $k) = (0, 1, 2);

# 牌の残りが2枚以下
if($#haipai < 2){
# アタマあり
if($head_count > 0) {
#メンツが3個以上
if($#menz > 1){
#残りの牌がターツかトイツ
if(&amari_check([@haipai])>0){
my @sorted = sort @menz;
my $tenpai = $atama.join("",@sorted)."[".join("",@haipai)."]";
# print "$tenpai\n";
&tenpai_check($tenpai);
}
}
return;
# アタマなし
}else{
#メンツが4個以上
if($#menz > 2){
my @sorted = sort @menz;
my $tenpai = $atama.join("",@sorted)."[".join("",@haipai)."]";
# print "$tenpai\n";
&tenpai_check($tenpai);
}
return;
}
}

while($i <= $#haipai - 2){

my @new_menz = @menz;

if($haipai[$i]+1 == $haipai[$k]){
$not_menz++;
}elsif(($haipai[$i] == $haipai[$j] && $haipai[$j] == $haipai[$k]) ||
($haipai[$i]+1 == $haipai[$j] && $haipai[$j]+1 == $haipai[$k])){
push @new_menz, "(".$haipai[$i].$haipai[$j].$haipai[$k].")";
}else{
#メンツにならなかったらカウント
$not_menz++;
}
#アタマありの場合非メンツが2つ、なしの場合1つあれば探索中止

if(($head_count == 0 && $not_menz > 0) ||
($head_count > 0 && $not_menz > 1)) {
$not_menz = 0;
}else{
#選んだパイを削除
my @new_haipai = @haipai;
$new_haipai[$i]=0;
$new_haipai[$j]=0;
$new_haipai[$k]=0;

@new_haipai = grep { $_ > 0 } @new_haipai;

#再帰呼び出しで残り牌からメンツを選ぶ
&select_menz([@new_haipai], [@new_menz], $atama);

}

$k++;
if($k>$#haipai){
$j++;
if($j>$#haipai -1){
$i++;
$j=$i+1;
$k=$j+1;
}else{
$k=$j+1;
}
}

}
}

#重複した聴牌形をハッシュでチェック
sub tenpai_check{
my ($tenpai) = @_;
# print "tenpai check :$tenpai\n";
$tenpai{$tenpai}++;
}

#余り牌がターツあるいはトイツであるかをチェック
sub amari_check{
my @haipai = @{ $_[0] };

if($haipai[0] == $haipai[1]){
return 1;
}
if($haipai[0]+1 == $haipai[1]){
return 1;
}
if($haipai[0]+2 == $haipai[1]){
return 1;
}
}

再帰を使って1からnまでの和を求める

さっきのをマネしてunlessを使ってみる。
wa(10000);

sub wa{
my ($num, $sum) = @_; unless($num) { print "$sum\n"; }else{ $sum += $num; $num--; &wa($num, $sum); } }

3枚ずつ区切る

8枚までは多分正しい。9枚以上はダメだ。

ただしこれは(123)(456) と (456)(123)を両方数えている。

combin(8, 3) * combin(5, 3) = 8*7*5*4 = 560通り。


use strict;
use warnings;

my $haipai = shift;

if(!$haipai){print "specify haipai.\n"; exit;};

print "haipai : $haipai\n";

my $max_menz = int(length($haipai) / 3);

print "max_menz : $max_menz\n";

my @haipai = split("", $haipai);
my $level=0;
my $count = 0;

my @found;

my @result;

&select_menz(\@haipai);

$count = 0;
for(@result){
$count++;
print "$count:$_\n";
}

sub select_menz{
my ($array_ref) = @_;

my ($i, $j, $k) = (0, 1, 2);

# print "array:@$array_ref\n";

while($i<$#$array_ref-1){
$count++;
# print "level: $level num of found: $#found - $i $j $k - $count : ".$array_ref->[$i].$array_ref->[$j].$array_ref->[$k]."\n";
# print "found:@found\n";
if($max_menz == 3){
if($#$array_ref > 4 && $#found == 2) {
pop @found;
pop @found;
pop @found;
}
}
if($level == 0 && $#found == $max_menz - 1 ) {
pop @found;
pop @found;
}elsif($level == 1 && $#found == $max_menz - 1 ){
pop @found;
}

push @found, "(".$array_ref->[$i].$array_ref->[$j].$array_ref->[$k].")";

if($#found > $max_menz - 2 ){
push @result, join("", sort @found);
}

my @new_array = @$array_ref;
$new_array[$i]=0;
$new_array[$j]=0;
$new_array[$k]=0;
@new_array = grep{ $_ > 0 } @new_array;

if($#new_array > 1){
$level++;
&select_menz(\@new_array);
}

$k++;
if($k>$#$array_ref){
$j++;
$k=$j+1;
if($j>$#$array_ref-1){
$i++;
$j=$i+1;
$k=$j+1;
}
}
}
$level = 0;
# print "--- end of loop --- $#$array_ref \n";
}





perlでpermutation

「Perl クックブック」より。

#!/usr/bin/perl

permute([qw(one two three four)],[]);

sub permute {
my @items = @{ $_[0] };
my @perms = @{ $_[1] };

unless (@items) {
print "@perms\n";
}else{
my(@newitems, @newperms, $i);
foreach $i (0 .. $#items) {
@newitems = @items;
@newperms = @perms;
unshift(@newperms, splice(@newitems, $i, 1));
permute([@newitems], [@newperms]);
}
}
}


実行結果

# perl permute.pl
four three two one
three four two one
four two three one
two four three one
three two four one
two three four one
four three one two
three four one two
four one three two
one four three two
three one four two
one three four two
four two one three
two four one three
four one two three
one four two three
two one four three
one two four three
three two one four
two three one four
three one two four
one three two four
two one three four
one two three four


なるほど・・・が、ソースの意味がほとんどわからない・・・。


2013/04/10

6個の中から3個えらぶ



6個のものから3個選ぶ場合の数は、combin(6,3) = 20 である。


たとえば 123456という文字列から3つを取るパターンは、以下の20通りである。


123, 124, 125, 126, 134, 135, 136, 145, 146, 156, 234, 235, 236, 245, 246, 256, 345, 346, 356, 456


ところで、これを「6個の物を二つのグループに分けるパターン」とすると、


123:456, 124:356, ... 146:235, 156:234, 234:156 ... となって、


234:156 以降はすでに選んだパターンと同じである。


6個の場合は数えられるが、これが10個、20個になったときはどうなるか?


6個の場合と同様、combin(6,3) / 2 でいいのだろうか?・・・よくない。


グループ分けした結果のグループの順番を考慮しない場合は、グループ数の階乗で割る。


6個のものを3個ずつわける場合は、 combin(6, 3) / 2! = 20 / 2 = 10


グループ数が3個であれば、abc, acb, bac, bca cab, cba の6個か。


では、7個のものを3個x2+1に分けるパターンはいくつだろうか?


順序が同じ組は3個ずつの2つなのでわるのは二組に分ける場合と同様2の階乗になる。


combin(7, 3) * combin(4, 3) * 1 /2!


9個のものを3個ずつにわけて組の順序を区別しない場合。3の階乗で割る。


combin(9,3) * combin(6,3) * 1 / 3!





・・・こんなこと習ったっけ?全然記憶にない。





ほぼ完成

とりあえず、聴牌形を出すまでできた。ただしチートイツは除く。
チュウレンポウトウの9面待ちで11パターンが出るので合ってるんじゃないかな。
でも、すごく遅い。30秒くらいかかる。
聴牌形を選ぶ時点で重複があることがわかっている。
なので、最後にハッシュに登録してチェックしている。


use strict;
use warnings;

if($#ARGV < 0){
print "please specify haipai.\n";
exit;
}

my @haipai = split //, shift;

my @menz;

my %tenpai;

my $menz_count = 0;
my $head_count = 0;
my $tenpai_count = 0;
my $not_menz = 0;

my $select_head = 0;

print "haipai: @haipai\n";

&select_head([@haipai]);

$head_count = 0;

&select_menz([@haipai],[@menz],"");

# 結果表示
foreach my $name (sort keys %tenpai){
$tenpai_count++;
print "$tenpai_count : $name\n";
}


#アタマを選んだ後、メンツを選ぶ
sub select_head{
my @haipai = @{ $_[0] };

my ($i, $j) = (0, 1);

while($i <= $#haipai - 1){
if($haipai[$i] == $haipai[$j]){
$head_count++;
# print "$head_count: <".$haipai[$i].$haipai[$j].">\n";
my $atama = "<".$haipai[$i].$haipai[$j].">";

my @menz;

#選んだ牌を消す
my @new_haipai = @haipai;
$new_haipai[$i]=0;
$new_haipai[$j]=0;

@new_haipai = grep { $_ > 0 } @new_haipai;

#残ったパイからメンツを選ぶ
&select_menz([@new_haipai], [@menz], $atama);
}

$j++;
if($j>$#haipai){
$i++;
$j=$i+1;
}

}
}


sub select_menz{
my @haipai = @{ $_[0] };
my @menz = @{ $_[1] };
my $atama = $_[2];

my ($i,$j, $k) = (0, 1, 2);

# 牌の残りが2枚以下
if($#haipai < 2){
# アタマあり
if($head_count > 0) {
#メンツが3個以上
if($#menz > 1){
#残りの牌がターツかトイツ
if(&amari_check([@haipai])>0){
my @sorted = sort @menz;
my $tenpai = $atama.join("",@sorted)."[".join("",@haipai)."]";
&tenpai_check($tenpai);
}
}
return;
# アタマなし
}else{
#メンツが4個以上
if($#menz > 2){
my @sorted = sort @menz;
my $tenpai = $atama.join("",@sorted)."[".join("",@haipai)."]";
&tenpai_check($tenpai);
}
return;
}
}

while($i <= $#haipai - 2){

my @new_menz = @menz;
#コーツ
if(($haipai[$i] == $haipai[$j] && $haipai[$i] == $haipai[$k])
#シュンツ
|| ($haipai[$i]+1 == $haipai[$j] && $haipai[$j]+1 == $haipai[$k])) {
push @new_menz, "(".$haipai[$i].$haipai[$j].$haipai[$k].")";
}else{
#メンツにならなかったらカウント
$not_menz++;
}
#非メンツが2個以上になったら探索中止
if($not_menz > 1){
$not_menz = 0;
}else{
#選んだパイを削除
my @new_haipai = @haipai;
$new_haipai[$i]=0;
$new_haipai[$j]=0;
$new_haipai[$k]=0;

@new_haipai = grep { $_ > 0 } @new_haipai;

#再帰呼び出しで残り牌からメンツを選ぶ
&select_menz([@new_haipai], [@new_menz], $atama);
}

$k++;
if($k>$#haipai){
$j++;
if($j>$#haipai -1){
$i++;
$j=$i+1;
$k=$j+1;
}else{
$k=$j+1;
}
}

}
}

#重複した聴牌形をハッシュでチェック
sub tenpai_check{
my ($tenpai) = @_;
# print "tenpai check :$tenpai\n";
$tenpai{$tenpai}++;
}

#余り牌がターツあるいはトイツであるかをチェック
sub amari_check{
my @haipai = @{ $_[0] };

if($haipai[0] == $haipai[1]){
return 1;
}
if($haipai[0]+1 == $haipai[1]){
return 1;
}
if($haipai[0]+2 == $haipai[1]){
return 1;
}
}


実行結果


# perl menz.pl 1112345678999
haipai: 1 1 1 2 3 4 5 6 7 8 9 9 9
1 : (111)(234)(567)(999)[8]
2 : (111)(234)(678)(999)[5]
3 : (111)(345)(678)(999)[2]
4 : <11>(123)(456)(789)[99]
5 : <11>(123)(456)(999)[78]
6 : <11>(123)(678)(999)[45]
7 : <11>(345)(678)(999)[12]
8 : <99>(111)(234)(567)[89]
9 : <99>(111)(234)(789)[56]
10 : <99>(111)(456)(789)[23]
11 : <99>(123)(456)(789)[11]





サブルーチンに複数の配列を渡す



リファレンスを使わない方法。さっきのpermutationがこれを使っている。

ミソは配列を[]で囲むことだ。


my @fruits = qw /apple banana orange strawberry/;
my @animals = qw /dog cat cow horse/;

&menz([@fruits],[@animals]);

sub menz{
my @array1 = @{ $_[0] };
my @array2 = @{ $_[1] };

print "array1:@array1\n";
print "array2:@array2\n";
}





アタマも選ぶ



アタマも選ぶようにした。これも、同じ牌であるかはまだ見ていない。

パターン数は

COMBIN(13,2) * COMBIN(11,3) * COMBIN(8,3) * COMBIN(5,3) = 7207200





use strict;
use warnings;

if($#ARGV < 0){
print "please specify haipai.\n";
exit;
}

my @haipai = split //, shift;

my @menz;

my $menz_count = 0;
my $head_count = 0;

my $select_head = 0;

print "haipai: @haipai\n";

&select_head([@haipai]);

#&select_menz([@haipai],[@menz]);

sub select_head{
my @haipai = @{ $_[0] };
use strict;
use warnings;

if($#ARGV < 0){
print "please specify haipai.\n";
exit;
}

my @haipai = split //, shift;

my @menz;

my $menz_count = 0;
my $head_count = 0;

my $select_head = 0;

print "haipai: @haipai\n";

&select_head([@haipai]);

#&select_menz([@haipai],[@menz]);

sub select_head{
my @haipai = @{ $_[0] };

my ($i, $j) = (0, 1);

while($i <= $#haipai - 1){
$head_count++;
# print "$head_count: <".$haipai[$i].$haipai[$j].">\n";
my $atama = "<".$haipai[$i].$haipai[$j].">";

my @menz;
my @new_haipai = @haipai;
$new_haipai[$i]=0;
$new_haipai[$j]=0;

@new_haipai = grep { $_ > 0 } @new_haipai;
&select_menz([@new_haipai], [@menz], $atama);


$j++;
if($j>$#haipai){
$i++;
$j=$i+1;
}

}
}


sub select_menz{
my @haipai = @{ $_[0] };
my @menz = @{ $_[1] };
my $atama = $_[2];

my ($i,$j, $k) = (0, 1, 2);

if($#haipai < 2){
$menz_count++;
print "$menz_count: $atama @menz amari:@haipai\n";
return;
}

while($i <= $#haipai - 2){

my @new_menz = @menz;

push @new_menz, "(".$haipai[$i].$haipai[$j].$haipai[$k].")";
my @new_haipai = @haipai;
$new_haipai[$i]=0;
$new_haipai[$j]=0;
$new_haipai[$k]=0;

@new_haipai = grep { $_ > 0 } @new_haipai;
&select_menz([@new_haipai], [@new_menz], $atama);

$k++;
if($k>$#haipai){
$j++;
if($j>$#haipai -1){
$i++;
$j=$i+1;
$k=$j+1;
}else{
$k=$j+1;
}
}

}
}





メンツ選択



今度こそできたと思う。

キモは取り出したメンツの配列を再帰呼び出しするサブルーチンに渡したことだ。

まだ、メンツになっているかどうかを問わず、3つずつに分けただけである。


use strict;1
use warnings;

if($#ARGV < 0){
print "please specify haipai.\n";
exit;
}

my @haipai = split //, shift;

my @menz;

my $count = 0;

print "haipai: @haipai\n";

&select_menz([@haipai],[@menz]);


sub select_menz{
my @haipai = @{ $_[0] };
my @menz = @{ $_[1] };

my ($i,$j, $k) = (0, 1, 2);

if($#haipai < 2){
$count++;
print "$count: menz:@menz\n";
return;
}

while($i <= $#haipai - 2){

my @new_menz = @menz;

push @new_menz, "(".$haipai[$i].$haipai[$j].$haipai[$k].")";
my @new_haipai = @haipai;
$new_haipai[$i]=0;
$new_haipai[$j]=0;
$new_haipai[$k]=0;

@new_haipai = grep { $_ > 0 } @new_haipai;
&select_menz([@new_haipai], [@new_menz]);

$k++;
if($k>$#haipai){
$j++;
if($j>$#haipai -1){
$i++;
$j=$i+1;
$k=$j+1;
}else{
$k=$j+1;
}
}

}
}


チュウレンの9面待ちに対してこれを実行すると、最後は以下のようになる。

同じならびが3つ続いているが、これは1が3枚あって、その3枚のうち2枚を選ぶパターンが3つあるためである。

4804800 = combin(13,3) * combin(10,3) * combin(7,3) * combin(4,3)

である。


4804793: menz:(999) (678) (245) (111)
4804794: menz:(999) (678) (245) (113)
4804795: menz:(999) (678) (245) (113)
4804796: menz:(999) (678) (245) (113)
4804797: menz:(999) (678) (345) (111)
4804798: menz:(999) (678) (345) (112)
4804799: menz:(999) (678) (345) (112)
4804800: menz:(999) (678) (345) (112)





2013/04/09

麻雀メンツ検索プログラム



直した。ただし、配牌から3個ずつの牌を選ぶパターンを洗い出すのみ。


刻子や順子になっているかは判定していない。


配牌は5枚から13枚まで試して、パターン数が正しいことだけ確かめた。


たとえば10枚の時は combin(10,3) * combin(7,3) * combin(4,3) = 16800。


だが、すでにこの時点ですごく遅い。とてもじゃないが麻雀ゲームには使えない。


デバッグ用のprint文がたくさん入っているがそれだけの問題ではないだろう・・・


と思ったら、パターン数が正しいだけで同じものが大量に出力されているので削除。





どうにもならないので、簡単なものから徐々に作っていく。


まずは、与えられた文字列から3文字ずつ選ぶパターンを網羅するもの。



use strict;
use warnings;

my $haipai = shift;

if(length($haipai)<0){print "specify haipai.\n"; exit;};

print "haipai : $haipai\n";

my $max_menz = int(length($haipai) / 3);

print "max_menz : $max_menz\n";

my @haipai = split("", $haipai);

my $count = 0;

&select_menz(\@haipai);

sub select_menz{
my ($array_ref) = @_;

my ($i, $j, $k) = (0, 1, 2);

while($i<$#$array_ref-1){
$count++;
print "$count : ".$array_ref->[$i].$array_ref->[$j].$array_ref->[$k]."\n";
$k++;
if($k>$#$array_ref){
$j++;
$k=$j+1;
if($j>$#$array_ref-1){
$i++;
$j=$i+1;
$k=$j+1;
}
}
}
}


これは間違いないと思う。


ここからが問題だ。


配列のリファレンスを与えて、その配列から3個の要素を選択するパターンを網羅することはできた。


それなら、各パターンについて、選択済みの要素を削除した配列を、再度このサブルーチンに渡せば、のこった要素の中から3個を選ぶパターンが網羅され、


それを要素が3個になるまで繰り返せばよい、と思う。


だが、問題がある。


まず、「配列から選択済みの要素を削除する」をどうするかだ。


たとえば「12345」という文字列から最初に選択する3文字のパターンは「123」である。


これを削除した配列は「45」である。


@array = (1,2,3,4,5)


だったとすると、


$array[0], $array[1], $array[2] を削除すればよい。


しかし・・・