Spliced treble-dodging minor - Introduction

Richard Smith richard at ex-parrot.com Tue Sep 28 04:19:50 BST 2010

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