# Enigmatic Code

Programming Enigma Puzzles

## Enigma 252: Three-point circle

From New Scientist #1399, 1st March 1984 [link] 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]

### 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
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
r.accumulate(r2)
if r2 == r.value:
printf("[({x1},{y1}) ({x2},{y2}) ({x3},{y3}) => ({x0},{y0}) {r2}]")

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. 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) ** 2 + (y - p) ** 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!

This site uses Akismet to reduce spam. Learn how your comment data is processed.