098. 字谜平方数(Anagramic squares)

将单词CARE中的四个字母依次赋值为1、2、9、6,我们得到一个平方数:\(1296 = 36^2\)。神奇的是,使用同样的数字赋值,重排后的单词RACE也是一个平方数:\(9216 = 96^2\)。我们称CARE和RACE为重排平方单词对,同时规定这样的单词对不允许有前导零或是不同的字母赋相同的值。

在这个16K的文本文件words.txt中包含了将近两千个常见英文单词,找出所有的重排平方单词对(一个回文单词不视为它自己的重排)。求重排平方单词对所给出的最大平方数是多少?

注意:所有的重排单词必须出现在给定的文本文件中。

分析:这道题目似乎没有什么太多的技巧,思路也是相对比较直接的。题目实际上给了我两种变换关系:一种是文本文件中的单词可以构成一些单词对,这些单词对包含完全相同的字母,只是字母的顺序不同,我们需要从文本文件中找到这些单词对;另一种变换关系是平方数之间的变换,把一个平方数的各位数字位置调换后形成的数还是一个平方数,由于不能把不同的字母赋相同的数值,所以构成这些平方数的数字必须是两两相异的。

我的基本思路是这样的:首先对文本文件中的单词进行分析,对所有单词的字母进行排序,如果有些单词对应的字母排序是相同的,说明他们可以构成一个单词对,比如有一个单词对是\((cat,act)\),他们的字母升序排列都是\(['a','c','t']\)。为实现这一点,需要我们创建一个字典,字典的键是各个单词,值为各个单词的字母排序,然后我们需要以这个字典的值为基准,对字典的键进行分类,把对应相同值的键分到同一类,类别的数量必须要大于一,否则就只是一个单词,而不是单词对了。为此,我专门编写了一个函数:

def group_by_value(d):
    res = {}
    for k,v in d.items():
        res[v] = [k] if v not in res.keys() else res[v] + [k]
    res = {k:v for k,v in res.items() if len(v)>1}
    return res

显而易见,一位和两位数中不可能出现平方数对,因此一字词和两字词中也不会有符合条件的单词对,因此我们可以把那些字母数小于等于二的单词去除,减小筛选的范围:

def get_word_pairs():
    with open('data/pe098.txt') as f:
        words = f.read().replace('"',"").split(',')
    d ={x:tuple(sorted(x)) for x in words}
    pairs = {k:v for k,v in group_by_value(d).items() if len(k)>2 and len(v)==2}
    return pairs

在筛选出符合条件的单词对之后,我们可以分析一下这些单词对包含的字母数,这些单词对中字母数最多的是\(['introduce', 'reduction']\)这个单词对,分别包含九个字母,字母数最少的显然包含三个字母,也就是说我们只需要筛选三位数到九位数的平方数就可以了。对这些平方数有一个要求,也就是它们包含的数位必须全不相同,否则就有可能为不同的字母赋上相同的值。在筛选出这些平方数之后,我们也需要按照它们是几位数进行分类:

def get_square_numbers():
    is_all_diff = lambda n: len(set(str(n))) == len(str(n))
    squares = [i**2 for i in range(10,31622) if is_all_diff(i**2)]
    sq_dict = {x:len(str(x)) for x in squares}
    return group_by_value(sq_dict)

最后,我们需要遍历单词对与平方数对,对每个给定的单词对,我们使用不同的平方数对进行实验,把单词对的第一个单词对平方数对的第一个平方数进行赋值,然后按照单词对反映的数位变换关系对平方数对的数位进行变换,然后检查它是否在我们已经筛选出来的平方数集合中。如果在我们就找到一组符合要求的单词对与平方数对,然后我们可以把这些平方数对添加一个列表当中。在遍历完所有的单词对与平方数对后,对这个列表求最大值,得到的即是题目的解:

def main():
    res = []
    squares = get_square_numbers()
    pairs = get_word_pairs()
    for arr in pairs.values():
        dt = len(arr[0])
        for sq in squares[dt]:
            d = {k:v for k,v in zip(arr[0],str(sq))}
            num = int("".join([d[x] for x in arr[1]]))
            if num in squares[dt]:
                res += [sq,num]
    return max(res)

这道题的基本思路并不复杂,但需要考虑很多的边界情况,我也不能完全确定这里的代码覆盖了所有这些边界情况(虽然最终结果是正确的),如果你发现代码中有错误,欢迎指出。

完整代码参见:https://github.com/sorrowise/euler/blob/master/098.py