Enigmatic Code

Programming Enigma Puzzles

Enigma 1570: Sets of cubes

From New Scientist #2733, 7th November 2009 [link]

1. Find the set of perfect cubes that between them use each of the digits 0 to 9 at least once whose sum is as small as possible. What is the sum of your set of cubes?

2. Find the set of perfect cubes that between them use each of the digits 0 to 9 exactly once whose sum is as small as possible. What is the sum of your set of cubes?

In answering either of these questions you may, if you wish, treat 0 as itself being a cube.

I think the question is expecting you to use non-negative cubes when constructing the sets.

[enigma1570]

Advertisements

One response to “Enigma 1570: Sets of cubes

  1. jimrandell 21 February 2012 at 12:54 pm

    The following Python program solves both parts and runs in 57ms.

    I decided to use classes to wrap the “best” solutions.

    class Part1:
    
      def __init__(self):
        self.best = None
        self.cubes = None
    
      def solve(self, cube, cubes, digits):
        # have we used all the digits?
        if len(digits) == 10:
          s = sum(cubes)
          if self.best is None or s < self.best:
            self.best = s
            self.cubes = cubes
        # what's the next cube?
        c = pow(cube, 3)
        # if it's bigger than the current best we're done
        if self.best is not None and c > self.best: return
        # try for a solution containing this cube
        self.solve(cube+1, cubes + [c], digits.union(list(str(c))))
        # and without it
        self.solve(cube+1, cubes, digits)
    
      def result(self):
        self.solve(0, [], set())
        print("1: sum={sum} cubes={cubes}".format(sum=self.best, cubes=self.cubes))
    
    
    class Part2:
    
      def __init__(self):
        self.best = None
        self.cubes = None
        # generate cubes without repeated digits
        self.l = []
        for i in range(0, 2155):
          c = pow(i, 3)
          s = str(c)
          if len(set(list(s))) == len(s):
            self.l.append(c)
    
      def solve(self, i, cubes, digits):
        # have we used all the digits?
        if len(digits) == 10:
          s = sum(cubes)
          if self.best is None or s < self.best:
            self.best = s
            self.cubes = cubes
        # what's the next cube?
        if not(i < len(self.l)): return
        c = self.l[i]
        # if it's bigger than the current best we're done
        if self.best is not None and c > self.best: return
        # check the digits aren't already used
        d = set(list(str(c)))
        if not(digits.intersection(d)):
          # try for a solution containing this cube
          self.solve(i+1, cubes + [c], digits.union(d))
        # and without it
        self.solve(i+1, cubes, digits)
    
      def result(self):
        self.solve(0, [], set())
        print("2: sum={sum} cubes={cubes}".format(sum=self.best, cubes=self.cubes))
    
    
    Part1().result()
    Part2().result()
    

    Solution: The sum for part 1 is 1269. The sum for part 2 is 205452.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: