Project Euler Problem #105

Problem #105 concerns sets with ordered sums of all of their subsets. The question reads:

Project Euler Problem 105: Special subset sums: testing
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).
For example, {81, 88, 75, 42, 87, 84, 86, 65} is not a special sum set because 65 + 87 + 88 = 75 + 81 + 84, whereas {157, 150, 164, 119, 79, 159, 161, 139, 158} satisfies both rules for all possible subset pair combinations and S(A) = 1286.
Using sets.txt (right click and "Save Link/Target As..."), a 4K text file with one-hundred sets containing seven to twelve elements (the two examples given above are the first two sets in the file), identify all the special sum sets, A1, A2, ..., Ak, and find the value of S(A1) + S(A2) + ... + S(Ak).
NOTE: This problem is related to Problem 103 and Problem 106.

My solution for this problem can most concisely be called brute force. Here’s my solution:

Solution #1: Brute Force Approach

We first eliminate obvious non-special subsets by comparing the largest subset of size n-1 with the smallest subset of size n for each n from 1 to the length of the potential special set. To check that no two subset sums are equal, brute force is used. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Brute Force Approach to Project Euler Problem #105
 '''
 
 import time
 f = open("PE105Sets.txt","r")
 
 if f.mode=="r":
     contents = f.readlines()
     realContents = []
     for x in contents:
         coords = map(int, x.split(","))
         realContents.append(coords)
 else:
     raise ValueError("Cannot read from file")
 
 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 projectEulerProblemOneHundredFive(myList):
     total = 0
     for x in myList:
         if isSpecialSet(x):
             total+=sum(x)
     return total
 
 print isSpecialSet([20,31,38,39,40,42,45])
 
 start = time.time()
 print projectEulerProblemOneHundredFive(realContents)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 73702
 --- 0.487046003342 seconds ---
 
 for input of given list of sets.
 ''' 

And with that, we’re done. Even with the obvious brute force approach, this program ran in well under a second. I may come back to this problem at some point to look for a more efficient means of checking that no two subsets have the same sum.

Thanks for reading! See you tomorrow.

Published by Walker Kroubalkian

My name is Walker Kroubalkian. I really enjoy math, computer science, and hiking.

Leave a comment

Design a site like this with WordPress.com
Get started