Enigmatic Code

Programming Enigma Puzzles

Enigma 1700: Polymagic

From New Scientist #2867, 2nd June 2012 [link]

From a box of counters numbered 1 to 12, Joe asked Penny to select a set of six and place them on the corners of a regular hexagon and then place the remaining six counters on the mid-points of each side, so that the number on each of these counters was the sum of the numbers on the counters on the two adjacent corners. Joe then produced 16 counters and asked Penny to repeat the challenge, but this time selecting a set of eight and placing them, and the remaining eight, similarly on an octagon.

In the first case, Penny found her choice of the set of six counters was rather limited. How many choices did she have?

And how many choices did she have in the case of the octagon?

[enigma1700]

Advertisements

12 responses to “Enigma 1700: Polymagic

  1. Jim Randell 30 May 2012 at 6:47 pm

    The following Python program runs in 44ms.

    from itertools import combinations, permutations
    from enigma import irange, printf
    
    def solve(n):
      # what are the values on the counters?
      ns = set(irange(1, n * 2))
      # the number of each vertex will be part of the sum on two edges,
      # hence if t is the sum of the vertices, t + 2t = sum(ns)
      (t, r) = divmod(sum(ns), 3)
      # so there is no solution unless sum(ns) is divisible by 3
      if r > 0: return 0
    
      # to eliminate duplicate solutions we will assume that the first
      # vertex has the lowest number, and the second vertex is numbered
      # lower than the final vertex
    
      ss = set()
      # find possible combinations for the vertices, except the final one
      for cs in combinations(ns, n - 1):
        # the first vertex
        a = min(cs)
        # the final vertex
        z = t - sum(cs)
        if not(a < z): continue
        if not(z in ns.difference(cs)): continue
        # remove the first vertex
        cs = set(cs).difference((a,))
        # consider permutations of the vertices (except the first and last)
        for ps in permutations(cs):
          # check the second vertex is lower than the final vertex
          if not(ps[0] < z): continue
          # consider all the vertices (as a circular list)
          vs = [a] + list(ps) + [z, a]
          # and determine the values on the edges
          es = list(vs[i] + vs[i+1] for i in range(n))
          # check the edges and vertices correspond to the counters
          if set(es).union(vs[:-1]) != ns: continue
          # what are the vertices?
          ss.add(tuple(sorted(vs[:-1])))
      return len(ss)
    
    for n in (6, 8):
      printf("n={n}: {s} choices", s=solve(n))
    

    Solution: For the hexagon Penny could choose from 4 different sets of counters. For the octagon there are no sets of counters that will give a solution.

    • Jim Randell 31 May 2012 at 7:36 am

      Here’s a slightly modified version that additionally uses the fact that the two lowest numbers must be vertices, and the two highest numbers must be edges. It doesn’t run noticeably faster, but running it under cProfile reveals that the number of function calls goes down from ~5500 to ~2900.

      It also uses a Counter object to track both the number of solutions and the number of different sets of counters used on the vertices in those solutions.

      from itertools import combinations, permutations
      from collections import Counter
      from enigma import irange, printf
      
      def solve(n):
        # what are the values on the counters?
        ns = list(irange(1, n * 2))
        # the number of each vertex will be part of the sum on two edges,
        # hence if t is the sum of the vertices, t + 2t = sum(ns)
        t, r = divmod(sum(ns), 3)
        # so there is no solution unless sum(ns) is divisible by 3
        if r > 0: return (0, 0)
      
        # the lowest two numbers must be placed on vertices, as they cannot
        # form a sum, and likewise the highest two numbers must be placed on
        # edges, as they must form a sum
      
        # to eliminate duplicate solutions we will assume that the first
        # vertex has the lowest number, and the second vertex is numbered
        # lower than the final vertex
      
        # so the first vertex is 1, and 2 is also a vertex (not the final one)
      
        c = Counter()
        # find possible combinations for the remaining vertices
        for cs in combinations(ns[2:-2], n - 3):
          # the final vertex
          z = t - sum(cs) - sum(ns[0:2])
          if not(z in set(ns[2:-2]).difference(cs)): continue
          # consider permutations of the vertices (except the first and last)
          for ps in permutations(set(cs).union(ns[1:2])):
            # check the second vertex is lower than the final vertex
            if not(ps[0] < z): continue
            # consider all the vertices (as a circular list)
            vs = [ns[0]] + list(ps) + [z, ns[0]]
            # and determine the values on the edges
            es = list(vs[i] + vs[i + 1] for i in range(n))
            # check the edges and vertices correspond to the counters
            if set(es).union(vs[:-1]) != set(ns): continue
            # what are the vertices?
            printf("[n={n}] vertices={vs} edges={es}", vs=vs[:-1])
            c[tuple(sorted(vs[:-1]))] += 1
        return sum(c.values()), len(c)
      
      
      for n in (6, 8):
        s, c = solve(n)
        printf("n={n}: {s} solutions, {c} choices")
      
  2. Brian Gladman 30 May 2012 at 10:53 pm

    Hi Jim,
    Here is my solution:

    from itertools import permutations
    
    def solve(n):
      # the sum of the edge counters is twice the sum of
      # the vertex counters - so vertex counter sum is 
      # 1/3 of the sum of the counter values (1 .. 2n)
      d, r = divmod(n * (2 * n + 1), 3)
      if r:
        return None
      cnt = 0
      s = set(range(1, 2 * n + 1))
      # counter 1 must be a vertex counter 
      # the maximum vertex counter is 2 * n - 2
      # permute n - 2 values
      for p in permutations(range(2, 2 * n - 1), n - 2):
        # now add the first and last vertexes
        q = (1,) + p + (d - 1 - sum(p),)
        # avoid counting solutions that are the same
        # clockwise and counterclockwise
        if q[1] < q[-1]:
          # compute the edge values
          t = tuple(q[i] + q[(i + 1) % n] for i in range(n))
          # and check we have a full set of counter values
          if set(t) | set(q) == s:
            cnt += 1
      return cnt
    
    print('Solutions for a hexagon:', solve(6))
    print('Solutions for a octagon:', solve(8))
    

    I get a different answer compared with your code – I am doubtful that your line of code:
    ss.add(‘ ‘.join(map(str, sorted(vs[:-1]))))
    should sort the vertexes in compiling the set of solutions as I think the vertex order matters.
    Brian

    • Jim Randell 30 May 2012 at 11:07 pm

      I agree that in the hexagonal case there are 6 different solutions, but in two cases the solution uses the same collection of counters as two of the other solutions. Which in a strict reading of the problem means there are only 4 possible sets of counters that can be chosen to solve the first part of the problem.

  3. Brian Gladman 31 May 2012 at 6:33 am

    Good point Jim, I didn’t read it that way but it does look as if that is what is intended.

  4. Brian Gladman 31 May 2012 at 10:19 am

    Here is a corrected version of my code:

    from itertools import permutations
    
    def solve(n):
      # the edge counter sum is twice the vertex counter sum
      # hence the vertex counter sum is 1/3 the counter sum
      vertex_sum, r = divmod(n * (n + n + 1), 3)
      if r:
        return None
      ctrs, sol_set = set(range(1, 2 * n + 1)), set()
      # vertex counters include 1 and have maximum values of
      # 2n - 2 so assume these are '1, (n - 2) values, last' 
      # and permute the middle n - 2 values
      for p in permutations(range(2, 2 * n - 1), n - 2):
        # now add the first and last vertex counter values
        q = (1,) + p + (vertex_sum - 1 - sum(p),)
        # avoid the same solutions clockwise/counterclockwise
        if q[1] < q[-1]:
          # compute the edge values
          t = tuple(q[i] + q[(i + 1) % n] for i in range(n))
          # and check we have the full set of counter values
          if set(t) | set(q) == ctrs:
            sol_set |= set((tuple(sorted(q)),))
      return len(sol_set)
    
    print('Solutions for a hexagon:', solve(6))
    print('Solutions for a octagon:', solve(8))
    
  5. arthurvause 31 May 2012 at 2:58 pm

    The sum of the counters on mid-points = 2 x sum of the counters on the corners, so the sum of counters on corners is 1/3 of the sum of all counters.

    For 12 counters, the sum of all counters is 13×6 (a multiple of 3).

    For 16 counters the sum of all counters is 17×8, not a multiple of 3, so we don’t need to write any code for this option.

    Also, (as Jim observed), 1 and 2 must be on corners, 11 and 12 must be on mid-points.

    So, a bit of code:

    import itertools
    
    count=0
    print "Solutions (including reflections):"
    edges = range(3,11)
    for x in itertools.combinations(edges, 4):
        if sum(x) + 3 == 26:
            x+=(2,)
            for y in itertools.permutations(x):
                s = set([y[0]+1,y[0]+y[1],y[1]+y[2],y[2]+y[3],y[3]+y[4],y[4]+1])
                s|=set(y)
                if s==set(range(2,13)):
                    y+=(1,)
                    count+=1
                    print y
    print "Count, ignoring reflections, = ", count/2
    

    I am taking the view that permutations that are not reflections or rotations of each other count as different choices, e.g. 2, 5, 6, 4, 8, 1 is different to 2, 8, 4, 5, 6, 1, hence the answer of 6 rather than 4.

  6. Brian Gladman 31 May 2012 at 3:43 pm

    Initially I also gave 6 rather than 4 as the answer but I think Jim is right that the answer to the actual question posed in this enigma is 4, the number of different sets of vertex counters, irrespective of their order.

  7. Jim Randell 1 June 2012 at 8:34 am

    As a variation here is a recursive solution. It’s quicker than using itertools for larger values of n. For example it finds 12932 solutions (556 different sets) when n=12 in under 20s. (My other algorithm took over an hour before I stopped it).

    from collections import Counter
    from enigma import irange, printf
    
    # n = target length
    # vs = vertices
    # es = edges
    # ns = numbers
    # c = counter for solutions
    def solve(n, vs, es, ns, c):
      # are we done?
      if len(vs) == n:
        # for uniqueness
        if not(vs[1] < vs[-1]): return False
        # check the final edge
        e = vs[-1] + vs[0]
        if e not in ns: return False
        printf("[n={n}] vertices={vs} edges={es}", es=es + [e])
        c[tuple(sorted(vs))] += 1
        return True
    
      # try the next vertex
      for v in ns:
        e = v + vs[-1]
        if e not in ns: continue
        solve(n, vs + [v], es + [e], ns.difference((v, e)), c)
    
    import sys
    n = 6 if len(sys.argv) < 2 else eval(sys.argv[1])
    
    c = Counter()
    solve(n, [1], [], set(irange(2, n * 2)), c)
    printf("n={n}: {s} solutions, {l} choices", s=sum(c.values()), l=len(c))
    
    • Jim Randell 5 June 2012 at 11:49 am

      Here are the results for values of n from 2 to 18:

      n = number of vertices of shape
      s = number of solutions
      d = number of different vertex sets
      
       n             s         d
      
       2             0         0
       3             1         1
       4             1         1
       5             0         0
       6             6         4
       7            17         8
       8             0         0
       9           148        42
      10           578        92
      11             0         0
      12        12_932       556
      13        70_092     1_274
      14             0         0
      15     2_505_240     7_628
      16    16_826_503    18_162
      17             0         0
      18   915_013_780   111_051
      
  8. Brian Gladman 2 June 2012 at 9:19 am

    Good work Jim!.

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: