Project Euler Problem 62 (C++和Python)_project euler 62

Problem 62 : Cubic permutations

The cube, 41063625 (345³), can be permuted to produce two other cubes: 56623104 (384³) and 66430125 (405³). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

C++ 代码 (如果打开编译开关 CPP_11，则要C+11编译器支持)

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <cmath>
#include <map>
#include <algorithm>
#include <cassert>
#include <ctime>
    
using namespace std;

#define CPP_11
//#define UNIT_TEST

typedef struct CubicPermutation
{
    int       number;
    long long cube; // number*number*number = cube
    string    digits;
} CubicPermutation;
    
class PE0062
{
private:
    string getDigitsString(long long number);
    bool checkCubicPermutations(map<string, int>& cubicPermu_mp,
                                vector<CubicPermutation>& cubicPermu,
                                long long& smallest_cube,
                                const int max_permutations);
public:
    long long findSmallestCube(const int max_permutations, 
                               int range_start, int range_end);
};
    
string PE0062::getDigitsString(long long number)
{
#ifndef CPP_11
    vector<int> digit_vec;

    while (number > 0)
    {
        digit_vec.push_back(number % 10);  // 197 => digits: 7, 9, 1
        number /= 10;
    }

    sort(digit_vec.begin(), digit_vec.end());

    vector<int>::iterator iter;
    string digits_str(digit_vec.begin(), digit_vec.end());

    for (unsigned int i = 0; i < digit_vec.size(); i++)
    {
        digits_str[i] = (char)(digit_vec[i] + '0');
    }

#else
    string digits_str = to_string(number);     // C++ 11
    sort(digits_str.begin(), digits_str.end());
#endif

    return digits_str;
}
    
bool PE0062::checkCubicPermutations(map<string, int>& cubicPermu_mp, 
                                    vector<CubicPermutation>& cubicPermu, 
                                    long long& smallest_cube,
                                    const int max_permutations)
{
    map<string, int>::iterator iter;

    for (iter = cubicPermu_mp.begin(); iter != cubicPermu_mp.end(); iter++)
    {
        if (max_permutations == iter->second)
        {
            vector<CubicPermutation>::iterator iter1;
            int number_of_Permutations = 0;
            for (iter1 = cubicPermu.begin(); iter1 != cubicPermu.end(); iter1++)
            {
                if (iter1->digits == iter->first)
                {
                    if (0 == smallest_cube)
                    {
                        smallest_cube = iter1->cube;
                    }
#ifdef UNIT_TEST
                    cout << iter1->cube << " (" << iter1->number << "^3)"<<endl;
#endif
                    number_of_Permutations++;
                    if (max_permutations == number_of_Permutations)
                    {
                        break;
                    }
                }
            }
            return true;
        }
    }
    return false;
}
    
long long PE0062::findSmallestCube(const int max_permutations, 
                                   int range_start, int range_end)
{
    vector<CubicPermutation>cubicPermu;
    map<string, int>cubicPermu_mp;
    CubicPermutation cp;

    for (long long number = range_start; number < range_end; number++)
    {
        cp.number = (int)number;
        cp.cube   = number * number*number;
        cp.digits = getDigitsString(cp.cube);
    
        cubicPermu.push_back(cp);
        cubicPermu_mp[cp.digits]++;
    }

    long long smallest_cube = 0;
    if (true == checkCubicPermutations(cubicPermu_mp, cubicPermu,
                                       smallest_cube, max_permutations))
    {
        return smallest_cube;
    }

    return 0;
}

int main()
{
#ifdef UNIT_TEST
    clock_t start = clock();
#endif

    PE0062 pe0062;

    assert(41063625 == pe0062.findSmallestCube(3, 100, 1000));

    const int max_permutations = 5;
    long long smallest_cube = pe0062.findSmallestCube(max_permutations,
                                                      406, 10000);

    cout << "The smallest cube for which exactly " << max_permutations;
    cout << " permutations of its digits are cube is ";
    cout << smallest_cube << "." << endl;

#ifdef UNIT_TEST
    clock_t finish = clock();
    double duration = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "C/C++ running time: " << duration << " seconds" << endl;
#endif
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

Python 代码

def checkCubicPermutations(cubicPermu_dict, cubicPermu_list, max_permutations):
    smallest_cube = 0
    for key, value in cubicPermu_dict.items():
        if value == max_permutations:
            number_of_Permutations = 0
            for cp in cubicPermu_list:
                if cp[2] == key:
                    if 0 == smallest_cube:
                        smallest_cube = cp[1]
                    print(cp[1], " (%d^3)" % cp[0])
                    number_of_Permutations += 1
                    if max_permutations == number_of_Permutations:
                        break
            return smallest_cube
    return 0
    
def findSmallestCube(max_permutations, range_start, range_end):
    cubicPermu_list = []
    cubicPermu_dict = {}
    for number in range(range_start, range_end):
        cube = number*number*number
        # cube_str = str(cube)
        # str_list = list(cube_str)
        # str_list.sort()
        # digits_str = ''.join(str_list)
        digits_str = ''.join((lambda x:(x.sort(),x)[1])(list(str(cube))))
        cubicPermu_list += [[ number, cube, digits_str ]]
        if digits_str in cubicPermu_dict.keys():
            cubicPermu_dict[digits_str] += 1
        else:
            cubicPermu_dict[digits_str] = 1
    
    smallest_cube = checkCubicPermutations(cubicPermu_dict,\
                                           cubicPermu_list, max_permutations)
    return smallest_cube

def main():
    assert 41063625 == findSmallestCube(3, 100, 1000)
    
    max_permutations = 5
    smallest_cube = findSmallestCube(max_permutations, 406, 10000)

    print("The smallest cube for which exactly %d" % max_permutations,end='')
    print(" permutations of its digits are cube is %d." % smallest_cube)

if  __name__ == '__main__':
    main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47