Project Euler Problem 68 Solution with Python

Magic 5-gon ring¶

Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.

Example magic 3-gon ring

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?

The solution for this problem is very simple. We will have to iterate through differnt combinations of numbers to find the solution.

To make it simple for you to understand, first lets take the example of 3-gon ring and solve it.

To fill the 3-gon ring we will need a total of 6 numbers. You can do this as follows:

In [1]:

numbers = [1, 2, 3, 4, 5, 6]

Now consider the following empty 3-gon-ring. As per the rule, sum of numbers on each line should be the same.

Empty 3-gon ring

For our convinience we will name each and every circle with letters - a, b, c, d, e, f and it will look as follows:

3 gon ring with letters for each circle

So a + b + c == d + c + e == f + e + b

Now the concept is very simple.

• first we will assign numbers to a, b, c
• Then the number is assigned to d
• Let us assume that line_sol = a + b + c
• Now the value of e = line_sol - c - d
• Value of f = line_sol - e - b

In this way for each and every combination of a, b, c you will get different d, e, f. We will maintain a list of all these combinations as avail_sol so that we can compute the largest value at the end.

In [2]:

# list of all combinations available
avail_sol = []

Now it is easy to imagine having different combinations of a, b, c, d, e, f. It should be noted here that we need only combinations and not permutations. With some iterations we will get the same numbers in a jumbled fashion. To overcome this problem, the question already states the solution - "Working clockwise, and starting from the group of three with the numerically lowest external node", so we will first have to find the numerically external node and then working clockwise arrange the numbers.

To tackle this problem, we will write a function, which will take a, b, c, d, e, f as input and arrange them as per requirement.

In [3]:

def convert_to_num(a, b, c, d, e, f):
    """
        This function will start with the
        numerically lowest external node,
        moving clockwise arrange the numbers
        on the given line.
    """
    big_num = {a:0, d:1, f:2}
    break_num = big_num[min(big_num.keys())]
    nums = [(a, b, c), (d, c, e), (f, e, b)]
    nums = nums[break_num:]+nums[:break_num]
    string = ''
    for num_tup in nums:
        for num in num_tup:
            string += str(num)
    return string

To make sure you understand the above function, we will take the example given in the question. According to the question

• a - 4
• b - 3
• c - 2
• d - 6
• e - 1
• f - 5

So, big_num = {4:0, 6:1, 5:2}

Consider break_num = big_num[min(big_num.keys())]:

big_num.keys() = [4, 6, 5] - only the external nodes

min(big_num.keys()) = 4

big_num[min(big_num.keys())] = 0

nums = [(4, 3, 2), (6, 2, 1), (5, 1, 3)]

nums = nums[0:] + nums[:0] - same as nums in previous step

At the end the value of string will be 432621513. Let us check the same with our function:

In [4]:

convert_to_num(4, 3, 2, 6, 1, 5)

Out[4]:

'432621513'

As we are confident that we can work with a, b, c, d, e, f, we will write a program to generate the required values of magic-gon

In [5]:

# iterate through values of a
for a in numbers:
    # duplicate the numbers list
    # so that we can use it for b
    numbers_b = numbers[:]
    # numbers_b should not have a
    numbers_b.remove(a)
    # iterate through values of b
    for b in numbers_b:
        # duplicate the numbers_b list
        # so that we can use it for c
        numbers_c = numbers_b[:]
        # remove b from numbers_b
        # numbers_c will not have a, b
        numbers_c.remove(b)
        # iterate through values of c
        for c in numbers_c:
            # sum of lines - line_sol
            line_sol = a + b + c
            # duplicate the numbers_c list
            # numbers_d will not have a, b, c
            numbers_d = numbers_c[:]
            numbers_d.remove(c)
            for d in numbers_d:
                # similarly numbers_e
                numbers_e = numbers_d[:]
                numbers_e.remove(d)
                # but according to above image
                # e = line_sol - c - d
                e = line_sol - c - d
                # check if e is in line_e
                # this is to check if the combination
                # of a, b, c will form magic gon
                if e in numbers_e:
                    # create numbers_f
                    numbers_f = numbers_e[:]
                    # numbers_f should only contain
                    # 1 number
                    numbers_f.remove(e)
                    # but according to image
                    # f = line_sol - e - b
                    f = line_sol - e - b
                    # check if f is in numbers_f
                    if f in numbers_f:
                        # convert the combination
                        # using convert_to_num func
                        temp = convert_to_num(a, b, c, d, e, f)
                        avail_sol.append(temp)

