Sunday Times Teaser 3083 – Village Signposts

by BRG on October 23, 2021

by Colin Vout

Published Sunday October 24 2021 (link)

Inside a shed I saw where the council was preparing signposts for seven neighbouring villages. Between any two villages there is at most one direct road, and the roads don’t meet except at village centres, where the signposts are to stand. The arms were all affixed, and labelled except for one name to be completed on each. The names in clockwise order on each were as follows:

Barton, Aston, ?;
Barton, Grafton, ?;
Carlton, Forton, Eaton, ?;
Grafton, Aston, ?;
Dalton, Grafton, Eaton, ?;
Barton, Forton, Carlton, ?;
Dalton, Aston, ?

Starting at Dalton, I walked along roads, taking the road furthest rightwards at each village and returning to Dalton. I chose the first road so that I visited as many other villages as possible with this method.

In order, what were the other villages I visited?

From → Uncategorized

One Comment Leave one →

Brian Gladman permalink

This solution needs the NetworkX library for determining whether the road arrangement is planar.


import networkx as nx

signs = ('BA', 'BG', 'CFE', 'GA', 'DGE', 'BFC', 'DA')

# follow a path from village to village starting at <cv>
# and taking the rightmost path on entering each village
def path(cv, v2s, seq=()):
  if cv in seq:
    yield seq + (cv,)
  else:
    pv_ix = v2s[cv].index(seq[-1])
    nv = v2s[cv][(pv_ix - 1) % len(v2s[cv])]
    yield from path(nv, v2s, seq + (cv,))

# allocate different villages to each sign
# avoiding villages already on the signs
def arrange(sgns, vs=set('ABCDEFG'), seq=()):
  if not sgns:
    yield seq
  else:
    for v in set('ABCDEFG').difference(sgns[0]).intersection(vs):
      yield from arrange(sgns[1:], vs.difference([v]), seq + (v,))

#  consider possible 'mystery' villages on the signposts
for mp in arrange(signs):
  
  # add these villages to the signposts
  csigns = tuple(s + m for s, m in zip(signs, mp))

  # consider possible assignments of signposts to villages
  for vl in arrange(csigns):
  
    # map villages to signposts
    v2s = dict(zip(vl, csigns))
    
    # ensure all roads are bi-directional
    if not all(all(v in v2s[x] for x in cs) for v, cs in v2s.items()):
      continue

    # check that the arrangement is planar
    g = nx.PlanarEmbedding()
    for v, sgn in v2s.items():
      for i, s in enumerate(sgn):
        g.add_half_edge_cw(v, s, sgn[i - 1] if i else None)
    try:
      g.check_structure()
    except:
      continue
    
    # output the map from villages to signposts
    print(f"{', '.join(f'{v} -> {s}' for v, s in sorted(v2s.items()))}")
    # find the longest path around the villages starting at D
    max_len = 0
    sol = None  
    for nv in v2s['D']:
      for p in path(nv, v2s, ('D',)):
        if len(p) > max_len:
          max_len = len(p)
          sol = p
    print(f"Order of villages visited {' -> '.join(p)}.")
    
    # draw the network (but not in planar form)
    # import matplotlib.pyplot as plt
    # nx.draw(g)
    # plt.show()

import networkx as nx

signs = ('BA', 'BG', 'CFE', 'GA', 'DGE', 'BFC', 'DA')

# follow a path from village to village starting at <cv>

# and taking the rightmost path on entering each village

def path(cv, v2s, seq=()):

if cv in seq:

yield seq + (cv,)

else:

pv_ix = v2s[cv].index(seq[-1])

nv = v2s[cv][(pv_ix - 1) % len(v2s[cv])]

yield from path(nv, v2s, seq + (cv,))

# allocate different villages to each sign

# avoiding villages already on the signs

def arrange(sgns, vs=set('ABCDEFG'), seq=()):

if not sgns:

yield seq

else:

for v in set('ABCDEFG').difference(sgns[0]).intersection(vs):

yield from arrange(sgns[1:], vs.difference([v]), seq + (v,))

# consider possible 'mystery' villages on the signposts

for mp in arrange(signs):

# add these villages to the signposts

csigns = tuple(s + m for s, m in zip(signs, mp))

# consider possible assignments of signposts to villages

for vl in arrange(csigns):

# map villages to signposts

v2s = dict(zip(vl, csigns))

# ensure all roads are bi-directional

if not all(all(v in v2s[x] for x in cs) for v, cs in v2s.items()):

continue

# check that the arrangement is planar

g = nx.PlanarEmbedding()

for v, sgn in v2s.items():

for i, s in enumerate(sgn):

g.add_half_edge_cw(v, s, sgn[i - 1] if i else None)

try:

g.check_structure()

except:

continue

# output the map from villages to signposts

print(f"{', '.join(f'{v} -> {s}' for v, s in sorted(v2s.items()))}")

# find the longest path around the villages starting at D

max_len = 0

sol = None

for nv in v2s['D']:

for p in path(nv, v2s, ('D',)):

if len(p) > max_len:

max_len = len(p)

sol = p

print(f"Order of villages visited {' -> '.join(p)}.")

# draw the network (but not in planar form)

# import matplotlib.pyplot as plt

# nx.draw(g)

# plt.show()

Sunday Times Teaser 3083 – Village Signposts

by Colin Vout

Published Sunday October 24 2021 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta