この記事は TLB Enjoy Developers Advent Calendar 2022 の 8日目の記事です。
お久しぶりです。8日ぶり2回目の yatabis です。
今回は Project Euler でコードゴルフをやっていきたいと思います。
早速やりたいのですが、その前に少しだけ説明をします。
（お急ぎの方は 本編 まで読み飛ばしてください。）
Project Euler
Project Euler (https://projecteuler.net/) は、数学っぽいプログラミングっぽい問題が出題されるウェブサイトです。
多くの問題は解くのに数学の知識とプログラミングのスキルが必要になっています。
プログラミングコンテスト（競技プログラミング）といった感じではどうやらなく、問題を解くことで他人と競い合うというよりは、純粋に一つ一つの問題を解くことを楽しむというほうがメインという感じがします。
また、一般的な競技プログラミングの問題と異なり、ソースコードを提出する必要はありません。
問題にも動的な要素はなく、答えは単一の整数になります。
そのため、極端に言えばすべて手計算で解答することも可能となっています。
（とはいえほとんどの問題はコンピューターを使わずに解を導き出すことが十分難しいほど規模が大きく、また適切なプログラムを書けば1分以内に計算が終了する程度の複雑さに調整されているようです。）
コードゴルフ
コードゴルフとは、プログラミングコンテストの一種で、問題を解くプログラムのソースコードの短さを競う競技です。
ソースコードの文字数が少ないほどスコアが高くなるのが特徴で、その言語が持つ仕様を最大限使って要求を満たすコードを極限まで短く切り詰めていくことに命をかけるエクストリームスポーツです。
ショートコーディングと呼ばれることもあります。
Project Euler でコードゴルフをやる
さて、Project Euler の問題でコードゴルフを遊んでいくのですが、今回勝手に以下のようにレギュレーションを決めておきます。
1. 問題で与えられる値のうち、いくつかを標準入力から受け取ることとする
前述の通り ProjectEuler の問題は必ずしもすべての部分をコンピューターに計算される必要がないのですが、コードゴルフではやはりコードを書くところが重要になってくるので、競プロっぽい形にしておきます。
また、なるべくコードを短くしたいという性質上、問題で与えられる情報のサイズにコード長が影響を受けるのを避けたいという狙いもあります。
どの値を標準入力から受け取ることにするかというところについては、問題ごとに空気を読んで決めたいと思います。
2. 標準入力から受け取る値を用いて事前に数値計算することを禁止とする
極端な話、事前に計算しておいた体で解答の値をそのまま出力することを禁じるみたいなことです。
ただし、標準入力から与えられない数に関する数値計算や、数式の式変形などは事前に行っても良いこととします。この辺はコードゴルフの醍醐味だと思うので。
なお、コード長の計測については下記を使用します。
wc -c main.py
今回は Project Euler の最初の 10問だけをやります。
私はプログラミング言語として Python を使います。
それではいよいよ試合開始です。
対戦よろしくお願いします
Problem 1: Multiples of 3 or 5
1問目：1000 未満の 3 または 5 の倍数の合計を求める問題です。
この問題では、 1000未満 のところを入力とします。
競プロっぽく書くと
問題
$N$ 未満の整数について、3 の倍数、または 5 の倍数の合計を出力してください。制約
$N$ は $1000$ 以下の整数
といったところでしょうか。
私の解答は以下です。
print(sum(i*(i%3*i%5<1)for i in range(int(input()))))
53 Bytes となりました。
これぐらいなら普段 Python をよく使う人だと普通に書いても
n = int(input())
print(sum(i for i in range(n) if i % 3 == 0 or i % 5 == 0))
ぐらいになるかなと思います。
ここから
- 入力を一時変数に置かない
- 省略できるスペースを全部削除する
-
boolはintとの演算で暗黙的に型変換されてTrue/Falseが1/0になるので、条件分岐は掛け算に変換できる - 「$a = 0$ または $b = 0$」 は 「$a \times b = 0$」 と等価
- 割った余りは必ず 0 以上なので、
a==0はa<1と書き換えられる
あたりを使えば上の答えになりました。
Problem 2: Even Fibonacci numbers
2問目：フィボナッチ数列の 4000000 を超えない偶数の項の値の合計を求める問題です。
この問題では 4000000 を標準入力で与えます。
私の解答は以下です。
n=int(input())
a,b,c=1,2,0
while b<n:a,b=b,a+b;c+=~a%2*a
print(c)
65 Bytes となりました。
このコードは、わかりやすく展開すると以下のような感じです。
n = int(input())
a = 1
b = 2
c = 0
while b < n:
a, b = b, a + b
if a % 2 == 0:
c += a
print(c)
a と b がフィボナッチ数列の隣接する 2項で、 c が求める合計ですね。
Python だとフィボナッチ数列の更新を 6行目のようにかけて便利ですね。
あとは偶数の時だけ c に足していくのですが、先ほどと同様に条件分岐を掛け算に直すテクニックを使います。
a % 2 は 0 か 1 になるので、 a にかけることで if分岐をなくせます。
ただし、このままだと論理が逆なので a をビット反転して ~a とすることで論理を合わせています。
最後にスペースと改行を極限まで無くして答えです。
Problem 3: Largest prime factor
3問目は：600851475143 の最大の素因数を求める問題です。
もちろん 600851475143 を標準入力で与えます。
私の解答は以下です。
n=int(input())
p=2
while n>2:
if n%p:p+=1
else:a=p;n//=p
print(a)
67 Bytes となりました。
こちらも展開すると以下のようになります。
n = int(input())
p = 2
while n > 2:
if n % p:
p += 1
else:
a = p
n //= p
print(a)
p を n の素因数候補とし、 a に最終的な答えが入るようにします。
n が p で割り切れるとき、 p は n の素因数になるので a を p で更新し、 n を p で割っていきます。
n が p で割り切れないときは p を 1つ大きくして次の素因数を探していきます。
n が p で割り切れる限り割っていくので、 次に見つかった因数は必ず素因数になります。
よって、 n が 2 になったときには a に n の最大の素因数が入っていることになります。
今回は if節と else節で異なる種類の処理が必要だったので、条件分岐を掛け算で処理するテクニックが使いにくかったです。
このためどうしてもインデントが必要になってしまったのですが、 Python のインデントは実はスペース 1個から作ることが出来ます。
Problem 4: Largest palindrome product
4問目は： 2つの 3桁の数をかけてできる回文数のうち最大のものを求める問題です。
この問題は特に動的にできそうなところがなかったので、標準入力はなしです。
私の解答は以下です。
print(max(a*b*(str(a*b)==str(a*b)[::-1])for a in range(1000)for b in range(1000)))
82 Bytes となりました。
展開すると以下のようなコードになります。
ans = 1
for a in range(100, 1000):
for b in range(100, 1000):
n = str(a * b)
if n == n[::-1]:
ans = max(a * b, ans)
print(ans)
2つの 3桁の数を a, b として全探索しています。
回文数かどうかは、文字列にして逆順にしたものと一致するかで判定しています。
これをリスト内包表記にして条件分岐を掛け算で処理すれば上のコードになります。
多少 range の範囲をズルしていますが、 a や b が 3桁未満であれば最大になることはないので 0スタートにしました。
（a または b が 999 になることもないので、 range(999) とすればさらに 2 Bytes 縮められそうですが、証明できなかったのでやめときました（甘え）
Problem 5: Smallest multiple
5問目は： 1 から 20 までのすべての数で割り切れる最小の数を求める問題です。
この問題では 20 を標準入力で与えます。
私の解答は以下です。
import math;print(math.lcm(*range(1,int(input())+1)))
53 Bytes となりました。
実はこの問題は言い換えると 1 から 20 までの数の最小公倍数を求めれば良いのですが、 Python には math パッケージに lcm 関数という超絶便利なものがあるので、これを import して使えば一発で答えが出ます。
Problem 6: Sum square difference
6問目： 1 から 100 までの 総和の二乗から 1 から 100 までの二乗の総和を引いた値を求める問題です。
100 を標準入力で与えます。
n=int(input());print(((n**3-n)*(3*n+2))//12)
44 Bytes となりました。
この問題では特にプログラミングのテクニックは使っておらず、数式の方をゴリゴリ計算しています。
まず 1 から $n$ までの総和の二乗ですが、これは等差級数の和の公式から
\left( \sum_{i=1}^n i \right)^2 = \left( \frac{1}{2} n (n + 1) \right)^2 = \frac{1}{4} n^2 (n + 1)^2
と求められます。
同様に 1 から $n$ までの二乗の総和についても公式があり
\sum_{i=1}^n i^2 = \frac{1}{6} n (n + 1) (2n + 1)
となります。
あとはこれを引き算して整理すれば
\left( \sum_{i=1}^n i \right)^2 - \sum_{i=1}^n i^2 = \frac{1}{12} n (n^2 - 1) (3n + 2)
と計算できました。
これをそのままコードに落としたのが上の解答です。
Problem 7: 10001st prime
7問目：小さいものから数えて 10001 番目の素数を求める問題です。
10001 を標準入力で与えます。
私の解答は以下です。
m=8**7
r=range
s={*r(2,m)}
for p in r(2,999):s-={*r(p*p,m,p)}
print(sorted(s)[int(input())-1])
94 Bytes となりました。
なかなかいい感じにキモいんですが、もともとは以下のようなコードでした。
n = int(input())
m = 10**6
is_prime = [i > 1 for i in range(m + 1)]
for p in range(2, int(m**0.5) + 1):
for i in range(p * p, m + 1, p):
is_prime[i] = False
primes = [i for i, p in enumerate(is_prime) if p]
print(primes[n - 1])
時間計算量的にあまり最適化されていないエラトステネスの篩を用いた素数列挙のコードです。
エラトステネスの篩についてご存知ない方は是非とも調べてほしいのですが、このようなコードを書くと is_prime という i番目の要素に数 i が素数かどうかを表す bool が入った配列が得られます。
これをいい感じにリスト内包表記で処理すると primes という配列に m 以下の素数が昇順で列挙されるので、これの 10001 番目を出力すれば良いわけです。
このコードを短くするために、以下のようなテクニックを使いました。
-
mは 10001 番目の素数よりも大きければ良いので、8**7でよい（-1 Byte) - 最初の forループの上端は
mの平方根より大きければ良いので、999で良い（-10 Bytes） -
is_primeを持たずに最初から素数を列挙する set で扱う（本質） -
rangeを 3回も使うのでrという 1文字の変数に置く（-4 Bytes） -
rangeからsetを作るのに{*range(..)}のように書ける（-2 Bytes）
これで最初のコードのようになり 100 Bytes を切ることが出来ました。
Problem 8: Largest product in a series
8問目：与えられた 1000桁の数字の中から、隣り合う 13つの数字を掛け合わせたものとして最大の数を求める問題です。
1000桁の数字と 13 を標準出力で与えます。
私の解答は以下です。
n=input()
l=len(n)
m=int(input())
a=[1]*l
for i in range(l-m+1):
for j in n[i:i+m]:a[i]*=int(j)
print(max(a))
110 Bytes となりました。
やっていることはわりとシンプルで、配列 a の i 番目に、先頭から i 番目の数から m 個掛け合わせた結果を代入しています。
これもう少し上手くできる気がしており、悔しいですね。
Problem 9: Special Pythagorean triplet
9問目： 下記の条件を満たす自然数 $(a, b, c)$ の組みがただ一つ存在するので、これを求める問題です。
- $a < b < c$
- $a^2 + b^2 = c^2$
- $a + b + c = 1000$
1000 を標準入力で与えます。
私の解答は以下です。
n=int(input());print(max(a*b*(n-a-b)for a in range(n)for b in range(n)if a*a+b*b==(n-a-b)**2))
94 Bytes となりました。
あえて展開する必要ももはやないと思いますが、リスト内包表記で二重の forループで a と b を全探索しつつ、3番目の条件を満たすように c を決定し、2番目の条件を満たすものだけをフィルタしています。
1番目の条件を完全に無視しているのでいくつかの値が残ってしまうのですが、これらはただ一つ存在する真の解よりも必ず小さくなるので、max を取れば真の解を取り出すことが出来ます。
Problem 10: Summation of primes
10問目：2000000 未満の素数の合計を求める問題です。
2000000 を標準入力に与えます。
私の解答は以下です。
n=int(input())
r=range
s={*r(2,n)}
for p in r(2,1500):s-={*r(p*p,n,p)}
print(sum(s))
84 Bytes となりました。
素数を列挙してその合計を計算するので、7問目と同じ素数列挙が使えます。
forループの上端は $\sqrt{n}$ 以上必要で、どうせ 3文字以下にはならないので適当に 1500 としました。
結果
最後に、10問の結果を表にまとめます。
| 問題 | コード長 |
|---|---|
| 1 | 53 Bytes |
| 2 | 65 Bytes |
| 3 | 67 Bytes |
| 4 | 82 Bytes |
| 5 | 51 Bytes |
| 6 | 44 Bytes |
| 7 | 94 Bytes |
| 8 | 110 Bytes |
| 9 | 94 Bytes |
| 10 | 84 Bytes |
ここまで一生懸命コードを短くすることだけを頑張ったのは初めてだと思います。
本当に基本的なことしかできていないのですが、わりといい感じにコードゴルフできたかなと思います。
特に、7問目のエラトステネスの篩の実装があんな形になったのはなかなか面白かったです。
実務では一切役に立たないような Python の豆知識とかも知ることが出来ましたし、何かコードゴルフをすることでしか満たされない欲求が満たされたような感じがしています。
みなさんも興味があればコードゴルフをやってみてはいかがでしょうか。
また、さらに短いコードで正解できた方がいればコメントなどで教えてもらえるとうれしいです。
対ありでした
明日は @kdr250 さんの記事です。お楽しみに！