java-beginner.com ブログ

プログラミングを学習するブログ(Javaをメインに)

Project EulerのProblem 53~54をやってみた

投稿日:

最終更新日:2018年01月21日

アイキャッチ

こんにちは。「Javaを復習する初心者」です。

Project Eulerという数学の問題サイトがあります。そのサイトのProblem 53から54を解いてみました。

Problem 53

自分なりに直訳してみました。

12345から3つ選択する方法はちょうど10通りある:

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

自分なりに直訳してみました。

カードゲーム・ポーカーでは、5枚のカードで1つの手が構成され、ランキングされていて、低い方から高い方は次のである:

  • ハイカード: 値が一番大きいカード。
  • ワンペア: 同じ数のカード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で、勝敗が付きません。問題文にあったルールではこの場合は残りのカードで一番大きい数字で勝敗をきめるようなのですが、その部分は実装しませんでした。