StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I've been thinking about this one and I'm sketching out a solution.</p> <p>Let's call a string of four symbols a <em>word</em> and we'll write <em>S(w)</em> to denote the set of symbols in word <em>w</em>.</p> <p>Each word <em>abcd</em> has "follow-on" words <em>bcde</em> where <em>a,...,e</em> are all symbols. </p> <p>Let <em>succ(w)</em> be the set of follow-on words <em>v</em> for <em>w</em> such that <em>S(w) != S(v)</em>. <em>succ(w)</em> is the set of successor words that can follow on from the first symbol in <em>w</em> if <em>w</em> is in a solution.</p> <p>For each non-empty set of symbols <em>s</em> of cardinality at most four, let <em>words(s)</em> be the set of words <em>w</em> such that <em>S(w) = s</em>. Any solution must contain exactly one word in <em>words(s)</em> for each such set <em>s</em>.</p> <p>Now we can do a reasonable search. The basic idea is this: say we are exploring a search path ending with word <em>w</em>. The follow-on word must be a non-excluded word in <em>succ(w)</em>. A word <em>v</em> is excluded if the search path contains some word <em>w</em> such that <em>v in words(S(w))</em>.</p> <p>You can be slightly more cunning: if we track the possible "predecessor" words to a set <em>s</em> (i.e., words <em>w</em> with a successor <em>v</em> such that <em>v in words(s)</em>) and reach a point where every predecessor of <em>s</em> is excluded, then we know we have reached a dead end, since we'll never be able to obtain <em>s</em> from any extension of the current search path.</p> <p>Code to follow after the weekend, with a bit of luck...</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload