061. 循环的有形数(Cyclical figurate numbers)

三角形数、正方形数、五边形数、六边形数、七边形数和八边形数都是有形数,且分别可以通过以下公式得到:

类型 公式 示例
三角形数 \(P_{3,n}=n(n+1)/2\) \(1,3,6,10,15\)
正方形数 \(P_{4,n}=n^2\) \(1,4,9,16,25\)
五边形数 \(P_{5,n}=n(3n-1)/2\) \(1, 5, 12, 22, 35\)
六边形数 \(P_{6,n}=n(2n-1)\) \(1, 6, 15, 28, 45\)
七边形数 \(P_{7,n}=n(5n-3)/2\) \(1, 7, 18, 34, 55\)
八边形数 \(P_{8,n}=n(3n-2)\) \(1, 8, 21, 40, 65\)

四位数的有序集合{8128, 2882, 8281}有三个有趣的性质:

  1. 这个集合中的元素是循环的,每个元素的后两位数等于后一个元素的前两位数;
  2. 每一类多边形数,如三角形数8128,正方形数8281和五边形数2882都在集合中有一个唯一的代表;
  3. 这是唯一具有上面性质的四位数集合。

找到唯一的拥有六个循环的四位数的有序集合,且这六个不同的数分别对应一个多边形数,求这个六个数的和。

分析:这道题和六十题一样,本质是一个图论的题目,也可以用图论中的算法加以解决。题目要求找到一个由六个有形数构成的集合,这六个数构成一个循环,实际上就是寻找一个六分图中的简单回路,这可以用深度优先搜索算法加以解决。整个过程可以分成以下几步:第一步,求出所有符合条件的六类有形数,即要是四位数,同时后两位数形成的数字应该大于九,否则紧接着它的有形数的前两数就会小于九,无法形成一个四位数。根据这个维基页面存在一个计算有形数的通用公式,因此就不需要用题目中给出的六个公式来分别计算六类有形数了,这可以简化一些代码。这里需要注意的是,我们不仅关心有形数的数值,还关心它的种类以及前两位数和后两位数,所以我们可以用python中内置的namedtuple数据结构把每个有形数打包成一个类,然后用类属性的方式访问它的类别、数值、前两位数和后两位数。

第二步,根据已经计算出来的所有符合条件的有形数(共有302个),遍历这个列表,对其中每个有形数找到每个前两位数和它后两位数相同,且属于不同类型的有形数加入到一个词典中。词典的键是某个有形数,值是所有后继和它类型不同的有形数。熟悉图论的同学可能已经发现,这里我们实际上已经建立一个邻接表用来表示图,而我们这里形成的图显然是一个无权有环的有向图。此外, 我们还可以发现同一类型的数,比如说三角数或者正方形数之间不互相联通,只有不同类型的数才可以联通。因此整个图会形成六个分散的集合,各个集合内的元素互不联通,而只与集合以外的其它集合中的元素联通,这实际上就是图论的多分图,感兴趣的同学可以看这个页面。我们的目标就是在这个六分图中找到一个简单回路,从某个集合中的某个元素出发,最后再回到这个集合。

第三步,在我们已经建立的图中进行深度优先搜索。从图中的任意顶点出发进行搜寻,注意我们要保证每种类型的有形数都只出现一次,因此需要建立一个存储已经访问过的顶点所属类型的列表。如此搜寻下去,只到结果列表中的数达到了六个,且列表中的最后一个数的后两位数和第一个数的前两位数相同,则我们已经找到了想要的六个循环的有形数。计算它们的总和,即为题目所求。这道题只要认识到它和图论有关,并会用深度优先搜索来找到结果,其它的部分都相对比较简单了。代码如下:

# time cost = 92.1 ms ± 1.28 ms

from collections import namedtuple

def poly_numbers(s,n):
    Pn = namedtuple('Pn','s v ftd ltd')
    v = (n**2*(s-2)-n*(s-4))//2
    ftd,ltd = v // 100, v % 100
    pn = Pn(s,v,ftd,ltd)
    return pn

def poly_number_graph():
    arr,graph = [],{}
    for s in range(3,9):
        for n in range(19,141):
            pn = poly_numbers(s,n)
            if 999 < pn.v < 10000 and pn.ltd>9:
                arr.append(pn)
    for pn in arr:
        res = []
        for apn in arr:
            if pn.s != apn.s and pn.ltd == apn.ftd:
                res.append(apn)
        graph[pn] = res
    return graph        

def dfs(graph,types,numbers):
    if len(types) == 6 and numbers[-1].ltd == numbers[0].ftd:
        print(sum([x.v for x in numbers]))
    else:
        for pn in graph.get(numbers[-1],[]):
            if pn.s not in types:
                dfs(graph,types+[pn.s],numbers+[pn])

def main():
    graph = poly_number_graph()
    for pn in graph:
        dfs(graph,[pn.s],[pn])