KEEP K.I.S.S.

tk's blog

pythonchallenge 10: what are you looking at?

python挑战的第10题

http://www.pythonchallenge.com/pc/return/bull.html(需要前面某题的钥匙,登录密码对 huge : file)

问题是 a = [1, 11, 21, 1211, 111221, 求 len(a[30]) = ?

数列的规律在于 后面一个元素是对前一个元素的“读法”,就是数数字,比如 "1211" 里是 1个"1"、1个"2"、2个"1",所以“读法”是"111221",这也就是下一个元素了。

其中一个字符串的“读法”关键是对于连续的同一个数字子序列是合并的读法,如果采用正则来匹配的话,就应该是这样的一个模式

pattern = re.compile(r'(\d)\1*')

(\d)用于匹配一个数字,然后成为一个组,\1就是引用这个组,* 默认是贪婪匹配,这样就可以匹配一个连续相同的数字串了。

用这个模式匹配一个字串后,就可以“读”出来,一个长度加上数字本身

# match 是匹配的 match object
s = match.group(0)
assert s
return "{0:d}{1:s}".format(len(s), s[0])

而对于一个完整的由多个不同数字子串构成的序列元素来说,完整“读法”的计算可以使用正则的 sub 方法

# repl function for regexp.sub
def repl(match):
    s = match.group(0)
    assert s
    return "{0:d}{1:s}".format(len(s), s[0])

# read a digit string, otherwise, the next string
def read_digit_str(str):
    # must be a digit string
    assert str.isdigit()

    return pattern.sub(repl, str)

这里的 sub 替换过程使用的是函数,函数将相同数字构成的串替换为对应的“读法”字符串

然后写一个序列生成器

# generators
def sequence():
    s = "1"
    while True:
        yield s
        s = read_digit_str(s)

这样就可以不断的生成序列元素了,如果要计算 a[30] 的长度,可以用内置的 enumerate 函数带索引遍历,完整代码:

# pythonchallenge 10
# http://www.pythonchallenge.com/pc/return/bull.html
#
# sequence: a = [1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211...
#
# puzzle: len(a[30]) = ?

import re
pattern = re.compile(r'(\d)\1*')

# repl function for regexp.sub
def repl(match):
    s = match.group(0)
    assert s
    return "{0:d}{1:s}".format(len(s), s[0])

# read a digit string, otherwise, the next string
def read_digit_str(str):
    # must be a digit string
    assert str.isdigit()

    return pattern.sub(repl, str)

# generators
def sequence():
    s = "1"
    while True:
        yield s
        s = read_digit_str(s)

for index, item in enumerate(sequence()):
    if index == 30:
        print(len(item))
        break

len(a[30]) = 5808