题目90：用两个立方体表示平方数的奇怪方式
Cube digit pairsEach 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?
题目：
一个立方体的六个面上每个面都有一个 0-9 的数字，另一个立方体也如此。将两个立方体用不同的方式挨着放置，我们可以得到不同的两位数。
例如，平方数 64 可以如下表示：
如果仔细选择每个立方体面上的数字，我们可以表示出 100 以下所有的平方数： 01, 04, 09, 16, 25, 36, 49, 64, 和 81。
例如，能够达到这个目的的一种方式在一个立方体上标示 {0, 5, 6, 7, 8, 9}，在另一个上标示 {1, 2, 3, 4, 8, 9}。
但是在这个问题中，我们允许 6 和 9 通过颠倒来互相表示。所以 {0, 5, 6, 7, 8, 9} 和 {1, 2, 3, 4, 6, 7} 就可以表示所有 9 个平方数，否则无法标示 09。
在判断不同的安排时，我们只对每个立方体上的数字感兴趣，而不考虑顺序。
{1, 2, 3, 4, 5, 6} 等价于 {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} 和{1, 2, 3, 4, 5, 9} 则是不同的安排
但是由于我们允许 6 和 9 互相颠倒，所以上面的第二个例子的两个安排都可以表示 {1, 2, 3, 4, 5, 6, 9}。
要表示所有 9 个平方数的话，一共有多少种可行的安排？
(1217, 1217)
import itertools
resultTotal = []
numbers90 =
count = 0
for i in itertools.combinations(numbers90, 6):
for j in itertools.combinations(numbers90, 6):
if (0 in i and 1 in j) or (1 in i and 0 in j):
if (0 in i and 4 in j) or (4 in i and 0 in j):
if (0 in i and (9 in j or 6 in j)) or ((9 in i or 6 in i) and 0 in j):
if (1 in i and (6 in j or 9 in j)) or ((6 in i or 9 in i) and 1 in j):
if (2 in i and 5 in j) or (5 in i and 2 in j):
if (3 in i and (6 in j or 9 in j)) or ((6 in i or 9 in i) and 3 in j):
if (4 in i and (9 in j or 6 in j)) or ((9 in i and 6 in i) and 4 in j):
if ((6 in i or 9 in i) and 4 in j) or (4 in i and (6 in j or 9 in j)):
if (8 in i and 1 in j) or (1 in i and 8 in j):
if i + j not in resultTotal:
result = j + i
resultTotal.append(result)
count = count +1
print(count,len(resultTotal)) 很垃圾的代码，但是很好用，暴力解法，速度也很快{:5_97:} # encoding:utf-8
# 用两个立方体表示平方数的奇怪方式
from time import time
from itertools import combinations
squrenums = [(0, 1), (0, 4), (0, 9), (1, 6), (2, 5), (3, 6), (4, 9), (6, 4), (8, 1)]
nums =
s_pre, s_beh = set(), set()
def check(l_i, l_j):
l_a, l_b = l_i.copy(), l_j.copy()
if 6 in l_a or 9 in l_a:
l_a.add(6)
l_a.add(9)
if 6 in l_b or 9 in l_b:
l_b.add(6)
l_b.add(9)
for each in squrenums:
if not ((each in l_a and each in l_b) or (each in l_b and each in l_a)):
return False
return True
def euler090(N=10000):
count = 0
for l_i in combinations(nums, 6):
for l_j in combinations(nums, 6):
if check(set(l_i), set(l_j)):
t1, t2 = ''.join(sorted(str(x) for x in l_i)), ''.join(sorted(str(x) for x in l_j))
if t1 in s_beh and t2 in s_pre:
continue
count += 1
s_pre.add(t1)
s_beh.add(t2)
print(count)
if __name__ == '__main__':
start = time()
euler090()
print('cost %.6f sec' % (time() - start))
1217
cost 0.181000 sec from itertools import combinations
numbers = list(map(lambda x: x ** 2, range(1, 10)))
pairs = list(map(lambda n: list(map(lambda x: 6 if x == 9 else x, )), numbers))
c = list(combinations(list(range(9)) + , 6))
ans = 0
for i in c:
for j in c:
for a, b in pairs:
if not ((a in i and b in j) or (b in i and a in j)):
break
else:
ans += 1
print(ans // 2)
https://github.com/devinizz/project_euler/blob/master/page02/90.py
页:
[1]