Enigmatic Code

Programming Enigma Puzzles

Enigma 312: Six-stamp sheet

From New Scientist #1460, 13th June 1985 [link]

Enigma 312

They are now printing stamp-books with stamps of different values on the same sheet. Let us take this a stage further, and design a sheet of 3 × 2 stamps, so that you can make up a postage of any whole number of pence from 1 up to N by tearing out a connected set of one or more stamps.

“Connected” means edge-connected, not just corner-touching, so that, for instance, the sheet illustrated achieves only N=5, since neither 4+2 nor 5+1 is a connected set, and so 6 is impossible.

Make a sketch showing how to make N as big as possible, and state what N is.

[enigma312]

Advertisements

2 responses to “Enigma 312: Six-stamp sheet

  1. Jim Randell 25 September 2015 at 8:55 am

    See also: Enigma 270, Enigma 1596.

    In Enigma 1596 we saw that N=36 is possible, and as there are 40 possible blocks the upper bound is N=40.

    This Python 3 program is adapted from my recursive solution to Enigma 270. It finds the possible arrangement of blocks of stamps, and then recursively assigns stamps to the grid to find the maximum possible value for N. It runs in 17.2s.

    from collections import Counter
    from itertools import permutations
    from enigma import irange, Accumulator, printf
    
    # we represent the grid as:
    #
    #   0 1 2
    #   3 4 5
    
    stamps = set(irange(0, 5))
    
    # then the adjacency list is:
    adjacent = (
      set((1, 3)), # 0
      set((0, 2, 4)), # 1
      set((1, 5)), # 2
      set((0, 4)), # 3
      set((1, 3, 5)), # 4
      set((2, 4)), # 5
    )
    
    # find all possible blocks of adjacent stamps
    def block(b, r):
      if b in blocks: return
      r.append(b)
      for i in stamps:
        if i in b: continue
        if adjacent[i].intersection(b):
          block(b.union([i]), r)
    
    blocks = []
    for i in stamps:
      block(set([i]), blocks)
    
    # number of different blocks
    B = len(blocks)
    printf("number of blocks = {B}")
    
    # determine what values can be made from stamps <vs>
    # without using the stamps in indices <zs> 
    def values(vs, zs):
      return Counter(sum(vs[i] for i in s) for s in blocks if not zs.intersection(s))
    
    # decompose <t> into <n> numbers
    # m - smallest allowable number
    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> into spaces <fs>
    def update(vs, fs, s):
      vs = list(vs)
      for (i, v) in zip(fs, s):
        vs[i] = v
      # return the new values
      return vs
    
    # vs - stamps, 0 = unassigned
    # c - Counter of values that can be made from <vs>
    # zs - unassigned indices in <vs>
    # r - Accumulator object for results
    def solve(vs, c, zs, r):
      # find the smallest value not in c
      for n in irange(1, B + 1):
        if n not in c: break
      # are we done?
      if not zs:
        N = n - 1
        # record N
        r.accumulate(N)
        if r.value == N: printf("N={N} {vs}")
        return
      # add in some new values, so we can make n
      for k in irange(n, 1, step=-1):
        # make k from j numbers
        for j in irange(1, len(zs)):
          for s in decompose(k, j, 1):
            # assign the values to j of the unassigned spaces
            for zs1 in permutations(zs, j):
              # check n is now a possible value
              vs2 = update(vs, zs1, s)
              zs2 = zs.difference(zs1)          
              c2 = values(vs2, zs2)
              if n in c2:
                solve(vs2, c2, zs2, r)
    
    r = Accumulator(fn=max)
    
    # try with 1 in a corner position (0) and in an edge position (1)
    for i in (0, 1):
      vs = [0] * 6
      vs[i] = 1
      zs = set(i for (i, v) in enumerate(vs) if v == 0)
      solve(vs, values(vs, zs), zs , r)
    
    printf("max N = {r.value}")
    

    Solution: The maximum values for N is N=36.

    There are two different ways of achieving this, shown below (along with their reflections):

    Enigma 312 - Solution

    As there are 40 ways of making blocks of stamps, some denominations must be repeated.

    For the first arrangement the repeated values are:

    8 = (8) = (2, 6)
    17 = (2, 15) = (1, 2, 6, 8)
    18 = (1, 2, 15) = (4, 6, 8)
    23 = (8, 15) = (2, 6, 15)

    For the second arrangement the repeated values are:

    5 = (5) = (2, 3)
    10 = (2, 8) = (2, 3, 5)
    11 = (1, 2, 8) = (1, 2, 3, 5)
    22 = (5, 17) = (2, 3, 17)

  2. hakank 26 September 2015 at 11:31 pm

    A solution in Picat using a combination of logic programming (e.g. member/2 for building the valid configurations), plain iterative programming, and Constraint Programming (for solving the specific instances): http://hakank.org/picat/six_stamp_sheet.pi

    It find max M=36 in 2.7s.

    import cp,util.
    
    main => go.
    
    go =>
      Rows = 2,
      Cols = 3,
      N = Rows*Cols,
      Graph=connected_cells(Rows,Cols),
      cl_facts(Graph), % make p(From,To) available
    
      All = [],
      Table = [], % for table_in/2
      foreach(I in 1..2**(N)-1)
        Bin = [J.to_integer() : J in I.to_binary_string()].reverse(),
        C = [J : J in 1..Bin.len, Bin[J]=1],
        OK = sum([1: K in C, L in C, K != L, (p(K,L) ; member(T,C), p(K,T), p(T,L))]),
        if OK >= (C.len*C.len-1) div 2 then
          All := All ++ [C],
          Bin2 = ([0:_ in 1..N-Bin.len] ++ Bin.reverse()).to_array(),
          Table := Table ++ [Bin2]
        end
      end,
      MaxM = _,
      OK = true,
      foreach(M in 5..100, OK == true) 
         printf("m=%d ", M),
         stamps(Rows,Cols,Table,M, X) ->
            println(x=X), MaxM := M
          ; 
            printf("not found\n"),
            OK := false
      end,
    
      println(maxM=MaxM),
    
      % println("\nOptimal solutions:"),
      % Sols = findall(X, stamps(Rows,Cols,Table,MaxM, X)).sort_remove_dups(),
      % foreach(Sol in Sols) println(Sol) end,
      nl.
    
    
    % CP approach using table_in/2 to handle the valid stamp combinations
    stamps(Rows,Cols,Table, M, X) =>
    
      N = Rows*Cols,
      X = new_array(Rows,Cols),
      X :: 1..M div 2,
      X1 = X.vars(),
      Y = new_array(M,N),
      Y :: 0..1,
    
      foreach(Num in 1..M)
        table_in(Y[Num],Table),
        Num #= sum([Y[Num,I]*X1[I] : I in 1..N])
      end,
      lex2(X),
      solve($[min,split],X++Y).
    
    % symmetry breaking
    lex2(X) =>
      Len = X[1].length,
      foreach(I in 2..X.length) 
        lex_le([X[I-1,J] : J in 1..Len], [X[I,J] : J in 1..Len])
      end.
    
    % create the graph
    connected_cells(Rows,Cols) = Graph =>
      V = -1..1,
      Graph = [$p(From,To) : I in 1..Rows, J in 1..Cols, A in V, B in V,
              I+A in 1..Rows,J+B in 1..Cols, abs(A+B)=1, From = (I-1)*Cols + J,
              To = (I+A-1)*Cols + J+B].
    
    

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: