Project Euler Problem 68 (C++和Python代码实现和解析)***

Problem 68 : Magic 5-gon ring

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?

1. 欧拉项目第68个问题 : 魔法五角环

考虑下面的“魔术”三角环，填充数字1到6，每一行加9。

按顺时针方向工作，从数值最小的外部节点<4，3，2的三组开始，每个解决方案都可以被唯一描述。例如，上述解决方案可以用“集合”来描述：4，3，2；6，2，1；5，1，3。可以用四种不同的总数完成环：9、10、11和12。总共有八种解决方案。

每个角三元组之和	方案集合
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

通过将每组方案的数字连接起来，就可以形成9位数字的字符串；三角环的最大字符串是432621513。

使用数字1到10，根据排列方式，可以形成16位和17位的字符串。“魔法”五角环的最大16位数字符串是多少？

2. 求解分析

这道题明显是一个6个或10个数字或字符的全排列问题，如何做排列，可以参考 Project Euler Problem 24 。但是这道题比简单的排列更复杂一些，因为还多了两个判断条件：第一：每个角的三个数之和要两两相等，第二：外圈的几个数要顺时针，大小要有顺序。

为了更好的理解这道题，我画了下面的草图：

事实上，s1, s2, s3, 和 t1, t2, t3等根据自己的方法确定，但会影响索引值，就是如何从一个排列后的数字字符串或列表中取到对应的值，再去做两项判断，判断通过，再组合成一个完整的方案字符串，最后按要求求最大的字符串。

3. C++ 代码实现

我们定义了一个类 PE0068，类图如下：

C++成员变量和函数设置或定义跟Python一样。

C++11 代码

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>  // next_permutation(), sort()
#include <cassert>    // assert()

using namespace std;

// #define UNIT_TEST

class PE0068
{
private:
    string m_gon_ring_type;
    map<string, int> m_gon_ring_mp;
    map<string, vector<int>> m_S_index_mp; 
    map<string, vector<int>> m_Index_mp;

    void updateGonRingSolutions(vector<int>& digits_vec, 
                                map<int, vector<string>>& gon_ring_solutions_mp);
    bool checkClockwiseWorking(vector<int>& digits_vec);
    int checkSumOfGonRing(vector<int>& digits_vec);

public:
    PE0068();

    string findMaximumSolutionString(string gon_type);
};

PE0068::PE0068()
{
    m_gon_ring_mp["three_gon"] = 6;  // max number is 6 for 3-gon ring
    m_gon_ring_mp["five_gon"]  = 10; // max number is 10 for 5-gon ring

    m_S_index_mp["five_gon"]  = { 3, 5, 7, 9 };
    m_S_index_mp["three_gon"] = { 3, 5 };

    m_Index_mp["five_gon"]  = { 0, 1, 2, 3, 2, 4, 5, 4, 6, 7, 6, 8, 9, 8, 1 };
    m_Index_mp["three_gon"] = { 0, 1, 2, 3, 2, 4, 5, 4, 1 };
}

// check clockwise working
bool PE0068::checkClockwiseWorking(vector<int>& digits_vec)
{
    for (auto index : m_S_index_mp[m_gon_ring_type])
    {
        if (digits_vec[0] > digits_vec[index])
        {
            return false;
        }
    }
    return true;
}

// check each gon sum of three numbers,
// if all are equal, return value of one gon sum, else return 0
int PE0068::checkSumOfGonRing(vector<int>& digits_vec)
{
    int gon_1_sum = 0, one_gon_sum = 0;
    int i = 0;

    for (auto index : m_Index_mp[m_gon_ring_type])
    {
        one_gon_sum += digits_vec[index];
        if ((i + 1) % 3 == 0)
        {
            if (i == 2)
            {
                gon_1_sum = one_gon_sum;
            }
            else
            {
                if (gon_1_sum != one_gon_sum)
                {
                    return 0;
                }
            }
            one_gon_sum = 0;
        }
        i++;
    }
    return gon_1_sum;
}
    
// update gon_ring_solutions_mp according to permutated digits vector
void PE0068::updateGonRingSolutions(vector<int>& digits_vec, 
                                    map<int, vector<string>>& gon_ring_solutions_mp)
{
    int one_gon_sum = 0;

    if (true == checkClockwiseWorking(digits_vec))
    {
        one_gon_sum = checkSumOfGonRing(digits_vec);
        if (one_gon_sum > 0)
        {
            string gon_ring_str = "";
            for (auto i : m_Index_mp[m_gon_ring_type])
            {
                gon_ring_str += to_string(digits_vec[i]);
            }

            vector<string> solutions_vec = gon_ring_solutions_mp[one_gon_sum];
            solutions_vec.push_back(gon_ring_str);
            gon_ring_solutions_mp[one_gon_sum] = solutions_vec;
        }
    }
}

