Project Euler 68

题目

Magic $5$-gon ring

Consider the following “magic” $3$-gon ring, filled with the numbers $1$ to $6$, and each line adding to nine.

Working clockwise, and starting from the group of three with the numerically lowest external node ($4,3,2$ in this example), each solution can be described uniquely. For example, the above solution can be described by the set: $4,3,2; 6,2,1; 5,1,3$.

It is possible to complete the ring with four different totals: $9, 10, 11$, and $12$. There are eight solutions in total.

Total	Solution Set
$9$	$4,2,3; 5,3,1; 6,1,2$
$9$	$4,3,2; 6,2,1; 5,1,3$
$10$	$2,3,5; 4,5,1; 6,1,3$
$10$	$2,5,3; 6,3,1; 4,1,5$
$11$	$1,4,6; 3,6,2; 5,2,4$
$11$	$1,6,4; 5,4,2; 3,2,6$
$12$	$1,5,6; 2,6,4; 3,4,5$
$12$	$1,6,5; 3,5,4; 2,4,6$

By concatenating each group it is possible to form $9$-digit strings; the maximum string for a $3$-gon ring is $432621513$.

Using the numbers $1$ to $10$, and depending on arrangements, it is possible to form $16$- and $17$-digit strings. What is the maximum $16$-digit string for a “magic” $5$-gon ring?

解决方案

为每个圈进行编号：

其中，外圈用$0\sim 4$标记，内圈用$5\sim9$来标记。

由于输出的是$16$位数，因此枚举过程中需要排除$10$在内圈的情况。

最终，枚举全排列，一个个进行判断。

代码

from itertools import permutations

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
ans = 0
for a in permutations(a):
    # 外圈最小的在首个，因此确保最小的下标是在0。
    # 输出值只能有16位数，因此10只能在外圈。
    if min(a[0:5]) != a[0] or 10 in a[5:10]:
        continue
    if a[0] + a[6] + a[7] == a[1] + a[7] + a[8] == a[2] + a[8] + a[9] == a[3] + a[9] + a[5] == a[4] + a[5] + a[6]:
        s = [str(x) for x in a]
        t = s[0] + s[6] + s[7] + s[1] + s[7] + s[8] + s[2] + s[8] + s[9] + s[3] + s[9] + s[5] + s[4] + s[5] + s[6]
        ans = max(ans, int(t))
print(ans)