[r-t] 147 TDMM

[Richard Smith]

I've spent quite a lot of the last month looking at spliced 
extents of treble dodging minor.

Thanks to a cunning algorithm (which I shall describe in a 
moment) designed by Ander which we've been fine-tuning it 
turns out to be possible to do exhaustive searches over 
search spaces that I had previously thought were impossibly 
large.

As a demonstration, I have just done a search for all true 
extents of minor using just methods from the standard 147 
treble dodging minor methods rung with 4ths place lead-end 
bobs.  I will do some further verification of this result 
over the next few days, but I believe the number of extents 
of this form is

   5,862,727,200,079,423,275,554

To put this number into perspective, if I were to produce a 
booklet listing these in a similar format to that used in 
the CC's spliced minor collection, then the resulting 
booklet would be about 5 light-years thick.


THE ALGORITHM

There are five main stages to the search algorithm.

First we remove lead splices and lead-end variants from the 
list of methods.  So, for example, we only want to include 
one of Beverley, Surfleet, Berwick and Hexham.  This reduces 
the list of methods from 147 to 75.

The second stage is to associate each lead end or lead head 
row with a method.  Start with a list of the 60 in-course 
rows with the treble leading -- these will all appear as a 
l.e. or a l.h., and we need to choose a method for each one, 
and doing so will join a l.h. to the subsequent l.e.

Suppose some l.e./l.h. rows already have methods chosen.  Of 
the remaining rows, we call a method 'possible' if

   (i) the l.e. that would be reached by ringing a lead of
   the method starting at the given l.h. row is not
   associated with a method; and

   (ii) the lead would be true against all other chosen
   leads.

Take the row that has the fewest possible methods and, in 
sequence, try each of its possible methods, recursing. 
This gives an exhaustive tree search.  The result of this is 
a 'plan' -- a list of which method is rung from each lead, 
but with no information on how to join the leads up.

Stage two can be speeded up significantly by implementing a 
form of rotational pruning.  Put the methods in some 
arbitrary order.  Any method (other than the first one 
chosen) must not be before the first one chosen in the 
ordering.  This will remove some but not all rotations and 
reflections.  If you want an accurate count, it's a good 
idea to check whether a plan is in its canonical rotation 
and only output it if it is.

The third stage is to do an exhaustive search of ways to 
join the 30 leads in each plan using 12, 14 or 16 lead end 
changes.  An normal tree search for compositions will do 
this fine.  There's no need to check for truth beyond 
checking for repetition of lead heads and lead ends as this 
was dealt with in stage two.  For each plan you then have a 
list of compositions that produce the extent.

Fourth, we remove compositions that include 16 lead ends in 
London (3-3.4) or Hills (3-34.6) backworks.  This is a 
little subtle for plans that include one of these backworks 
and another one -- as 16 lead ends are fine as long as they 
only occur in the non-London, non-Hills backworks.

A further subtlety arises if rotational pruning was done in 
stage two.  Because there is no clear distinction between 
rotation and reflection of a plan (because we don't yet know 
which rows will become a l.h. and which a l.e.), pruning 
removes both rotations and reflections.  However, going from 
Carlisle-over to London-over with a 16 l.e. is fine; but 
going the other way is not.

This gives the complete set of extents.

Fifth, and assuming we want to count them, for each plan, 
the number of extents is the product of three terms: the 
number of distinct rotations / reflections (assuming 
rotational pruning); the number of lead splices (N^n where N 
is the number of methods in the lead splice set -- 2 or 4 
for everything in the 147 -- and n the number of leads of 
it); and the number of compositions for each plan.  Adding 
the values for each plan gives the overall total.

For the 147, the five stages took: 4s, 4h 1m, 1h 7m, 16m 44, 
and 1m 18s.  So the total search time was just under 6h. 
I've only made an effort to optimise stages two and three 
(stage five in particular is woefully suboptimal), but given 
that's where most of the time is spent, that seems 
reasonable.  I reckon that without too much work the search 
could be reduced to under 4h -- maybe even under 3h.


THE EXTENTS

Because the search first finds plans, and the number of 
plans (modulo rotation) is a fairly managable 4614, it's 
fairly easy to get a good idea of what's there.  And a quick 
scan through the list of plans shows that there are some 
interesting plans that are new (at least to me).  I'll give 
a breakdown of what's there in a later email.

RAS