Largest palindrome product, Project Euler Problem 4
February 25, 2020
https://projecteuler.net/problem=4
palindrome、回文、つまり最上位の桁からの数字の並びと最下位の桁からの数字の並びとが同じ数値。2つの2桁の数値の積から求められる最大の回文数は、
9009 = 91 × 99
ということで、2つの3桁の数値の積から求められる最大の回文数を求めよっていう問題。
100〜999までの2値を動かして全パターンチェックすれば良さそうだけど、その場合は 900 × 900 = 810,000 回の演算か。とりあえず書いてみる。
Solution 1 #
# https://projecteuler.net/problem=4
from datetime import datetime
def is_palindrome(num: int) -> bool:
num_str = str(num)
num_len = len(num_str)
idx = 0
while idx < num_len:
if num_str[idx] != num_str[-1 - idx]:
return False
idx += 1
return True
# test
print(is_palindrome(123))
print(is_palindrome(12321))
# main
start_time = datetime.now()
result = 0
count = 0
for i in range(100, 1000):
for j in range(100, 1000):
count += 1
if is_palindrome(i * j):
result = max(result, i * j)
exec_time = datetime.now() - start_time
print(f"result: {result!r}")
print(f"count : {count!r}")
print(f"e_time: {exec_time!s}")
出力
False
True
result: (答えなので伏せておく)
count : 810000
e_time: 0:00:01.009521
重複した計算を省く #
Solution 1 の場合、例えば 100 × 900 と 900 × 100 は同じなのでどちらか片方だけ計算すれば良いのでループが改善できそう。ネストした j 側のループのスタートを i からにする。
Solution 2 #
main処理だけ
# main
start_time = datetime.now()
result = 0
count = 0
for i in range(100, 1000):
for j in range(i, 1000):
count += 1
if is_palindrome(i * j):
result = max(result, i * j)
exec_time = datetime.now() - start_time
出力(計算回数と処理時間のみ)
count : 405450
e_time: 0:00:00.577004
半分ぐらいになった。
途中でループを打ち切る #
最大値を求める問題なので「今求められている候補値よりも大きな値は出てこない」が判定できればループを打ち切れる。そのためには、
- 大きな数値からループを始める
- 例えば候補値が 900 × 800 の場合、800以下の2値は計算する必要ない
Solution 3 #
# main
start_time = datetime.now()
result = 0
count = 0
loop_limit = 100
for i in range(1000, 100, -1):
for j in range(i, loop_limit, -1):
count += 1
if is_palindrome(i * j):
result = max(result, i * j)
loop_limit = j
break
if i < loop_limit:
break
exec_time = datetime.now() - start_time
出力
count : 8055
e_time: 0:00:00.024518
いい感じで計算量が約 1 / 100 になった。やったぜ。
今日の学び(Python) #
- datetimeで処理時間計測
- format string literal で文字列整形
- {} で置換、!s で str() と等価、!r で repr() と等価
- repr() は a printable representation of an object ってことで