In [6]:

print avail_sol

['146362524', '156264345', '164542326', '165354246', '235451613', '165354246', '253631415', '156264345', '164542326', '156264345', '165354246', '146362524', '253631415', '423531612', '432621513', '235451613', '432621513', '146362524', '423531612', '164542326', '423531612', '235451613', '432621513', '253631415']

As you can see, there are a lot of duplicates in the list. This is just because of different arrangements of given numbers.

To find the solution we will have to find the maximum of avail_sol

In [7]:

# solution will be the maximum of all the numbers
sol = max([int(x) for x in avail_sol])
print sol

432621513

Program¶

In [8]:

# http://radiusofcircle.blogspot.com

# time module
import time

# time at the start of program execution
start = time.time()

# numbers from 1-10
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

def convert_to_num(a, b, c, d, e, f, g, h, i, j):
    """
    Function to convert a-j to
    required string based on the criteria
    """
    big_num = {a:0, d:1, f:2, h:3, j:4}
    break_num = big_num[min(big_num.keys())]
    nums = [(a,b,c), (d,c,e), (f,e,g), (h,g,i), (j,i,b)]
    nums = nums[break_num:]+nums[:break_num]
    string = ''
    for num_tup in nums:
        for num in num_tup:
            string += str(num)
    return string

# list to store solutions
avail_sol  = []

# start with all the numbers
for a in numbers:
    numbers_b = numbers[:]
    numbers_b.remove(a)
    # numbers without a
    for b in numbers_b:
        numbers_c = numbers_b[:]
        numbers_c.remove(b)
        # numbers without a, b
        for c in numbers_c:
            line_sum = a+b+c
            numbers_d = numbers_c[:]
            numbers_d.remove(c)
            # numbers without a, b, c
            for d in numbers_d:
                numbers_e = numbers_d[:]
                numbers_e.remove(d)
                e = line_sum - c - d
                # numbers without a, b, c, d
                if e in numbers_e:
                    numbers_f = numbers_e[:]
                    numbers_f.remove(e)
                    # numbers without a, b, c, d, e
                    for f in numbers_f:
                        numbers_g = numbers_f[:]
                        numbers_g.remove(f)
                        g = line_sum - e - f
                        # numbers without a, b, c, d, e, f
                        if g in numbers_g:
                            numbers_h = numbers_g[:]
                            numbers_h.remove(g)
                            # numbers without a, b, c, d, e, f, g
                            for h in numbers_h:
                                numbers_i = numbers_h[:]
                                numbers_i.remove(h)
                                i = line_sum - g - h
                                # check if i is in numbers_i list
                                if i in numbers_i:
                                    j = line_sum - i - b
                                    numbers_j = numbers_i[:]
                                    numbers_j.remove(i)
                                    # numbers without a, b, c, d, e, f, g, h, i
                                    if j in numbers_j:
                                        ctn = convert_to_num(a, b, c, d, e, f, g, h, i, j)
                                        avail_sol.append(ctn)

# solution will be the maximum of all the numbers
sol = max([int(x) if len(x) == 16 else 0 for x in avail_sol])

# print the solution
print "Answer: " , sol

# time at the end
end = time.time()

# total time taken
print "Time taken: " , end - start

Answer:  6531031914842725
Time taken:  0.0471189022064

The program is very much similar to the one which I have explained above. The program is written keeping the following image in mind:

Magic 5 gon ring with alphabets

Rest of the code is almost same, the only change is the following:

sol = max([int(x) if len(x) == 16 else 0 for x in avail_sol])

As mentioned in the question, we only require numbers which are 16 digits in length. To make it simple we will make all the other numbers 0, then find the largest of all the given numbers.

You can download the above program from here: Github Gist

Summary¶

I am writing this solution after a very long time. To find the best suitable solution for this problem, it took some time. But it was worth working. As you have already seen, the solution for this problem is straight forward. If we can imagine the concept of the magic gon ring with alphabets, then you are on the right track. You can solve this problem easily. To be frank, a part of the solution has been given in the question itself.

To conclude, even though this code doesn't follow the pep standards, I am satisfied with its execution time. As you can see the program runs in fraction of a second. I am not sure whether this approach will work for higher order magic gon rings but I am sure that it will atleast work for Magic 6, 7 gon rings.

As always, if you have any doubts please feel free to comment in the comment box below and I will be glad to see your comment.

If you have any better program or suggestions or doubts related to anything drop a message at contact me.

Have a nice day.