Problem #103 concerns sets of integers with ordered sums of all possible subsets. The question reads:
Project Euler Problem 103: Special subset sums: optimum Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true: S(B) ≠ S(C); that is, sums of subsets cannot be equal. If B contains more elements than C then S(B) > S(C). If S(A) is minimised for a given n, we shall call it an optimum special sum set. The first five optimum special sum sets are given below. n = 1: {1} n = 2: {1, 2} n = 3: {2, 3, 4} n = 4: {3, 5, 6, 7} n = 5: {6, 9, 11, 12, 13} It seems that for a given optimum set, A = {a1, a2, ... , an}, the next optimum set is of the form B = {b, a1+b, a2+b, ... ,an+b}, where b is the "middle" element on the previous row. By applying this "rule" we would expect the optimum set for n = 6 to be A = {11, 17, 20, 22, 23, 24}, with S(A) = 117. However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for n = 6 is A = {11, 18, 19, 20, 22, 25}, with S(A) = 115 and corresponding set string: 111819202225. Given that A is an optimum special sum set for n = 7, find its set string. NOTE: This problem is related to Problem 105 and Problem 106.
This is possibly the most troll question in all of Project Euler. My solution technically isn’t a complete solution, but luckily it doesn’t need to be. Here’s my solution:
Solution #1: Engineer’s Induction Approach
Contrary to the problem’s advice, we can apply the “rule” another time on the optimal set for n = 6 to get a potential set for n = 7 of {20,31,38,39,40,42,45}. From here, I checked all 7-tuples with each element within 2 of the element for this potential set to find other sets with lower sums. Because no new sums were found, I concluded that the algorithmic set was the correct optimal set. Here’s an implementation of this approach in Python 2.7:
''' Author: Walker Kroubalkian Brute Force Approach to Project Euler Problem #103 ''' import time def testOrder(a): a = sorted(a) first = [] total = 0 for x in a: first.append(total) total+=x first.append(total) back = [] total = 0 for x in a[::-1]: back.append(total) total+=x back.append(total) l = len(a) for x in range(1,l): if first[x+1]<back[x]: return False return True def subset(myList,n): if n==0: return [[]] l = len(myList) if l<n: return [] a = myList[0] b = subset(myList[1:],n) c = subset(myList[1:], n-1) for x in c: x.append(a) b.append(sorted(x)) return b def testNoneEqual(a): l = len(a) allSums = [] for x in range(1,l+1): v = subset(a,x) for y in v: value = sum(y) if value in allSums: return False allSums.append(value) return True def isSpecialSet(myList): if testOrder(myList): if testNoneEqual(myList): return True return False def allPossible(myList,length): if length==0: return [[]] v = allPossible(myList, length-1) total = [] for a in myList: for x in v: t = x[:] t.append(a) total.append(t) return total def projectEulerProblemOneHundredThree(): bestKnown = [20,31,38,39,40,42,45] l = len(bestKnown) potential = True possible = [-2,-1,0,1,2] addition = allPossible(possible, l) final = [] for a in addition: if sum(a)<0: final.append(a) while(potential): potential = False for a in final: t = bestKnown[:] for x in range(l): t[x]+=a[x] if isSpecialSet(t): potential = True bestKnown = t break s = "" for x in bestKnown: s+=str(x) return s start = time.time() print projectEulerProblemOneHundredThree() print ("--- %s seconds ---" % (time.time()-start)) ''' Prints 20313839404245 --- 0.617619991302 seconds --- for input of given problem. '''
And with that, we’re done. I found it pretty funny that they explained the rule and gave one counterexample when the solution involved simply applying the rule once to the counterexample. This problem would probably be considerably more difficult if they hadn’t explained the rule in the problem statement.
Thanks for reading! See you tomorrow.