Codility Lesson1 BinaryGap 2進数整数の1と1の間に連続して存在する0の最大長探索

Codilityとは？

Codilityはアルゴリズム系のプログラミングテストを提供しているサイトです。限られた時間内に問題の解答を提出すると、以下の2つの観点でスコアが評価されます。

• 正確性(Correctness)
• 効率性(Performance)

企業が人を採用する際に実力を確認するためのプログラミングテストとしても使われているようです。プログラミングテストの対応言語はメジャーな言語はほぼ対応しています。

https://app.codility.com/programmers/
上記のリンクにLesson問題が公開されていたのでPythonでLesson1をやってみました。

Lesson1 BinaryGap 問題説明

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N. For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps

正の整数Nを２進数表現にし、2つの1で囲まれた連続して並んでいる0の最大長をbinary gapとする。binary gapが複数ある場合は、最大のものの値を返す関数を作成する。

例： N = 529 == 10000010001 戻り値の正解： return 5

解答コード

以下がスコア100%の解答になります。

実行環境

• Python 3.6

binary_gap.py

import time

def solution(N):
    bin_str = bin(N)
    bin_main = bin_str[2:]
    counter, max_gap = 0, 0
    flag = False
    for s in bin_main[::-1]:
        if s == "1":
            if 0 < counter:
                if max_gap < counter:
                    max_gap = counter
            counter = 0
            flag = True
        else:
            if flag:
                counter += 1

    return max_gap

def main():
    print("test1")
    actual1 = solution(9)
    assert actual1 == 2, "actual: {} expected {}".format(actual1, 2)

    print("test2")
    actual2 = solution(529)
    assert actual2 == 4, "actual: {} expected {}".format(actual2, 4)

    print("test3")
    actual3 = solution(20)
    assert actual3 == 1, "actual: {} expected {}".format(actual3, 1)

    print("test4")
    actual4 = solution(15)
    assert actual4 == 0,  "actual: {} expected {}".format(actual4, 0)

    print("test5")
    actual5 = solution(32)
    assert actual5 == 0,  "actual: {} expected {}".format(actual5, 0)

    print("test6")
    actual6 = solution(1041)
    assert actual6 == 5, "actual: {} expected {}".format(actual6, 5)

    print("test7")
    start = time.time()
    actual7 = solution(2147483647)
    print("calculation time: {}".format(time.time() - start))
    assert actual7 == 0, "actual: {} expected {}".format(actual7, 0)


if __name__ == "__main__":
    main()

Out

$ python binary_gap.py
test1
test2
test3
test4
test5
test6
test7
calculation time: 4.0531158447265625e-06

以下のようなスコア結果が表示されます。

Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..2,147,483,647].

上のように効率的なアルゴリズムを書けと問題文にはあったのに、今回の問題ではperformanceは評価されないようです。

Lesson2以降もPythonで挑戦したいですね。