Problem #68 concerns magic 5-gon rings that are very similar to magic squares. The question reads:
This is yet another problem that I dreaded solving for years because I thought it would be a pain to implement. Luckily, it’s not too bad with a little brute force. Here’s my solution:
Solution #1: Brute Force Approach
We do casework on the numbers in the outer circles. We know that if 10 is in one of the inner circles, it will appear twice in the string, and thus the string will have 1*2*2+4*1*2+5 = 17 digits. Thus, 10 must appear in one of the outer circles. Therefore, it suffices to check all (9 choose 4) = 126 subsets of the 9 digits to fill the other four outer circles. In addition, we can notice that if the sum of the numbers in the outer circles is t, then the sum of the five rows is t+2*(55-t) = 110-t. Because the sum of the five rows is five times the magic sum, we must have that t is a multiple of 5. From here, it suffices to check all 5! permutations of the 5 remaining digits for each acceptable subset and through brute force, the maximum 16-digit string can be found. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #68
'''
import time
def subset(myList,n):
if(n == 0):
return [[]]
l = len(myList)
if(n>l):
return []
a = myList[0]
b = subset(myList[1:],n)
c = subset(myList[1:],n-1)
for x in c:
t = x[:]
t.append(a)
t = sorted(t)
b.append(t)
return b
def complement(a,b):
c = []
for x in a:
if x not in b:
c.append(x)
return c
def permutations(myList):
l = len(myList)
if(l==1):
return [myList]
a = myList[0]
b = permutations(myList[1:])
total = []
for x in b:
for z in range(l):
t = x[0:z]
t.append(a)
t.extend(x[z:])
total.append(t)
return total
def projectEulerProblemSixtyEight():
maxFound = -1
digits = [1,2,3,4,5,6,7,8,9]
arrangements = subset(digits,4)
for x in arrangements:
t = 0
for y in x:
t+=y
if(t%5==0):
theSum = (100-t)/5
a = sorted(x)
c = complement(digits,x)
d = permutations(c)
e = a
e.append(10)
for w in d:
v = []
for z in range(5):
temp = theSum-(w[z]+w[(z+1)%5])
v.append(temp)
v = sorted(v)
possible = True
for f in range(5):
if(v[f]!=e[f]):
possible = False
break
if(possible):
s = ""
s+=str(e[0])
for a in range(5):
if(w[a]+w[(a+1)%5] == theSum - e[0]):
break
s+=str(w[a])+str(w[(a+1)%5])
for b in range(1,5):
temp = theSum-(w[(a+b)%5]+w[(a+b+1)%5])
s+=str(temp)
s+=str(w[(a+b)%5])
s+=str(w[(a+b+1)%5])
if(int(s)>maxFound):
maxFound = int(s)
return str(maxFound)
start = time.time()
print projectEulerProblemSixtyEight()
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
6531031914842725
--- 0.0102789402008 seconds ---
for given puzzle.
'''
And with that, we’re done. Even with the crazy amount of brute force we had to do, the program only took 10 milliseconds to run.
Thanks for reading. See you tomorrow.
The Inner Machinations of Walker 