Enigmatic Code

Programming Enigma Puzzles

Enigma 1596: Semi-detached

From New Scientist #2761, 22nd May 2010 [link]

While Joe was in Hong Kong recently he bought a book of stamps with six stamps per page. From each page it was possible to extract a single stamp or block of stamps (each stamp still attached to at least one other) with any value from 1$ up to the total value of the six stamps. Joe noticed that for most values this could only be achieved in just one way, but for each of four of the values it was possible to select a single stamp or a block of stamps in two ways.

What value were the stamps X & Y?

[enigma1596]

Advertisements

One response to “Enigma 1596: Semi-detached

  1. jimrandell 17 January 2012 at 11:47 am

    The following Python program runs in 38ms:

    from collections import Counter
    from enigma import irange, printf
    
    # if we represent the grid as:
    # 0 1 2
    # 3 4 5
    stamps = set(irange(0, 5))
    
    # the adjacency list is:
    adjacent = (
      set((1, 3)), set((0, 2, 4)), set((1, 5)),
      set((0, 4)), set((1, 3, 5)), set((2, 4))
    )
    
    # find all possible blocks of adjacent stamps
    blocks = []
    
    def solve(b):
      if b in blocks: return
      blocks.append(b)
      for i in stamps:
        if i in b: continue
        if adjacent[i].intersection(b):
          solve(b.union([i]))
    
    for i in stamps:
      solve(set([i]))
    
    # it follows that the total value of the stamps is n-4
    # (as 4 values can be made in two ways)
    total = len(blocks) - 4
    
    def check(g):
      # count the number of ways to make various values from this grid
      c = Counter()
      for b in blocks:
        c[sum(g[i] for i in b)] += 1
      v = list(c.values())
      # check there are t values, and 4 of them can be done in 2 ways
      return len(v) == total and (v.count(1), v.count(2)) == (total - 4, 4)
    
    xy = total - (1 + 2 + 4 + 6)
    for x in irange(1, xy - 1):
      y = xy - x
      if check((1, 2, x, 4, 6, y)):
        printf("X={x} Y={y}")
    

    Solution: X = 15, Y = 8.

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: