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

Arantium Maestum

プログラミング、囲碁、読書の話題

Python Code Snippet - 最大の三連続

時々メモっておきたくなるようなPythonコードを思いつくので備忘録的に「Python Code Snippet」の題で保存していこうと思う。

今回はStackOverflowで一旦質問として提示されて、あまりにも宿題っぽかった上に質問者自身がなんら解決に向けて努力していなかったということでマイナス投票されまくって質問が削除されたといういわくつきの問題。いろいろとPythonの好きな機能を重ねて使えるので個人的に問題自体はすごく好き。

多くの整数が含まれているリストから、もっとも総和が大きい『連続した三つの数字』のはじめの数字のインデックスを返す関数を作成せよ

答えとしては

def max_triplet(input_list):
    shifted_lists = [input_list[i:] for i in xrange(3)]
    triplets = zip(*shifted_lists)
    max_triplet = max(enumerate(triplets), key=lambda x:sum(x[1]))
    return max_triplet[0]

試しにランダムで作成したリストを入れてみると

    >>>> import random
    >>>> random.seed(0)
    >>>> rand_list = [random.randint(1, 100) for _ in xrange(100)]
    >>>> print max_triplet(rand_list)
    16
    >>>> print rand_list[16:19]
    [91, 99, 82]

でそれっぽい。

個人的に気に入っているところは、比較的短いコードの中にlist comprehension、xrangezipkeyパラメータを使ったmaxenumeratelambdaなど好きなPythonの機能が多く入っていること、そのわりに可読性はそれなり(のつもり)な点、そしてマジックナンバーのxrange(3)を変更すれば三連続からn連続に容易にアップデート可能ということである。さらに、これでアルゴ的複雑度はO(n)のはず。

すこし残念なのはyield、generator expressionやitertoolsが入っていないこと。