Enigmatic Code

Programming Enigma Puzzles

Enigma 266: Twelve trees

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

Enigma 266 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:

(a) the smallest possible radius?
(b) the largest possible radius?

for such a circle enclosing exactly 12 trees?

[enigma266]

Advertisements

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
    
      circles.add((r2, x0, y0))
    
    # 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:

    Enigma 266 - Solution A

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

    Enigma 266 - Solution B

  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.

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: