# 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]

### 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.