Project Euler Solution 68: Magic 5-gon ring

Martin Ueding

2023-08-19

Code & Zahlen

Project Euler Problem 68: Magic 5-gon ring needs us to find solution to a number puzzle with a peculiar shape.

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?

Let us first reproduce the triangle example and when that works, apply it to the more complicated pentagon. We require that the maximum solution string found for the triangle is the number given. We can codify that into a test:

def test_triangle_solutions() -> None:
    assert max(triangle_solutions([])) == 432621513

But now we need to do some planning for the implementation. For the numbers inside of the magic structure we need to have some numbering scheme. I propose the following scheme as it will allow to validate the numbers as early as possible:

This allows to write a validation function that checks whether the three lines sum up to the same number. If there are only two lines filled, it will check that and ignore the additional numbers. This is the function:

def triangle_valid(numbers: list[int]) -> bool:
    if len(numbers) > 5:
        first = numbers[0] + numbers[1] + numbers[2]
        second = numbers[3] + numbers[2] + numbers[4]
        third = numbers[5] + numbers[4] + numbers[1]
        return first == second == third
    elif len(numbers) > 4:
        first = numbers[0] + numbers[1] + numbers[2]
        second = numbers[3] + numbers[2] + numbers[4]
        return first == second
    else:
        return True

We can then also directly define a function for the solution string. It uses a function shift_lines that makes sure that the line with the lowest value is first. That will be shown right after.

def triangle_solution_string(coefficients: list[int]) -> int:
    lines = [
        (coefficients[0], coefficients[1], coefficients[2]),
        (coefficients[3], coefficients[2], coefficients[4]),
        (coefficients[5], coefficients[4], coefficients[1]),
    ]
    lines = shift_lines(lines)
    return int("".join(map(str, (number for line in lines for number in line))))

And this is the function that rotates the lines until the one with the minimum start is at the front.

def shift_lines(lines: list[tuple]) -> list[tuple]:
    starts = [line[0] for line in lines]
    min_start = min(starts)
    while lines[0][0] != min_start:
        lines = lines[1:] + lines[:1]
    return lines

We can now use backtracking to just try all valid number combinations. We evaluate the triangle as often as we can and directly abort when solving it becomes impossible. I have used the generators here such that it produces the solutions right away and that I don't have to collect them manually within the function.

def triangle_solutions(coeffcients: list[int]) -> Iterator[list[int]]:
    if triangle_valid(coeffcients):
        if len(coeffcients) == 6:
            yield triangle_solution_string(coeffcients)
    else:
        return
    for number in range(1, 7):
        if number in coeffcients:
            continue
        coeffcients.append(number)
        yield from triangle_solutions(coeffcients)
        coeffcients.pop()

That then fulfils the test! We can move on to the pentagon.

There is one insight that we can directly use. The solution string is supposed to be 16 digits long. This means that the number 10 may only be counted once, it needs to be in one of the external nodes. This also has the nice side effect of removing the rotational symmetry once we put the 10 into the starting number.

I propose this numbering scheme for the pentagon ring such that we can place the 10 into one of the external nodes and go from there.

This allows us to write a validation function:

def pentagon_valid(numbers: list[int]) -> bool:
    if len(numbers) > 9:
        first = numbers[0] + numbers[1] + numbers[2]
        second = numbers[3] + numbers[2] + numbers[4]
        third = numbers[5] + numbers[4] + numbers[6]
        fourth = numbers[7] + numbers[6] + numbers[8]
        fifth = numbers[9] + numbers[8] + numbers[1]
        return first == second == third == fourth == fifth
    elif len(numbers) > 8:
        first = numbers[0] + numbers[1] + numbers[2]
        second = numbers[3] + numbers[2] + numbers[4]
        third = numbers[5] + numbers[4] + numbers[6]
        fourth = numbers[7] + numbers[6] + numbers[8]
        return first == second == third == fourth
    elif len(numbers) > 6:
        first = numbers[0] + numbers[1] + numbers[2]
        second = numbers[3] + numbers[2] + numbers[4]
        third = numbers[5] + numbers[4] + numbers[6]
        return first == second == third
    elif len(numbers) > 4:
        first = numbers[0] + numbers[1] + numbers[2]
        second = numbers[3] + numbers[2] + numbers[4]
        return first == second
    else:
        return True

And then we can have a similar function for the solution string:

def pentagon_solution_string(coefficients: list[int]) -> int:
    lines = [
        (coefficients[0], coefficients[1], coefficients[2]),
        (coefficients[3], coefficients[2], coefficients[4]),
        (coefficients[5], coefficients[4], coefficients[6]),
        (coefficients[7], coefficients[6], coefficients[8]),
        (coefficients[9], coefficients[8], coefficients[1]),
    ]
    lines = shift_lines(lines)
    return int("".join(map(str, (number for line in lines for number in line))))

Finally we use the same backtracking idea just with more numbers:

def pentagon_solutions(coeffcients: list[int]) -> Iterator[list[int]]:
    if pentagon_valid(coeffcients):
        if len(coeffcients) == 10:
            yield pentagon_solution_string(coeffcients)
    else:
        return
    for number in range(1, 10):
        if number in coeffcients:
            continue
        coeffcients.append(number)
        yield from pentagon_solutions(coeffcients)
        coeffcients.pop()

The solution is simple, it is just the maximum solution string for pentagon rings where we have put the 10 into an external node.

def solution() -> int:
    return max(pentagon_solutions([10]))

This produces the solution in 7.0 ms, so that's quite fast enough. Besides the backtracking algorithm there wasn't anything else which we needed.