Enigmatic Code
Programming Enigma Puzzles
Enigma 1354: Sound idea
Posted by on 20 January 2014
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]
Enigmatic Code 
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
floatobjects it checks the centre of mass is “close enough” to the centre of the disc. For a completely accurate (but slower) solution, you can importsin, cos, pifromsympy(instead ofmath), and check 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.
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)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))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 breakThis 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}")