読者です 読者をやめる 読者になる 読者になる

すこしふしぎ.

VR/HI系院生による技術ブログ.まったりいきましょ.(友人ズとブログリレー中.さぼったら焼肉おごらなきゃいけない)

Check iO にハマりそうな話 - sum関数を使わないで総和を求めるいろんな方法

python Check iO

こんばんは.1000chです. ここ数日facebookでバズってるようですが,Check iOというサイトがとても面白いです. 今回はこの紹介をしたいと思います.

そういえば今日は誕生日です. そんな日に締め切りに追われながらブログ書くってのもなかなかオツですね. (なお後半のとんちコーディングが記事のメインです.調子に乗ったら結構長い記事になりましたのでご了承)

Check iO ?

まずはこちらへどうぞ.

Check iO

日本語の紹介だとこちらでしょうか.

このサイトでは,ユーザは冒険者となって様々な島を冒険します. それぞれの島には様々なクエストが用意されており,これをクリアしていくことによりレベルがあがったり,新しい島に行けるようになったりします,

f:id:ism1000ch:20140219012349p:plain

...これだけだと「ただのモンハンじゃん」という感じですね.

このサイトの何がすごいって,クエストの内容でして.すべてプログラミングの問題になっているんです.

f:id:ism1000ch:20140219012509p:plain

問題を選ぶと簡単な茶番ストーリーと共にプログラミングの問題が表示されます. ここで"solve it"を選択すると,IDEっぽい画面に移動し,ブラウザ上でプログラミング,テストが行えます. そしてすべてのテストを通過するとポイントを取得,次の問題へ,というのが基本的な流れです.

f:id:ism1000ch:20140219012615p:plain

自分で解くだけでも面白い問題が多く,とても楽しめるのですが,いったん正解すると見れるようになる他人の解答コードを眺めるのがまた面白いです. 「そんな解き方があるのか!」「こんな関数しらなかった..」「ここは自分だったらこう書くのになぁ」など,自分で解く以上に勉強になります.

現状では言語としてpythonのみ対応しているようですが,これから先いろいろな言語に対応していくとのこと. オンラインでプログラミングを学習する環境が多々登場しているなか,ここまでゲーム要素を大きくしたものはあまり無かったのではないでしょうか.

pythonistaはもちろん,これからpython触ってみようかなぁという人も是非遊んでみてはいかがでしょうか.

こんな問題ありますよ

さて,このCheck iOで僕が面白いなぁとおもった問題をひとつご紹介します. ある意味ネタバレになってしまうので,自分で解くよ!って人はここらでお引き返しください.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

よろしいでしょうか?

ではいきます.

問題

(原文コピペ)

Our new calculator is censored and as such it does not accept some words. You should trick this thing and write a program to calculate the sum of numbers.

Given a list of numbers, you should find the sum of numbers. Your solution should not contain any of the forbidden words (even as a part of another word).

The list of forbidden words:

sum import for while reduce

題意:次の用語を用いること無く,与えられたリストの数字の和を求めよ.使用不可ワード:sum import for while reduce

普段だったらsum(list_of_numbers)で一発のところ,そんなもん使わず書けや!という話ですね.おもしろい!

なら要素を前から順に足していけばいいのかなー...と思うとforもwhileも使えません.

..あれ?

といてみた

一瞬悩みましたが,再帰使えばいいんじゃね?ということで実装したのがこちら.

def checkio(data):
    if len(data) <= 1:
        return data[0]
    else:
        return data[0] + checkio(data[1:])

dataの要素数をチェックしながら,要素が複数含まれていれば1つ目を保持して以降のリストに関して同じ処理を繰り返します. 無事テストを通りました.

ただ,なんかlen(data)の行が気に食わないですね. さらに言うとdata[1:]ってのもなんか気に食わないですね.

てことでこんな感じに書き換えました.

def checkio(data):
    if not data:
        return 0
    else:
        return data.pop() + checkio(data)
        

どうでしょうか?個人的にはちょっとスッキリ感が増したように思います. pythonにおいて,空リストはブール値としてはFalseと判別されること,リストのpopメソッドを用いるとリストの一番後ろの要素を抜き出し&削除することを利用,index指定という煩わしさを軽減しました.

...今気づいたけどわざわざnotつける必要ないですねこれw

まぁいいや.

if分岐以降が1行で収まっているので,コレなら参考演算子的な書き方をするともっと簡略化できるのでは?と思いまた書き換えました.

def checkio(data):
    return data.pop() + checkio(data) if data else 0

おお,かなりスッキリした感じがします.

この辺りまでつくって,「さーて他の人はどんなコード書いてるんだろう^^」と思ってsolutionを見てみました.

ここから,自分のpython力が以下に甘いかを思い知ることになります.

こんな解き方もあるんだって

eval関数がすごい

さて,一番最初に解いた人はどんなコードなのかなー,と見てみます. そして解答を見ると,なんとただこれだけ.

checkio = eval("su"+"m")

.....ん?

なんだこれ?ほんとにこれ解答なのか?

