[r-t] Out of course treble-dodging minor

[Alexander Holroyd]

That's awesome work John!

Suggestion for what to look for: all _maximal_ sets of methods that admit 
an extent.  It may take a bit of thought to figure out a good algorithm 
for this, but it should be doable, and the list will probably not be that 
long.  I did it for the surprise only by a pretty naive algorithm.  There 
were only about 20 sets IIRC.

>From this list it is possible to deduce the minimum extents needed for all 
147 methods (again by dancing links, although dealing with lead end 
variants may be a nuisance).  (For the 41 surprise the number is 9).

Then, do the same thing for extents with only 2 types of call, or one type 
of call that is not a bob (bobs are done), or all the work extents...

Ander

On Sun, 6 Dec 2015, John Danaher wrote:

> Inspired by Ander's post last fall, I've been working (on and off) on an
> exhaustive search for extents of minor. If my code is correct, I've been
> able to enumerate every composition of the 147 regular treble-dodging
> methods, spliced at the lead end, using bobs or any/all of the four single
> changes as calls.
>
> My approach starts similarly to Ander's: a backtracking search on all of
> the possible leads, using Knuth's "dancing links" data structure to solve
> the complete-cover problem.
>
> Where my approach differs is that rather than producing plans that need to
> be joined at a later stage, I've included the calls in the search itself.
> So rather than choosing 30 leads to cover 720 rows, I choose 30 leads and
> 30 calls to cover 840 "rows": the 600 rows without the treble leading, plus
> each treble-lead row twice, once in a method and once at a call (or lack
> thereof). Then each call covers 2 rows and each lead covers 26: the 24
> you'd expect, plus the two "call" rows with the treble leading at the snap
> again, since those two rows won't appear at either blow of an actual call.
>
> In theory, that permits pruning to eliminate unjoinable plans early, at the
> cost of additional bookkeeping to avoid cycles short of the full extent.
> That said, I haven't implemented a plan-based solution for comparison, so I
> don't know how much, if any, my solution improves upon a plan-based
> strategy.
>
> I found 419,388,705 total compositions of the 147 methods excluding
> lead-splices, rotations, and reflections. The list includes 32330
> combinations of methods, again excluding lead-splices, though that number
> is a bit fuzzier since e.g. a composition with only bobbed leads of
> Cambridge might also be considered to include Primrose instead.
>
> I've been focused on just getting to this point, so I'm honestly not sure
> what sort of thing to look for in that haystack. My favorite discovery so
> far is that (again supposing my code is correct) if you try choosing four
> methods from the four quadrants (one each of S, 3D, 4D, and TB), there are
> only three sets that can produce an all-the-work composition:
>
> Wo Di Te Ms
> Sa Di Ev Ms
> No Cv Br Kt
>
> The first two form a tidy bundle of intersecting work above and below the
> treble, but the third has more variety and also only uses bobs. One of its
> three compositions:
>
> No No No No No-
> Br No-Kt-No Br
> No-Kt-No Br No-
> Kt-No Br No-Kt
> Cv-Cv-Cv-Cv-Cv
> Kt-No-No No Br-
>
> I know bobs-only treble-dodging minor has been investigated in the past.
> Was that composition (or one like it) previously known?
>
> - John
>