Problem #90 concerns pairs of dice that can be rearranged to form all of the 2-digit square numbers. The question reads:
My solution for this problem is very brute force-heavy, so I may come back to this problem to look for a more efficient solution. Here is my solution:
Solution #1: Brute Force Approach
We simply list all 6-element subsets of the 10 digits and check every pair for each 2-digit square number. Most square numbers are simple to check. The ones that contain 9 or 6 are a bit more complex as any time a 6 appears, it can also be a 9 by flipping the cube. Thus, the squares which contain 9 or 6 must be handled separately. After doing this, the number of possible pairs can be counted. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #90
'''
import time
def subset(myList,n):
l = len(myList)
if(l==0):
if(n==0):
return [[]]
return []
if(l<n):
return []
if(l==n):
return [sorted(myList)]
a = myList[0]
total = subset(myList[1:],n)
possible = subset(myList[1:],n-1)
for x in possible:
t = x[:]
t.append(a)
total.append(sorted(t))
return total
def projectEulerProblemNinety():
total = subset(["0","1","2","3","4","5","6","7","8","9"],6)
simpleSquares = ["01","04","25","81"]
complexSquares = ["09","16","36","49","64"]
allFound = []
for a in total:
for b in total:
if(a!=b):
possible = True
for x in simpleSquares:
if not ((x[0] in a and x[1] in b) or (x[1] in a and x[0] in b)):
possible = False
break
for y in complexSquares:
for c in y:
if c!="6" and c!="9":
letter = c
break
if not ((letter in a and ("6" in b or "9" in b)) or (letter in b and ("6" in a or "9" in a))):
possible = False
break
if possible:
myPair = sorted([a,b])
if myPair not in allFound:
allFound.append(myPair)
return len(allFound)
start = time.time()
print projectEulerProblemNinety()
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
1217
--- 0.110777139664 seconds ---
for given problem.
'''
And with that, we’re done. That may have been a brute force solution, but it still only took just over a tenth of a second to run.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 