HRBrain Advent Calendar 2022 カレンダー1の12日目の記事です。
1. Code Golfとは
Code Golfという競技をご存知でしょうか。Code Golfとは、あるアルゴリズムをいかに短く書けるかを競うもので、Byte数がスコアになります。できるだけ低いスコアを目指すことから、コード「ゴルフ」と名付けられたそうです。言語によって最短のコード長が異なるので、基本的に言語ごとに順位づけされます。
界隈では割と盛んに行われており、Anarchy GolfやCode Golfなど、専用のコンテストサイトがいくつか存在します。また、競プロでおなじみのAtCoderにも、コード長で最短を目指すゴルファー達がたくさんいます。AtCoderでは他の参加者のソースコードを閲覧できるため、コード長で昇順にソートすれば、プロゴルファーによる短すぎてよくわからないコードが見られます。
2. 本記事について
今回は、Python3におけるCode Golfテクニックを紹介していきたいと思います。Pythonは書き方の自由度が高く、個人的ゴルフ楽しい言語ランキングNo.1です。みなさまのCode Golfへの興味や、Pythonの書き方の新しい発見につながれば幸いです。
3. 基本
3.1 変数名は短く
result="Hello, World"
print(result)
r="Hello, World"
print(r)
また、可能な限り変数は省略しましょう（上の例ではもちろんprint("Hello, World")の方がベター）。
3.2 改行を減らす
一般的なCode Golfでの扱いはわからないのですが、AtCoderでは改行コードは2Byteとして扱われるようです（補助ツールを使うと1Byteにできるらしい？）。それだけでなく、Pythonではインデントでのロスが発生するので、改行は少なくした方がお得です。
if a>0:
print("Positive")
exit()
if a>0:print("Positive");exit()
なお、インデントを入れる際はスペース1つにしましょう。
3.3 空白を除く
数字の直後に文字がくる場合と、記号と何か（文字、数字、記号）が隣接する場合は間の空白を省略可能です。Code Golfをするときはformatterは大敵なので切っておきましょう。
// 数字 + 文字
- 1 if x>0 else 0
+ 1if x>0else 0
// 記号 + 文字 + 記号
- if int(x) in [1,2,3]: r = "Exist"
+ if int(x)in[1,2,3]:r="Exist"
// 記号 + 数字 + 記号
- if -1 > x:
+ if -1>x:
// 記号 + 記号 + 記号
- (x+1) % -y
+ (x+1)%-y
表にまとめると以下のようになります。
| 後 | ||||
| 文字 | 数字 | 記号 | ||
| 前 | 文字 | × | × | ○ |
| 数字 | ○ | なし | ○ | |
| 記号 | ○ | ○ | ○ | |
4. 変数の初期化、代入
4.1 初期化をまとめる
変数の初期化は、できるだけまとめて短くしましょう。
a=0;b=0;c=0
x="X";y="Y";z="Z"
a=b=c=0
x,y,z="XYZ"
何か変数を初期化したとき、ついでに空の配列も欲しいときは、以下のように省略して書けます。
a=0;L=[]
a,*L=0,
4.2 セイウチ演算子（ウォルラス演算子） :=
Python3.8から導入された演算子で、変数に代入しながら使用できます。
s=input()
if len(s)>5:print(s)
if len(s:=input())>5:print(s)
5. 計算
5.1 割り算の商をintに
Python3から、割り算は割り切れるときも自動的にfloatになります。intで欲しいときは//が使えます。
y=int(x/2)
y=x//2
5.2 x + 1, x - 1
x + 1 = -~x, x - 1 = ~-xと書けます。~はビット反転を表し、~x = -x - 1であるからです。一見Byte数は変わりませんが、以下のようにカッコを省くことができます。
y=(x-1)*x*(x+1)//6
y=~-x*x*-~x//6
これは、演算子の優先順位によるもので、-や~は四則演算に比べ優先度が高いため、カッコが要らなくなります。Pythonの演算子の優先順位はこちらを参照してください。さらに嬉しいことに、記号（-, ~）から始まるため、前の空白も省略可能です。記号だらけで最高に読みにくい...
同様にして、x + y + 1はx-~yと書けますね。
5.3 切り上げ、切り捨て
import math;y=math.ceil(x) # 切り上げ
z=int(x) # 切り捨て
y=-(-n//1) # 切り上げ
z=n//1 # 切り捨て
値がfloatになることに注意です。
5.4 数字の書き方
x=0.5;y=10000000
x=.5;y=1e7
6. 標準入力：open(0)
Pythonで標準入力によく使われるのはinput()ですが、改行を含む入力を取るのは面倒です。Code Golfにおいてはopen(0)がよく使われます。open(0)はTextIOWrapper型のiteratorで、標準入力の一行ずつ（改行コード含む）を順に返すので、下のように書くことができます。
標準入力（N, Viは整数値）
N
V1
︙
VN
N=int(input());V=[int(input())for _ in range(N)]
N,*V=map(int,open(0))
また、空白区切りの場合、open(0).read().split()が使用できます。
標準入力（N, Viは整数値）
N
V1 ... VN
N=int(input());V=list(map(int,input().split()))
N,*V=map(int,open(0).read().split())
ローカルで実行する場合、open(0)を使うと標準入力の受け取りが自動で終わらないので、入力の最後にCtrl+Dを押して終わらせる必要があります。
7. 条件分岐
7.1 bool型について
Pythonでは、bool型はint型のサブクラスであり、True = 1, False = 0です。
よって、and, orは次のように書くことができます。
[1] a and b
[2] a*b
[3] a&b
[4] a>0<b
[1] a or b
[2] a+b
[3] a|b
カッコが必要になったりならなかったりするので、どれが良いかはケースバイケースです(>0<)。
7.2 比較演算子
値の大小を比較する演算子（>, >=, <, <=）はつなげて書くことができます。
if 0<x and x<5 and 0<y and y<10:
if 5>x>0<y<10:
また、できるだけ>=, <=は使わず>, <で書きましょう（> , <)。
数値に対するノットイコール（!=）は、-で置き換えられます。
if len(input())!=5:exit("Input 5 chars")
if len(input())-5:exit("Input 5 chars")
7.3 否定演算子
notの代わりに~-が使えます。これは5.2で説明したように~-x = x - 1なので、
~-True = 1 - 1 = 0 = False
~-False = 0 - 1 = -1 = True
となるからです。最初が記号になるので直前の空白も消せます。
if x not in"123":
if~-(x in"123"):
7.4 if-else
if-elseで代入などを行う際には、以下のように短く書けます。
if x>0:r="Yes"
else:r="No"
[1] r="Yes"if x>0else"No"
[2] r=(x>0)*"Yes"or"No"
[3] r=["No","Yes"][x>0]
[4] r="NYoe s"[x>0::2]
[5] r="YNeos"[x<=0::2] (条件反転)
[1]： Pythonの三項演算子の書き方です。
[2]： True(=1)なら、orの前が"Yes"(=True)のため"Yes"が代入され、orの後は評価されません（短絡評価）。False(=0)なら、orの前が0(=False)のため、orの後が代入されます。
[3]： 配列のindexをTrue(=1), False(=0)で選択しています。両方が評価されてしまうことに注意です。
[4]： indexがTrue(=1), False(=0)の文字列を1文字目として、1つ飛ばしに文字をとっています。Falseの際に"No "と末尾に空白が入りますが、AtCoderでは許容されるケースが多いです。
[5]： [4]の条件を反転させたものです。
特に[3], [4], [5]は重要です。
[3]は、配列内に関数なども入れることができます。また、値を複数の範囲で条件分けするような場合に下のような書き方ができます。
if 175<h:s="L"
elif 165<h:s="M"
else:s="S"
print(s)
print("SML"[(165<h)+(175<h)])
[4], [5]は、文字列の場合しか使えませんが、こちらも選択肢が複数あるときに威力を発揮します。
if x>0:r="posi"
elif x<0:r="nega"
else:r="zero"
print(r)
print("nzpeeogrsaoi"[(x>0)-(x<0)+1::3])
8. 反復
8.1 一重ループ
forでindexが必要ない場合（単純にn回繰り返したい場合）次のように書けます。
for i in range(n):x-=x/2-1/x
[1] for _ in[0]*n:x-=x/2-1/x
[2] exec("x-=x/2-1/x;"*n)
indexが必要な場合で、rangeの引数が4以下の場合には、以下のように書いた方が短いです（あまり見かけることはありませんが）。
for i in range(4):print(i)
for i in 0,1,2,3:print(i)
8.2 二重ループ
二重ループは、商と余りを使うことで一重ループ化して次のように書けます。
for i in range(h):
for j in range(w):print(S[i][j])
for k in range(h*w):print(S[k//w][k%w])
9. iterable
9.1 set, list, tupleに変換
iterableなオブジェクト（listや文字列、rangeなど）は、以下のようにしてset, list, tupleに変換できます。
set(I) # set
list(I) # list
tuple(I) # tuple
{*I} # set
[*I] # list
(*I,) # tuple
list, tupleに変換した後代入する場合は、さらに短く書けます。
L=list(I) # list
T=tuple(I) # tuple
*L,=I # list
T=*I, # tuple
ところどころにあるカンマによりtuple化されています。
9.2 listのappend, extend, insert
L.append(a)
L.extend(a)
L.insert(i,a)
L+=a, # append
L+=a # extend
L[i:i]=a, # insert
10. 出力
10.1 空白区切り
listをunpackしてprintに渡すことで、空白区切りの出力が得られます。
for x in L:print(x,end=' ')
print(*L)
10.2 改行区切り
mapでprintを各要素に作用させることで改行区切りの出力ができます。
for x in L:print(x)
[1] print(*L,sep='\n')
[2] *_=map(print,A)
[3] [*map(print,A)]
10.3 改行しないprint
print()でend=""とすることで改行されなくなりますが、このendに直接出力する内容を指定した方が短くなります。
print("I love Code Golf",end="")
print(end="I love Code Golf")
10.4 int→stringに変換
いろんな方法がありますが、%演算子を使うと最初が記号になり直前の空白を消せるため、最短になる場合が多いです。
str(x)
f"{x}"
"%d"%x
11. おわりに
最後まで読んでいただきありがとうございました。こんな書き方はプロダクトコードを書く上で全く参考にならないですが、少しでもCode Golfをおもしろいと思っていただけたら嬉しいです！自分自身、このようにまとめていく中でいろんな発見があり、とても勉強になりました。ここには書いていないけれども他にすごい書き方がありましたらぜひ教えてください！