5
\$\begingroup\$

The cube, 41063625 (\$345^3\$), can be permuted to produce two other cubes: 56623104 (\$384^3\$) and 66430125 (\$405^3\$). 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.

from collections import Counter
from time import perf_counter


def get_cube_permutations(upper_bound, number_of_permutations):
    """Return minimum cube that has number_of_permutations permutations as cubes."""
    cubes = [str(number ** 3) for number in range(1, upper_bound)]
    sorted_cubes = [''.join(sorted(cube)) for cube in cubes]
    count = Counter()
    for sorted_cube in sorted_cubes:
        count[sorted_cube] += 1
    for sorted_cube, number_of_occurrences in count.items():
        if number_of_occurrences == number_of_permutations:
            return cubes[sorted_cubes.index(sorted_cube)]
    return 0


if __name__ == '__main__':
    START_TIME = perf_counter()
    UPPER_BOUND = 10 ** 4
    TARGET_PERMUTATIONS = 5
    MINIMUM_CUBE = get_cube_permutations(UPPER_BOUND, TARGET_PERMUTATIONS)
    if MINIMUM_CUBE:
        print(f'Minimum cube that has {TARGET_PERMUTATIONS} permutations of its digits as cubes: {MINIMUM_CUBE}.')
    else:
        print(f'No cube found that has {TARGET_PERMUTATIONS} of its digits for numbers within range {UPPER_BOUND}.')
    print(f'Time: {perf_counter() - START_TIME} seconds.')
\$\endgroup\$
3
\$\begingroup\$

Several issues with your code:

  1. You are storing too much data.
  2. Inefficient usage of Counter()
  3. Is Counter() ordered?
  4. You are needing to guess at upper bounds to the solution
  5. Your timing code is flawed.

Storing too much data

You store the cubes of 1 to \$10^4\$:

cubes = [str(number ** 3) for number in range(1, upper_bound)]

This is then used once as input to computing sorted_cubes, and then once to look up the value at a single index.

When you get an index value from sorted.cubes.index(sorted_cube), say 1000, you look up the value of cubes[1000]. The value at that location will be the string representation of the cube of the 1000th value, which by looking at the range() limits, we can conclude is the \$1001^3\$.

So, you could instead:

return (sorted_cubes.index(sorted_cube) + 1) ** 3

Now that we've removed that pesky final lookup, cubes is only used once in the computation of sorted_cubes, so you can eliminate it entirely.

sorted_cubes = [''.join(sorted(str(number ** 3))) for number in range(1, upper_bound)]

Memory usage has been cut in half.

Inefficient usage of Counter()

As mentioned by @Tweakimp in their answer , you're using Counter() poorly:

count = Counter()
for sorted_cube in sorted_cubes:
    count[sorted_cube] += 1

can be written as:

count = Counter(sorted_cubes)

Is Counter() ordered?

Counter is a dict subclass, and as such on Python 3.6+, it maintains insertion order of the keys. But in earlier versions, the contents is unordered.

This means, if two or more sets of cubic permutations of the required size are found, in Python 3.6+, the first cube added to the dictionary will be returned first in count.items(), and the correct sorted_cube will be used. This cannot be relied upon in prior versions of Python.

Guessing at the upper bounds

Where do you need to stop searching for 5 permutations? How about for 13 permutations? How about 20? Where did UPPER_BOUND = 10 ** 4 come from? Did you just keep increasing it until it worked?

You know there is an answer, so why not keep searching until one is found? Start at 1 digit cubes, and look for the required number of permutations. Then try 2 digit cubes, then 3 digit cubes, until an answer is found. The search space for each would be: \$\sqrt[3]{10^{n}} \le x \lt \sqrt[3]{10^{n+1}}\$, where n is the number of digits in the cube.

Your timing code is flawed.

This code:

START_TIME = perf_counter()
MINIMUM_CUBE = ...
print(f"... {MINIMUM_CUBE} ...")
print(f'Time: {perf_counter() - START_TIME} seconds.')

produces different results on my computer depending on whether the cursor is at the top of a blank terminal window, or at the bottom long scroll of previous text. Avoid, as much as possible, including printing in timing results.

