2
2

More than 3 years have passed since last update.

QuizKnockで取り上げられたLook-and-say Sequence (見て言って数列) をPythonで生成する

Last updated at Posted at 2019-11-28

先日投稿されたQuizKnockさんの動画 【東大】Google本社でGoogle入社試験に挑戦! で、 Look-and-say Sequence(見て言って数列) が取り上げられていました。
これは以下のように、初項を1として「前の項を読み上げた数字を並べたものが次の項になる」という規則で変化する数列です。

1   = 1が1個 (One 1)  → 1 1
1 1 = 1が2個 (Two 1s) → 2 1
2 1 = 2が1個,1が1個(One 2, One 1) → 1 2 1 1
1 2 1 1 = 1が1個,2が1個,1が2個...

今回の動画で初めてこの数列の存在を知り、面白いと思ったので
この数列を生成するプログラムをPythonで作成してみました。

def lookAndSay(initialValues, maxIteration=None):
    x = initialValues
    yield x

    iteration = 1

    while True:
        if maxIteration is not None and iteration >= maxIteration:
            break

        new_x = []
        prev = x[0]
        count = 1

        for n in x[1:]:
            if n == prev:
                count += 1
            else:
                new_x.append(count)
                new_x.append(prev)
                prev = n
                count = 1
        new_x.append(count)
        new_x.append(prev)

        x = new_x
        yield x

        iteration += 1

下のようにすると、初項を1としたLook-and-say Sequenceを第10項まで生成し、出力します。

>>> for li in lookAndSay([1], 10):
...     print(li)
...
[1]
[1, 1]
[2, 1]
[1, 2, 1, 1]
[1, 1, 1, 2, 2, 1]
[3, 1, 2, 2, 1, 1]
[1, 3, 1, 1, 2, 2, 2, 1]
[1, 1, 1, 3, 2, 1, 3, 2, 1, 1]
[3, 1, 1, 3, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1]
[1, 3, 2, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 1, 1]

もっと上手いやり方があったらコメントで教えて下さい!

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2