Holroyd at 06:54, 27 June 2011

2011-06-27T06:54:28Z

Holroyd at 06:48, 28 October 2010

2010-10-28T06:48:40Z

Holroyd at 06:44, 28 October 2010

2010-10-28T06:44:09Z

Holroyd at 06:41, 28 October 2010

2010-10-28T06:41:53Z

Holroyd: moved Spliced treble-dodging minor to Spliced treble-dodging minor - Introduction

2010-10-24T22:55:45Z

moved Spliced treble-dodging minor to Spliced treble-dodging minor - Introduction

Holroyd: Created page with '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 cu…'

2010-10-24T22:50:08Z

Created page with '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 cu…'

New page

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

← Older revision		Revision as of 06:54, 27 June 2011
Line 12:		Line 12:
	\|		\|
	[[Spliced treble-dodging minor - 6\|Plans 6]]		[[Spliced treble-dodging minor - 6\|Plans 6]]
		+	\|
		+	[[Spliced treble-dodging minor - 7\|Plans 7]]

← Older revision		Revision as of 06:48, 28 October 2010
Line 6:		Line 6:
	\|		\|
	[[Spliced treble-dodging minor - 3\|Plans 3]]		[[Spliced treble-dodging minor - 3\|Plans 3]]
		+	\|
		+	[[Spliced treble-dodging minor - 4\|Plans 4]]
		+	\|
		+	[[Spliced treble-dodging minor - 5\|Plans 5]]
		+	\|
		+	[[Spliced treble-dodging minor - 6\|Plans 6]]

← Older revision		Revision as of 06:44, 28 October 2010
Line 1:		Line 1:
	[[Spliced treble-dodging minor - clusters\|Clusters of plans]]		[[Spliced treble-dodging minor - clusters\|Clusters of plans]]
		+	\|
		+	[[Spliced treble-dodging minor - 1\|Plans 1]]
		+	\|
		+	[[Spliced treble-dodging minor - 2\|Plans 2]]
		+	\|
		+	[[Spliced treble-dodging minor - 3\|Plans 3]]
		+

	Richard Smith richard at ex-parrot.com		Richard Smith richard at ex-parrot.com

← Older revision		Revision as of 06:41, 28 October 2010
Line 1:		Line 1:
		+	[[Spliced treble-dodging minor - clusters\|Clusters of plans]]
		+
	Richard Smith richard at ex-parrot.com		Richard Smith richard at ex-parrot.com
	Tue Sep 28 04:19:50 BST 2010		Tue Sep 28 04:19:50 BST 2010