自分がサイトの英語を勘違いしていたのかな?

...などと思ってしまったくらいにシンプル過ぎる解答です. 冷静になるまで本当に意味が分かりませんでしたw

自分のしるeval()関数は,文字列を与えることでそれを式として評価,結果を数値として返すものでした.

このコードをみてもよく意味が分からないので,とりあえずipython上で同じことをしてみます.

すると.

In [1]: eval("su"+"m")
Out[1]: <function sum>

なんとsum関数そのものが返ってきているではありませんか!

ちょっと試してみた感じ,eval関数が受ける文字列は式に限らず,その時点での変数名などでもよいみたいです.

#変数aを宣言
In [2]: a = 1

In [3]: eval("a")
Out[3]: 1 #変数aの中身が取得できた

In [4]: sum
Out[4]: <function sum> #ちなみにsumはsum関数への参照

#未定義変数をevalすると?
In [5]: eval("b")
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-5-79956a6bf797> in <module>()
----> 1 eval("b")

<string> in <module>()

NameError: name 'b' is not defined # そんなもんねぇよ,って怒られた(´・ω・`)

In [6]: b = "hoge" # 改めて変数bを定義

In [7]: eval("b")
Out[7]: 'hoge' # 変数bの中身が取得できた

eval関数ってかんな使い方もできたんですね..

先ほどの解答に戻りましょう, 問題文では「"sum"という(れんぞくした)文字列を利用してはいけない」ということになっていたので,"su"と"m"を結合して"sum"という文字列を生成,evalで評価してsum関数への参照を取得,そしてcheckio変数に格納していたようです.

テストはcheckio関数を通じて行われますが,pythonでは関数も変数に格納できるため,checkio(data)という呼び出しがsum(data)そのものになっているということですね.

いやぁこりゃぁすごい.

map関数をつかう

つづいて同じ方の別解.

def checkio(d):
    r=''.join(map(lambda x:"+"*x+"-"*-x,d)).count
    return r("+")-r("-")

またよくわからん解答ですね...

map関数は第一引数に関数をとり,第二引数にリストをとります. そして,リストの各要素に関して第一引数の関数を適用した帰り値によるリストを返すようです.

実例を見た方が早そうですw

In [12]: import math

In [13]: math.sqrt(4)
Out[13]: 2.0

In [14]: ls = range(5)

In [15]: ls
Out[15]: [0, 1, 2, 3, 4]

In [16]: map(math.sqrt,ls)
Out[16]: [0.0, 1.0, 1.4142135623730951, 1.7320508075688772, 2.0]

与えたリストの各要素にmath.sqrtを適用したリストが取得できていますね.

通常map関数はラムダ式と組み合わせて利用することがおおいようです.

# 各要素を2乗してみる
In [18]: map(lambda x:x*x,ls)
Out[18]: [0, 1, 4, 9, 16]

# リスト内包だとこんな感じでかける
In [19]: [x*x for x in ls]
Out[19]: [0, 1, 4, 9, 16]

リスト内包表記が好きなので普段map関数を利用することが少ないのですが,まぁこんなことができるようですね.

さて,解答に戻りましょう.

r=''.join(map(lambda x:"+"*x+"-"*-x,d)).count

問題はこの行ですね.何をやっているのでしょう.まずjoinの中身,mapがやってることだけ確認しましょう.

In [23]: map(lambda x:"+"*x+"-"*-x,range(4))
Out[23]: ['', '+', '++', '+++']

In [29]: map(lambda x:"+"*x+"-"*-x,[-2,3])
Out[29]: ['--', '+++']

# 文字列 * 数値の挙動
In [30]: "test"*3
Out[30]: 'testtesttest'

In [31]: "test"*-1
Out[31]: ''

ふむ,どうやら与えられた数値のぶん,正の数なら"+"を,負の数なら"-"を生成するようです.

で今度はコレをjoinするわけですか.joinの挙動を見てみましょう.

# joinで数値リストを与える
In [32]: 'masa'.join([1,2,3])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-32-dc57a3b463a8> in <module>()
----> 1 'masa'.join([1,2,3])

TypeError: sequence item 0: expected string, int found

# joinで文字列リストを与える
In [33]: 'masa'.join(["hoge","---","huga"])
Out[33]: 'hogemasa---masahuga'

# map後のリストを与えるとこんな感じ
In [34]: ''.join(["++","---","++++"])
Out[34]: '++---++++'

ふむ.joinはstr型オブジェクトのもつメソッドで,引数に与えられた文字列を順にくっつけていくみたいです. ざんねんながら数値を与えるとエラーになってしまいましたねw ここまでで,与えられたリストぶんの"+"と"-"が結合された文字列が生成されます.

ここからがまたトリッキーです. ここまでの文字列を取得するのであれば

r=''.join(map(lambda x:"+"*x+"-"*-x,d))

だけですむのですが,解答は

r=''.join(map(lambda x:"+"*x+"-"*-x,d)).count

となっています.countだけで止まっているってどういうことになるのでしょう?ためしてみます.

