Enigmatic Code

Programming Enigma Puzzles

Enigma 1759: Cell count

From New Scientist #2927, 27th July 2013 [link]

On a sheet of paper divided by horizontal and vertical lines into 1cm × 1cm cells I drew a circle whose centre was at a point where lines intersected and whose radius was an integral number of centimetres (less than 50). I counted the number of cells that the circumference of my circle passed through.

The circumference of a circle whose radius was 1cm smaller would have passed through a greater number of cells.

How many cells did the circumference of my circle pass through?

[enigma1759]

9 responses to “Enigma 1759: Cell count

  1. Jim Randell 24 July 2013 at 6:19 pm

    This puzzle reminds me of Enigma 1686.

    This Python program works by considering the squares cut by a quadrant of the circle. It runs in 54ms.

    from itertools import product
    from enigma import irange, printf
    
    # return the numbers of cells cut by a circle of radius r
    def cut(r):
      r2 = r ** 2
      # count the number of cells in a quadrant that are cut
      return sum(4 for (x, y) in product(irange(0, r - 1), repeat=2)
                 if x ** 2 + y ** 2 < r2 < (x + 1) ** 2 + (y + 1) ** 2)
    
    # find a radius r where r-1 cuts more cells
    n0 = 0
    for r in irange(1, 49):
      n = cut(r)
      printf("r={r} n={n} {s}", s=('*** SOLUTION ***' if n < n0 else ''))
      n0 = n
    

    Solution: The circumference of the circle passes through 180 cells.

    This diagram shows the cells that are cut by a circle of radius 25 (the grey and dark blue squares), there are 45 in a quadrant, so 180 in a full circle. And also the cells that are cut by a circle of radius 24 (the light blue and dark blue squares), there are 47 of these in a quadrant, so 188 in a full circle.

    Enigma 1759 - Solution

    • Jim Randell 25 July 2013 at 10:20 am

      Here’s a longer, but faster Python solution. It considers squares cut by an eighth of the circle, and determines these by following the circumference. It runs in 39ms.

      from itertools import product
      from enigma import irange, compare, printf
      
      # check where the square with diagonal (x, y) - (x+1, y+1)
      # is in relation to the circle x^2 + y^2 = r2
      def check(x, y, r2):
        (a, b) = (x ** 2 + y ** 2, (x + 1) ** 2 + (y + 1) ** 2)
        return compare(a, r2) + compare(b, r2)
      
      # deltas to move onto next line
      C = ((1, 0), (0, -1), (-1, -1))
      
      # return the numbers of cells cut by a circle of radius r
      # by considering one eighth of the circle
      def cut(r):
        r2 = r ** 2
        (x, y, n) = (0, r - 1, 0)
        while not(x > y):
          c = check(x, y, r2)
          if c == 0: n += (4 if x == y else 8)
          (xd, yd) = C[c]
          x += xd
          y += yd
        return n
      
      # find a radius r where r-1 cuts more cells
      n0 = 0
      for r in irange(1, 49):
        n = cut(r)
        printf("r={r} n={n} {s}", s=('*** SOLUTION ***' if n < n0 else ''))
        n0 = n
      
      • Jim Randell 26 July 2013 at 12:59 pm

        Here’s my final variation on the circumference following plan. It also considers 1/8 of the circle, but it accumulates chunks of cut squares by using Pythagoras’ Theorem to determine where the circumference leaves a row. It runs in 38ms.

        This code also includes a determination of [[ int(sqrt(n)) ]] using Newton’s Method, because I’m thinking of replacing the [[ is_square() ]] function in the enigma.py library with a similar implementation so that it works on arbitrarily large integers. (The current implementation will fail when the conversion of int to float loses precision (around 2^53)). Although with the size of numbers we’re talking about in this puzzle nipping into floats would be fine.

        from enigma import irange, printf
        
        # calculate int(sqrt(n)) using Newton's method
        def isqrt(n):
          a = n
          while True:
            b = (a + n // a) // 2
            if not(b < a): break
            a = b
          return a
        
        # return the numbers of cells cut by a circle of radius r
        # by considering one eighth of the circle
        def cut(r):
          (x, y, n, s2) = (0, r - 1, 0, 0)
          while True:
            # how many squares in row y does the circle cut
            s2 += 2 * y + 1
            s = isqrt(s2)
            w = int(s * s != s2) # does it miss the grid intersection?
            # are we done?
            if not(s < y):
              n += y - x
              return 8 * n + 4
            # move on to the next row
            n += s + w - x
            y -= 1
            x = s
        
        # find a radius r where r-1 cuts more cells
        n = 0
        for r in irange(1, 49):
          (n, n0) = (cut(r), n)
          printf("r={r} n={n} {s}", s=('*** SOLUTION ***' if n < n0 else ''))
        
  2. Brian Gladman 24 July 2013 at 11:06 pm

    Pretty similar in principle.

    from math import floor, ceil
    
    # within a quadrant of the circle (from the point x = 0, y = r to
    # the point x = r, y = 0),  consider the column of cells with its
    # left and right hand sides at x and x + 1 respectively
    def count_cells(r):
      # y is vertical coordinate at which the circle crosses into this column
      cnt, y = 0, r
      for x in range(r):
        # add all the cells below and including that crossed by the circle
        cnt += ceil(y)
        # find the y value at which the circle leaves this column on the right
        y = (r ** 2 - (x + 1) ** 2) ** (1 / 2)
        # subtract all the the cells below that crossed by the circle
        cnt -= floor(y)
      return 4 * cnt
    
    fs = 'Circle of radius {:d} is crossed {:d} times.'
    c1 = 0
    for r in range(1, 50):
      c0, c1 = c1, count_cells(r)
      if c1 < c0:
        print(fs.format(r - 1, c0))
        print(fs.format(r, c1))
    
  3. Brian Gladman 25 July 2013 at 9:04 am

    I realised that the approach I used above could be analysed further to give a count based on counting pythagorean triples.

    from math import floor, ceil
    
    # within a quadrant of the circle (from the point x = 0, y = r to
    # the point x = r, y = 0),  consider the column of cells with its
    # left and right hand sides at x and x + 1 respectively
    def count_cells1(r):
      # y is vertical coordinate at which the circle crosses into this column
      cnt, y = 0, r
      for x in range(r):
        # add all the cells below and including that crossed by the circle
        cnt += ceil(y)
        # find the y value at which the circle leaves this column on the right
        y = (r ** 2 - (x + 1) ** 2) ** (1 / 2)
        # subtract all the the cells below that crossed by the circle
        cnt -= floor(y)
      # return value for the whole circle
      return 4 * cnt
    
    # We see from the approach above that each of the r - 1 internal
    # vertical grid lines adds ceil(y) - floor(y) to the count, i.e.
    # 1 unless y is an integer. Since the first column adds r to the
    # count, the overall count will be 2 * r - 1 - x, where x is the
    # number of internal grid lines on which y is integer
    def count_cells2(r):
      cnt = 0
      # count pythagorean triples
      for x in range(1, r):
        y2 = r ** 2 - x ** 2
        cnt += 1 if round(y2 ** (1 / 2)) ** 2 == y2 else 0
      return 4 * (2 * r - 1 - cnt)
    
    fs = 'Circle of radius {:d} is crossed {:d} times.'
    c1 = 0
    for r in range(1, 50):
      c0, c1 = c1, count_cells2(r)
      if c1 < c0:
        print(fs.format(r - 1, c0))
        print(fs.format(r, c1))
    
    • Jim Randell 25 July 2013 at 2:59 pm

      I was thinking about doing an implementation based on Pythagorean triples, but I see you’ve saved me the bother. Nice work!

      • Brian Gladman 25 July 2013 at 3:44 pm

        It is also pretty fast in its simplest form:

        sq = set(x * x for x in range(1, 50))
        def count_cells(r):
          cnt = sum(1 for x in range(1, r) if r * r - x * x in sq)
          return 4 * (2 * r - 1 - cnt)
        c1 = 0
        for r in range(1, 50):
          c0, c1 = c1, count_cells(r)
          if c1 < c0:
            print(c1, 'cells')
        

        I made made real mess of counting crossings in my first (unpublished) attempt so I was relieved to find my first formulation above. But I should have realised earlier that this could be pushed further. And, even then, count_cells2() is not my best effort at producing efficient code either. But it didn’t look too bad until I looked at alternatives – Python is so often counterintuitive when it comes to the time code takes to run.

      • Jim Randell 28 July 2013 at 4:38 pm

        A variation on the theme. I used the Pythagorean triple generator from Enigma 1708 to count the hypotenuses up front, then the definition of cut() becomes very simple.

        from enigma import irange, sqrt, printf
        
        # max radius
        import sys
        R = 49 if len(sys.argv) < 2 else int(sys.argv[1])
        
        # generate pythagorean triples (including non-primitive ones)
        def generate():
          a = 0
          while True:
            a += 2
            n = (a * a) // 2
            s = int(sqrt(n))
            for b in irange(s, 1, step=-1):
              (c, r) = divmod(n, b)
              if r > 0: continue
              yield (a + b, a + c, a + b + c)
        
        # count pythagorean hypotenuses up to R (OEIS A046080)
        Ph = [0] * (R + 1)
        for (x, y, h) in generate():
          if x > R: break
          if not(h > R): Ph[h] += 1
        
        # return the numbers of cells cut by a circle of radius r
        def cut(r):
          return 8 * (r - Ph[r]) - 4
        
        # find a radius r where r-1 cuts more cells
        n = 0
        for r in irange(1, R):
          (n, p) = (cut(r), n)
          printf("r={r} n={n} {s}", s=('*** SOLUTION ***' if n < p else ''))
        
  4. ahmet çetinbudaklar 27 July 2013 at 6:40 pm

    Radius runs from 1cm to 49 cm and accordingly each circle cuts a number of 1cmx1cm cells as follows except when certain circles intersect the cell corners at(x,y-y,x):

    Radius(cm)                   Number of cells
                                             (8r-4)
        1                                        4
        2                                       12 
        3                                       20
        4                                       28
        5(3,4-4,3)                         28
        6                                       44
        7                                       52
        8                                       60
        9                                       68     
       10(6,8-8,6)                        68
       11                                      84
       12                                      92
       13(5,12-12,5)                     92
       14                                      108        
       15(9,12-12,9)                     108
       16                                       124 
       17(8,15-15,8)                     124
       18                                       140  
       19                                       148
       20(12,16-16,12)                 148   
       21                                       164
       22                                       172
       23                                       180
       24                                       188
       25(7,24-24,7/15,20-20,15) 180
       26(10,26-26,10)                 196
       27                                       212
       28                                       220
       29(20,21-21,20)                 220,
       30(18,24-24,18)                 228  
       31                                      244
       32                                      252    
       33                                      260
       34(16,30-30,16)                260
       35(21,28-28,21)                268
       36                                      284
       37(12,35)                          284
       38                                     300
       39(15,36)                         300
       40(24,32)                         308                                 
       41(9,40)                           316
       42                                    332
       43                                    340
       44                                    348
       45(29,36-36,29)              348
       46                                    364
       47                                    372
       48                                    380
       49                                    388

    This table gives us the unique solution easily.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

%d bloggers like this: