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]

Advertisements

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
      
      # start with 2 steps, and record (x, y, distance)
      (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))
              ds.add(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:
            next_set.add((xn, yn, i))
      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
    

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: