Project Euler 41,42,43問目

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

#41問目
n桁パンデジタルであるとは, 1からnまでの数を各桁に1つずつ持つこととする.(数学的定義とは異なる)

例えば2143は4桁パンデジタル数であり, かつ素数である. n桁（この問題の定義では9桁以下）パンデジタルな素数の中で最大の数を答えよ.

```Csharp
private void button41_Click(object sender, EventArgs e)
        {
            int Max = 0;
            for (int i = 100001; i < 1000000000; i = i + 2)
            {
                string NumberString = i.ToString();
                if (NumberString.Contains("0")) continue;
                var Hash = new HashSet<char>(NumberString);
                if (Hash.Count == NumberString.Length)
                {
                    int Flag = 0;
                    for (int j = 1; j <= NumberString.Length; j++)
                    {

                        if (NumberString.Contains(j.ToString()) == false)
                        {
                            Flag = 1;
                        }
                    }
                    if (Flag == 0)
                    {
                        if (Sosuu(i) == true)
                        {
                            Max = i;
                        }
                    }
                }
            }
            label1.Text = "Answer= " + Max;
        }
```
9桁での最大の数値まで全探索しています。その数字を文字列に変換し、0が入っていないことを確認した後ハッシュセットに1文字ずつ代入することで重複がないことを確認しています。その後、桁数までの数字がすべて含まれていた場合、素数かどうか確認してその最大値を答えとしました。iを奇数からスタートして2ずつ足しているのは、偶数だと必ず素数ではないからです。

#42問目
三角数のn項は $t_n = \frac{1}{2}n(n+1)$で与えられる. 最初の10項は

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
である.

単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば SKY は $19 + 11 + 25 = 55 = t_{10}$である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ.

16Kのテキストファイル words.txt 中に約2000語の英単語が記されている. 三角語はいくつあるか?

```Csharp
private void button42_Click(object sender, EventArgs e)
        {
            string Path = Environment.GetFolderPath(Environment.SpecialFolder.Desktop) + @"\words.txt";
            Encoding UTF8 = Encoding.GetEncoding("utf-8");
            string Word = "";
            using (var Reader = new StreamReader(Path, UTF8))
            {
                try
                {
                    Word = Reader.ReadToEnd();
                }
                catch
                {

                }
            }
            char[] DelimiterChars = { ',' };
            string[] Words = Word.Split(DelimiterChars);
            int Count = 0;
            foreach (string EachWord in Words)
            {
                int Score = EachWord.ToCharArray().Where(x => x >= 'A').Select(x => x - 'A' + 1).Sum();
                int Delta = 1;
                for (int i = 2; Score >= Delta; i++)
                {
                    if (Score == Delta)
                    {
                        Count++;
                        break;
                    }
                    Delta += i;
                }
            }
            label1.Text = "Answer = " + Count.ToString();
        }
```
読み込むファイルはデスクトップに置いています。英単語は， で区切られているので、，で区切って配列に格納します。その1単語ごとに対して、1文字ずつに対してAより文字コードが大きいと、その文字コードの値からAの文字コードの値を引いて1を足したものを合計することでスコアを出しています。その後、三角数かどうか判定してカウントし、カウントされた数を答えとしました。
#43問目
数1406357289は0から9のパンデジタル数である (0から9が1度ずつ現れるので). この数は部分文字列が面白い性質を持っている.

d1を上位1桁目, d2を上位2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.

- $d_2d_3d_4=406$ は 2 で割り切れる
- $d_3d_4d_5=063$ は 3 で割り切れる
- $d_4d_5d_6=635$ は 5 で割り切れる
- $d_5d_6d_7=357$ は 7 で割り切れる
- $d_6d_7d_8=572$ は 11 で割り切れる
- $d_7d_8d_9=728$ は 13 で割り切れる
- $d_8d_9d_{10}=289$ は 17 で割り切れる  
このような性質をもつ0から9のパンデジタル数の総和を求めよ.

```Csharp
static bool reject(string Number)
        {
            var list = new List<int>(Eratosthenes(18));
            int Length = Number.Length;
            for (int i = 4; i < 11; i++)
            {
                if (Length == i) { return (int.Parse(Number.Substring(i - 3, 3)) % list[i - 4]) != 0; }
            }
            return false;
        }

private void button43_Click(object sender, EventArgs e)
        {
            var Stack = new Stack<string>();
            for (int i = 1; i <= 9; i++)
            {
                Stack.Push(i.ToString());
            }

            long sum = 0;
            while (Stack.Count > 0)
            {
                string Popped = Stack.Pop();
                if (Popped.Length == 10)
                {
                    sum += Convert.ToInt64(Popped);

                }

                for (int i = 0; i <= 9; i++)
                {
                    if (Popped.Contains(i.ToString()) == false)
                    {
                        string WillPush = Popped + i.ToString();
                        if (reject(WillPush) == false)
                        {
                            Stack.Push(WillPush);
                        }
                    }
                }
            }
            label1.Text = "Answer= " + sum.ToString();
        }
```
10桁の数字を題意に沿わない場合は枝切りしながらスタックを使って作っています。枝切りの条件は$d_2d_3d_4$, $d_3d_4d_5$...というように3つずつ取り出して素数で割れるかという題意の条件です。

#終わりに
スタックを使った枝切りは高速ですね。for文を使った41問目はかなり長い時間がかかりましたが、42，43問目はすぐ終わりました。速度を高めるというところも考えたアルゴリズムを作っていきたいです。