string PE0068::findMaximumSolutionString(string gon_type)
{
    // gon type : 'three_gon' or 'five_gon'
    m_gon_ring_type = gon_type;
    int n = m_gon_ring_mp[gon_type];

    // create digits vector for 3-gon ring or 5-gon ring
    vector<int> digits_vec(n);

    for (int i = 0; i < n; i++)
    {
        digits_vec[i] = i + 1;
    }

    map<int, vector<string>> gon_ring_solutions_mp;

    while (true == next_permutation(digits_vec.begin(), digits_vec.end()))
    {
        updateGonRingSolutions(digits_vec, gon_ring_solutions_mp);
    }

    vector<string> gon_ring_solutions_vec;
    
    map<int, vector<string>>::iterator iter = gon_ring_solutions_mp.begin();
    while (iter != gon_ring_solutions_mp.end())
    {
#ifdef UNIT_TEST
        cout << "each gon sum = " << iter->first << ", solution string = ";
#endif
        for (auto solution_str : iter->second)
        {
            gon_ring_solutions_vec.push_back(solution_str);
#ifdef UNIT_TEST
            cout << solution_str << " ";
#endif
        }
#ifdef UNIT_TEST
        cout << endl;
#endif
        iter++;
    }

    sort(gon_ring_solutions_vec.begin(),gon_ring_solutions_vec.end(),greater<string>());

    for (auto solution_str : gon_ring_solutions_vec)
    {
        if (gon_type == "three_gon")  // 3-gon ring
        {
            return solution_str;
        }
        else                          // 5-gon ring
        {   // find maximum 16-digit string for a "magic" 5-gon ring
            if (16 == solution_str.size())
            {
                return solution_str;
            }
        }
    }

    return "No solution";
}

int main()
{
    PE0068 pe0068;

    assert("432621513" == pe0068.findMaximumSolutionString("three_gon"));

    cout << "The maximum 16-digit string for a \"magic\" 5-gon ring is " <<
            pe0068.findMaximumSolutionString("five_gon") << "." << endl;

    return 0;
}

4. Python 代码实现

为了支持从1到10 一共10个整数做全排列，我重写了函数getNthPermutation()，输入参数dl是列表，在Project Euler Problem 24里的函数next_permutation(s, n) 的输入参数s 是字符串。

为了同时支持3-gon 和5-gon的参数，三个字典变量被初始化：gon_ring_dict， S_index_dict 和 Index_dict。

为了让代码更加紧凑和简洁，我们使用了class MagicGonRing。

Python 代码

import math
 
class MagicGonRing(object):
    def __init__(self):
        """
        define some variables as class data memebers
        """
        self.gon_ring_type = ''
        self.gon_ring_dict = {'three_gon' : 6, 'five_gon' : 10}
        self.S_index_dict  = {'five_gon':[3, 5, 7, 9],'three_gon':[3, 5]}              
        self.Index_dict = {'five_gon':[0, 1, 2, 3, 2, 4, 5, 4, 6, 7, 6, 8, 9, 8, 1],
                           'three_gon':[0, 1, 2, 3, 2, 4, 5, 4, 1]}

    def getNthPermutation(self, n, dl):
        """
        requires function factorial()
        Find the nth permutation of the digits list. Example:
        >>>getNthPermutation(10, [1,2,3,4)
        [2, 4, 1, 3]
        """
        if len(dl) == 1: return dl
        q, r = divmod(n, math.factorial(len(dl)-1))
        return [ dl[q] ] + self.getNthPermutation(r, dl[:q] + dl[q+1:])

    def checkClockwiseWorking(self, dl):    
        """
        check clockwise working
        """
        for index in self.S_index_dict[self.gon_ring_type]:
            if dl[0] > dl[index]:
                return False
        return True

    def checkSumOfGonRing(self, dl):
        """
        check each gon sum of three numbers, 
        if all are equal, return value of one gon sum, else return 0
        """
        gon_1_sum, one_gon_sum = 0, 0

        for i, index in enumerate(self.Index_dict[self.gon_ring_type]):
            one_gon_sum += dl[index]
            if (i+1) % 3 == 0:
                if i == 2:
                    gon_1_sum = one_gon_sum
                else:
                    if gon_1_sum != one_gon_sum: 
                        return 0
                one_gon_sum = 0
        return gon_1_sum

    def updateGonRingSolutionsDict(self, dl, gon_ring_solutions_dict):
        """
        update gon_ring_solutions_dict according to permutated digits list
        """
        if True == self.checkClockwiseWorking(dl):
            one_gon_sum = self.checkSumOfGonRing(dl)
            if one_gon_sum > 0:
                gon_ring_list = []
                for i in self.Index_dict[self.gon_ring_type]:
                    gon_ring_list += [ dl[i] ]
                
                gon_ring_str = ''.join(list(map(str, gon_ring_list)))
                
                if one_gon_sum not in gon_ring_solutions_dict.keys():
                    gon_ring_solutions_dict[one_gon_sum]  = [ gon_ring_str ]
                else:
                    gon_ring_solutions_dict[one_gon_sum] += [ gon_ring_str ]

    def findMaximumString(self, gon_type):
        """
        gon type: 'three_gon' or 'five_gon'
        """
        self.gon_ring_type, n = gon_type, self.gon_ring_dict[gon_type]
        
        # create digits list for 3-gon ring or 5-gon ring
        dl = [ i for i in range(1, n+1) ]   
    
        gon_ring_solutions_dict = {}

        for i in range(math.factorial(n)):
            solution_list = self.getNthPermutation(i, dl)
            self.updateGonRingSolutionsDict(solution_list, gon_ring_solutions_dict)

        #print(gon_ring_solutions_dict)
    
        gon_ring_solutions_list = []
        for gon_sum, solution in gon_ring_solutions_dict.items():
            gon_ring_solutions_list += solution
    
        for solution_str in sorted(gon_ring_solutions_list)[::-1]:
            if gon_type == 'three_gon' :   # 3-gon ring
                return solution_str
            else:                          # 5-gon ring 
                # find maximum 16-digit string for a "magic" 5-gon ring
                if len(solution_str) == 16: return solution_str
        
def main():
    magic_gon_ring = MagicGonRing()
            
    assert '432621513' == magic_gon_ring.findMaximumString('three_gon')

    print("The maximum 16-digit string for a \"magic\" 5-gon ring is %s." %
          magic_gon_ring.findMaximumString('five_gon'))
    
if  __name__ == '__main__':
    main()