Enigmatic Code
Programming Enigma Puzzles
Enigma 543: Spires point the way
Posted by on 30 March 2020
From New Scientist #1695, 16th December 1989 [link]
The quiet town of Spirechester is divided into nine square parishes as shown on the map. Each parish church has its spire precisely at the centre of the parish, and these are marked by crosses on the map.
The churches are named after St Agnes, St Brigid, St Cecilia, St Donwen, St Etheldreda, St Felicity, St Genevieve, St Helen and St Isabel. Each spire is topped by a weather vane which has, instead of a cock, the initial letter of its saint’s name.
Recently I walked in the meadows which surround the town and took a number of photos from different positions. Fortunately, no spire was ever hidden by another spire and the wind was such that the weather vane letters were clearly visible. However, I was not sufficiently distant from the town to capture all nine spires and, in fact, each photo contains just five spires. The orders of the spires of the photos, reading from left to right, were GEIAC, EACHD, EACDH, AECHD, IFCGB.
Starting with A (for St Agnes) list the eight churches in clockwise order around the outside of the square.
[enigma543]
I supposed the walk was a circular walk at a fixed distance from the central church.
The following Python program performs the walk, stopping at defined intervals and determining the bearings for each church (relative to the central church). We collect the different left-to-right sequences of churches.
We then consider possible assignments of labels to positions, and look to see if the photos can be constructed.
Placing the central church at the origin, and the other churches at the 8 lattice points surrounding it, we find that a walk at a distance of 5 units, stopping every degree is sufficient to collect the required views.
This Python program runs in 1.8s.
Run: [ @repl.it ]
from math import radians, sin, cos, atan2 from enigma import unpack, subsets, irangef, tuples, join, chunk, printf # the positions of the churches pos = [ (-1, 1), (0, 1), (1, 1), (-1, 0), (0, 0), (1, 0), (-1, -1), (0, -1), (1, -1), ] # radius of the walk r = 5 # return the bearing of (x, y) from (x0, y0) bearing = lambda x0, y0, x, y: atan2(x - x0, y - y0) # collect different views of all churches views = set() # consider possible angles inc = 1 for a in irangef(inc, 360, step=inc): # consider viewpoint at (r, a) t = radians(a) (x, y) = (r * cos(t), r * sin(t)) # bearing on the central church b0 = bearing(x, y, 0, 0) # bearings on all the churches bs = list(bearing(x, y, x1, y1) - b0 for (x1, y1) in pos) view = tuple(i for (i, b) in sorted(enumerate(bs), key=unpack(lambda i, b: b))) # drop any views where the churches are too close together if any(abs(bs[i] - bs[j]) < 0.01 for (i, j) in tuples(view)): continue views.add(view) # possible photos (restricted views) photos = ("GEIAC", "EACHD", "EACDH", "AECHD", "IFCGB") # place A at 0, and consider the values for the remainder for s in subsets("BCDEFGHI", size=len, select="P"): s = ("A",) + s # determine possible views vs = list(join(s[i] for i in v) for v in views) # find a view for each picture if all(any(p in v for v in vs) for p in photos): printf("{s}", s=join((join(x, sep=" ") for x in chunk(s, 3)), sep=" / "))Solution: The arrangement of the churches is: A, H, F, B, D, E, G, I.
The central church is C.
Here is a diagram of the churches and possible view points from which the photos could be taken:
It is not possible to take a photograph that includes five churches but not the central church. So the central church must be included in each photograph, and from this we can see that the central church can only be C, and we can use this fact to speed up the program. Fixing A and C and trying the remaining permutations brings the run time down to a much more reasonable 730ms (see [ @repl.it ]).