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

### 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):
if all(len(x) == 1 for x in p2t.values()):
break
else:
continue
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.

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