We have now been dealing with continued fractions for a good while, except for the last problem which was solved a good while ago. Problem 68 of Project Euler is completely different. It reads
Consider the following “magic” 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.
Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.
It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.
Total Solution Set 9 4,2,3; 5,3,1; 6,1,2 9 4,3,2; 6,2,1; 5,1,3 10 2,3,5; 4,5,1; 6,1,3 10 2,5,3; 6,3,1; 4,1,5 11 1,4,6; 3,6,2; 5,2,4 11 1,6,4; 5,4,2; 3,2,6 12 1,5,6; 2,6,4; 3,4,5 12 1,6,5; 3,5,4; 2,4,6 By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.
Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a “magic” 5-gon ring?
Well we could try to pursue a brute force approach but we have 10! = 3628800 combinations to check. An approach I will take in the end of this post. However, we can see if we can solve it by hand. So let’s try greedy algorithm using pen & paper.
Pen & paper solution
We want to maximize the number we get, so we want as big a number in the outer ring as possible. Since we have to start with the smallest number in the out ring we can maximize it by putting 6,7,8,9 and 10 in the outer ring. If we do that we get 1-5 in the inner ring.
If we assume that this will lead to a solution we have each number in the inner ring counts twice and thus we get a total sum of 2*(1+2+3+4+5) +6+7+8+9+10 = 70, or in other words each of the 5 strings must sum up to 14.
So lets start with looking at the string with 6. In order to sum up to 14, which means we are missing 8. Using 1-5 we only have one choice 3+5. And in order to maximize the number we have to put them in the order 6-5-3 as shown in the picture below.
Looking at 10 we are missing 4 to sum up to 14, and that means 1+3+10 is the only choice. Since three has already been placed the rest is given and we need to place them as in the picture.
Now we have three strings left that needs to sum up to 14 and that gives us the following options
7 + 2 + 5, 7 + 3 +4
8 + 2 + 4, 8 + 1 + 5
9 + 1 +4 , 9 + 2 + 3
Since three is fully used it removes two of the options. and thus means that we only have one option to fill the string that must start with 7 and 9. Since 5 and 3 are already placed we only have one way to arrange these two strings so we end up with
Now it is rather easy to place the last digit to get the solution for the puzzle which is
Since we could find a solution with 6 in the outer ring and we have placed the numbers to always maximize the solution this is the solution answering the question and the solution will be 6531031914842725. A 16 digit string just as we were asked to produce.
Brute force
When I first sat down to code this problem I found the difficult part to find a fitting data structure to represent the 5gon. I found out the easiest way to do it was an array and just let the numbers correspond to a circle. I chose the following indexes
The choice here is arbitrary, but I needed to keep track of it when checking the solution. Since we are going through all possible permutations I have chosen to only consider solutions where we can start from 0.
From Problem 24 we have an algorithm that goes through all permutations of a given array, so we will reuse that, you can see the algorithm in the source code. The following piece of code will check if it is a valid solution
public bool CheckResult() {
if (p[1] == 10 ||
p[2] == 10 ||
p[4] == 10 ||
p[6] == 10 ||
p[8] == 10) return false;
if (p[0] > p[3] ||
p[0] > p[5] ||
p[0] > p[7] ||
p[0] > p[9] ) return false;
if (p[0] + p[1] + p[2] != p[3] + p[2] + p[4]) return false;
if (p[0] + p[1] + p[2] != p[5] + p[4] + p[6]) return false;
if (p[0] + p[1] + p[2] != p[7] + p[6] + p[8]) return false;
if (p[0] + p[1] + p[2] != p[9] + p[8] + p[1]) return false;
return true;
}
First we check if 10 is in the outer nodes, since otherwise we would end up with a 17 character string. Then we check if node 0 is the smallest one, otherwise it is not a solution. And last we check if the sum is the same for all lines. If this is fulfilled we have a solution to the problem which we can check to see if it is the best solution. The main loop including this check looks like
while (true) {
if (!GetNextPerm()) break;
if (CheckResult()) {
string candidate = "" + p[0] + p[1] + p[2]
+ p[3] + p[2] + p[4]
+ p[5] + p[4] + p[6]
+ p[7] + p[6] + p[8]
+ p[9] + p[8] + p[1];
if (candidate.CompareTo(result) > 0) result = candidate;
}
}
The main problem with this code is the execution time
I get the following
The maximal string is 6531031914842725 Solution took 129 ms
Wrapping up
I presented you with a pen & paper solution as well as a programmed solution. There is no doubt that I like the pen & paper method better. The programmed solution is pure brute force and I am sure we could have used some of the knowledge we derived in the pen & paper solution to limit the search space. However, that was not really my intention with the brute force solution. As always you are welcome to look at the source code.
How did you solve this problem? Did you use a computer, and if so did you brute force it, or did you have some sort of elimination at first? I am very curious about your answer to this problem.
cool!!