[PROJECT_EULER] 62. Cubic permutations

   문제는 이곳에서 확인할 수 있다.

   문제의 조건에서 순열에 속하는 모든 수는 같은 자리의 수임을 알 수 있다. 따라서 n을 1부터 늘려가면서 세제곱을 구해가면서 자리수가 달라질때 체크하면 된다.

import collections

cubic_nums = collections.defaultdict(list)

digit_len, n = 1, 1
target_perm_len = 5

while True:
    cubic_num = str(n ** 3)
    _len = len(cubic_num)
    
    if _len != digit_len:
        res = [min(v) for v in cubic_nums.values() if len(v) == target_perm_len]
        
        if len(res) > 0:
            print(min(res))
            break
        
        digit_len = _len
        cubic_nums = collections.defaultdict(list)
    
    _key = tuple(sorted(s for s in cubic_num))
    cubic_nums[_key].append(cubic_num)

    n += 1

   답은 127035954683이다.

   포럼에서 정확하게 같은 방식으로 문제를 풀었지만 더 짧은 코드를 보았다. while을 쓰면서 n을 하나씩 누적하는 것보다 itertools를 쓰는 것이 더 좋아보인다.

import collections, itertools

perms = collections.defaultdict(list)
for cube in (b**3 for b in itertools.count()):
   cubes = perms[tuple(sorted(str(cube)))] # list of cubes with the same digits
   cubes.append(cube)
   if len(cubes) == 5:      
      break
#NOTE: I don't check that it has *exactly* five permutations
#      but it worked out for the problem
print cubes[0] # 127035954683 0.45 seconds