Project Euler 68: What is the maximum 16-digit string for a “magic” 5-gon ring?

Project Euler 68: What is the maximum 16-digit string for a “magic” 5-gon ring?

Written by on 29 October 2011

Topics: Project Euler

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.

TotalSolution Set
94,2,3; 5,3,1; 6,1,2
94,3,2; 6,2,1; 5,1,3
102,3,5; 4,5,1; 6,1,3
102,5,3; 6,3,1; 4,1,5
111,4,6; 3,6,2; 5,2,4
111,6,4; 5,4,2; 3,2,6
121,5,6; 2,6,4; 3,4,5
121,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.

First part of the solution

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.

Two strings placed

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

Four strings place

Now it is rather easy to place the last digit to get the solution for the puzzle which is

Final solution

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

Data structure

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.

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

  1. Tom Leslie says:

    I think you’ll find that 653,914,842,725,1031 is bigger. I have only inserted commas to show the sequence along each line. This uses the same “lines” as the solution you have found ie 653,1031,914,842,725, but I’m pretty sure you have concatenated in the wrong order.

    (Probably because you assumed that 10>9>8>7, which is true, but won’t give the maximum when concatenated in this order, because 98710 is bigger than 10987!

    BTW I did this by coding my own “pencil-and-paper solution” which is broadly similar to your own. On reflection, I’m not sure this was a good idea because the resulting code is very, very, untidy

    rgds
    Tom

  2. Kristian says:

    You are sort of right, except that the problem states that “Working clockwise, and starting from the group of three with the numerically lowest external node”. So if you have the same configuration (and I believe there is only one solution), you have a unique string which is the solution I proposed.

  3. Tom Leslie says:

    Yeah sorry,

    A short time after my original post I re-read the original question and realised that there wasn’t a free choice in which lines to pick – I’d missed the “working clockwise” condition.

    I really must learn to read the whole problem!

    Apologies
    Tom

  4. Kristian says:

    Hi Tom

    No worries there. It is always good to be challenged on the answers. It means that I have to think through the solution again.

  5. Bildo says:

    While I like the pen and paper solution best, too, I solved it by brute force, but with a bunch of pruning. In particular, I fix the 10 at the zeroth element (since there’s rotational symmetry) and permute the remainder. Runs in 5 ms. Here’s the code:


    namespace ProjectEuler68
    {
    class Magic5gon
    {
    public static string FindLargest16DigitString()
    {
    return Recurse(new int[10] { 10, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, 1, 0).ToString(); // fix 10 at the 0th spot and permute the rest.
    }

    private static long Recurse(int[] ngon, int depth, long largestSoFar)
    {
    if (depth == ngon.Length)
    { // convert ngon to long. Compare against largest and return whichever's bigger
    // find smallest external node, then go clockwise.
    int smallestIndex = 0;
    int smallest = ngon[0];
    if (smallest > ngon[2]) { smallest = ngon[2]; smallestIndex = 2; }
    if (smallest > ngon[4]) { smallest = ngon[4]; smallestIndex = 4; }
    if (smallest > ngon[6]) { smallest = ngon[6]; smallestIndex = 6; }
    if (smallest > ngon[8]) { smallest = ngon[8]; smallestIndex = 8; }

    long n = 0;
    n = SumTriple(n, ngon, 0, 1, 3, smallestIndex);
    n = SumTriple(n, ngon, 2, 3, 5, smallestIndex);
    n = SumTriple(n, ngon, 4, 5, 7, smallestIndex);
    n = SumTriple(n, ngon, 6, 7, 9, smallestIndex);
    n = SumTriple(n, ngon, 8, 9, 1, smallestIndex);

    if (n > largestSoFar)
    return n;
    return largestSoFar;
    }

    for(int i=depth; i<10; ++i)
    {
    Swap(ngon, i, depth); // Sedgewick
    if (IsOkSoFar(ngon, depth)) //
    largestSoFar = Recurse(ngon, depth+1, largestSoFar);
    Swap(ngon, i, depth);
    }
    return largestSoFar;
    }

    private static long SumTriple(long n, int[] ngon, int i, int j, int k, int smallest)
    {
    i = (i + smallest) % 10;
    j = (j + smallest) % 10;
    k = (k + smallest) % 10;

    n *= i == 0 ? 100 : 10; n += ngon[i];
    n *= j == 0 ? 100 : 10; n += ngon[j];
    n *= k == 0 ? 100 : 10; n += ngon[k];
    return n;
    }

    private static bool IsOkSoFar(int[] ngon, int depth)
    {
    switch (depth)
    {
    case 5: return (ngon[0] + ngon[1] + ngon[3] == ngon[2] + ngon[3] + ngon[5]);
    case 7: return (ngon[0] + ngon[1] + ngon[3] == ngon[4] + ngon[5] + ngon[7]);
    case 9: return (ngon[0] + ngon[1] + ngon[3] == ngon[6] + ngon[7] + ngon[9]) &&
    (ngon[0] + ngon[1] + ngon[3] == ngon[8] + ngon[9] + ngon[1]);
    default:
    return true;
    }
    }

    private static void Swap(int[] ngon, int i, int depth)
    {
    int t = ngon[ i ];
    ngon[ i ] = ngon[depth];
    ngon[depth] = t;
    }
    }

    [TestClass]
    public class UnitTest1
    {
    [TestMethod]
    public void TestItAll()
    {
    Assert.AreEqual("6531031914842725", Magic5gon.FindLargest16DigitString());
    }
    }
    }

  6. James Neale says:

    While this is a post from long ago I believe that the logic for the pen and paper solution is flawed. While it does by chance give the right answer the greedy algorithm should try and put the 10 counter clockwise 1 place from the 6.

    As you work through this logic is turns out that we cant put the 10 anywhere except 1 place clockwise from the 6 but that is actually the least desirable place for it so not somewhere we should be placing it from the outset.

  7. Kristian says:

    As a such the pen & paper solution is not a greedy algorithm. It was actually me sitting down and reasoning why it should be like that.

    The reason for placing ten next to the 3, is that we need to the inner numbers of the 10 to sum to 4, and with the number 1-5 that can only be done with the 1 + 3, so after placing 5 and 3, the place for 10 was given.

  8. jeras says:

    For a brute force solution with no pruning of the search space, there are 10! (3,628,800) permutations to try.

    We can reduce the search space by fixing the first outer node as the value 6, since a solution starts with the numerically lowest node and we know that a maximal solution must have values 6 through 10 as the outer nodes. That leaves 9! (362,880) permutations to try.

    We can do better though. Since we deduced that the outer nodes must be 6 through 10 and the inner nodes 1 through 5, that gives only 5! times 5! (14,400) permutations to try.

    But again, if we fix the first outer node as 6, then that leaves only 4! times 5!, or 2880, permutations. That reduces the original search space by over 3 orders of magnitude.

    My python solution brute forces these permutations in 2.5 ms. The implementation is left as an exercise for the reader.

  9. Jean-Marie Hachey says:

    Table 1
    Maximum strings of four “magic” n-gon rings (n = 3, 4, 5, 6)

    http://img4.hostingpics.net/pics/772025pe68tab1ngon.jpg

    ___

    Sources:

    1) PE68, Kristian’s algorithm
    http://www.mathblog.dk/files/euler/Problem68.cs
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

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.