# 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.

• 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 `float`s 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

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.

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