# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1774: March of the ants

From New Scientist #2942, 9th November 2013 [link]

A vertical piece of string is attached to a flat horizontal sheet of chicken wire, which forms a lattice of regular hexagons with 1-centimetre-long sides. The string is attached at one of the joints between three hexagons. Six ants marched down the string and along the wire, always moving further from their starting point on the wire. After a while, they had all marched the same distance along the wire (which was a whole number of centimetres less than 20 centimetres), but they were all at different straight-line distances from the starting point.

If I told you one of these straight-line distances, you would be able to calculate the straight-line distances the other five ants were from the starting point.

How far had the ants marched along the wire?

[enigma1774]

### 4 responses to “Enigma 1774: March of the ants”

1. Jim Randell 6 November 2013 at 7:03 pm

Here’s a Python 3 solution. It runs in 234ms. I’ll probably try another version as I have a natural dislike for floats (although I’m sure 64-bit floats are up to the job for this puzzle).

```from collections import defaultdict
from enigma import sqrt, hypot, irange, printf

r32 = sqrt(3) / 2

# deltas for even and odd steps
deltas = (
( (r32, 0.5), (0, -1), (-r32, 0.5) ),
( (0, 1), (r32, -0.5), (-r32, -0.5) ),
)

# march increasing distances from (x0, y0) for n steps
def march(x0, y0, n, d0):
if n == 0:
yield (x0, y0, d0)
else:
for (xd, yd) in deltas[n % 2]:
(x1, y1) = (x0 + xd, y0 + yd)
d1 = hypot(x1, y1)
if d0 < d1:
yield from march(x1, y1, n - 1, d1)

# consider less than 20 steps
for n in irange(0, 19):
r = defaultdict(int)
for (x, y, d) in march(0, 0, n, 0):
r[round(d, 6)] += 1
# look for 6 distinct distances
if len(r.keys()) == 6:
printf("n={n} {ds}", ds=sorted(r.keys()))
```

Solution: The ants had marched 11cm along the wire.

• Jim Randell 7 November 2013 at 10:55 am

We can remove the need to use floats by using a co-ordinate system where the axes are 60° apart (instead of the more usual 90°). The distance metric is given by the cosine rule, and I only track the squares of the distances to keep things in the integers (although I do calculate the actual distances in order to display the solution). This Python program runs in 40ms.

```from enigma import sqrt, printf

# using a co-ordinate system where the axes are 60 degrees apart

# deltas for even and odd steps
deltas = (
( (0, +1), (+1, -1), (-1, 0) ),
( (+1, 0), (0, -1), (-1, +1) ),
)

# distance metric (cosine rule)
def distance2(x, y):
return x * x + y * y + x * y

(n, ps) = (2, [(1, 1, 3)])
while n < 19:
(n, ps2, ds) = (n + 1, list(), set())
# march from each point
for (x0, y0, d0) in ps:
for (xd, yd) in deltas[n % 2]:
(x1, y1) = (x0 + xd, y0 + yd)
d1 = distance2(x1, y1)
if d0 < d1:
ps2.append((x1, y1, d1))
# are there exactly 6 different distances from the origin?
if len(ds) == 6:
ds = sorted(ds)
rds = list(round(sqrt(d), 6) for d in ds)
printf("n={n} ds={rds} ds2={ds}")
ps = ps2
```
2. Brian Gladman 7 November 2013 at 9:16 am

Tidied up version

```# the x and y distances travelled for a direction of 60.n degrees
xi = (0, 1,  1,  0, -1, -1)    # in 1/2 cm units
yi = (2, 1, -1, -2, -1,  1)    # in sqrt(3)/2 cm units

# For an input list of possible ant positions at step n,  calculate
# the possible ant positions at step n + 1. The individual elements
# in xya_set are (x, y, a) where (x, y) is the current ant position
# and 'a' is angle at which the ant enters this grid node (in units
# of 60 degrees)

def next_set(xya_set):
# a set to hold the next ant positions
next_set = set()
# for each current ant position
for x, y, a in xya_set:
# the squared distance from the starting point
lsq = 3 * x * x + y * y
# move the ant along paths 60 degrees to the left and right
for i in (a - 1, a + 1):
xn, yn = x + xi[i % 6], y + yi[i % 6]
# add this move if it is further from the origin
if 3 * xn * xn + yn * yn > lsq:
return next_set

# set the first move from (0, 0) to (0, 2) at angle zero from north
xya_set = {(0, 2, 0)}
# for ants moving moving up to 19 cm along the wire
for n in range(2, 20):
# compute the list of possible ant positions at step n
xya_set = next_set(xya_set)
# compute the set of squared distances from the origin
dis = {3 * x * x + y * y for x, y, a in xya_set}
# there must be exactly six possible positions since any more
# would prevent the six being determined given any one of them
if len(dis) == 6:
t = tuple(sorted(round(0.5 * x ** 0.5, 2) for x in dis))
print('The ants each move {} cm along the wire {}.'.format(n, t))
```
3. arthurvause 8 November 2013 at 11:02 am

Another variation on the same theme, restricting the points reached to the quadrant where x and y coordinates are non-negative, and not considering steps that would always reduce the distance from the start point.

```points = set( ( (0.0, 0.0),))
root3over2 = (3**0.5)*0.5
dist=1

while dist < 20:
points_next = set()
for (x,y) in points:
d2 = x**2+y**2
if (2*x)%3==0:
neighbours = set( ((x+1.0,y),(x-0.5,y+root3over2)))
elif (2*x)%3==2:
neighbours = set( ((x+0.5,y+root3over2),(x+0.5,y-root3over2)))
points_next|=  set(( (x,y) for (x,y) in neighbours
if x**2+y**2 > d2 and x>=0.0 and y>=0.0))
distances2 = set(round(x**2+y**2,10) for (x,y) in points_next)
if len(distances2)==6:
print dist,"cm travelled",  sorted([ x**0.5 for x in distances2])

points = points_next
dist+=1
```

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