こんにちは。ラクスルで24新卒として内定者インターンをしている新開です。 早速ですがみなさんは競技プログラミングやハッカソンなどのプログラミングコンテストに参加した経験はありますか？
今回はプログラミングコンテストの1種であるコードゴルフという、アルゴリズムをどれだけ短いソースコードで記述できたかを競う競技に取り組みましたので、自分なりに考えたことをお話ししたいと思います。
コードゴルフをするまでの経緯
ラクスルの24新卒エンジニアのメンバー全員が初めてオフィスで顔合わせする懇親会が開催され、 当日は自己紹介や他メンバーとの共通点を探すゲームなどを通して同期の親睦を深める良い機会になりました。
懇親会のプログラムのひとつにコードゴルフがあり、同期を4つのチームに分けて1時間程度かけてコードを短くすることに取り組みました。
どんな問題？
問題は非常にシンプルで以下の文字列（ラクスルのロゴ）を標準出力することです。 表示が崩れている場合があるのでgistで確認することをお勧めします。
###############
#########################
################################
########### ##### ##########
######## ##### #########
####### ##### #######
####### ##### #######
###### ##### #### #######
###### ############ ######
##### ############### ######
##### #################### ######
##### ########### ########### ######
##### ############## ########### #####
###### ######### ##### ######### #####
##### ######### ##### ###### #####
###### ########### ##### ##### #####
##### ############## ##### ##### ######
############## ###### ##### ##### #####
########## ###### ##### ##### #####
######## ###### ##### ###### #####
###### ###### ############## #####
###### ###### ############### #####
##### ###### ####### ######## #####
##### ###### ##### ######## #####
##### ###### #### ######## #####
###### ###### ## ######## #####
##### ###### ######## ######
##### ###### ######### #####
##### ####### ######### #####
##### ######## # ######### ######
##### ################ #### ######## ######
###### ###################### #############
###### ############## ###########
####### ####### ########
###### #######
######## #######
######### ########
########### ##########
###############################
########################
##############
ルール
- 言語はオンラインのコード実行環境で実行可能であること
- 標準ライブラリのみを使用すること
どのような戦略を取るか？
記述言語
まずどの言語で記述するかというところですが、私たちのチームではPython3を選択しました。 理由としては次の2つが挙げられます。
- チームメンバー全員が理解＆記述できる
- 超高級言語である（≒複雑な処理をシンプルに記述できる）
文字列を圧縮しよう！
今回の文字列はと#、改行コードの3種類と少なく、繰り返し箇所が多いです。
この場合にはランレングス圧縮が適切と判断しました。
まずはランレングス圧縮を試してみる
from itertools import groupby def run_length(logo): res = [] for line in logo.splitlines(): compressed = [(key, len(list(group))) for key, group in groupby(line)] res.append(compressed) return res
各行に対して(符号, 繰り返し回数)のタプル型にランレングス圧縮した結果を要素とする配列を作成してみました。
[[(' ', 27), ('#', 15)], [(' ', 22), ('#', 25)], ..(省略)..]
文字列の特徴から符号を省略できる
さらに各行に着目すると、と#のブロックが交互に並んでいて最初にが来るというルールがあります。
つまり(符号, 繰り返し回数)のタプル型で表現されるところを、符号を省略した連続回数のみで表現できるようになります。
繰り返し回数の数値同士を、各行を,で区切ることによりランレングス圧縮した結果を1つの文字列へと可逆に変換できます。
"27 15,22 25, ..(省略).."
数値を一文字で表現する
さらにさらに2桁の数値でも1文字で表現できるようになると、繰り返し回数の数値同士を区切る必要もなくなりさらに圧縮できると考えました。
"RF MP JW ..(省略).." （後ほど解説します）
これを実現するには次の2つの方法が考えられます。
- 10進数とASCIIコードの変換を行う
- pythonではchr関数↔︎ord関数を用いて実現できる
- 10進数の
33から126までの94種類の数値は1文字のASCIIコードで表現できる - 例で先ほど示した最初の27という数値は32を足すと59になるが、10進数の
59はASCIIコードで;と表現できる
>>> n = 27 >>> c = chr(n + 32) # 1~94の範囲の数値を33~126の範囲に並行移動するために32を追加 ';' >>> ord(c)-32 # 9バイトで記述できる 27
- 出現する最大値をNとしてN+1進数に変換する
- pythonではnumpyのbase_repr関数↔︎int関数を用いて実現できる（今回外部ライブラリが使えないというルールだが、提出するソースコードはint関数で復元するので外部ライブラリを使用しないのでセーフ）
- 例として10進数の
27は36進数でRと表現できる
>>> import numpy as np >>> n = 27 >>> c = np.base_repr(n, 36) 'R' >>> int(c,36) # これも9バイトで記述できる 27
ここでは圧縮した文字列を復元するときのコードの短さは同じなのでどちらの手法を取っても構わないと判断しました。
今回は出現する数値が35であることを把握して、後者の「36進数に変換する」手法を取りました。
改行を,ではなくとして表現して（これは次節で用いるsplit関数の引数を省くため）、この手法を取ることで次の文字列まで圧縮することができました。
RF MP JW GB457A E895B9 C7C5E7 A7E5G7 96G514D7 86HCD6 75JFB6 65HKA6 55FB3B96 45DE5B85 36A9357995 35896596B5 265B7585D5 253E7575E6 2E267555H5 2A667535J5 18967526J5 16B67EI5 16B67FH5 25B67728F5 25B67558E5 25B67478C5 26A672A8B5 35A6K896 4596L975 4587M955 5568C1A936 654G24C816 761MED 866EHB 97A7J8 B6Z7 C8U7 E9O8 GBGA JV NO SE
シンプルな復元処理を書こう！
ここでは前節の圧縮したラクスルのロゴを用いてできるだけ短いソースコードで復元して標準出力する方法を模索します。
まずは可読性の高いソースコードで記述する場合は次のようになるかと思います。
compressed_logo = "RF MP JW GB457A E895B9 C7C5E7 A7E5G7 96G514D7 86HCD6 75JFB6 65HKA6 55FB3B96 45DE5B85 36A9357995 35896596B5 265B7585D5 253E7575E6 2E267555H5 2A667535J5 18967526J5 16B67EI5 16B67FH5 25B67728F5 25B67558E5 25B67478C5 26A672A8B5 35A6K896 4596L975 4587M955 5568C1A936 654G24C816 761MED 866EHB 97A7J8 B6Z7 C8U7 E9O8 GBGA JV NO SE" for line in compressed_logo.split(): # 各行に分割 for i,j in zip(line[::2],line[1::2]): print("".join(" "*int(i,36)+"#"*int(j,36)),end="") # 偶数番目は空白、奇数番目は# print()
ここで用いているzip(line[::2],line[1::2])は、文字列lineを奇数番目と偶数番目の要素で分割してと#の組み合わせを生成します。
例えばline="GB457A"のとき、line[::2]="G47"と偶数番目の要素を返し、line[1::2]="B5A"と奇数番目の要素を返します。
そしてzip関数をfor文で用いることで、[('G', 'B'), ('4', '5'), ('7', 'A')]のように2つの文字列を同時に反復処理しています。
さて、この可読性の高いソースコードからどのように短くしたかですが、結論を先に述べるとリスト内包表記を用いました。 リスト内包表記は既存のリストの各要素に対してある処理をシンプルに記述できます。
>>> [i*2 for i in range(5)] # 既存のリストの各要素を2倍にした新たなリストを作成 [0, 2, 4, 6, 8] >>> [print(i*2) for i in range(5)] # 新たなリストの作成を目的とせずにprint文の処理を行うということもできる 0 2 4 6 8 [None, None, None, None, None] # これは標準出力でない
それでは先ほどのソースコードにこのリスト内包表記を用いてみましょう。 まずは2重になっている内側のfor文から取り掛かります。
compressed_logo = "RF MP JW GB457A E895B9 C7C5E7 A7E5G7 96G514D7 86HCD6 75JFB6 65HKA6 55FB3B96 45DE5B85 36A9357995 35896596B5 265B7585D5 253E7575E6 2E267555H5 2A667535J5 18967526J5 16B67EI5 16B67FH5 25B67728F5 25B67558E5 25B67478C5 26A672A8B5 35A6K896 4596L975 4587M955 5568C1A936 654G24C816 761MED 866EHB 97A7J8 B6Z7 C8U7 E9O8 GBGA JV NO SE" for line in compressed_logo.split(): # 各行に分割 [print("".join(" "*int(i,36)+"#"*int(j,36)for i,j in zip(line[::2],line[1::2])))]
さらにもう一つのfor文も同様に行うと、、、
compressed_logo = "RF MP JW GB457A E895B9 C7C5E7 A7E5G7 96G514D7 86HCD6 75JFB6 65HKA6 55FB3B96 45DE5B85 36A9357995 35896596B5 265B7585D5 253E7575E6 2E267555H5 2A667535J5 18967526J5 16B67EI5 16B67FH5 25B67728F5 25B67558E5 25B67478C5 26A672A8B5 35A6K896 4596L975 4587M955 5568C1A936 654G24C816 761MED 866EHB 97A7J8 B6Z7 C8U7 E9O8 GBGA JV NO SE" [print("".join(" "*int(i,36)+"#"*int(j,36)for i,j in zip(line[::2],line[1::2])))for line in compressed_logo.split()]
かなりシンプルになりました！
最後に不要な空白や変数の表現を省き、変数名は1文字で定義するなど、調整を行なって最終的に以下のソースコードで提出を行いました。
[print("".join(" "*int(i,36)+"#"*int(j,36)for i,j in zip(l[::2],l[1::2])))for l in "RF MP JW GB457A E895B9 C7C5E7 A7E5G7 96G514D7 86HCD6 75JFB6 65HKA6 55FB3B96 45DE5B85 36A9357995 35896596B5 265B7585D5 253E7575E6 2E267555H5 2A667535J5 18967526J5 16B67EI5 16B67FH5 25B67728F5 25B67558E5 25B67478C5 26A672A8B5 35A6K896 4596L975 4587M955 5568C1A936 654G24C816 761MED 866EHB 97A7J8 B6Z7 C8U7 E9O8 GBGA JV NO SE".split()]
結果は416バイトでした。 今回作成したプログラムはgistにて共有しています。
最後に
コードゴルフは処理速度や可読性など普段コードを書く際に意識すべきことを度外視した遊びです。 しかし今回取り組んでみて様々な発見があり、いつもとは違う刺激的かつ有意義な時間を送ることができました。
みなさんも一度コードゴルフに取り組んでみてはいかがでしょうか？ここまで読んでいただきありがとうございました。
