【C#】Project Euler 17,18,19問目

はじめに

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

17問目

1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている.

では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.

注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.

private void button17_Click(object sender, EventArgs e)
        {
            long LetterNumber1 = 3 + 3 + 5 + 4 + 4 + 3 + 5 + 5 + 4;//1~9
            long LetterNumber2 = 3 + 6 + 6 + 8 + 8 + 7 + 7 + 9 + 8 + 8;//10~19
            long LetterNumber3 = (6 * 10 + LetterNumber1) * 4;//20~29,30~39,80~89,90~99
            long LetterNumber4 = (5 * 10 + LetterNumber1) * 3;//40~49,50~59,60~69
            long LetterNumber5 = 7 * 10 + LetterNumber1;//70~79
            long HundredAnd = 7 + 3;
            long Hundred = 7 * 9 + LetterNumber1;//100,200,300,400,500,600,700,800,900
            long LetterNumber6 = 3 * (99 * (3 + HundredAnd) + LetterNumber1 + LetterNumber2 + LetterNumber3 + LetterNumber4 + LetterNumber5);//101~199,201~299,601~699
            long LetterNumber7 = 3 * (99 * (4 + HundredAnd) + LetterNumber1 + LetterNumber2 + LetterNumber3 + LetterNumber4 + LetterNumber5);//401~499,501~599,901~999
            long LetterNumber8 = 3 * (99 * (5 + HundredAnd) + LetterNumber1 + LetterNumber2 + LetterNumber3 + LetterNumber4 + LetterNumber5);//301~399,701~799,801~899
            long OneThousand = 11;
            long Answer = LetterNumber1 + LetterNumber2 + LetterNumber3 + LetterNumber4 + LetterNumber5 + LetterNumber6 + LetterNumber7 + LetterNumber8 + Hundred + OneThousand;
            label1.Text = "Answer = " + Answer;
        }

出現する単語の文字数を足していきました。どれだけ足したかわからなくなるので、コメントで対応する英単語の部分を確認し、全部足しているか確認しました。型はlongである必要は全くないですね……。

18問目

以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.

internal struct MyStack
        {
            internal int X;
            internal int Y;
            internal int SumValue;
        };
private void button18_Click(object sender, EventArgs e)
        {
            var Delta = new int[][]{
                new int[]{ 75},
                new int[]{ 95,64},
                new int[]{ 17,47,82},
                new int[]{ 18,35,87,10},
                new int[]{ 20,04,82,47,65},
                new int[]{ 19,01,23,75,03,34},
                new int[]{ 88,02,77,73,07,63,67},
                new int[]{ 99,65,04,28,06,16,70,92},
                new int[]{ 41,41,26,56,83,40,80,70,33},
                new int[]{ 41,48,72,33,47,32,37,16,94,29},
                new int[]{ 53,71,44,65,25,43,91,52,97,51,14},
                new int[]{ 70,11,33,28,77,73,17,78,39,68,17,57},
                new int[]{ 91,71,52,38,17,14,91,43,58,50,27,29,48,},
                new int[]{ 63,66,04,68,89,53,67,30,73,16,69,87,40,31},
                new int[]{ 04,62,98,27,23,09,70,98,73,93,38,53,60,04,23}
            };

            var Stack = new Stack<MyStack>();
            MyStack StackState;
            StackState.X = StackState.Y = 0;
            StackState.SumValue = Delta[0][0];
            Stack.Push(StackState);

            int Max = 0;

            while (Stack.Count > 0)
            {
                MyStack Popped = Stack.Pop();
                if (Popped.X == Delta.GetUpperBound(0))
                {
                    if (Max < Popped.SumValue)
                    {
                        Max = Popped.SumValue;
                        label1.Text = "Answer = " + Popped.SumValue;
                    }
                    continue;
                }

                StackState.X = Popped.X + 1;
                StackState.Y = Popped.Y;
                StackState.SumValue = Popped.SumValue + Delta[StackState.X][StackState.Y];
                Stack.Push(StackState);

                StackState.X = Popped.X + 1;
                StackState.Y = Popped.Y + 1;
                StackState.SumValue = Popped.SumValue + Delta[StackState.X][StackState.Y];
                Stack.Push(StackState);
            }
        }

色々調べて、スタックを使って探索する方法を実装しました。しかし、正直まだ理解が追い付いていません。探索アルゴリズム自体は理解しているのですが、それをコードに落とし込むところが理解できていません。理解できるようにしたいです。

ちなみに、局所解になりそうだなと思いながら、今いる地点から下の2つの数値で大きいほうに進むというアルゴリズムを実装しました。やはり局所解でした。

//下の二つの項で大きいほうに進むアルゴリズム。やはり局所解でした。
            int Depth = 0;
            int Depth = 0;
            int SideIndex = 0;
            int Sum = 0;
            int Max = 0;
            Sum += Delta[Depth][SideIndex];
            while (Depth < 14)
            {
                if (Delta[Depth + 1][SideIndex] < Delta[Depth + 1][SideIndex + 1])
                {
                    Sum += Delta[Depth + 1][SideIndex + 1];
                    Max = Delta[Depth + 1][SideIndex + 1];
                    SideIndex++;
                }
                else
                {
                    Sum += Delta[Depth + 1][SideIndex];
                    Max = Delta[Depth + 1][SideIndex];
                }
                Depth++;
                textBox1.Text += Max + " ";
                Max = 0;
　　　　　　 }

19問目

次の情報が与えられている.

• 1900年1月1日は月曜日である
• 9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである
• 2月は28日まであるが, うるう年のときは29日である
• うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない

20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になるのは何回あるか?

private void button19_Click(object sender, EventArgs e)
        {
            var Date1 = new DateTime(1901, 1, 1);
            int Count = 0;
            while (Date1 <= new DateTime(2000, 12, 31))
            {
                if (Date1.DayOfWeek == DayOfWeek.Sunday)
                {
                    Count++;
                }
                Date1 = Date1.AddMonths(1);
            }
            label1.Text = "Answer = " + Count;
        }

1901年1月1日と2000年12月31日を宣言し、月を1つずつ進めつつDayOfWeekで曜日を調べるループを回してます。