Enigmatic Code

Programming Enigma Puzzles

Enigma 191: Tetrahedral differences

From New Scientist #1336, 16th December 1982 [link]

Enigma 191

The picture represents a tetrahedron, with a circle at each vertex and a square at each mid-edge. You first write a positive number at each vertex. Then at each mid-edge you write the difference between the numbers at the ends of the edge. All 10 numbers are to be different. You want the total of all 10 numbers to be as small as possible. Subject to that, you want the total of the vertex-numbers to be as small as possible.

What numbers should you put at the vertices?

[enigma191]

Advertisements

One response to “Enigma 191: Tetrahedral differences

  1. Jim Randell 14 May 2014 at 7:14 am

    This Python program runs in 127ms.

    from itertools import count, combinations
    from enigma import irange, diff, Accumulator, printf
    
    # consider the numbers on the vertices, to reduce symmetrical
    # solutions we will assume v1 is the smallest vertex and v2 < v3
    
    # decompose n into m numbers
    def decompose(n, m, s=1):
      if m == 1:
        if not(n < s):
          yield [n]
      else:
        for x in irange(s, n - s):
          if m > n: break
          for ds in decompose(n - x, m - 1, x + 1):
            yield [x] + ds
    
    # minimise the totals
    r = Accumulator(fn=min)
    
    # consider increasing vertex sums
    for s in count(1):
      # if the vertex sum exceeds the total sum then we're done
      if r.value and s > r.value[0]: break
    
      for vs in decompose(s, 4):
        # compute edge differences
        ss = vs + list(abs(a - b) for (a, b) in combinations(vs, 2))
        if len(set(ss)) != 10: continue
        r.accumulate_data((sum(ss), s), vs)
    
    printf("min total = {r.value[0]}, vertices = {r.data}, vertex sum = {r.value[1]}")
    

    Solution: The numbers at the vertices should be 3, 4, 9 and 11. The sum of all the numbers is 56, and the vertex sum is 27.

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: