# Enigmatic Code

Programming Enigma Puzzles

## Enigma 266: Twelve trees

From New Scientist #1413, 7th June 1984 [link]

The dots are very thin vertical trees, laid out on an endless square grid, with each tree a kilometre from its nearest neighbours. The two circles are Sue’s first attempts at drawing the smallest and the largest possible circles which enclose exactly 12 trees. The smaller has a radius of 1803 metres, the larger of 2061 metres. Given that the centres can be anywhere you like, that the radius must be an exact whole number of metres, and that the circles must not pass through any tree, can you do better? What in fact is:

for such a circle enclosing exactly 12 trees?

[enigma266]

### 4 responses to “Enigma 266: Twelve trees”

1. Jim Randell 18 March 2015 at 8:00 am

This is another Lattice Circle problem – like Enigma 136 and Enigma 229 (also by Stephen Ainley).

I adapted my lattice circle solver for this problem. It runs in 796ms.

```from itertools import product, combinations
from fractions import Fraction as F
from enigma import irange, isqrt, compare, Accumulator, printf

# 1/2
h = F(1, 2)

# points that define the triangle
pts = [(0, 0), (h, h), (h, 0)]

# collect lattice points
lattice = tuple(product(irange(-2, 3), repeat=2))

# collect candidate circles
circles = set()

# choose 3 lattice points
for ((x1, y1), (x2, y2), (x3, y3)) in combinations(lattice, 3):
# the parameters for the perpendicular bisector of p1 and p2 (Ax + By = C)
A1 = 2 * (x2 - x1)
B1 = 2 * (y2 - y1)
C1 = (x2 ** 2 + y2 ** 2) - (x1 ** 2 + y1 ** 2)
# the parameters for the perpendicular bisector of p1 and p3 (Ax + By = C)
A2 = 2 * (x3 - x1)
B2 = 2 * (y3 - y1)
C2 = (x3 ** 2 + y3 ** 2) - (x1 ** 2 + y1 ** 2)
# do they intersect in the triangle?
d = A2 * B1 - A1 * B2
if d == 0: continue
y0 = F(A2 * C1 - A1 * C2, d)
if y0 < 0: continue
if A1 == 0: continue
x0 = F(C1 - B1 * y0, A1)
if x0 > h or y0 > x0: continue

# work out the radius of the circle
r2 = (x0 - x1) ** 2 + (y0 - y1) ** 2

# find the smallest and largest circles containing 12 points
mn = Accumulator(fn=min)
mx = Accumulator(fn=max)

for (r2, x0, y0) in circles:

# calculate the number of interior (ni) and perimeter (np) lattice points
ni = np = 0
for (x, y) in lattice:
c = compare((x0 - x) ** 2 + (y0 - y) ** 2, r2)
if c == 0:
np += 1
elif c < 0:
ni += 1

if ni + np == 12:
# there are 12 points in the interior and perimeter
# so the minimum size of a circle containing 12 points is...
r = isqrt(1000000 * r2) + 1
mn.accumulate_data(r, (x0, y0))

if ni == 12:
# there are 12 interior points
# so the maximum size of circle containing 12 points is...
r = isqrt(1000000 * r2)
if r * r == 1000000 * r2: r -= 1
mx.accumulate_data(r, (x0, y0))

printf("min radius = {mn.value}m @ ({mn.data[0]}, {mn.data[1]})")
printf("max radius = {mx.value}m @ ({mx.data[0]}, {mx.data[1]})")
```

Solution: (a) The smallest possible radius is 1582m. (b) The largest possible radius is 2124m.

Here is a diagram of a circle with the smallest possible radius, the circle is centred 500m north and 500m east of a tree:

Here is a diagram of a circle with the largest possible radius, the circle is centred 0m north and 125m east of a tree:

2. Brian Gladman 18 March 2015 at 9:46 am

I avoided a lot of code by experimenting to find the positions that minimised and maximised the number of points in the circle. I don’t know yet whether it is an error in my code but my maximum circle is 2125m rather than 2124m

```# Experimentation shows that the minimum number of grid points within
# a circle occurs when the centre of the circle is midway between the
# grid points on both axes. And the maximum occurs when the centre is
# on a grid line at one eighth of the distance between grid points.

from itertools import count

# count the number of grid points within a circle of radius r and
# centre (x0, y0) with the grid points at (x, y) = (i.d, j.d) for
# -inf < i, j < inf
def count_points(x0, y0, r, d):
ix = d * ((x0 - r - 1) // d) - x0
iy = d * ((y0 - r - 1) // d) - y0
return sum(x ** 2 + y ** 2 < r ** 2
for x in range(ix, r + 2, d) for y in range(iy, r + 2, d))

for min_r in count(1803, -1):
if count_points(500, 500, min_r - 1, 1000) != 12:
break

for max_r in count(2061):
if count_points(0, 125, max_r + 1, 1000) != 12:
break

fs = 'The minimum and maximum radii are {} and {}.'
print(fs.format(min_r, max_r))
```
• Jim Randell 18 March 2015 at 10:13 am

The maximum circle with a radius of 2125m would hit exactly three of the thin trees on the perimeter of the fence. (In my diagram they are the black dots that touch the outside of the circle). So you reduce the radius to avoid that, but it has to be an exact number of metres, so the answer is 2124m.

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