题目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?

题目：

一个立方体的六个面上每个面都有一个 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 个平方数的话，一共有多少种可行的安排？

jerryxjr1220

(1217, 1217)
[Finished in 0.2s]

1. import itertools
   
2. resultTotal = []
   
3. numbers90 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
   
4. count = 0
   
5. for i in itertools.combinations(numbers90, 6):
   
6.     for j in itertools.combinations(numbers90, 6):
   
7.         if (0 in i and 1 in j) or (1 in i and 0 in j):
   
8.             if (0 in i and 4 in j) or (4 in i and 0 in j):
   
9.                 if (0 in i and (9 in j or 6 in j)) or ((9 in i or 6 in i) and 0 in j):
   
10.                     if (1 in i and (6 in j or 9 in j)) or ((6 in i or 9 in i) and 1 in j):
    
11.                         if (2 in i and 5 in j) or (5 in i and 2 in j):
    
12.                             if (3 in i and (6 in j or 9 in j)) or ((6 in i or 9 in i) and 3 in j):
    
13.                                 if (4 in i and (9 in j or 6 in j)) or ((9 in i and 6 in i) and 4 in j):
    
14.                                     if ((6 in i or 9 in i) and 4 in j) or (4 in i and (6 in j or 9 in j)):
    
15.                                         if (8 in i and 1 in j) or (1 in i and 8 in j):
    
16.                                             if i + j not in resultTotal:
    
17.                                                 result = j + i
    
18.                                                 resultTotal.append(result)
    
19.                                                 count = count +1
    
20. 
    
21. print(count,len(resultTotal))

复制代码

jerryxjr1220

很垃圾的代码，但是很好用，暴力解法，速度也很快

芒果加黄桃

1. # encoding:utf-8
   
2. # 用两个立方体表示平方数的奇怪方式
   
3. from time import time
   
4. from itertools import combinations
   
5. squrenums = [(0, 1), (0, 4), (0, 9), (1, 6), (2, 5), (3, 6), (4, 9), (6, 4), (8, 1)]
   
6. nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
   
7. s_pre, s_beh = set(), set()
   
8. def check(l_i, l_j):
   
9.     l_a, l_b = l_i.copy(), l_j.copy()
   
10.     if 6 in l_a or 9 in l_a:
    
11.         l_a.add(6)
    
12.         l_a.add(9)
    
13.     if 6 in l_b or 9 in l_b:
    
14.         l_b.add(6)
    
15.         l_b.add(9)
    
16.     for each in squrenums:
    
17.         if not ((each[0] in l_a and each[1] in l_b) or (each[0] in l_b and each[1] in l_a)):
    
18.             return False
    
19.     return True
    
20. def euler090(N=10000):
    
21.     count = 0
    
22.     for l_i in combinations(nums, 6):
    
23.         for l_j in combinations(nums, 6):
    
24.             if check(set(l_i), set(l_j)):
    
25.                 t1, t2 = ''.join(sorted(str(x) for x in l_i)), ''.join(sorted(str(x) for x in l_j))
    
26.                 if t1 in s_beh and t2 in s_pre:
    
27.                     continue
    
28.                 count += 1
    
29.                 s_pre.add(t1)
    
30.                 s_beh.add(t2)
    
31.     print(count)
    
32. if __name__ == '__main__':
    
33.     start = time()
    
34.     euler090()
    
35.     print('cost %.6f sec' % (time() - start))

复制代码

1217
cost 0.181000 sec

fc1735

1. from itertools import combinations
   
2. numbers = list(map(lambda x: x ** 2, range(1, 10)))
   
3. pairs = list(map(lambda n: list(map(lambda x: 6 if x == 9 else x, [n // 10, n % 10])), numbers))
   
4. 
   
5. c = list(combinations(list(range(9)) + [6], 6))
   
6. ans = 0
   
7. for i in c:
   
8.   for j in c:
   
9.     for a, b in pairs:
   
10.       if not ((a in i and b in j) or (b in i and a in j)):
    
11.         break
    
12.     else:
    
13.       ans += 1
    
14. 
    
15. print(ans // 2)

复制代码

https://github.com/devinizz/project_euler/blob/master/page02/90.py