### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,367)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (48)
- site news (58)
- tantalizer (94)
- teaser (7)

### Site Stats

- 233,129 hits

Programming Enigma Puzzles

24 July 2013

Posted by on **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]

%d bloggers like this:

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.

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.

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.

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 theenigma.pylibrary 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.Pretty similar in principle.

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

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

It is also pretty fast in its simplest form:

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.

A variation on the theme. I used the Pythagorean triple generator from

Enigma 1708to count the hypotenuses up front, then the definition of`cut()`

becomes very simple.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):

This table gives us the unique solution easily.