Project Euler 032を解いてみる。「パンデジタル積」

Project Euler 032

032

すべての桁に 1 から n が一度だけ使われている数をn桁の数がパンデジタル (pandigital) であるということにしよう: 例えば5桁の数 15234 は1から5のパンデジタルである.
7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる.
掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ.
HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

->次の問題

考え方

1~9の数字でパンデジタルとなるように積を作るには、かけられる数Aとかける数Bと積ABの桁の合計が9になる必要があります。
A<Bとすると考えられるA-B-ABの組み合わせは、

• 1桁×4桁=4桁
• 2桁×3桁=4桁

の組み合わせです。
なので、1~9の数字を並び替えた組み合わせを作り、それを1-4-4または2–3-4に分け、左辺と右辺が一致するか総当たりしていきます。
組み合わせの生成にはitertoolsのpermutationsを使用しました。
また、答えには重複があるとのことなのでsetを使い重複を削除しました。

コード

euler032.py

from itertools import permutations


def main():
    pandigital_set = set()
    # itertools.permutationsを使用し1~9までの数字を使用した順列の組み合わせを生成
    # 生成された数列を1-4-4または2-3-4に分け、左辺2つの乗算結果が右辺と一致するか検証
    for numbers in permutations(range(1, 10)):
        right_side = numbers[5] * 1000 + numbers[6] * 100 + numbers[7] * 10 + numbers[8]
        # 1-4-4の場合
        numA = numbers[0]
        numB = numbers[1] * 1000 + numbers[2] * 100 + numbers[3] * 10 + numbers[4]
        if numA * numB == right_side:
            pandigital_set.add(right_side)
            print(f'{numA} * {numB} = {right_side}')
        # 2-3-4の場合
        numA = numbers[0] * 10 + numbers[1]
        numB = numbers[2] * 100 + numbers[3] * 10 + numbers[4]
        if numA * numB == right_side:
            pandigital_set.add(right_side)
            print(f'{numA} * {numB} = {right_side}')
    print('Answer:', sum(pandigital_set))


if __name__ == '__main__':
    from time import time as t

    st = t()
    main()
    print(t() - st, 'sec')

paizaにて実行
結果 12 * 483 = 5796 18 * 297 = 5346 27 * 198 = 5346 28 * 157 = 4396 39 * 186 = 7254 4 * 1738 = 6952 4 * 1963 = 7852 42 * 138 = 5796 48 * 159 = 7632 Answer: 45228 0.20388317108154297 sec
先頭が”9”の場合、必ず桁が上がりすぎるので省いても良かったですが、そこまで変わらなそう(1割くらい)なので簡素さを優先しました。