6
$\begingroup$

for these puzzles you're given a set of letter pairings that you line up into a code via the overlapping letters as an example:

you have pairs "CA", "CO", "DC" and "OD" for a 5-letter code. with the answer being CODCA (contains CO, OD, DC, CA in that order)

$\endgroup$
  • $\begingroup$ Pattern matching? $\endgroup$ – Lawrence Jul 24 '18 at 6:10
  • $\begingroup$ Pattern matching would be a generic category of puzzle though sadly it's starting to look like this particular puzzle type doesn't have a proper name $\endgroup$ – Goku Gohan Jul 24 '18 at 6:53
  • 1
    $\begingroup$ An interesting term to look up for this puzzle is "Eulerian Path" en.wikipedia.org/wiki/Eulerian_path $\endgroup$ – LeppyR64 Jul 24 '18 at 11:06
  • $\begingroup$ @LeppyR64 Quite true. Once you convert the letter pairs into the directed edges of a graph where the nodes are the letters, the puzzle becomes trivial. $\endgroup$ – Jaap Scherphuis Jul 24 '18 at 12:44
  • $\begingroup$ @JaapScherphuis Or it has a whole bunch of solutions :) $\endgroup$ – LeppyR64 Jul 24 '18 at 20:06
4
$\begingroup$

It looks like a $1$-dimensional overlapping jigsaw puzzle,

or Marshall Squares in 1d.

They are very easy to make, just type in a string and then partition it accordingly.

For example:

AD DF DS FD FS SA SF

is derived from:

ADSFDFSA

To solve or check for the uniqueness of a solution, we can check all $k!$ permutations, but we can improve on this using a recursive sieved tree algorithm.

First check the opening pairs for successful candidates, and store the result in a new array as [{pair},last letter, remaining array], and repeat the process on the new array.

For example, the new array for my example, starting from:

[{},NULL,[AD,DF,FD,DS,SF,FS,SA]]

would contain:

[{AD,DF},F,[DS,FD,FS,SA,SF]]
...
[{FD,DF},F,[AD,DS,FS,SA,SF]]
[{FD,DS},S,[AD,DF,FS,SA,SF]]
...

giving only 13 new entries.

The next level should produce entries like:

[{AD,DF,FD},D,[DS,FS,SA,SF]]

and repeat until:

[{AD,DF,FD,DS,SF,FS,SA},NULL,[]]

for example.

(Note that this means my example is not uniquely defined - ADFDSFSA also works!)

$\endgroup$
  • $\begingroup$ Yea but I'm not looking to make them I'm looking for a proper name for them or a solver (which is what i was hoping to use the proper name for to see if anyone has written a solver) $\endgroup$ – Goku Gohan Jul 24 '18 at 6:52
  • 1
    $\begingroup$ Your example starts and ends on the same letter, which automatically allows multiple solutions by cyclically shifting parts, i,e. ADSFDFSA -> SADSFDFS -> FSADSFDF -> DFSADSFD -> FDFSADSF -> SFDFSADS -> DSFDFSAD. $\endgroup$ – Jaap Scherphuis Jul 24 '18 at 13:55
  • $\begingroup$ That's interesting I'm not a programmer my self though I have done some script editing for some IRC bots back when i used to use mIRC and have written a number of .bat files back when I used to use Dos ... how would I go about using that method? (I also know how to use the browsers console(chrome) to some extent) $\endgroup$ – Goku Gohan Jul 25 '18 at 8:37
  • $\begingroup$ you need fairly sophisticated coding skills and a modern language, such as JavaScript, which will work in your browser. Try developer.mozilla.org/en-US for a good reference site. $\endgroup$ – JMP Jul 25 '18 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.