Find the diameter of a word graph

Question

Introduction

A popular word puzzle is to convert one word into another via a series of steps which replace only one letter and which always result in a valid word. For example, BAG can be converted to DOG via a path of five steps:

BAG -> BAT -> CAT -> COT -> COG -> DOG

Shorter paths also exist in this case; for example:

BAG -> BOG -> DOG

If one drew a graph whose vertices were labelled by words, with an edge between any pair of words that differ by one letter, then the shortest path from "BAG" to "DOG" would consist of two edges.

Challenge

You are to write a program which receives as input a "dictionary" of words which all have the same length, representing all allowable words that can appear as steps along a path. It should output at least one "longest shortest path", that is, a path between two of the words which is:

• no longer than any other path between those two words;

• at least as long as the shortest possible path between any other pair of words in the list.

In the context of the graph described above, the length of such a path is the diameter of the graph.

In the degenerate case where none of the input words can be transformed into any of the others, output at least one path of length zero, that is, a single word.

Examples

• The input ["bag", "bat", "cat", "cot", "dot", "dog"] should yield a path traversing all six words in that order (or reverse order), since the shortest path from "bag" to "dog" within this dictionary is the longest achievable, five steps.

• The input ["bag", "bat", "bot" , "cat", "cot", "dot", "dog"] should yield the path "bag, bat, bot, dot, dog" and/or its reversal.

• The input ["code","golf","male","buzz","mole","role","mold","cold","gold","mode"] should yield a path between "code and "golf".

• The input ["one", "two", "six", "ten"] corresponds to a graph with no edges, so output one or more single-word (zero-length) paths.

• If the input contains any two words of unequal length, the output is undefined.

Rules

• Standard code golf rules apply
• There will be multiple "shortest" paths. You must output at least one, but are free to output as many as you wish.
• You are free to decide how the input dictionary is passed into your program.
• Shortest code in bytes wins.

Answer 1

Jelly, 20 bytes

ŒPŒ!€ẎnƝ§ỊẠƲƇ.ịⱮḢƙƊṪ

Try it online!

Answer 2

APL (Dyalog Classic), 84 80 77 76 74 66 61 bytes

{⍵⌷⍨{⍵,⍨⊃⍋(1≠a⌷⍨⊃⍵),⍪⍺⌷a}⍣d/⊃⍸a=d←⌈/512|,a←⌊.+⍨⍣≡9*⍨2⌊⍵+.≠⍉⍵}

Try it online!

input and output are character matrices

⍵+.≠⍉⍵ matrix of hamming-like distances between words

9*⍨2⌊ leave 0s and 1s intact, turn 2+ into some large number (512=2⁹, used as "∞")

⌊.+⍨⍣≡ floyd&warshall's shortest path algorithm

• ⌊.+ like matrix multiplication but using min (⌊) and + instead of + and × respectively

• ⍨ use the same matrix on the left and right

• ⍣≡ repeat until convergence

d←⌈/512|, length of longest (not "∞") path, assigned to d

⊃⍸a= which two nodes does it connect, let's call them i and j

{⍵,⍨⊃⍋(1≠a⌷⍨⊃⍵),⍪⍺⌷a}⍣d/ reconstruct the path

• { }⍣d/ evaluate the { } function d times. the left arg ⍺ is always i. the right arg ⍵ starts as j and gradually accumulates the internal nodes of the path

• (1≠a⌷⍨⊃⍵),⍪⍺⌷a build a 2-column matrix of these two vectors:

  • 1≠a⌷⍨⊃⍵ booleans (0 or 1) indicating which nodes are at distance 1 to the first of ⍵

  • ⍺⌷a distances of all graph nodes to ⍺

• ⊃⍋ index of the lexicographically smallest row

• ⍵,⍨ prepend to ⍵

⍵⌷⍨ index the original words with the path

Answer 3

Python 3, 225 bytes

from itertools import*
def f(a):b=[((p[0],p[-1]),(len(p),p))for i in range(len(a))for p in permutations(a,i+1)if all(sum(q!=r for q,r in zip(*x))<2for x in zip(p,p[1:]))];return max(min(r for q,r in b if x==q)for x,y in b)[1]

Try it online!

Basically, take all possible paths, only keep the ones that are valid, then go through each start-end combination, find the minimum path distance, and find the maximum of that.

Answer 4

Wolfram Language (Mathematica), 105 bytes

f@x_:=MaximalBy[AdjacencyGraph[x,UnitStep[1-DistanceMatrix@x]]~FindShortestPath~##&@@@Tuples[x,2],Length]

Try it online!

Answer 5

Python 3, 228 bytes.

def G(w):
    D={A+B:[A,B]if sum(a!=b for a,b in zip(A,B))<2else[0,0]*len(w)for A in w for B in w}
    for k in w:
        for i in w:
            for j in w:
                p=D[i+k]+D[k+j][1:]
                if len(p)<len(D[i+j]):D[i+j]=p
    return max(D.values(),key=len)

Implements the Floyd-Warshall algorithm for all-pairs shortest-paths, then takes the maximum over the found paths.

16 of the characters in this implementation are tabs, which is unfortunate :(

Answer 6

JavaScript (ES6),  195  194 bytes

Returns [optimal_length, [optimal_path]].

f=(a,p=[],w=o=[],l=0)=>Object.values(o,o[k=[w,p[0]]]=(o[k]||0)[0]<l?o[k]:[l,p],a.map((v,i)=>w+w&&[...v].map((c,i)=>s-=c!=w[i],s=1)|s||f(a.filter(_=>i--),[...p,v],v,l+1))).sort(([a],[b])=>b-a)[0]

Try it online!

How?

We use a recursive function \$f\$ which builds an object \$o\$ whose keys consist of a pair of words \$w_0\$ and \$w_1\$ separated by a comma and whose values are defined as \$[l, p]\$, where \$p\$ is the shortest path between \$w_0\$ and \$w_1\$ and \$l\$ is the length of this path.

Given a path \$p\$ of length \$l\$ and the last word \$w\$ added to \$p\$, \$o\$ is updated with:

o[k = [w, p[0]]] = (o[k] || 0)[0] < l ? o[k] : [l, p]

We eventually return the longest path stored in \$o\$:

Object.values(o).sort(([a], [b]) => b - a)[0]

(this code is executed at each recursion depth, but only the root level really matters)

We use the following test to know whether a word \$v\$ differs by exactly one letter with the last word \$w\$:

[...v].map((c, i) => s -= c != w[i], s = 1) | s

For each word \$v\$ that can be added to the path, we process a recursive call as follows:

f(                    //
  a.filter(_ => i--), // remove the i-th word from a[]
  [...p, v],          // append v to p[]
  v,                  // pass v as the last word
  l + 1               // increment the length of the path
)                     //

Answer 7

Wolfram Language (Mathematica), 92 bytes

MaximalBy[Select[Rule@@@a,EditDistance@@#<2&]~FindShortestPath~##&@@@(a=#~Tuples~2),Length]&

Try it online!