QuizKnock's video posted the other day [University of Tokyo] Challenge the Google entrance exam at the Google headquarters! featured ** Look-and-say Sequence **. This is a sequence that changes according to the rule that the first term is 1 and the numbers read out from the previous term are arranged in the next term, as shown below.
1 =1 is 1(One 1) → 1 1
1 1 =2 1s(Two 1s) → 2 1
2 1 =2 is 1,1 is 1(One 2, One 1) → 1 2 1 1
1 2 1 1 =1 is 1,2 is 1,2 1s...
I first learned about the existence of this sequence in this video and found it interesting. I wrote a program in Python that generates this sequence.
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
If you do as below, Look-and-say Sequence with the first term as 1 will be generated up to the 10th term and output.
>>> 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]
Let us know in the comments if there is a better way!
Recommended Posts