Enigmatic Code

Programming Enigma Puzzles

Enigma 409: Hands and feet

From New Scientist #1559, 7th May 1987 [link]

There are six footpaths through our extensive local woods, one linking each pair of four large oaks. I decided to go on a long walk starting at one of the oaks, keeping to the footpaths, ending back where I started, covering each of the footpaths exactly twice, and never turning around part-way along a path.

Whenever I was at an oak my watch showed an exact number of minutes, and in the previous 30 seconds up to and including arriving at the oak or in the 30 seconds after leaving the oak the hour and minute hands of the watch were coincident.

I set out sometime after 6am and I was back home before midnight on the same day. I walked at a steady pace from start to finish.

What time was I at the oak at the start of my round walk, and what time did I get back there at the end of the day?

[enigma409]

Advertisements

6 responses to “Enigma 409: Hands and feet

  1. Jim Randell 11 August 2017 at 7:01 am

    Another puzzle about coincident clock hands (See: Enigma 1761).

    At first I thought there must be multiple solutions to this problem.

    We can find the times to the nearest minute when the hour and minute hands of the watch are coincident in the required time period. There are 16 of them:

    06:33, 07:38, 08:44, 09:49, 10:55, 12:00, 13:05, 14:11,
    15:16, 16:22, 17:27, 18:33, 19:38, 20:44, 21:49, 22:55.

    And the walk has 12 legs, so if each leg takes about the same time and we don’t stop anywhere along the way (no stops are mentioned), we could have any of the following start and finish times:

    06:33 – 19:38
    07:38 – 20:44
    08:44 – 21:49
    09:49 – 22:55

    It’s also possible that one path could take about twice as long to traverse as the other paths, which would mean we could have the following possible start and finish times:

    06:33 – 21:49
    07:38 – 22:55

    One way to reduce the number of possible answers is to assume that the time taken to traverse a path must be exactly the same both times it is traversed, even if it is traversed in the opposite direction.

    Using this interpretation of the text I was able to write a program to try all possible routes and determine that there was, indeed, a unique start and end time that satisfied the puzzle.

    This Python 3 program determines the times (to the nearest minute) when the hands are coincident, and then uses the differences between these times to find routes where paths are always traversed in the same time. It runs in 94 ms.

    from collections import Counter
    from enigma import irange, tuples, update, printf
    
    # times of exact coincidence between 6am and midnight (to the nearest minute)
    ts = list()
    for n in irange(6, 21):
      t = (1440 * n + 11) // 22 # = int(720n/11 + 1/2)
      (h, m) = divmod(t, 60)
      printf("n={n}, h={h} m={m}")
      ts.append(t)
    
    # compute the differences
    ds = list(b - a for (a, b) in tuples(ts))
    
    # label the trees, so that paths can be labelled with t1 + t2
    trees = (1, 2, 4, 8)
    
    # path - record the order the trees are visited in
    # ds - durations to traverse paths
    # double - which path take two durations
    # r - record time taken to travese a path
    # (0 = not yet traversed, n = traversed once, -n = traversed twice)
    def solve(path, ds, double, r=dict()):
      # are we done?
      if len(path) == 13:
        yield path
      else:
        t0 = path[-1]
        # move to the next tree
        for t1 in trees:
          if t1 == t0: continue
          k = t0 + t1
          v = r.get(k, 0)
          if v == 0:
            # first traversal of this path
            if k == double:
              if len(ds) > 1:
                yield from solve(path + [t1], ds[2:], double, update(r, [(k, ds[0] + ds[1])]))
            else:
              yield from solve(path + [t1], ds[1:], double, update(r, [(k, ds[0])]))
          elif v > 0:
            # second traversal of this path
            if k == double:
              if len(ds) > 1 and v == ds[0] + ds[1]:
                yield from solve(path + [t1], ds[2:], double, update(r, [(k, -v)]))
            else:
              if v == ds[0]:
                yield from solve(path + [t1], ds[1:], double, update(r, [(k, -v)]))
    
    # record start time and end time
    r = Counter()
    
    # d = a path that take twice as long to traverse as the rest
    # (this is either one of the first paths we travel or one of the others)
    # n = number of duration steps required
    for (d, n) in ((0, 12), (1 + 2, 14), (2 + 4, 14)):
      # possible start times
      for i in irange(0, len(ds) - n):
        # start from tree 1
        for s in solve([1], ds[i:], d):
          start = ts[i]
          end = ts[i + n]
          printf("d={d} i={i} s={s}, start={start} end={end}")
          r[(start, end)] += 1
    
    # output solutions
    for ((start, end), n) in r.most_common():
      (h1, m1) = divmod(start, 60)
      (h2, m2) = divmod(end, 60)
      printf("{h1:02d}:{m1:02d} - {h2:02d}:{m2:02d} [{n} solutions]")
    

    Solution: The walk started from the first oak at 6:33am, and returned to it (for the final time), completing the walk, at 9:49pm.

    One possible itinerary is:

    path AB takes 65m to traverse
    path AC takes 66m to traverse
    path AD takes 65m to traverse
    path BC takes 131m to traverse
    path BD takes 66m to traverse
    path CD takes 65m to traverse

    06:33 – start at tree A
    07:38 – arrive at tree B, via path AB (65m)
    09:49 – arrive at tree C, via path BC (131m)
    10:55 – arrive at tree A, via path AC (66m)
    12:00 – arrive at tree D, via path AD (65m)
    13:05 – arrive at tree A, via path AD (65m, again, but in the other direction)
    14:11 – arrive at tree C, via path AC (66m, again, but in the other direction)
    15:16 – arrive at tree D, via path CD (65m)
    16:22 – arrive at tree B, via path BD (66m)
    18:33 – arrive at tree C, via path BC (131m, again)
    19:38 – arrive at tree D, via path CD (65m, again)
    20:44 – arrive at tree B, via path BD (66m, again)
    21:49 – arrive at tree A, via path AB (65m, again, but in the other direction)

    I was close to marking this puzzle as flawed, and I still think it could have been worded better.

  2. Hugh Casement 11 August 2017 at 9:54 am

    I too must have found multiple solutions: when I added this one to my own archive a few years ago I modified the wording to “I set out after 7 and got home in the evening” — which is somewhat more probable for a full day’s outing, not even stopping for lunch.
    Definitely flawed!

    • Hugh Casement 11 August 2017 at 12:56 pm

      I had assumed the layout of paths to be a bit like a four-leafed clover, the four outer arcs each the same length as a diagonal.  That’s not very likely, so I’d like to suggest the following modification to the wording:

      [diagram showing a rhombus with shorter diagonal equal in length to each of the sides]

      >>
      At each corner of the forest is a magnificent oak tree.  There are six footpaths, one linking each pair of oaks.  At the weekend I went on a long hike, starting at an oak and finishing at the same oak, keeping to the paths and going along each one exactly twice (in one direction or the other).  Each time I was on the long diagonal I stopped for a while to eat part of my picnic lunch, so that the distance AC (in either direction) took me twice as long as each of the other paths, including BD.  Otherwise I kept up a steady pace all day.  I always went straight across at the central crossing point.

      Whenever I was at an oak I noticed that the minute hand of my watch coincided with the hour hand.  I set out soon after 6 in the morning and got home by 22:15.
      To the nearest minute, what were my starting and finishing times (at the oaks, I mean)?
      <<

      So in my version it's AC that takes 131 minutes.
      And by the way in English we say turn round, not "around".

      • Jim Randell 19 August 2017 at 11:30 am

        For me the confusion arose because I don’t think it is sufficient to say the paths were “walked at a steady pace”, if we require the time taken to traverse a path to be exactly the same (to the second) in both directions. Especially if the path is uphill in one direction. I think it would be quite consistent to walk from A to B in 66 minutes, and back from B to A in 65 minutes and still be walking at “a steady pace”.

        Instead I would phrase the question using an object being transported at a steady pace by a conveyance that ensures journey times between stations are always exactly the same. Here is a rephrasing on the puzzle:

        At the factory there are four workstations which are interlinked by six conveyor belts (one for each pair of stations) that allow items to travel between each of the stations. The time taken for items to travel between stations is an exact number of minutes, and as each of the six belts forms a loop the travel time is exactly the same in both directions. To make life a bit more interesting the workers at the workstations have a fluffy toy which rides the conveyor belts. When the toy arrives at a workstation the worker can move it to one of the other belts or leave it on the belt it is on.

        One day the fluffy toy started it’s journey from one workstation at an exact number of minutes past the hour, and so during its entire journey, it arrived at each workstation it visited at an exact number of minutes past the hour. Furthermore during the 30 seconds before or the the 30 seconds after arriving at a workstation the hour and minute hands of the big factory clock were exactly coincident. The toy travelled on each of the six conveyor belts between stations exactly twice during the journey and ended up at the same station it started at. It spent the whole time on the conveyor belts moving between stations. The first shift of the day starts at 6am, and the final shift finishes at midnight.

        What time did the toy set out from the first workstation? And what time did it arrive back at the end of its journey?

        This has a unique answer that is the same as the published answer for the original puzzle, and doesn’t require any adjustment of the possible time windows involved.

        Here is a recursive Python 3 program that finds the solution in 150ms. It’s a bit neater than my original program in that it doesn’t require any analysis or special cases to account for the fact that one of the journeys between stations may take (roughly) twice as long as the others.

        from collections import Counter
        from enigma import irange, update, find, printf
        
        # times of exact coincidence between 6am and midnight (to the nearest minute)
        times = list((1440 * n + 11) // 22 for n in irange(6, 21))
        
        # label the nodes, so that segments can be labelled with n1 + n2
        nodes = (1, 2, 4, 8)
        
        # find a loop of length 13 that traverses each segment twice
        # ns - sequence of nodes visited (so far)
        # ts - sequence of times the nodes are visited (so far)
        # ss - remaining potential times for visiting nodes
        # ds - allocated durations for individual segments
        # ps - sequence of segments traversed (so far)
        def solve(ns, ts, ss, ds, ps):
          # are we done?
          if len(ns) == 13:
            if ns[0] == ns[-1]:
              yield (ns, ts)
          # otherwise, can we complete the itinerary?
          elif len(ts) + len(ss) > 12:
            (n0, t0) = (ns[-1], ts[-1])
            # move to the next node
            for n in nodes:
              # must move to a different node
              if n == n0: continue
              # visit new nodes in order
              if n not in ns and n >> 1 not in ns: break
              # key for this segment
              k = n0 + n
              # don't use segments more than twice
              if ps.count(k) > 1: continue
              # does this segment already have a duration
              d = ds.get(k, None)
              if d is not None:
                # would we arrive at a valid time?
                t = t0 + d
                i = find(ss, t)
                if i != -1:
                  yield from solve(ns + [n], ts + [t], ss[i + 1:], ds, ps + [k])
              else:
                # choose an arrival time (which fixes a duration for this segment)
                for (i, t) in enumerate(ss):
                  yield from solve(ns + [n], ts + [t], ss[i + 1:], update(ds, [(k, t - t0)]), ps + [k])
        
        # record start time and end time
        r = Counter()
        
        # consider possible start times at the first node
        # (a full itenarary has 13 times in it)
        for i in irange(0, len(times) - 13):
          for (ns, ts) in solve([nodes[0]], [times[i]], times[i + 1:], dict(), []):
            printf("{ns} {ts}")
            r[(ts[0], ts[-1])] += 1
        
        # output solutions
        for ((start, end), n) in r.most_common():
          (h1, m1) = divmod(start, 60)
          (h2, m2) = divmod(end, 60)
          printf("{h1:02d}:{m1:02d} - {h2:02d}:{m2:02d} [{n} solutions]")
        
  3. Brian Gladman 16 August 2017 at 6:41 am
    from itertools import combinations, count
    from collections import defaultdict
    
    # map of the paths between the four oaks
    con = {x:set(range(4)).difference([x]) for x in range(4)}
    
    # find circular paths starting at <node> of length <length> and 
    # passing the four oaks with each path traversed <count> times;
    # return the nodes and paths on the path in <nodes> and <paths>
    def find_path(node, length, count, con, nodes=[], paths=[]):
      
      # add the last node to the path
      nodes = nodes + [node]
      ln = len(nodes)
      # add the last path to the paths
      if ln > 1:
        paths = paths + [tuple(sorted((nodes[-2], nodes[-1])))]
        
      # have we traversed <length> paths (i.e. <length> + 1 nodes)
      if ln == length + 1:
        # if the path is circular 
        if nodes[0] == nodes[-1]:
          # return this solution
          yield  nodes, paths
        return  
      
      # consider possible paths from this node
      for n in con[node]:
        # except that we entered on
        if n != nodes[-1]:
          # ensure that we traverse a path at most <count> times
          np = tuple(sorted((nodes[-1], n)))
          if paths.count(np) < count:
            # continue on to the next path 
            yield from find_path(n, length, count, con, nodes, paths) 
    
    # store possible paths for the walk
    paths = []
    for n, p in find_path(0, 12, 2, con):
      paths.append(p)
    
    # at time t minutes the minute and hour hands are at 6.t
    # and t/2 degrees respectively;  the hands will hence be
    # coincident  when 6.t - t/2 is a multiple of 360 giving 
    # t = 720.n / 11; in general this will not be an integer
    # but we are looking an integer t' such that t is in the
    # range t' - 1/2 < t < t' + 1/2, that is,  t' = round(t)
    
    # find the possible times that the oaks can be passed
    tms = []
    for n in count():
      tm = round(720 * n / 11)
      if tm >= 1440:
        break
      if tm >= 360:
        tms.append(tm)
    
    sols = set()
    # there are 6 paths between the 4 oaks, each path being
    # traversed twice with a total of 13 visits to the oaks
    # - select 13 times for these visits
    for c in combinations(tms, 13):
      # find the 12 times to traverse the paths
      dif = [y - x for y, x in zip(c[1:], c)]
      # since each path is traversed twice, the times
      # to walk the paths must occur in pairs
      if all(dif.count(v) % 2 == 0 for v in set(dif)):
        # check if this sequence of times matches a possible path;
        # the positions of pairs of times must match the positions
        # of the same path in the sequence of paths on the walk 
        for p in paths:
          p2t = defaultdict(set)
          for pp, dd in zip(p, dif):
            p2t[pp].add(dd)
          if all(len(x) == 1 for x in p2t.values()):
            break
        else:
          continue
        sols.add((c[0], c[-1]))
        print(dif)
    
    # output times <t> in minutes in hours:minutes AM/PM format
    def tm(t):
      h, m = divmod(t, 60)
      s, h = ('AM', h) if h < 12 else ('PM', h - 12)
      return f'{h}:{m} {s}'
      
    for s, f in sols:
      print(f'\nThe walk started at {tm(s)} and finsihed at {tm(f)}.')
    
  4. Tessa Fullwood 28 August 2017 at 7:38 pm

    I like the rewording with the toys. The final shift must end before midnight, (or the factory workers turn into pumpkins). I agree that Brian is right that there are multiple solutions. Given the times that the clock hands are coincident and hence the arrival times at each oak / workstation (node) have already been calculated, then there are 8 possible legs of length 65 minutes and 7 possible legs of length 66 minutes. Each leg must be traversed twice, so that there must be an even number of traverses of each leg length. The solution with 6 x 66 minutes and 6 x 65 minutes can be eliminated since the sequence then must contain two adjacent legs of 66 minutes. This leaves a solution with 6 x 65 minutes, 4 x 66 minutes and 2 x 131 minutes. This can only be achieved beginning at 6:33 and ending at 21:49. The solution is correct if one path can be traced.
    In the case of the python programme the algorithm has solved the problem and on top of that, calculated a multiple of paths.

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: