Bash
ProjectEuler
数学

Project Euler Q54 【ポーカーハンド】

Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。

問題

カードゲームのポーカーでは, 手札は$5$枚のカードからなりランク付けされている. 役を低い方から高い方へ順に並べると以下である.

・役無し(ハイカード): 一番値が大きいカード
・ワン・ペア: 同じ値のカードが$2$枚
・ツー・ペア: $2$つの異なる値のペア
・スリーカード: 同じ値のカードが$3$枚
・ストレート: $5$枚の連続する値のカード
・フラッシュ: 全てのカードが同じスート (注: スートとはダイヤ・ハート・クラブ/スペードというカードの絵柄のこと)
・フルハウス: スリーカードとペア
・フォーカード: 同じ値のカードが$4$枚
・ストレートフラッシュ: ストレートかつフラッシュ
・ロイヤルフラッシュ: 同じスートの$10, J, Q, K, A$

ここでカードの値は小さい方から$2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A$である. (訳注:データ中で$10$は$'T'$と表される)

もし$2$人のプレイヤーが同じ役の場合には, 役を構成する中で値が最も大きいカードによってランクが決まる: 例えば, $8$のペアは$5$のペアより強い (下の例$1$を見よ). それでも同じランクの場合には (例えば, 両者とも$Q$のペアの場合), 一番値が大きいカードによってランクが決まる (下の例$4$を見よ). 一番値が大きいカードが同じ場合には, 次に値が大きいカードが比べれられ, 以下同様にランクを決定する.

例:

試合 プレイヤー1 プレイヤー2 勝者
1 5H 5C 6S 7S KD
5のペア
2C 3S 8S 8D TD
8のペア
プレイヤー2
2 5D 8C 9S JS AC
役無し, A
2C 5C 7D 8S QH
役無し, Q
プレイヤー1
3 2D 9C AS AH AC
Aのスリーカード
3D 6D 7D TD QD
ダイヤのフラッシュ
プレイヤー2
4 4D 6S 9H QH QC
Qのペア, 9
3D 6D 7H QD QS
Qのペア, 7
プレイヤー1
5 2H 2D 4C 4D 4S
4-2のフルハウス
3C 3D 3S 9S 9D
3-9のフルハウス
プレイヤー1

poker.txtには$1000$個のランダムな手札の組が含まれている. 各行は$10$枚のカードからなる (スペースで区切られている): 最初の$5$枚がプレイヤー$1$の手札であり, 残りの$5$枚がプレイヤー$2$の手札である. 以下のことを仮定してよい

・全ての手札は正しい (使われない文字が出現しない. 同じカードは繰り返されない)
・各プレイヤーの手札は特に決まった順に並んでいるわけではない
・各勝負で勝敗は必ず決まる

$1000$回中プレイヤー$1$が勝つのは何回か? (訳注 : この問題に置いて$A 2 3 4 5$というストレートは考えなくてもよい)

はじめに

この問題はシェルスクリプトで関数をつくってちょっとずつやった方が分かりやすいと思います。

アプローチ

1.役に点数をつける。
・役無し(ハイカード):0
・ワン・ペア:100
・ツー・ペア:200
・スリーカード:300
・ストレート:400
・フラッシュ:500
・フルハウス:600
・フォーカード:-
・ストレートフラッシュ:-
・ロイヤルフラッシュ:-
※上位3つの役は存在しなかった為、考慮しない。
(カード単体では$2$桁なので、役は$3$桁にする。)

2.$A$は計算途中では便宜的に$14$とする。

3.役の中に入っている数字で最大の数字を上記の点数に加算する。

4.ワンペアで同じ数字で勝負している組があった為、次に大きい数字を考慮する。

解答

