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]

Advertisements

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)
    def add(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
              add(f)
              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
        # made from j numbers
        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)
    
    # start with U=1
    vs = [1, 0, 0, 0, 0, 0]
    solve(vs, values(vs), r)
    
  4. Julian Gray 6 April 2015 at 10:12 pm

    After an Easter break, how about 55 with 1/2, 3/7 and 14/28?

  5. Paul 7 April 2015 at 9:52 am

    As a matter of interest, the maximum for 6 stamps also corresponds to the maximum you can score with 3 darts with a choice of 6 numbers with these 2 sets.
    1, 3, 7, 9, 19, 24 and 1, 4, 6, 14, 17, 29

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: