Project Euler 53,54,55問目

#はじめに
C#を用いてProjectEulerに挑戦している人の記録です。VisualStudio2017で、1つのフォームアプリの中に問題番号のボタンを作成し、そのボタンをクリックすると結果をラベルに表示するという形式でやっています。
#53問目
12345から3つ選ぶ選び方は10通りである.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345.
組み合わせでは, 以下の記法を用いてこのことを表す: $ _5C_3 $ = 10.

一般に, r ≤ n について$ nCr = n!/(r!(n-r)!) $である. ここで,$ n! = n×(n−1)×...×3×2×1,  0! = 1 $と階乗を定義する.

n = 23 になるまで, これらの値が100万を超えることはない: $nC_{10}$ = 1144066.

1 ≤ n ≤ 100 について, 100万を超える nCr は何通りあるか?

```CSharp
public static BigInteger factorial(int n, int times)
        {
            BigInteger Number = n;
            for (; times > 1; times--)
            {
                Number = Number * (n - 1);
                n--;
            }
            return Number;
        }

private void button53_Click(object sender, EventArgs e)
        {
            int count = 0;
            for (int n = 1; n <= 100; n++)
            {
                for (int r = 1; r <= n; r++)
                {
                    BigInteger value = factorial(n, r) / factorial(r, r);
                    if (value > 1000000)
                    {
                        count++;
                    }
                }
            }
            label1.Text = "Answer= " + count;
        }
```
階乗を行うfactorical関数を定義して、それを用いて組み合わせの値を出しています。100まで組み合わせを全通り行って答えを出しています。
#54問目
カードゲームのポーカーでは, 手札は5枚のカードからなりランク付けされている。
ここでカードの値は小さい方から2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, Aである. (訳注：データ中で10は'T'と表される)

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

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

- 全ての手札は正しい (使われない文字が出現しない. 同じカードは繰り返されない)
- 各プレイヤーの手札は特に決まった順に並んでいるわけではない
- 各勝負で勝敗は必ず決まる   
1000回中プレイヤー1が勝つのは何回か? (訳注 : この問題に置いてA 2 3 4 5というストレートは考えなくてもよい)

```CSharp
public static int ConvertValue(string Value)
        {
            if (Value == "A") return 14;
            else if (Value == "J") return 11;
            else if (Value == "K") return 13;
            else if (Value == "Q") return 12;
            else if (Value == "T") return 10;
            else return int.Parse(Value);
        }
        
        public static List<int> StrengthCheck(List<int> CardValue, List<string> CardMark)
        {

            int Pair = 0;
            int Flash = 0;
            int Straight = 0;
            int Strength = 0;
            var StrengthList = new List<int>();
            var ValueCompareList = new List<int>();
            //ペア判定
            for (int i = 0; i < 5; i++)
            {
                for (int j = 1; i + j < 5; j++)
                {
                    if (CardValue[i] == CardValue[i + j])
                    {
                        Pair++;
                    }
                }
            }
            //ストレート判定
            for (int i = 1; i < 5; i++)
            {
                if (CardValue[i - 1] - 1 == CardValue[i])
                {
                    Straight = 1;
                }
                else
                {
                    Straight = 0;
                    break;
                }
            }
            //フラッシュ判定
            for (int i = 1; i < 5; i++)
            {
                if (CardMark[i - 1] == CardMark[i])
                {
                    Flash = 1;
                }
                else
                {
                    Flash = 0;
                    break;
                }
            }

            if (Straight == 1 && Flash == 1 && CardValue[0] == 10)
            {
                Strength = 9;//ロイヤルストレートフラッシュ
            }
            else if (Straight == 1 && Flash == 1) Strength = 8; //ストレートフラッシュ
            else if (Straight == 1) Strength = 4;//ストレート
            else if (Flash == 1) Strength = 5;//フラッシュ
            else if (Pair == 0) Strength = 0;//役なし
            else if (Pair == 1)
            {
                Strength = 1;//ワンペア
                ValueCompare(CardValue, ValueCompareList);
            }
            else if (Pair == 2)
            {
                Strength = 2;//ツーペア
                ValueCompare(CardValue, ValueCompareList);
            }
            else if (Pair == 3)
            {
                Strength = 3;//スリーカード
                ValueCompare(CardValue, ValueCompareList);
            }
            else if (Pair == 4)
            {
                Strength = 6;//フルハウス
                ValueCompare(CardValue, ValueCompareList);
            }
            else if (Pair == 6)
            {
                Strength = 7;//フォーカード
                ValueCompare(CardValue, ValueCompareList);
            }
            StrengthList.Add(Strength);
            StrengthList.AddRange(ValueCompareList);
            StrengthList.AddRange(CardValue);
            var Hash = new HashSet<int>(StrengthList);
            var StrengthList2 = new List<int>(Hash);
            return StrengthList2;
        }
        private static List<int> ValueCompare(List<int> CardValue, List<int> ValueCompareList)
        {
            int count = 0;
            for (int i = 0; i < CardValue.Count - 1; i++)
            {
                if (CardValue[i] == CardValue[i + 1])
                {
                    ValueCompareList.Add(CardValue[i]);
                    count++;
                }
                else count = 0;
                if (count == 2 && CardValue.Count - 2 == i)
                {
                    ValueCompareList.Insert(0, CardValue[i]);
                }
            }
            return ValueCompareList;
        }
        private void button54_Click(object sender, EventArgs e)
        {
            string path = Environment.GetFolderPath(Environment.SpecialFolder.Desktop) + @"\poker.txt";
            Encoding utf8 = Encoding.GetEncoding("utf-8");
            string[] NumberString;
            NumberString = new string[1000];
            int P2WinCount = 0;
            using (var reader = new StreamReader(path, utf8))
            {
                try
                {
                    for (int i = 0; i < 1000; i++)
                    {
                        NumberString[i] = reader.ReadLine();
                    }
                }
                catch (Exception ex)
                {

                }
            }
            char[] DelimiterChars = { ' ' };
            int P1WinCount = 0;
            for (int i = 0; i < 1000; i++)
            {
                var BothHand = NumberString[i].Split(DelimiterChars);
                string[] P1Hand = new string[5];
                string[] P2Hand = new string[5];
                for (int j = 0; j < 5; j++)
                {
                    P1Hand[j] = BothHand[j];
                }
                for (int j = 5, k = 0; j < 10; j++, k++)
                {
                    P2Hand[k] = BothHand[j];
                }
                var P1CardValue = new List<int>();
                var P1CardMark = new List<string>();
                var P2CardValue = new List<int>();
                var P2CardMark = new List<string>();
                for (int j = 0; j < 5; j++)
                {
                    P1CardValue.Add(ConvertValue(P1Hand[j].Substring(0, 1)));
                    P1CardMark.Add(P1Hand[j].Substring(1, 1));
                    P2CardValue.Add(ConvertValue(P2Hand[j].Substring(0, 1)));
                    P2CardMark.Add(P2Hand[j].Substring(1, 1));
                }
                P1CardValue.Sort();
                P1CardValue.Reverse();
                P2CardValue.Sort();
                P2CardValue.Reverse();
                var P1Strength = StrengthCheck(P1CardValue, P1CardMark);
                var P2Strength = StrengthCheck(P2CardValue, P2CardMark);

                for (int j = 0; j < P1Strength.Count-1; j++){
                    if (P1Strength[j] > P2Strength[j]) {
                        P1WinCount++;
                        break;
                    }
                    else if (P1Strength[j] < P2Strength[j]) { P2WinCount++; break; }
                    else if (P1Strength[j] == P2Strength[j])
                    {
                        if (P1Strength[j + 1] > P2Strength[j + 1]) {
                            P1WinCount++;
                            break;
                        }
                        else { P2WinCount++; break; }
                    }
                }
            }
            label1.Text = "Answer= " + P1WinCount;
        }
```

Convartvalueは、絵札を数字に変換する関数です。StrengthCheckでポーカーの役判定を行っています。全てのカードに対して、条件を満たす場合にのみフラグが経つようにして、強さを決めています。
メインの関数では、まずデスクトップにあるpoker.txtの内容を読み込みます。空白でカードが区切られているため、セパレーターを使ってP1とP2の手札に分けます。それぞれの手札をマークと値の2つのリストに入れてソートし、StrengthCheckに入れます。Strengthのリストには、[0]に役の強さ、[1]以降には役を構成する数字を強い順に並べています。フルハウスの時だけ条件が難しいので、その時はInsertで先に数字を入れることで役の強さを正しくしています。P1が勝った回数をカウントして答えとしました。
#55問目
47とその反転を足し合わせると, 47 + 74 = 121となり, 回文数になる.

全ての数が素早く回文数になるわけではない. 349を考えよう,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
349は, 3回の操作を経て回文数になる.

まだ証明はされていないが, 196のようないくつかの数字は回文数にならないと考えられている. 反転したものを足すという操作を経ても回文数にならないものをLychrel数と呼ぶ. 先のような数の理論的な性質により, またこの問題の目的のために, Lychrel数で無いと証明されていない数はLychrel数だと仮定する.

更に, 10000未満の数については，常に以下のどちらか一方が成り立つと仮定してよい.

- 50回未満の操作で回文数になる
- まだ誰も回文数まで到達していない

実際, 10677が50回以上の操作を必要とする最初の数である: 4668731596684224866951378664 (53回の操作で28桁のこの回文数になる).

驚くべきことに, 回文数かつLychrel数であるものが存在する. 最初の数は4994である.

10000未満のLychrel数の個数を答えよ.

注: 2007/04/24にLychrel数の理論的な性質を強調するために文面が修正された.

```CSharp
public static BigInteger BigIntReverse(BigInteger Value)
        {
            char[] Reverse = Value.ToString().ToCharArray();
            Array.Reverse(Reverse);
            var Reversed = new string(Reverse);
            return BigInteger.Parse(Reversed);
        }
        private void button55_Click(object sender, EventArgs e)
        {
            BigInteger Value = 0;
            int Count = 0;
            for (int i = 1; i < 10000; i++)
            {
                Value += i;
                for (int j = 0; j < 50; j++)
                {
                    Value += BigIntReverse(Value);
                    if (Value == BigIntReverse(Value))
                    {
                        break;
                    }
                    else if (j == 49)
                    {
                        Count++;
                    }
                }
                Value = 0;
            }
            label1.Text = "Answer=" + Count;
        }
```
BigIntReverseでどんな大きな値でも反転した数にします。10000未満の数に対して、50回未満反転して足す操作を行って回文にならなかった数をカウントして答えとしました。

#感想
54問目のポーカーはかなり考えました。プログラミングをやっているという気分になりましたし、修正すればポーカーを作れるという自信になりました。大体の問題に対して全通り探索をしているので、簡単になるアルゴリズムがあるなら思いつくようにしていきたいです。