C# で Project Euler に挑戦: Problem 4

問題

最大の回文積

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.

では, 3桁の数の積で表される回文数のうち最大のものを求めよ.

• Problem4 - Project Euler (公式サイト)
• Problem4 - Project Euler (和訳サイト)

ぼくの解答

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var threeDigitNumbers = Enumerable.Range(100, 900).ToList();
        var answer = threeDigitNumbers
            .SelectMany(i => threeDigitNumbers.Select(j => i * j))
            .Where(i => i.IsPalindrome())
            .Max();

        Console.WriteLine(answer);
        Console.ReadLine();
    }
}

public static class NumberHelper
{
    public static bool IsPalindrome(this int n)
    {
        return n.Digits().SequenceEqual(n.Digits().Reverse());
    }

    public static IEnumerable<int> Digits(this int n)
    {
        if (n == 0)
            yield return 0;

        const int radix = 10;
        var q = n;

        while (q != 0)
        {
            yield return q % radix;
            q /= radix;
        }
    } 
}

解説

この問題のポイントは、どうやって回文数かどうか判定するか、でしょうか。以下のどちらかになると思います。

1. 文字列で判定する
2. 各桁の数値をリストにして判定する

文字列でやるほうが簡単ですが、せっかくなので数値の桁を列挙する Digits() メソッドを作って解いてみました。

ある数値の桁の求め方

求めたい進法の基数で割っていって余りを取り出すと桁を求めることができます。例えば 4603 の場合、手順は以下です。

1. 4603 / 10 = 460 ... 3 (商を次の割られる数へ回します)
2.  460 / 10 =  46 ... 0
3.   46 / 10 =   4 ... 6
4.    4 / 10 =   0 ... 4 (商が 0 になったら終了です)

回文数かどうか

上記のように桁のリストを求めるか、文字列に変換して内容を反転させて元のものと同じかどうか調べればよいですね。

今回は int の拡張メソッドに IsPalindrome というメソッドを用意しています。内容は簡単です。

上記の Digits メソッドで桁を列挙し、Reverse メソッドで反転させたものと同じかを、SequenceEqual メソッドで調べます。SequenceEqual メソッドが true を返せば回文数です。

三桁の数字の積

単純にループしても良いですが、せっかく C# なので LINQ です。

はじめに三桁の数字のリストを作ります。Enumerable.Range(100, 900) で簡単ですね。(100 ∼ 999)

組み合わせを作ってそれらをかければいいので、SelectMany と Select メソッドを使って簡単に記述できます。

実行効率

この解は実行効率が悪いです。三桁の数字の組み合わせを全部作ってしまう点がネックですね。
実行効率でいえば、999 * 999 から 999 * 998, 999 * 997 ... とデクリメントしながら積を求め、回文数になった時点で処理を中断するほうが良いです。