CodilityのBinaryGapをPythonで解いてみた

こんにちは😄えびならいふです。
今日はプログラミングに関する話題で、CodilityというプログラミングテストのようなもののLessonをPythonで解いてみた。
Lesson自体はたくさんあるんだけど、今日はその中の最初のLesson 1 BinaryGapという問題を解いてみた。 ちなみにCodilityは英語で書かれているので英語が読めないとつらい。。

BinaryGap

BinaryGapは、ある10進数で書かれた自然数が与えられた際にそれを2進数に変換して、1と1の間にある0の数を数えてその最大値を返す問題。
例えば、10進数の32が与えられた場合、それを2進数に変換すると10000010001が得られる。
この時、1と1の間に挟まれている0は00000 (長さ5)と000 (長さ3)になり、長い方の長さである5を返すのが正解となる。
最初の問題だけあってそこまで難しくなさそうな問題ではある。

解いてみる

ということで早速解いてみる。 まずは10進数の数字を2進数に変換する。

binary_val = format(N, "b")

普通に解くとここからfor文で回して0の数を足し算していくような感じになるのだけど、ちょっと変わった解き方をしてみる。
1で挟まれた0を抜き出せば良いので、1の文字で文字列を分割する。

splited_val = binary_val .split("1")

このあとの処理を考えるためにいくつか実例を見てみる。

"10000010001".split("1")
# ['', '00000', '000', '']
"1000001000".split("1")
# ['', '00000', '000']

splitで分割されたリストの0番目は必ず空文字になる。
これは2進数にしたときに一番左が1になるためである。
一方でリストの一番最後は、1で終わる場合と0と終わる場合があり、1で終わると空文字になり、0で終わっている場合は分割されて得られた0の文字列となる。
こうなると少し処理がめんどくさそうに見えるが、問題自体が1と1の間にある0の長さを数えることなので、0で終わっている場合も無視することができる。
popを使ってリストの一番最後を削除する。

splited_val.pop()

ここまで来ると後はfor文を回して文字列の長さを見ていくだけで良い。

max_val = 0
    for s in splited_val:
        n = len(s)
        if max_val < n:
            max_val = n

    return max_val

最初の空文字も少し気になるが、lenを取った時に0になるのでこちらも気にせず処理をしてしまっても問題ない。
スコアはこんな感じになる。

終わりに

今回はCodilityのBinaryGapを解いてみた。
初回とありそんなに難しい問題ではなかったが、少し特殊な解き方をしてみた。
Lesson 2からは難しい問題も増えてくるので少しずつ進めていきたい。