time cat poker.txt |
awk -v FS= '{for(i=1;i<=NF;i+=3){printf $i" "};for(i=2;i<=NF;i+=3){printf $i" "};print ""}' |
sed 's/T/10/g' | sed 's/J/11/g' | sed 's/Q/12/g' | sed 's/K/13/g' |  sed 's/A/14/g' |
awk '{delete s;for(i=1;i<=5;i++){s[$i]+=1};printf $0length(s)" ";for(i=2;i<=14;i++){printf s[i]*1" "};print ""}' |
awk '{delete s;for(i=6;i<=10;i++){s[$i]+=1};printf $0length(s)" ";for(i=2;i<=14;i++){printf s[i]*1" "};print ""}' |
awk '{delete s;for(i=22;i<=34;i++){s[$i]=i-20};print $0,3*(3 in s)+2*(2 in s),s[3]*1,s[2]*1,s[1]*1}' |
awk '{delete s;for(i=36;i<=48;i++){s[$i]=i-34};print $0,3*(3 in s)+2*(2 in s),s[3]*1,s[2]*1,s[1]*1}' |
awk '{print $0,(600+$50)*($21$49==25)}' |
awk '{print $0,(600+$54)*($35$53==25)}' |
awk '{print $0,(500+$52)*($11$12$13$14$15 ~ "H{5}|D{5}|S{5}|C{5}")}' |
awk '{print $0,(500+$56)*($16$17$18$19$20 ~ "H{5}|D{5}|S{5}|C{5}")}' |
awk '{print $0,(400+$52)*($22$23$24$25$26$27$28$29$30$31$32$33$34 ~ ".*11111.*")}' |
awk '{print $0,(400+$56)*($36$37$38$39$40$41$42$43$44$45$46$47$48 ~ ".*11111.*")}' |
awk '{print $0,(300+$50)*($21$49==33)}' |
awk '{print $0,(300+$54)*($35$53==33)}' |
awk '{print $0,(200+$51)*($21$49==32)}' |
awk '{print $0,(200+$55)*($35$53==32)}' |
awk '{print $0,(100+$51+$52/10)*($21$49==42)}' |
awk '{print $0,(100+$55+$56/10)*($35$53==42)}' |
awk '{a=0;b=0;for(i=57;i<=NF;i+=2){a+=$i;b+=$(i+1)};print $0,a,b}' |
awk '{print ($69==0)*$52+($69!=0)*$69,($70==0)*$56+($70!=0)*$70}' |
awk '$1>$2' |
wc -l
376

real    0m0.126s
user    0m0.197s
sys     0m0.052s

解説

将来の自分が見ても分からなさそうなので解説を記載しておく。

awk -v FS= '{for(i=1;i<=NF;i+=3){printf $i" "};for(i=2;i<=NF;i+=3){printf $i" "};print ""}' |

数字とマークを分ける。

# 1~5:プレイヤーAの手札の数字
# 6~10:プレイヤーBの手札の数字
# 11~15:プレイヤーAの手札のマーク
# 16~20:プレイヤーBの手札のマーク

sed 's/T/10/g' | sed 's/J/11/g' | sed 's/Q/12/g' | sed 's/K/13/g' |  sed 's/A/14/g' |

絵札およびAを数字に置換する。AはK(13)の次なので14とする。

awk '{delete s;for(i=1;i<=5;i++){s[$i]+=1};printf $0length(s)" ";for(i=2;i<=14;i++){printf s[i]*1" "};print ""}' |
awk '{delete s;for(i=6;i<=10;i++){s[$i]+=1};printf $0length(s)" ";for(i=2;i<=14;i++){printf s[i]*1" "};print ""}' |

数字に着目したとき手札が何種類あるか、またそれぞれの数字が何枚あるかを2~14(A)まで表示。

# 1~5:プレイヤーAの手札の数字
# 6~10:プレイヤーBの手札の数字
# 11~15:プレイヤーAの手札のマーク
# 16~20:プレイヤーBの手札のマーク
# 21:プレイヤーAの手札の数字の種類
# 22~34:プレイヤーAの手札の数字の枚数(数字毎)
# 35:プレイヤーBの手札の数字の種類
# 36~48:プレイヤーBの手札の数字の枚数(数字毎)

awk '{delete s;for(i=22;i<=34;i++){s[$i]=i-20};print $0,3*(3 in s)+2*(2 in s),s[3]*1,s[2]*1,s[1]*1}' |
awk '{delete s;for(i=36;i<=48;i++){s[$i]=i-34};print $0,3*(3 in s)+2*(2 in s),s[3]*1,s[2]*1,s[1]*1}' |

役の特定に必要な「最大枚数」(スリーカード、フルハウスなら3、ツーペア、ワンペアなら2)と3枚、2枚、1枚でのそれぞれの数字を表示。
これが役が同じ場合に勝負するときの情報元になる。

