87 lines
2.6 KiB
Python
87 lines
2.6 KiB
Python
#!/usr/bin/env python3
|
|
|
|
# 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:
|
|
# |6||4|
|
|
#
|
|
# 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?
|
|
|
|
from copy import copy
|
|
from itertools import product
|
|
|
|
from projecteuler import timing
|
|
|
|
|
|
N = 10
|
|
K = 6
|
|
COMBINATIONS = []
|
|
|
|
|
|
def combination(i, k, comb):
|
|
if len(comb) == K:
|
|
COMBINATIONS.append(copy(comb))
|
|
|
|
return
|
|
|
|
for j in range(i, N - k + 1):
|
|
comb.append(j)
|
|
combination(j + 1, k - 1, comb)
|
|
comb.pop()
|
|
|
|
|
|
@timing
|
|
def p090():
|
|
squares = [1, 4, 9, 16, 25, 36, 49, 64, 81]
|
|
combination(0, K, [])
|
|
|
|
for c in COMBINATIONS:
|
|
if 6 in c and 9 not in c:
|
|
c.append(9)
|
|
if 9 in c and 6 not in c:
|
|
c.append(6)
|
|
|
|
count = 0
|
|
|
|
for i, c in enumerate(COMBINATIONS):
|
|
for j in range(i + 1, len(COMBINATIONS)):
|
|
cur_squares = copy(squares)
|
|
|
|
prods = list(product(c, COMBINATIONS[j]))
|
|
prods.extend(list(product(COMBINATIONS[j], c)))
|
|
|
|
for elem in prods:
|
|
val = int(str(elem[0]) + str(elem[1]))
|
|
|
|
if val in cur_squares:
|
|
cur_squares.remove(val)
|
|
|
|
if len(cur_squares) == 0:
|
|
count += 1
|
|
|
|
break
|
|
|
|
print('Project Euler, Problem 90')
|
|
print(f'Answer: {count}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p090()
|