Enigmatic Code

Programming Enigma Puzzles

Enigma 1386: Fair shares

From New Scientist #2546, 8th April 2006

It was Penny’s birthday and Joe provided a box of 25 sweets. He arranged five saucers in a circle and placed 5, 1, 9, 2 and 8 sweets in that order round the circle in the saucers.

To share out the sweets Penny and her four friends had to take turns to remove sweets from or replace sweets in a saucer of their choice until there were five sweets in each. Any sweets removed were placed temporarily on the table.

However, Joe stipulated that if they moved a number of sweets into or out of a saucer, then they must move the same number of sweets into or out of the two adjacent saucers. So each turn consisted of three moves. Needless to say they tried to share out the sweets as quickly as possible.

What is the minimum number of turns needed to share out the sweets?

Penny and Joe are revisited in Enigma 1410.

[enigma1386]

Advertisements

One response to “Enigma 1386: Fair shares

  1. Jim Randell 7 October 2013 at 9:50 am

    I generalised the code I wrote to determine the minimum sequence of moves for Enigma 1410, so that the initial sequence can be specified. Although it doesn’t need the initial analysis, this is a harder puzzle and it took 72s to find 26 ways of solving the puzzle in 8 moves. (Although it finds the first of these minimal solutions after about 16s. I recoded from Python 3 to Python 2 so that I could use PyPy to speed up the execution).

    This code is less time efficient than a breadth first search, as it considers increasing numbers of maximum moves, so will become hopelessly bogged down if a large number of moves is required. But it won’t use much memory while it’s working.

    from itertools import count
    from enigma import irange, printf
    
    # initial state
    import sys
    ss = [5, 1, 9, 2, 8] if len(sys.argv) < 5 else list(int(i) for i in sys.argv[1:])
    
    # determine final state
    (t, n) = (sum(ss), len(ss))
    (d, r) = divmod(t, n)
    assert r == 0, "invalid initial state"
    fs = [d] * n
    printf("[initial: {ss}, target: {fs}]")
    
    
    # triples of saucers
    ts = tuple((i, (i + 1) % n, (i + 2) % n) for i in irange(0, n - 1))
    
    # update a list, setting indices i with values vs
    def update(s, i, vs):
      s = list(s)
      for (j, v) in zip(i, vs):
        s[j] = v
      return s
    
    # s - contents of the saucers
    # t - counters on the table (/3)
    # p - sequence of moves so far
    # fs - final state
    # m - max number of moves
    def solve(s, t, p, fs, m):
      if s == fs:
        yield p
      elif len(p) < m:
        # choose a triple
        for i in ts:
          # but different from the last one
          if len(p) > 1 and p[-1][1] == i: continue
          # attempt to distribute what's on the table
          for n in irange(1, t):
            cs = list(s[j] + n for j in i)
            for x in solve(update(s, i, cs), t - n, p + [(n, i)], fs, m): yield x
          # attempt to take from that triple
          for n in irange(1, min(s[j] for j in i)):
            cs = list(s[j] - n for j in i)
            for x in solve(update(s, i, cs), t + n, p + [(-n, i)], fs, m): yield x
    
    # try to solve in the minimum number of moves
    for m in count(1):
      n = 0
      for p in solve(ss, 0, [], fs, m):
        print(p)
        n += 1
      printf("{m} moves, {n} solutions")
      if n > 0: break
    

    Solution: The minimum number of turns required is 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: