先日投稿された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]
もっと上手いやり方があったらコメントで教えて下さい!