# 一般的なcountの使い方
In [35]: 'masa'.count('a')
Out[35]: 2

# 今回
In [36]: 'masa'.count
Out[36]: <function count>

なんと,'masa'文字列におけるcount関数への参照が取得できています!ということは...

In [37]: f = 'masa'.count

In [38]: f('a') # 'masa'.count('a')と同値
Out[38]: 2

こんなことができてしまうんですね.fに入っているのがただのcount関数オブジェクトではなく,"masa"オブジェクトにおけるcount関数オブジェクトへの参照ということですね.同一文字列に関して複数文字の個数を調べる時には便利...なのかな?

ここでもう一度解答に戻ると,

def checkio(d):
    r=''.join(map(lambda x:"+"*x+"-"*-x,d)).count
    return r("+")-r("-")

とあります.つまり,変数rには"++--++---++"のような文字列に対するcount関数への参照が格納されていることになります. それゆえ次の行で,rが関数として利用できているんですね.

そこまでわかれば後は簡単で,最終行は文字列中の"+"と"-"を数え,その差をreturnしていると.与えられたリストに含まれている数値分の"+"および"-"を含む文字列が生成されているはずなので,これによってリストの数値の総和が求まるのですね.正直総和の問題だということを忘れていましたよ.

いやはや,すごいなぁこれ.

触発されてやってみた1

こんな訳の分からん解答コード見せられたら,再帰で解答した自分が恥ずかしく思えてきます.

というわけで,今回勉強したeval関数を利用してこんな解答を作ってみました.

def checkio(data):
    return eval(str(data)[1:-1].replace(',','+'))

いかがでしょう?ちょこっと解説します.

まず与えられるのは数値型を含むリストと限定されていますので,これを文字列化します. pythonのリストは"["と"]"で挟まれ,要素は","で区切られており,文字列化しても構造そのものが取得できます.こんな感じです.

In [39]: ls = range(5)

In [40]: ls
Out[40]: [0, 1, 2, 3, 4]

In [41]: str(ls)
Out[41]: '[0, 1, 2, 3, 4]'

さてここで,区切り文字のカンマを+記号に変えてevalしてみてはどうだろう?と思いつきました. その際冒頭とラストの大カッコは余計なので,コレを無視する必要があります. pythonの文字列はそのものをリストと同じようにインデックス指定できるので,こんな感じでやってみます.

In [42]: txt = str(ls)

In [43]: txt[1:-1]
Out[43]: '0, 1, 2, 3, 4'

In [44]: txt[1:-1].replace(',','+')
Out[44]: '0+ 1+ 2+ 3+ 4'

見事,要素を+記号でつないだ文字列が取得できました! あとはこれをevalするだけです!

In [45]: eq = txt[1:-1].replace(',','+')

In [46]: eval(eq)
Out[46]: 10

きちんと0,1,2,3,4の和として10が出力されましたね. 負値がリストに含まれていても,きちんと動作するようです. 無事本家Check iOのテストも通すことができました.

触発されてやってみた2

さらにこんなのもいかがでしょう.

def checkio(data):
    num = len(data)
    eq = "%d + " * num
    # eq = "%d + %d + ... %d +"という文字列

    eq = eq[:-2] % tuple(data) # dataの数字を%dに埋めていく
    return eval(eq)

ちょっとコードに冗長感がありますが,これもなかなか面白いのでは?と思います.

ポイントは%を用いて文字列に数字を埋め込んでいるところです. ただラストの"+"を無視する為に[:-2]というのは汚いですね(´・ω・`)

つわけでこんなんもできるかな?

def checkio(data):
    num = len(data)
    eq = "%d " * num
    eq = eq.replace(" ","+",num-1) % tuple(data) 
    return eval(eq)

空白を+記号に置き換えているところがポイントです. %dと空白文字のセットをnum個繰り返しているので,最後に空白があってもevalには影響しないというトリックですw でもやはりreplaceのnum-1は美しくない気がしてしまいます.

rfindみたいにreplaceも右から要素探って置換できればいいんですけどねー. さすがに

eq = "+%d"+num
eq.replace("+","")
eq = eq.[::-1] #文字列におけるreverse的な感じ

ってのは汚いですし...

なーんてやってるといろんなコード案が頭に浮かんできて楽しいです. 際限ないのでこの辺で止めておきましょう.

おわりに

いかがでしたか?今回の例は少々特殊な気もしますが,Check iOにはまだまだ様々な問題が用意されています. 自分でシンプルな答えを作ったあとに,先人のハイパー解答を見ると自分の引き出しが広がった気になれます.

まず自力で,汚くてもいいからゴールにたどり着く.

そして次に,スマートなルート,トリッキーなルートを模索する.

プログラミングという自由度の高いフィールドだからこそ,このような遊びができるのかもしれません. 一つの解答で満足せず,自分の世界を広げてみてはいかがでしょうか. きっと自分の本業にも活かされる時がくると思いますよ.

*sumをつかわない総和,他にもこんなアイディアがあるよ!ってのがあれば是非教えていただきたいです.