START_TIME = perf_counter()
MINIMUM_CUBE = ...
END_TIME = perf_counter()
print(f"... {MINIMUM_CUBE} ...")
print(f'Time: {END_TIME - START_TIME} seconds.')

Better implementation

Python 3.6+ only:

def cubic_permutations(required_permutations):
     min_cube = 1
     third = 1/3

     while True:
         max_cube = min_cube * 10 - 1
         lo = int(min_cube ** third)
         hi = int(max_cube ** third)

         cubes = [ "".join(sorted(str(x**3))) for x in range(lo, hi+1) ]
         count = Counter(cubes)
         digits = next((digits for digits, n in count.items()
                        if n == required_permutations), None)

         if digits:
             root = cubes.index(digits) + lo
             return root ** 3

         min_cube *= 10

This code runs over 5 times faster than @Tweakimp's code for their 13 permutation code. No artificial upper bound is required. Memory usage is further reduced, since smaller subsets (from lo to hi) of cubes and count are in memory at once.

\$\endgroup\$
  • \$\begingroup\$ Nice. In each iteration both lo and hi are calculated, but lo is the hi of the last iterations low. Does this help us improve even more? \$\endgroup\$ – Tweakimp Aug 17 at 20:47
  • \$\begingroup\$ @Tweakimp Yes, that would remove one exponentiation from the loop, so should yield a slight speed improvement. I like the symmetry of the lo and hi calculation, and think it makes it slightly clearer what is going on, so I won't modify my answer to make that micro-improvement. \$\endgroup\$ – AJNeufeld Aug 17 at 22:21
0
\$\begingroup\$

I managed to improve the speed of your code by ~11% with simple changes:

def get_cube_permutations_improved(upper_bound, number_of_permutations):
    """Return minimum cube that has number_of_permutations permutations as cubes."""
    cubes = [number ** 3 for number in range(1, upper_bound)]
    sorted_cubes = ["".join(sorted(str(cube))) for cube in cubes] # create string here
    count = Counter(sorted_cubes) # insert it on Counter object initialization
    for sorted_cube, number_of_occurrences in count.items():
        if number_of_occurrences == number_of_permutations:
            return cubes[sorted_cubes.index(sorted_cube)]
    return 0

My test looks like this:

print("old version")
UPPER_BOUND = 10 ** 6 
TARGET_PERMUTATIONS = 13
# UPPER_BOUND = 10 ** 4
# TARGET_PERMUTATIONS = 5
START_TIME = perf_counter()
MINIMUM_CUBE = get_cube_permutations(UPPER_BOUND, TARGET_PERMUTATIONS)
if MINIMUM_CUBE:
    print(f"Minimum cube that has {TARGET_PERMUTATIONS} permutations of its digits as cubes: {MINIMUM_CUBE}.")
else:
    print(f"No cube found that has {TARGET_PERMUTATIONS} of its digits for numbers within range {UPPER_BOUND}.")
print(f"Time: {perf_counter() - START_TIME} seconds.")
print("improved version")
START_TIME = perf_counter()
MINIMUM_CUBE = get_cube_permutations_improved(UPPER_BOUND, TARGET_PERMUTATIONS)
if MINIMUM_CUBE:
    print(f"Minimum cube that has {TARGET_PERMUTATIONS} permutations of its digits as cubes: {MINIMUM_CUBE}.")
else:
    print(f"No cube found that has {TARGET_PERMUTATIONS} of its digits for numbers within range {UPPER_BOUND}.")
print(f"Time: {perf_counter() - START_TIME} seconds.")

My results for UPPER_BOUND = 10 ** 6 and TARGET_PERMUTATIONS = 13:

old version
Minimum cube that has 13 permutations of its digits as cubes: 1027182645350792.
Time: 2.5825698000000004 seconds.
improved version
Minimum cube that has 13 permutations of its digits as cubes: 1027182645350792.
Time: 2.3012089000000002 seconds.

My results for UPPER_BOUND = 10 ** 4 and TARGET_PERMUTATIONS = 5:

old version
Minimum cube that has 5 permutations of its digits as cubes: 127035954683.
Time: 0.020258699999999998 seconds.
improved version
Minimum cube that has 5 permutations of its digits as cubes: 127035954683.
Time: 0.018043399999999994 seconds.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.