求字图的直径

Question

Introduction

一个流行的单词难题是通过一系列的步骤将一个单词转换成另一个单词，这些步骤只替换一个字母，并且总是产生一个有效的单词。例如，包可以通过五个步骤的路径转换为狗：

袋装->蝙蝠->猫->胶辊-> COG ->狗

在这种情况下也存在较短的路径；例如：

袋装->沼泽->犬

如果一个人画了一个图，它的顶点被文字标记，每一对单词之间都有一个边，那么从“袋子”到“狗”的最短路径是由两个边组成的。

挑战

您将编写一个程序，该程序接收所有长度相同的单词的“字典”作为输入，表示所有允许的单词，这些单词可以作为路径上的步骤出现。它应至少输出一条“最长最短路径”，即两个字之间的一条路径，即：

• 这两句话之间的任何一条路都不会长；
• 至少只要列表中任何其他单词之间的最短路径即可。

在上面描述的图的上下文中，这种路径的长度就是图的直径。

在退化的情况下，没有一个输入字可以转换成其他的任何一个，输出至少一条长度为零的路径，即一个单词。

示例

• 输入“袋”、“蝙蝠”、“猫”、“婴儿床”、“点”、“狗”应该生成一个路径，按该顺序遍历所有六个单词(或反向顺序)，因为本词典中从“包”到“狗”的最短路径是最长的，可实现的五个步骤。
• 输入的“袋”、“蝙蝠”、“机器人”、“猫”、“婴儿床”、“点”、“狗”应该产生路径“袋子，蝙蝠，机器人，点，狗”和/或它的反转。
• 输入的“密码”、“高尔夫”、“男性”、“嗡嗡”、“鼹鼠”、“角色”、“模子”、“冷”、“黄金”、“模式”应该在“代码”和“高尔夫”之间产生一条路径。
• 输入“一”、“二”、“六”、“十”对应于一个没有边的图，因此输出一个或多个单字(零长)路径。
• 如果输入包含任意两个长度不等的单词，则输出未定义。

规则

• 适用标准码高尔夫球规则
• 将有多条“最短”路径。您必须至少输出一个，但可以自由地输出任意数量的输出。
• 您可以自由决定如何将输入字典传递到程序中。
• 以字节为单位的最短代码获胜。

Answer 1

果冻，20字节

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

在网上试试！

Answer 2

Python 3，225个字节

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]

在网上试试！

基本上，采取所有可能的路径，只保留那些是有效的，然后经过每个开始-结束组合，找到最小的路径距离，并找到最大的。

Answer 3

Wolfram语言(数学)，105个字节

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

在网上试试！