# Enigmatic Code

Programming Enigma Puzzles

## Enigma 270: Cubic stamp-sheet

From New Scientist #1417, 16th August 1984 [link]

Picnicaria’s independence is to be celebrated by a triumph of technological virtuosity, a Cubic stamp-sheet, which you are asked to design. Let me explain. The “sheet” will look like a cubic die, with a square postage-stamp forming each of the six faces, and with perforations along each of the 12 edges. The whole object of the exercise is to enable the customer to stamp a letter or parcel with a postage of any whole number pence from 1 up to N by tearing along suitable perforations and thus getting a connected set of one or more stamps which add up to exactly the right amount. N is to be made as large as possible.

How large can N be? And what values have the stamps on the various faces?

(The easiest way to specify a layout is to give the values of opposite faces: e.g. a layout like that of an ordinary die is “1/6, 2/5, 3/4”, giving N=21).

[enigma270]

### 7 responses to “Enigma 270: Cubic stamp-sheet”

1. Jim Randell 3 April 2015 at 9:22 am

Of the 63 possible non-empty subsets of the stamps the only non-connected ones are the 3 sets of opposite faces. So that leaves 60 connected subsets. So the maximum possible values for N is 60 (when each subset has a different value).

This Python 3 program works down from stamps with a total value of 60. It runs in 5.9s

```from collections import Counter
from enigma import subsets, diff, irange, Accumulator, printf

# consider values on the cube as (U, D, F, B, L, R)
# we can use all non-empty combinations apart from U+D, F+B, L+R
# so there are 60 possible combinations

sets = diff(subsets((0, 1, 2, 3, 4, 5), min_size=1), [(0, 1), (2, 3), (4, 5)])

# decompose <t> into <n> numbers, starting from <m>
def decompose(t, n, m=1, s=()):
if n == 1:
if not(t < m):
yield s + (t,)
else:
for x in irange(m, t // 2):
yield from decompose(t - x, n - 1, x, s + (x,))

def generate(t):
# decompose the total into the totals for opposite faces
for (t1, t2, t3) in decompose(t, 3, 2):
# decompose each pair
for p1 in decompose(t1, 2, 1):
for p2 in decompose(t2, 2, 1):
# if we haven't used a 1 then use it in the last pair
if 1 not in p1 and 1 not in p2:
yield (p1, p2, (1, t3 - 1))
else:
for p3 in decompose(t3, 2, 1):
yield (p1, p2, p3)

# record max N
r = Accumulator(fn=max)

# consider decreasing totals
for t in irange(60, 6, step=-1):
# generate possible sums for opposite pairs of faces
for (p1, p2, p3) in generate(t):
# compute possible values
vs = p1 + p2 + p3
c = Counter(sum(vs[i] for i in s) for s in sets)
# find smallest value not in c
for i in irange(1, 61):
if i not in c: break
N = i - 1
r.accumulate(N)
if r.value == N: printf("t={t} N={N} [{p1} {p2} {p3}]")

# are we done?
if not(t > r.value): break

printf("max N = {r.value}")
```

Solution: The largest value for N is 53. The four possible cubes are 1/2 + 3/7 + 13/27; 1/6 + 2/4 + 13/27; 1/26 + 2/4 + 6/14; 1/26 + 2/12 + 4/8.

For a total value of stamps t > 60 (actually t ≥ 56) the best we can manage is subsets with values from 1 to 27 using an arrangement of 4/8 + 2/12 + 1/(t-27).