# 1~5:プレイヤーAの手札の数字
# 6~10:プレイヤーBの手札の数字
# 11~15:プレイヤーAの手札のマーク
# 16~20:プレイヤーBの手札のマーク
# 21:プレイヤーAの手札の数字の種類
# 22~34:プレイヤーAの手札の数字の枚数(数字毎)
# 35:プレイヤーBの手札の数字の種類
# 36~48:プレイヤーBの手札の数字の枚数(数字毎)
# 49:プレイヤーAの最大枚数
# 50~52:プレイヤーAの3枚、2枚、1枚の数字
# 53:プレイヤーBの最大枚数
# 54~56:プレイヤーBの3枚、2枚、1枚の数字

awk '{print $0,(600+$50)*($21$49==25)}' |
awk '{print $0,(600+$54)*($35$53==25)}' |
awk '{print $0,(500+$52)*($11$12$13$14$15 ~ "H{5}|D{5}|S{5}|C{5}")}' |
awk '{print $0,(500+$56)*($16$17$18$19$20 ~ "H{5}|D{5}|S{5}|C{5}")}' |
awk '{print $0,(400+$52)*($22$23$24$25$26$27$28$29$30$31$32$33$34 ~ ".*11111.*")}' |
awk '{print $0,(400+$56)*($36$37$38$39$40$41$42$43$44$45$46$47$48 ~ ".*11111.*")}' |
awk '{print $0,(300+$50)*($21$49==33)}' |
awk '{print $0,(300+$54)*($35$53==33)}' |
awk '{print $0,(200+$51)*($21$49==32)}' |
awk '{print $0,(200+$55)*($35$53==32)}' |
awk '{print $0,(100+$51+$52/10)*($21$49==42)}' |
awk '{print $0,(100+$55+$56/10)*($35$53==42)}' |

それぞれの役毎に点数を末尾に追加していく。
ポイント1.条件に合致するときと合致しないときで処理を分けたいが、条件判断の結果が1か0なのでそれをかけている(邪道かもしれないが)。

# 1~5:プレイヤーAの手札の数字
# 6~10:プレイヤーBの手札の数字
# 11~15:プレイヤーAの手札のマーク
# 16~20:プレイヤーBの手札のマーク
# 21:プレイヤーAの手札の数字の種類
# 22~34:プレイヤーAの手札の数字の枚数(数字毎)
# 35:プレイヤーBの手札の数字の種類
# 36~48:プレイヤーBの手札の数字の枚数(数字毎)
# 49:プレイヤーAの最大枚数
# 50~52:プレイヤーAの3枚、2枚、1枚の数字
# 53:プレイヤーBの最大枚数
# 54~56:プレイヤーBの3枚、2枚、1枚の数字
# 57~58:フルハウスの点数
# 59~60:フラッシュの点数
# 61~62:ストレートの点数
# 63~64:スリーカードの点数
# 65~66:ツーペアの点数
# 67~68:ワンペアの点数

awk '{a=0;b=0;for(i=57;i<=NF;i+=2){a+=$i;b+=$(i+1)};print $0,a,b}' |

役の点数を加算し仮の点数を算出する。
この値が0の場合は役無しである。

# 1~5:プレイヤーAの手札の数字
# 6~10:プレイヤーBの手札の数字
# 11~15:プレイヤーAの手札のマーク
# 16~20:プレイヤーBの手札のマーク
# 21:プレイヤーAの手札の数字の種類
# 22~34:プレイヤーAの手札の数字の枚数(数字毎)
# 35:プレイヤーBの手札の数字の種類
# 36~48:プレイヤーBの手札の数字の枚数(数字毎)
# 49:プレイヤーAの最大枚数
# 50~52:プレイヤーAの3枚、2枚、1枚の数字
# 53:プレイヤーBの最大枚数
# 54~56:プレイヤーBの3枚、2枚、1枚の数字
# 57~58:フルハウスの点数
# 59~60:フラッシュの点数
# 61~62:ストレートの点数
# 63~64:スリーカードの点数
# 65~66:ツーペアの点数
# 67~68:ワンペアの点数
# 69~70:仮の点数

awk '{print ($69==0)*$52+($69!=0)*$69,($70==0)*$56+($70!=0)*$70}' |

仮の点数が0かどうかを判断する。
0の場合は手札の中で一番強いカードを点数とする。

途中途中不要なカラムがたくさんあるが、デバッグ的な需要がある為最後まで削除せずに残しておいた。

答え合わせ

こちらのサイト様と一致していればOKとした。
漫ろ草 SozoroGusa Project Euler - Problem 54