Project Euler 105: Find the sum of the special sum sets in the file.

Project Euler 105: Find the sum of the special sum sets in the file.

Written by on 14 July 2012

Topics: Project Euler

Problem 105 of Project Euler is closely related to Problem 103 as has been mentioned in both problem descriptions. The problem formulation for this problem is

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:

  1. S(B) ≠ S(C); that is, sums of subsets cannot be equal.
  2. 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, a 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).

To be completly honest, I haven’t gotten all that many new insights from solving this problem compared to Problem 103. What we need here is to check if a set of numbers fulfils both properties. In problem 103 we  generated specific functions for checking each of the properties, so I have just reused these functions in order to solve this problem. I did discover a bug in Problem 103 when I solved this, but that has been corrected now, so I did get something from the problem but not much.

The all we need is a bit of wrapping the problem in something that can read the input file and sum up all the sets that fulfils the properties. Personally I think that solving this problem first will make a lot more sense, since it forces you to write functions for checking if a set is valid.

The code for this problem looks as in C#

int result = 0;
int j = 0;
string[] lines = File.ReadAllLines(filename);

foreach (string line in lines) {
    //Parse the line
    string[] segments = line.Split(',');
    int dim = segments.Length;
    int[] numbers = new int[dim];
    for(int i = 0; i < dim; i++){
        numbers[i] = Convert.ToInt32(segments[i]);
    }

    Array.Sort(numbers);
    if (VerifyRule2(numbers)) {
        int[] s = MakeSubsetSums(numbers);
        if (VerifyRule1(s)) {
            result += numbers.Sum();
            j++;
        }
    }
}

this runs in

The sum of valid sss is 73702
Solution took 33,358 ms

You can see the methods either in Problem 103, or in the source code.

Wrapping up

Having already solved problem 103, this problem was close to trivial. However, I think the problem on it’s own is a rather fun one which does require a whole lot of thinking.

You are as always welcome to take a look at the source code, and as always I would love to hear from you about how you solved the problem.

2 Comments For This Post I'd Love to Hear Yours!

  1. Replace

    string[] lines = File.ReadAllLines(filename);
    
    foreach (string line in lines) {
      // ...
    }
    

    with:

    foreach (string line in File.ReadLines(filename)) {
      // ...
    }
    

    See File.ReadLines Method:

    The ReadLines and ReadAllLines methods differ as follows: When you use ReadLines, you can start enumerating the collection of strings before the whole collection is returned; when you use ReadAllLines, you must wait for the whole array of strings be returned before you can access the array. Therefore, when you are working with very large files, ReadLines can be more efficient.

  2. Kristian says:

    Good point, I wasn’t aware of that method when I did the implementation.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.