1
$\begingroup$

Consider the following strings

  'dcabab',
  'cdabab',
  'dacbab',
  'adcbab',
  'cadbab',
  'acdbab',
  'dbacab',
  'bdacab',
  'dabcab',
  'adbcab',
  'badcab',
  'abdcab',
  'cbadab',
  'bcadab',
  'cabdab',
  'acbdab',
  'bacdab',
  'abcdab',
  'dabacb',
  'adbacb',
  'badacb',
  'abdacb',
  'adabcb',
  'abadcb',
  'cabadb',
  'acbadb',
  'bacadb',
  'abcadb',
  'acabdb',
  'abacdb',
  'cababd',
  'acbabd',
  'bacabd',
  'abcabd',
  'abacbd',
  'ababcd' 

If you are currently at one of those strings, you can attempt to make another one by swapping any pairs of characters. For example, you can go from 'dcabab' to 'cdabab' by swapping the first two characters. This is good because the characters that are swapped are right next to each other, that is of distance one.

The puzzle

Find a way to go from one of the strings of your choosing to all the other strings by doing one swap per new string. That is start at a string, do one swap making a new string from the list, then do another swap from the new string making another string from the list and so on. You must only ever visit strings from the list.

For those who like graphs, you can think of the strings as forming nodes in a graph and two nodes being connected by an edge if you can get from one string to another by a single swap.

Your goal is to make the distance between characters that you swap as small as possible. If you only ever need to swap adjacent characters then you have perfect solution.

If it can't be done, please explain why.

$\endgroup$
8
  • $\begingroup$ So we can just ignore the last 'cd', and treat the strings as 6 characters long? Why did you choose to show the last 'cd'? $\endgroup$
    – Lezzup
    Aug 13, 2023 at 6:22
  • $\begingroup$ And why specifically these strings? I would expect for example 'abcdbacd' there as well. $\endgroup$
    – Lezzup
    Aug 13, 2023 at 6:26
  • 1
    $\begingroup$ @justhalf No. That would be interesting but more difficult. If you can do it that way it's definitely a bonus though. $\endgroup$
    – Simd
    Aug 13, 2023 at 15:23
  • 1
    $\begingroup$ I think this was downvoted because it really boils down to a shortest-path problem, of which we already have algorithms like Dijkstra or A*. $\endgroup$ Aug 13, 2023 at 23:58
  • 3
    $\begingroup$ @newQOpenWid It is TSP, much harder than shortest path. $\endgroup$
    – RobPratt
    Aug 13, 2023 at 23:59

1 Answer 1

7
$\begingroup$

By introducing a dummy node that is adjacent to all other nodes, we have a traveling salesman problem on a graph with $37$ nodes and $130$ edges. The distance between nodes is $0$ if either node is the dummy and otherwise is the distance between the two swap characters. These distances are thus in $\{0,1,2,3,4\}$. The minimum total distance in a tour turns out to be:

$36$, with $2$ edges of distance $0$ (for the dummy), $34$ edges of distance $1$, and $1$ edge of distance $2$

Here is such a tour,

with the distance-$2$ edge highlighted: $$\text{DUMMY},acabdb,acbadb,acbdab,acdbab,cadbab,cdabab,dcabab,dacbab,adcbab,adbcab,abdcab,abcdab,bacdab,bcadab,cbadab,cabdab,cabadb,cababd,acbabd,abcabd,bacabd,bacadb,abcadb,abacdb,abacbd,\color{blue}{ababcd,abadcb},abdacb,badacb,badcab,bdacab,dbacab,dabcab,dabacb,adbacb,adabcb,\text{DUMMY}$$

To see that it is impossible to have a shorter tour, consider the subgraph with $37$ nodes and $89$ edges that have distances at most $1$. Removing the following $13$ nodes yields a graph with $14$ connected components: $$\text{DUMMY},abacdb,abcabd,abcdab,abdacb,acbadb,adbacb,adcbab,bacadb,badcab,cabdab,cdabab,dabcab$$ Having more connected components than removed nodes is a well-known sufficient criterion for non-Hamiltonicity.

The following $11$ nodes, the removal of which yields $12$ connected components, provide an even shorter certificate of non-Hamiltonicity: $$\text{DUMMY},abacdb,abcabd,abcdab,abdacb,acbadb,adbcab,bacadb,badcab,cabdab,dabcab$$

$\endgroup$
3
  • $\begingroup$ That's a great solution. What software did you use? $\endgroup$
    – Simd
    Aug 13, 2023 at 16:34
  • $\begingroup$ Thanks. I used the OPTMODEL procedure in SAS. $\endgroup$
    – RobPratt
    Aug 13, 2023 at 16:36
  • 1
    $\begingroup$ Nice, this also doesn't visit any node twice. $\endgroup$
    – justhalf
    Aug 14, 2023 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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