Enigmatic Code

Programming Enigma Puzzles

Enigma 1354: Sound idea

From New Scientist #2513, 20th August 2005

Joe’s daughter has been asking him for weeks to make a wind chime. So this week Joe cut a length of stainless steel tubing into 10 lengths from 1 cm to 10 cm in steps of 1 cm. He also cut out a disc from a sheet of stainless steel and drilled 10 evenly spaced holes round the perimeter and one in the centre.

Joe hung one tube from each hole and hung the disc up by a thread from its centre. That was a big mistake as the disc tilted right over.

So Joe rearranged the tubes until the disc balanced perfectly. In making a note of the lengths of the tubes in order round the disc the result was an 11-digit number.

What is the smallest of all the 11-digit numbers Joe could have written down?

[enigma1354]

Advertisements

5 responses to “Enigma 1354: Sound idea

  1. Jim Randell 20 January 2014 at 9:17 am

    This Python program calculates the centre of mass for each arrangement of tubes, and then determines the smallest of the numbers corresponding to balanced discs. Since it’s using Python’s floats it checks the centre of mass is “close enough” to the centre of the disc. For a completely accurate (but slower) solution, you can import sin, cos, pi from sympy (instead of math), and check of the centre of mass corresponds exactly to the centre of the disc – you get the same results.

    The Python program below runs in 291ms (under PyPy).

    from math import sin, cos, pi
    from itertools import permutations
    from enigma import Accumulator, irange, nconcat, printf
    
    # centre of mass of particles placed around the disc
    def mass(ps):
      n = len(ps)
      s = 2 * pi / n
      x = y = M = 0
      for (i, m) in enumerate(ps):
        M += m
        x += m * cos(i * s)
        y += m * sin(i * s)
      return (x / M, y / M)
    
    # tolerance
    T = 1e-12
    
    # lets place 10 (the lexicographically lowest number in the first
    # position), and consider the remaining lengths
    r = Accumulator(fn=min)
    for s in permutations(irange(1, 9)):
      # eliminate duplicate solutions
      if not(s[0] < s[-1]): continue
      ps = (10,) + s
      (x, y) = mass(ps)
      if abs(x) < T and abs(y) < T:
        n = nconcat(ps)
        r.accumulate(n)
        printf("[{ps} -> {n}]")
    
    printf("min = {r.value}")
    

    Solution: The smallest 11-digit number is 10145892367.

  2. Brian Gladman 20 January 2014 at 2:07 pm
    
    from itertools import count, permutations
    from math import pi, sin, cos
    
    # sines and cosines for positions around the circle
    ci = tuple(cos(pi * i / 5.0) for i in range(10))
    si = tuple(sin(pi * i / 5.0) for i in range(10))
    # marker to signal that minimum has (not) been found
    sentinel = 11000000000
    # put the 10cm chime at angle zero and then look for 
    # a balance with chimes 1, 2, ... in the next position
    chime, min_no = 0, sentinel
    while min_no == sentinel:
      chime += 1
      # now permute the remaining values and check for a minimum
      # value of the 11 digit number
      for cc in permutations(set(range(1, 10)) - set((chime,))):
        chimes = (10, chime) + cc
        # check for a balance
        v = sum(x * ci[j] for j, x in enumerate(chimes))
        h = sum(x * si[j] for j, x in enumerate(chimes))
        if v * v + h * h < 1e-10:
          # if the arrangement is balanced, check if the
          # number is less than any previously seen
          no = int(''.join(str(x) for x in chimes))
          if no < min_no:
            min_no = no
    print('The minimum number is', min_no)
    
    • Brian Gladman 21 January 2014 at 2:45 pm

      Here is a version that avoids the approximations involved in using floating point arithmetic by using complex integers (x + i.y with x and y integer) to represent the algebraic cosine and sine values.

      from itertools import permutations
      
      # sines and cosines for positions around the circle
      # (algebraic numbers are represented by complex values)
      ci = ( ( 4+0j), ( 1+1j), (-1+1j), ( 1-1j), (-1-1j), 
             (-4+0j), (-1-1j), ( 1-1j), (-1+1j), ( 1+1j) )
      si = ( ( 0+0j), ( 1-1j), ( 1+1j), ( 1+1j), ( 1-1j),
             ( 0+0j), (-1+1j), (-1-1j), (-1-1j), (-1+1j) )
      # put the 10cm chime at angle zero and then look for 
      # a balance with chimes 1, 2, ... in the next position
      chime, nbrs = 0, []
      while not nbrs:
        chime += 1
        # now permute the remaining values and check for a minimum
        # value of the 11 digit number
        for cc in permutations(set(range(1, 10)) - set((chime,))):
          chimes = (10, chime) + cc
          # check for a balance
          if not (sum(x * ci[j] for j, x in enumerate(chimes)) or
                  sum(x * si[j] for j, x in enumerate(chimes))):
            # if the arrangement is balanced, check if the
            # number is less than any previously seen
            nbrs += [int(''.join(str(x) for x in chimes))]
      print('The minimum number is', min(nbrs))
      
  3. arthurvause 21 January 2014 at 10:48 am

    Here is another variation. The reasoning behind the code is in a Blog post

    from itertools import permutations as perm
    
    a=10
    onetoten=frozenset(range(1,11))
    
    for b,c,d,e in perm(range(1,10),4):
      f=55-a-2*(b+c+d+e)
      g=55-b-2*(c+d+e+f)
      h=55-c-2*(d+e+f+g)
      i=55-d-2*(e+f+g+h)
      j=55-e-2*(f+g+h+i)
    
      s=(a,b,c,d,e,f,g,h,i,j)
      if set(s)==onetoten:
    
        # sanity check
        if all( sum(s[i%10] for i in xrange(m,m+4))
                ==sum(s[i%10] for i in xrange(m+5,m+9))
                for m in xrange(10)):
          print "solution", a,b,c,d,e,f,g,h,i,j
          break
    
  4. Jim Randell 23 January 2014 at 9:46 am

    This is a recursive Python solution that uses the analysis that opposite pairs of adjacent weights sum to the same value (i.e if the weights are numbered from w0 to w9 around the circle, then w0 + w1 = w5 + w6, w1 + w2 = w6 + w7, w2 + w3 = w7 + w8, w3 + w4 = w8 + w9, w4 + w5 = w9 + w0).

    It runs in 35ms – much faster than computing the centre of mass of all combinations.

    from enigma import Accumulator, nconcat, irange, printf
    
    # update a list with a sequence of (index, value) pairs
    def update(ws, *args):
      r = list(ws)
      for (i, w) in args:
        r[i] = w
      return r
    
    # ws - weights allocated so far
    # rs - remaining weights
    # i - next index to allocate
    # r - accumulator for solution
    def solve(ws, rs, i, r):
      # are we done?
      if not rs:
        # eliminate mirror image solutions
        if ws[1] < ws[-1]:
          n = nconcat(ws)
          r.accumulate(n)
          printf("{ws} -> {n}")
      else:
        # choose a weight to place at the next index
        for w0 in rs:
          # and determine the opposite weight
          w1 = w0 + ws[i - 1] - ws[i + 4]
          if w1 != w0 and w1 in rs:
            solve(update(ws, (i, w0), (i + 5, w1)), rs.difference((w0, w1)), i + 1, r)
    
    # place 10 at position 0, and all other possible weights opposite (position 5)
    ws = [10] + [None] * 9
    rs = set(irange(1, 9))
    r = Accumulator(fn=min)
    for w in rs:
      solve(update(ws, (5, w)), rs.difference([w]), 1, r)
    
    # output the minimal solution
    printf("min = {r.value}")
    

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: