Enigmatic Code

Programming Enigma Puzzles

Enigma 252: Three-point circle

From New Scientist #1399, 1st March 1984 [link]

Enigma 252

Each of the black dots in the picture is one of the elements — 3 speakers and 22 suppressors — in Uncle Pinkle’s Triphonic Asymmetric Garden Audio-system. The whole square array measures 40 × 40 metres. Uncle Pinkle sits at C, precisely the same distance D from each speaker, but not at distance D from any suppressor; and C must not be directly between any two system-elements, so it isn’t on any of the vertical, horizontal or diagonal lines in the picture. Within these restrictions, Uncle Pinkle has arranged the system-elements and placed his seat so that D is as small as possible.

How far is the distance D? (An answer to the nearest centimetre will do).

[enigma252]

Advertisements

3 responses to “Enigma 252: Three-point circle

  1. Jim Randell 21 January 2015 at 8:28 am

    This is lattice circle problem, similar to Enigma 136 and Enigma 229 (also by Stephen Ainley).

    I adapted the lattice circle solver I wrote for Enigma 136 to solve this.

    This Python program runs in 555ms.

    from itertools import product, combinations
    from fractions import Fraction as F
    from enigma import irange, Accumulator, sqrt, printf
    
    # positions
    points = tuple(product(irange(0, 40, step=10), repeat=2))
    
    r = Accumulator(fn=min)
    
    # choose 3 positions to be the speakers
    for ((x1, y1), (x2, y2), (x3, y3)) in combinations(points, 3):
      # parameters for the perpendicular bisectors of (p1, p2), (p1, p3)
      (a1, a2) = (2 * (x2 - x1), 2 * (x3 - x1))
      (b1, b2) = (2 * (y2 - y1), 2 * (y3 - y1))
      (c1, c2) = ((x1 ** 2 - x2 ** 2) + (y1 ** 2 - y2 ** 2), (x1 ** 2 - x3 ** 2) + (y1 ** 2 - y3 ** 2))
      # are they parallel?
      d = a1 * b2 - a2 * b1
      if d == 0: continue
      # determine the centre
      x0 = F(b1 * c2 - b2 * c1, d)
      y0 = F(a2 * c1 - a1 * c2, d)
      # ignore centres on grid lines or diagonals
      (x, y) = (x0 % 10, y0 % 10)
      if x == 0 or y == 0 or x == y or x + y == 10: continue
      # and the radius
      r2 = (x1 - x0) ** 2 + (y1 - y0) ** 2
      # count the points with the same distance
      if sum(1 for (x, y) in points if (x0 - x) ** 2 + (y0 - y) ** 2 == r2) > 3: continue
      # track the minimal radius
      r.accumulate(r2)
      if r2 == r.value:
        printf("[({x1},{y1}) ({x2},{y2}) ({x3},{y3}) => ({x0},{y0}) {r2}]")
    
    # find the minimal radius
    D = sqrt(r.value)
    printf("D={D:.2f}m")
    

    Solution: D is 18.21m (or (25/7)√26).

    This diagram shows one of the 32 possible positions for C. The position C is marked with a large cross, and the three equidistant speakers are marked with circles. The 31 alternative positions for C are marked with smaller crosses.

    Enigma 252 - Solution

    The example position for C is at (95/7, 85/7) (= 10 × (19/14, 17/14)).

  2. Brian Gladman 22 January 2015 at 11:34 am

    I don’t normally post my solution if it is too similar to your own and this one certainly is in terms of approach. But there are a number of practical differences so I decided to post in this case.

    As you found in the related lattice based teasers, the GMPY2 implementation of rational fractions is much faster than that in Python (as posted it uses the latter).

    from itertools import combinations
    from fractions import Fraction as RF
    # from gmpy2 import mpq as RF
    
    # compute the square of radius (r2) and the coordinates of the centre
    # of a circle (x, y) given the coordinates of three points on it's
    # circumference in the tuples mn, pq and rs.  RF (Rational Fractions)
    # can be represented by either Python Fractions or GMPY2 mpq values
    def three_point_circle(mn, pq, rs):
      m, n = mn
      p, q = pq
      r, s = rs
      bot = 2 * ((m * s + p * n + r * q) - (m * q + p * s + r * n))
      mn2, pq2, rs2 = m * m + n * n, p * p + q * q, r * r + s * s
      x = RF(mn2 * (s - q) + pq2 * (n - s) + rs2 * (q - n), bot)
      y = RF(mn2 * (p - r) + pq2 * (r - m) + rs2 * (m - p), bot)
      r2 = RF(((m - p) ** 2 + (n - q) ** 2) 
            * ((m - r) ** 2 + (n - s) ** 2) 
            * ((p - r) ** 2 + (q - s) ** 2), bot ** 2)
      return x, y, r2
    
    # the (x, y) coordinates of the points in the grid 
    pts = tuple((10 * x, 10 * y) for y in range(5) for x in range(5))
    
    # for the square of the radius of the minimum circle 
    min_r2 = None
    # a dictionary mapping the three points on minimum
    # radius circles to the coordinates of their centres
    d = dict()
    
    # consider all combinations of three grid points
    for pt3 in combinations(pts, 3):
      # and calculate the (x, y) coordinates and the square of
      # the radius for a circle passing through these three points
      try:
        x, y, r2 = three_point_circle(*pt3)
      except ZeroDivisionError:
        continue
      
      # remove any circles with centres on any horizontal, vertical
      # or diagonal straight lines through the grid points
      if not (x % 10 and y % 10 and (x - y) % 10 and (x + y) % 10):
        continue
      # the circles must only pass though the three given grid points
      if any((x - p[0]) ** 2 + (y - p[1]) ** 2 == r2 
                for p in pts if p not in pt3):
        continue
    
      # record the minimum radius found 
      if not min_r2 or r2 < min_r2:
        min_r2 = r2
        d.clear()
      # and the details for the associated three point circles
      if r2 == min_r2:
        d[pt3] = (x, y)
          
    print(' D (in metres) = {:.2f} = sqrt({})'.format(min_r2 ** 0.5, min_r2))
    for cnt, pt3 in enumerate(sorted(d)):
      print('{:2d} {} {}'.format(cnt + 1, pt3, d[pt3]))
    
  3. Hugh Casement 25 January 2015 at 12:37 pm

    The numbers would have been neater if the grid spacing in Uncle’s array had been, say, 28 ft.
    Then the coordinates of C (measured from the corner speaker) would be (34, 38) or (38, 34); and the distance D would be sqrt(2600) which is very close to 51.

    I wonder what his “suppressors” consist of. Think I’ll stick to indoor stereo myself!

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: