【アルゴリズム力強化計画】社内で Project Euler に取り組んでみました

社内で「アルゴリズム力強化」をテーマにした取り組みを行いました。

Project Euler を題材に挑戦してみましたので、今回はその様子を紹介させていただきます。

Project Eulerとは？

Project Eulerは、数学にまつわるプログラミングの問題が豊富に用意されているウェブサイトです。
(他の有名どころだと、AtCoderやLeetCodeですかね)

各問題は、効率的なアルゴリズムを設計することで解けるよう工夫されています。
任意のプログラミング言語を使って各問題に挑戦していく形式です。

ただ、「なぜ今、アルゴリズムなの？」と思われる方もいるのではないでしょうか。

きっかけ

弊社ではインフラ構築からアプリ開発まで一気通貫で対応できる体制を強みとしています。

私自身、直近ではアプリ開発をメインで担当していますが、開発現場でよく耳にするのが、

• 「I/Oやパフォーマンス面でインフラリソースに問題がある」
• 「データベースのチューニングに課題がある」

といった声です。

もちろんそれらの問題は重要ですし、改善すべき点ではあります。
ただ、コストや技術的な制約から、インフラにかけられるリソースには限界があるのも事実ですよね。

そんなときにふと思ったのが、「アプリのロジック自体に問題があるケース、意外と見過ごされていないか？」という疑問でした。

「実装段階から、アプリケーション内部の処理効率を意識することで、パフォーマンスを向上させられるのではないか。」

そんなもやもやから、アルゴリズムにフォーカスを当てることの重要性を再認識し、今回取り組もうと思ったきっかけとなりました。

取り組みの様子

「とりあえず1週間、1日1問やってみようか。」
というやり取りから、この取り組みはぬるっと始まりました。

1週間という期間設定でしたが、なんだかんだ1ヶ月以上コミットが続いていたのは良い取り組みになったな、と感じています。

取り組みにあたって、1つだけルールを設けました。

「回答にAIは使わない。」

問題を解くことがゴールではなくて、思考力を鍛えたい、が取り組みの意図だからです。

メンバーごとにいろいろな取り組みをしていたみたいです。

• メンバーが各々リポジトリを作成して、他の人の回答と自身の回答を比較してみる。
• 自身が実装した処理に対して、AIにフィードバックをしてもらう。
• ベンチマークを計測して、どの実装が一番速いかを競う。
• 複数のAIモデルで回答を出して、それぞれのベンチマークを計測して競わせてみる。
• 複数のプログラミング言語で解いてみる。
• あえてパフォーマンスが悪いと言われている言語で解いてみる。

どんな問題があるの？

序盤のNo.1~10までは、コーディング試験等でもよく取り上げられる問題が多い印象で、 比較的時間をかけずに解くことができます。

No.11以降は、スマートな計算が必要となってきて、難易度が上がってきます。
（3分かかってやっと答えが出る、といった経験もありました...。）

以下は、No.25: Fibonacci数列の問題です。

Fibonacci数列は、以下の漸化式で定義されます。

F_n = F_(n-1) + F_(n-2)

ただし、F_1 = 1 および F_2 = 1 とします。
したがって、最初の12項は次のようになります。

F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, F_7 = 13, F_8 = 21, F_9 = 34, F_10 = 55, F_11 = 89, F_12 = 144

12番目の項であるF_12は、初めて3桁の数になる項です。
では、Fibonacci数列において、初めて1000桁の数になる項は何番目でしょうか？

1000桁に到達したFibonacci数列のインデックスを求める問題ですね。

私は以下の様に解きました。

func main() {
	x, y := big.NewInt(1), big.NewInt(1)
	count := 2
	for len(y.Text(10)) < 1000 {
		x, y = y, x.Add(x, y)
		count++
	}
	fmt.Println(count)
}

実際に挑戦してみて

メンバーによって得意・苦手が見えてくるのが面白いな、と感じました。

• 規則があるような問題が得意なメンバー
• 素数問題が異常に得意なメンバー
• 意地でも力技でゴリ押すメンバー
• などなど。

正直なところ、私自身、アルゴリズムに関してさほど興味を持っている分野ではありませんでした。
ただ、問題を解くにあたって「線形探索が遅い」や「メモリの確保領域によるベンチマークの改善」を実際に肌で感じることができました。

また、特に印象的だったのは、計算量やアルゴリズムの概念をチーム内の共通認識にできたことです。

コードレビューの際、
「この実装だと計算量が O(N^2) になるから、$O(N \log N) に改善できないか？」
といった具体的な議論ができるようになり、意思疎通が格段にスムーズになりました。

想像よりも実務への即効性があったのが意外でしたし、かなりいい取り組みだったな、と感じています。

まとめ

皆さんも、アルゴリズム力に磨きをかけたいと思ったら、ぜひProject Eulerに挑戦してみてはいかがでしょうか？