General Discussions
Discuss any topics that are not product-specific here.
Euleryx Problem 9 - Special Pythagorean Triplet
My workflow and answer:
Answer: 31875000
Last Weeks Favourite Solution:
@Carolyn realised that, in last weeks problem, we could treat 0s as delimiters. Because a 0 minimises the multiplications, we don’t even need to compute lists containing them. Although this may sound counter intuitive to some, assumptions are also a key part of mathematics. @Carolyn made an educated assumption that other small integers could be treated as delimiters too, drastically reducing the computation required to get to a solution. There were some great replies but this was our favourite solution from last week. If you want to check out this solution, please view it on page one of last weeks post or by clicking here.
Mathematical Theory:
This week we are again going to look into bounds, to help restrict the amount of data we need to process. Whilst it is possible to simply generate 1000 rows each for a, b and c, appending these would lead to 1,000,000,000 rows of data (which is no small value). So lets see what we can do to reduce the volume of data we deal with.
Firstly, we can figure out the maximum value for one of the variables. Lets begin with “a”. We know that our variables are integers and that:
a < b < c therefore a + 1 <= b (as b has to be an integer bigger than a)
Following similar logic:
b < c therefore b + 1 <= c therefore a + 2 <=c
Using the above, it should be evident that the smallest possible value for b, is a + 1, and the smallest possible value of c, is a + 2.
Now, we also know that a + b + c = 1000. If we can use this to find the largest possible value for a, we will have our upper bound. ‘a’ will be at its largest value, when b and c are at their smallest, so lets set them equal to their smallest value. After some simple substitution, we get:
a + (a + 1) + (a + 2) = 1000 which equals 3a + 3 = 1000
After some simple rearrangement, we are left with a = 332.333.. As we were calculating the largest possible value of a, and we know the variables are all integers, we could write a <= 332. We now have a upper bound for a!
The lower bound is a bit trickier but, as proven in some of the solutions last week, an educated assumption can be very valuable. I assumed that all the numbers would be in the triple digits, hence I set the lower bound for a as a > = 100. This means that we only need to generate values for a where the following is true:
100 <= a <= 332
Once we have generated the values for a, we can generate the values for b. The lower bound is simple. As a < b, the lower bound for b, is simply the value for a; the upper bound is a bit more complicated. To begin with, we know that:
a + b + c = 1000 therefore 1000 – a = b + c
Similarly to before, b will be at its greatest when c is at is smallest (Remember a is already calculated/fixed in the previous section. The smallest value for c, is b + 1, so if we substitute this into the above, we get:
1000 – a = b + (b + 1) therefore 1000 – a = 2b + 1 therefore (999-a)/2 = b
So b can be expressed as:
a < b <= (999-a)/2
The final step is to calculate c. Thankfully this is quite easy with the values of a and b already assigned as c = 1000 – a – b. Now that we have all this prepped, we can begin the question.
Method:
1) Generate rows of data, for all the possible values of a, as calculated above. (i.e 100 <= a <= 332).
2) Generate, rows of data, for all the possible values of b, as calculated above. (i.e a < b <= (999-a)/2)
3) Calculate c (1000 - a – b = c)
4) Filter to records with a pythagorian triplet.
5) Find the product of a, b and c
6) Submit your answer to the Project Euler Website!
Summary:
Like last week, this approach doesn’t have a simple formular that just gives you the answer, but considering we limited a potential 1 billion rows down to ~ 40 thousnd, I hope the power of setting bounds can be seen.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
@pilsworth-bulien-com Nice introduction.
While this problem could be solved using Brute Force, an approach that minimizes the increase in the number of records is also useful in business.
In Approach 1, Brute Force was utilized, and the number of records had grown to 62 million rows, resulting in a processing time in 2 seconds.
In Approach 2, conditions were applied to minimize the increase in the number of records, reducing the record count significantly to 82,000 rows and shortening the processing time to 0.4 seconds.
My solution.
[c] is smaller than 500 because:
c < a + b // triangle
c < 1000 - c // a + b + c = 1000
2c < 1000
c < 500
Assuming a < b, the range of b is c/2 < b < c, because;
c < a + b <= (b - 1) + b = 2b - 1
And a must be integer after calculation of;
a = sqrt(c^2 - b^2)
Generate the set of (a, b, c) with the above conditions and filter the set which satisfies;
a + b + c = 1000
Workflow
With a bit of extra math we can arrive at a much smaller search space!
1. a + b + c = 1000
2. a^2 + b^2 = c^2
Using (1), we can square both sides to get
a^2 + b^2 + c^2 + 2 * (ab + bc + ac) = 1000^2
Then apply (2) to simplify
2 * c^2 + 2 * (ab + bc + ac) = 1000^2
=> ab + ac + bc + c^2 = 500 * 1000
=> ab + c * (a + b + c) = 500 * 1000
=> ab + 1000 * c = 500 * 1000
=> ab + 1000 * (1000 - a - b) = 500 * 1000 [apply (1) again]
=> ab - 1000 * a - 1000 * b = -500 * 1000
=> a * (b - 1000) = 1000 * (b - 500)
=> a = 1000 * (500 - b) / (1000 - b)
Voila! We now have an equation for "a" only in terms of "b". Thus,we now have a O(n) search to perform. We know that a < b < 499 (since c < 500) and thus we can solve this problem examining only 207 values for "b"!
Happy Solving! This was certainly a fun one.
I did a variation on the brute force approach.
I knew that a 30-40-50 triangle would be a lot too small and a 300-400-500 would be a bit too big, so I started my Generate Rows [for a and b] at 200 and went up to 550 and hoped for the best, lol.
The final workflow ran in 0.5 seconds, so I'm happy with it