2. Brian Gladman 3 April 2015 at 11:23 am
```from itertools import combinations

# we can combine faces in all combinations of 1, 2, 3, 4, 5 and 6
# faces with the sole exception that we cannot pair opposite faces
#
#            +---------+
#            |         |
#            |    1    |
#            |         |
#   +--------+---------+---------+---------+
#   |        |         |         |         |
#   |   2    |    0    |    3    |    5    |
#   |        |         |         |         |
#   +--------+---------+---------+---------+
#            |         |
#            |    4    |
#            |         |
#            +---------+

# create all allowed combinations of faces
r = range(6)
combs = (
tuple((t,) for t in r) +
tuple(t for t in combinations(r, 2) if sum(t) != 5) +
tuple(t for t in combinations(r, 3)) +
tuple(t for t in combinations(r, 4)) +
tuple(t for t in combinations(r, 5)) +
tuple(t for t in combinations(r, 6))
)

# for storing the maximum N found and the related face values
max_n, max_v = 0, set()

# add another face to the list of faces (f)
global max_n, max_v
# compute the sums of all allowed combinations of faces
sums = set(sum(f[x] for x in t) for t in combs)
# find the highest number in a contiguous sequence of
# values from 1 upwards
hi = min(set(range(1, max(sums) + 2)) - sums) - 1
# are all faces occupied?
if f.count(0) == 0:
# if so, save a new maximum if the same or higher
# than the previous maximum
if hi >= max_n:
# if a new maximum, clear the maximum solution set
if hi > max_n:
max_n = hi
max_v = set()
# add to the set of solutions for the the three
# 'opposite face' values
t = tuple(sorted(tuple(sorted([f[i], f[5 - i]]))
for i in range(3)))
max_v.update([t])
else:
# add another face value starting at one above the maximum
# possible so far and decreasing to three below this
for h in range(hi + 1, max(hi - 4, 0), -1):
# try this value in all unallocated positions
for i in range(6):
if not f[i]:
f[i] = h
f[i] = 0

# find the maximum sum and solutions for the three 'opposite face' values
add([1, 0, 0, 0, 0, 0])
for f1, f2, f3 in sorted(max_v):
fs = '{0:d}: {1[0]:d}/{1[1]:d}, {2[0]:d}/{2[1]:d}, {3[0]:d}/{3[1]:d}'
print(fs.format(max_n, f1, f2, f3))
```
3. Jim Randell 6 April 2015 at 11:37 am

I had abandoned my attempt at a recursive solution because it got too complicated, and was too slow. But inspired by Brian’s approach I’ve resurrected it. My recursive step is somewhat more complicated than Brian’s, but the code in update() to filter out non-canonical orderings brings it back to running in 5.5s – slightly faster than my code that works by considering possible totals (and you don’t have to worry about the case where t>N).

```from collections import Counter
from itertools import permutations
from enigma import subsets, diff, irange, chunk, Accumulator, printf

# consider values on the cube as (U, D, F, B, L, R)
# we can use all non-empty combinations apart from U+D, F+B, L+R
# so there are 60 possible combinations
sets = diff(subsets((0, 1, 2, 3, 4, 5), min_size=1), [(0, 1), (2, 3), (4, 5)])

# decompose <t> into <n> numbers
def decompose(t, n, m=1, s=()):
if n == 1:
if not(t < m):
yield s + (t,)
else:
for x in irange(m, t // 2):
yield from decompose(t - x, n - 1, x, s + (x,))

# update <vs> to insert values from <s> on faces <fs>
# return None if canonical ordering is violated
def update(vs, fs, s):
vs = list(vs)
for (i, v) in zip(fs, s):
vs[i] = v
# reject invalid orderings
for (ps, qs) in (([0], [1]), ([2], [3]), ([4], [5]), ([0, 1], [2, 3]), ([0, 1], [4, 5]), ([2, 3], [4, 5])):
(pv, qv) = (tuple(vs[i] for i in ps), tuple(vs[i] for i in qs))
if 0 not in pv and 0 not in qv and pv > qv: return None
# return the new values
return vs

# determine what values can be made from stamps vs = (U, D, F, B, L, R)
# return a Counter object
def values(vs):
return Counter(sum(vs[i] for i in s) for s in sets)

# vs - stamps (U, D, F, B, L, R), 0 = unassigned
# c - Counter of values that can be made
# r - Accumulator object for results
def solve(vs, c, r):
# find smallest value not in c
for n in irange(1, 61):
if n not in c: break
# find indices of values remaining to be assigned
fs = tuple(i for (i, v) in enumerate(vs) if v == 0)
# are we done?
z = len(fs)
if z == 0:
# record N
N = n - 1
r.accumulate(N)
if r.value == N: printf("[N={N} {vs}]", vs=tuple(chunk(vs, 2)))
return
# add in some new values so we can make n
for k in irange(1, n):
if k < n and n - k not in c: continue
for j in irange(1, z):
for s in decompose(k, j, 1):
# assign the values to j of the empty faces
for fs2 in permutations(fs, j):
# check n is now a possible value
vs2 = update(vs, fs2, s)
if vs2 is None: continue
c2 = values(vs2)
if n in c2:
solve(vs2, c2, r)

# find max N
r = Accumulator(fn=max)