On level 2, the rule is "which ever letter you used to form the first word in level 2 can't be used in any word for the remainder of the level

Clarification please. Do you really mean that only the letter used in the first word can't be used thereafter? Or do you mean "which ever letter you used in any previous step can't be used from then on for the remainder of the level" ?

In the first case the graph wouldn't change after the first step, which would really trivially divide the problem into less than 26 unchanging subproblems. Only in the second case there is constant change in the graph

One refinement for level 2 in the second case would be to pick random pairs of expensive words (without any letter common to the first word of level 2) and look for an expensive path of 4 words between them. For every row of 6 words found this way check if there is a path from the first word of level 2 to either end of this row (since you can turn around the row without invalidating it).

Example:

First word in level 2 is "bean". Now randomly find two words that have neither 'b','e','a' and 'n' in them and no common letter between them. For example "womb" and "pixy". Now look for a string of 4 words between "womb" and "pixy" using no letter from "bean" inbetween. Since 4 of the 5 letters needed to change from womb to pixy are already known ('p','i','x' and 'y'), an exhaustive search of routes between the two words should be very fast.

If you find such a route (which should be very expensive since you could freely select 8 out of the 9 letters), you now would look for a route from 'bean' to either 'womb' or 'pixy' with 3 words inbetween, also rather trivial as the letters to use are all fixed.

In reply to Re: Not Quite Longest Path Problem by jethro
in thread Not Quite Longest Path Problem by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.