Project Euler 90

题目

Cube digit pairs

Each of the six faces on a cube has a different digit ($0$ to $9$) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of $2$-digit numbers.
For example, the square number $64$ could be formed:

In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: $01, 04, 09, 16, 25, 36, 49, 64$, and $81$.

For example, one way this can be achieved is by placing ${0, 5, 6, 7, 8, 9}$ on one cube and ${1, 2, 3, 4, 8, 9}$ on the other cube.

However, for this problem we shall allow the $6$ or $9$ to be turned upside-down so that an arrangement like ${0, 5, 6, 7, 8, 9}$ and ${1, 2, 3, 4, 6, 7}$ allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain $09$.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

${1, 2, 3, 4, 5, 6}$ is equivalent to ${3, 6, 4, 1, 2, 5}$
${1, 2, 3, 4, 5, 6}$ is distinct from ${1, 2, 3, 4, 5, 9}$

But because we are allowing $6$ and $9$ to be reversed, the two distinct sets in the last example both represent the extended set ${1, 2, 3, 4, 5, 6, 9}$ for the purpose of forming $2$-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

解决方案

每个盒子一共有$\dbinom{10}{6}=210$种情况可以填数。两个盒子一起则有$\dfrac{210\times(210+1)}{2}=22155$种。

此处使用itertools库的combinations产生所有组合。

枚举所有的组合，然后判断平方数中的两个位是否分别在两个集合中。

代码

from itertools import combinations

x, y = [0, 0, 0, 1, 2, 3, 4, 6, 8], [1, 4, 9, 6, 5, 6, 9, 4, 1]
ls = []
for s in combinations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 6):
    st = set(s)
    if 6 in st or 9 in st:
        st.add(6)
        st.add(9)
    ls.append(st)

ans = 0
for i in range(len(ls)):
    for j in range(i, len(ls)):
        sa, sb = ls[i], ls[j]
        ok = True
        for k in range(9):
            if not (x[k] in sa and y[k] in sb or x[k] in sb and y[k] in sa):
                ok = False
                break
        ans += ok
print(ans)