こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 53から54を解いてみました。
Problem 53
自分なりに直訳してみました。
123、124、125、134、135、145、234、235、245、345
組合せでは、5_C_3 = 10という表記を使う。
一般に、n_C_r = n! / r!(n−r)!である、ここで、r ≤ n, n! = n×(n−1)×…×3×2×1及び0! = 1である。
n = 23未満では100万は超えない:23_C_10 = 1144066である。
1 ≤ n ≤ 100に対して、100万を超えるn_C_rは重複を考えずに何通りあるか?
ソース
private void test() {
int count = 0;
BigInteger oneMillion = new BigInteger("1000000");
for (int n = 1; n <= 100; n ++) {
for (int r = 1; r <= n; r++) {
if (combinationOf(n, r).compareTo(oneMillion) >= 0) {
count ++;
}
}
}
System.out.println(count);
}
private BigInteger combinationOf(int n, int r) {
BigInteger numerator = factorialOf(new BigInteger(String.valueOf(n)));
BigInteger denominator = factorialOf(new BigInteger(String.valueOf(r)))
.multiply(factorialOf(new BigInteger(String.valueOf(n - r))));
return numerator.divide(denominator);
}
private static final BigInteger ONE = new BigInteger("1");
private BigInteger factorialOf(BigInteger n) {
if (n.compareTo(ONE) <= 0) {
return ONE;
} else {
return n.multiply(factorialOf(new BigInteger(String.valueOf(n.intValue() - 1))));
}
}
Javaには桁数制限のない整数を扱うためのクラスBigIntegerがあります。組合せの公式で階乗を計算するため、今回はこのクラスを使いました。
BigInteger factorialOf(BigInteger n)は引数に対して、その階乗を計算するメソッドです。再帰呼び出しを使ってます。この再帰が終了するためにpublic int compareTo(BigInteger val)を使ってます。このBigIntegerの数値がvalより小さい場合は -1、等しい場合は0、大きい場合は1をへんきゃくするメソッドです。引数が数値1のBigIntegerの場合、factorialOfは1を返却するということです。
BigInteger combinationOf(int n, int r)は組合せn_C_rを計算するメソッドです。組合せの公式の分母と分子をそれぞれ計算して、最後に割り算をしています。
Problem 54
自分なりに直訳してみました。
- ハイカード: 値が一番大きいカード。
- ワンペア: 同じ数のカード2枚。
- ツーペア: 2つの異なるPair。
- スリーカード: 同じ数の3枚のカード。
- ストレート: カード全部が連続する値。
- フラッシュ: カード全部が同じ柄。
- フルハウス: スリーカードとペア。
- フォーカード: 4枚が同じ数。
- ストレートフラッシュ: 同じ柄で連続するカード.
- ロイヤルストレートフラッシュ: 同じ柄の10・J・Q・K・A。
カードは次の順序づけである:2、3、4、5、6、7、8、9、10、J、Q、K、A。
もし2人のプレーヤーが同じランクの手を持つならば、大きい値で構成されるものが勝つ:例えば、8のペアは5のペアを打ち負かす(次の例1を見よ)。しかし、2つのランクが同じならば、例えば、Qのペアを両方のプレーヤーが持つ場合、各手の一番大きいカードが比較される(次の例4を見よ)。同じ場合では、次に大きいカードが比較され、以下同様である。
手 | プレーヤー1 | プレーヤー2 | Winner | |||
1 | 5H 5C 6S 7S KD
5のペア
|
2C 3S 8S 8D TD
8のペア
|
Player 2 | |||
2 | 5D 8C 9S JS AC
Aのハイカード
|
2C 5C 7D 8S QH
Qのハイカード
|
Player 1 | |||
3 | 2D 9C AS AH AC
Aのスリーカード
|
3D 6D 7D TD QD
ダイアのフラッシュ
|
Player 2 | |||
4 | 4D 6S 9H QH QC
Qのペア
9のハイカード |
3D 6D 7H QD QS
Qのペア
7のハイカード |
Player 1 | |||
5 | 2H 2D 4C 4D 4S
フルハウス
With 4のスリーカード |
3C 3D 3S 9S 9D
フルハウス
with 3のスリーカード |
Player 1 |
ファイルpoker.txtは二人のプレーヤーが扱う1000個のダンダムな手が含まれる。そのファイルの各行には(1つの空白で区切られる)10枚のカードが含まれる:最初の5枚はプレーヤー1のカードで最後の5枚がプレーヤー2のカード。全ての手は(不正な数字やカードの繰り返しなく)正しい、各プレーヤーの手は特別な順序ではない、各々の手では明確な勝者がいる、ということを仮定して良い。
プレーヤー1は何回勝つか?
大まかな流れはテキストファイルを読み取り、どちらが勝ちか判定し、プレーヤーの勝利数をカウントするという流れです。
ソース
private final String SEPALATOR = " ";
private void test() {
Poker poker = new Poker();
File file = new File("resource/p054_poker.txt");
try (BufferedReader br = new BufferedReader(new FileReader(file))) {
String line = null;
int count = 0;
while ((line = br.readLine()) != null) {
String[] allCards = line.split(SEPALATOR);
if (poker.getWinner(allCards) == Poker.PLAYER.FIRST) {
count ++;
}
}
System.out.println(count);
} catch (FileNotFoundException e) {
System.out.println("ファイルが存在しません。");
} catch (IOException e) {
System.out.println("エラーが発生しました。");
}
}
上記のPokerクラスが実際に勝敗を判定するクラスで次のように作りました。
ソース
package problem00054;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class Poker {
// ----------------------------------------
// 順序の定義と比較用クラス
// ----------------------------------------
private final String DEF_OF_ORDER = "23456789TJQKA";
private class CardComparator implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
int v1 = DEF_OF_ORDER.indexOf(o1.charAt(0));
int v2 = DEF_OF_ORDER.indexOf(o2.charAt(0));
return v1 - v2;
}
}
// ----------------------------------------
// 勝者を判定するための定義とメソッド群
// ----------------------------------------
public enum PLAYER {
FIRST,
SECOND
}
public PLAYER getWinner(String[] allCards) {
// プレーヤーの手
List<String> cardsOfPlayer1 = new ArrayList<>();
List<String> cardsOfPlayer2 = new ArrayList<>();
for (int i = 0; i < 5; i++) {
cardsOfPlayer1.add(allCards[i]);
cardsOfPlayer2.add(allCards[i + 5]);
}
CardComparator comparator = new CardComparator();
cardsOfPlayer1.sort(comparator);
cardsOfPlayer2.sort(comparator);
String[] card1 = cardsOfPlayer1.toArray(new String[0]);
String[] card2 = cardsOfPlayer2.toArray(new String[0]);
Hand hand1 = getHandOf(card1);
Hand hand2 = getHandOf(card2);
// 勝敗を判定
int rank1 = hand1.rank.ordinal();
int rank2 = hand2.rank.ordinal();
if (rank1 > rank2) {
return PLAYER.FIRST;
} else if (rank1 < rank2){
return PLAYER.SECOND;
}
// ランクが同じの場合は順序を判定
int order1 = hand1.order;
int order2 = hand2.order;
if (order1 > order2) {
return PLAYER.FIRST;
} else if (order1 < order2) {
return PLAYER.SECOND;
}
return null;
}
// ----------------------------------------
// 手を判定するための定義とメソッド群
// ----------------------------------------
private enum Rank {
HIGH_CARD,
ONE_PAIR,
TWO_PAIRS,
THREE_OF_A_KIND,
STRAIGHT,
FLUSH,
FULL_HOUSE,
FOUR_OF_A_KIND,
STRAIGHT_FLUSH,
ROYAL_FLUSH
}
private class Hand {
public Rank rank;
public int order;
public String[] cards;
@Override
public String toString() {
return "Hand [rank=" + rank + ", order=" + order + ", cards=" + Arrays.toString(cards) + "]";
}
}
private Hand getHandOf(String[] cards) {
Hand hand = new Hand();
hand.cards = cards;
// 連続しているか取得
boolean isStraight = checkStraight(cards);
// 柄が同じか取得
boolean isFlush = checkFlush(cards);
// 登場回数をカウント
int[] counts = new int[DEF_OF_ORDER.length()];
for (int i = 0; i < cards.length; i++) {
counts[DEF_OF_ORDER.indexOf(cards[i].charAt(0))] ++;
}
// ロイヤルストレートフラッシュか判定
if (cards[0].charAt(0) == 'T' && isStraight && isFlush) {
hand.rank = Rank.ROYAL_FLUSH;
hand.order = DEF_OF_ORDER.indexOf(cards[cards.length - 1].charAt(0));
return hand;
}
// ストレートフラッシュか判定
if (isStraight && isFlush) {
hand.rank = Rank.STRAIGHT_FLUSH;
hand.order = DEF_OF_ORDER.indexOf(cards[cards.length - 1].charAt(0));
return hand;
}
// フォーカードか判定
for (int i = 0; i < counts.length; i++) {
if (counts[i] == 4) {
hand.rank = Rank.FOUR_OF_A_KIND;
hand.order = i;
return hand;
}
}
// フルハウスか判定
boolean threeOfAKind = false;
for (int i = 0; i < counts.length; i++) {
if (counts[i] == 3) {
threeOfAKind = true;
}
}
int countOfpairs = 0;
for (int i = 0; i < counts.length; i++) {
if (counts[i] == 2) {
countOfpairs ++ ;
}
}
if (threeOfAKind && countOfpairs == 1) {
hand.rank = Rank.FULL_HOUSE;
for (int i = 0; i < counts.length; i++) {
if (counts[i] == 3) {
hand.order = i;
}
}
return hand;
}
// フラッシュか判定
if (isFlush) {
hand.rank = Rank.FLUSH;
hand.order = DEF_OF_ORDER.indexOf(cards[cards.length - 1].charAt(0));
return hand;
}
// ストレートか判定
if (isStraight) {
hand.rank = Rank.STRAIGHT;
hand.order = DEF_OF_ORDER.indexOf(cards[cards.length - 1].charAt(0));
return hand;
}
// スリーカードか判定
if (threeOfAKind) {
hand.rank = Rank.THREE_OF_A_KIND;
for (int i = 0; i < counts.length; i++) {
if (counts[i] == 3) {
hand.order = i;
}
}
return hand;
}
// ツーペアか判定
if (countOfpairs == 2) {
hand.rank = Rank.TWO_PAIRS;
for (int i = 0; i < counts.length; i++) {
if (counts[i] == 2 && i > hand.order) {
hand.order = i;
}
}
return hand;
}
// ワンペアか判定
if (countOfpairs == 1) {
hand.rank = Rank.ONE_PAIR;
for (int i = 0; i < counts.length; i++) {
if (counts[i] == 2) {
hand.order = i;
}
}
return hand;
}
// どれでもない場合
if (hand.rank == null) {
hand.rank = Rank.HIGH_CARD;
hand.order = DEF_OF_ORDER.indexOf(cards[cards.length - 1].charAt(0));
}
return hand;
}
private boolean checkStraight(String[] cards) {
int min = DEF_OF_ORDER.indexOf(cards[0].charAt(0));
for (int i = 1; i < cards.length; i++) {
if (min + i != DEF_OF_ORDER.indexOf(cards[i].charAt(0))) {
return false;
}
}
return true;
}
private boolean checkFlush(String[] cards) {
char c = cards[0].charAt(1);
for (int i = 1; i < cards.length; i++) {
if (c != cards[i].charAt(1)) {
return false;
}
}
return true;
}
}
途中にHandクラスの定義があります。メンバ変数は以下です。
- public Rank rank
- Rankは自作の列挙型です。列挙型ではハイカードからロイヤルストレートフラッシュまでを定義しています。プレーヤーの手のランクを格納するための変数です。
- public int order
- これはランクが同じ時に勝敗判定をするための順序を格納する変数です。例えばワンペアの場合では、そのペアのカードの数です。
- public String[] cards
- 与えられたカードは”[カードの数一文字][柄を表す一文字]”で表されていて、その配列を格納するための変数です。
getHandOfメソッドが上記クラスを返却するメソッドです。引数がはカード5枚を表す配列です。
getWinnerメソッドでプレーヤー1か2どちらが勝った方を返却するメソッドです。引数は2人分のカード10枚を表す配列です。
与えられたテキストを上記のプログラムで判定すると正解は出せましたが、実際には判定できてないパターンがあります。出力させてみた結果、以下の一つだけ勝敗の判定ができてません。しかし、これはプレーヤー2の勝利なため、プレーヤー1の勝利数には影響ありませんでした。
- [6D, 7C, 5D, 5H, 3S, 5C, JC, 2H, 5S, 3D]
このパターンはハイカード同士でともに5のペアです。なので上記プログラムのHand.orderの値がともに5で、勝敗が付きません。問題文にあったルールではこの場合は残りのカードで一番大きい数字で勝敗をきめるようなのですが、その部分は実装しませんでした。