Laddergrams

作者Ned排水沟,2023年1月25日

13次查看(过去30天)|0个赞|6个评论

            MATLAB是擅长数学,当然,但它也可以让你有一些有趣的单词。去游戏>文字游戏类别文件交换,你可以找到各种不同的文字游戏。

            我喜欢laddergrams,因为我找不到任何文件交换,我想有一些有趣的和写在这里。Laddergrams(也称为词梯子)是一个文字游戏发明的刘易斯·卡罗尔你改变一个词到另一个通过中间相差一个字符的单词。他介绍了与这个词对谜题:头到尾。

            这是挑战:如何变换一次从头到尾一个字母吗?这是他的回答从1879年。

            我们可以写一些MATLAB代码,会找到一个解决这个问题的?

            这个问题让我们有机会玩在MATLAB的图形对象。经常就是这样,一旦你建立正确的问题,这是一个微风计算任何一对laddergrams单词。我们会通过阅读英语单词成一个字符串的列表。

              url =“https://raw.githubusercontent.com/first20hours/google - 10000 english/master/google - 10000 english.txt”;
             

              wordList =字符串(webread (url));
             

              话说= wordList.splitlines;
             

            提取所有的单词是4字母长的。

              保持= words.matches (lettersPattern (4));
             

              单词=单词(保持);
             

              numWords =长度(字)
             

               numWords = 1125

            让我们依字母顺序排列的列表。

              话说=排序(单词);
             

            我们想建立一个图,包含所有这些低俗的字眼。每个节点都是一个单词,每条边连接两个词,可以“架桥”在一个laddergram一步。让我们构建邻接矩阵。

            两个词连接的边缘,如果他们相差一个且只有一个字母的位置。所以头和连接愈合。头,注意连接。但这里头,不,因为您需要更改两个字母从一个到另一个。

              disorderly = 0 (numWords);
             

              为我= 1:numWords
             

              为j =我:numWords
             

              %三个字母必须精确匹配
             

              如果sum (char(话说(i)) = = char(话说(j))) = = 3
             

              %的矩阵是对称的(无向图),所以我们
             

              %触摸邻接矩阵的两个位置。
             

              的(i, j) = 1;
             

              的(j,我)= 1;
             

              结束
             

              结束
             

              结束
             

              间谍(的)
             

            邻接矩阵有一些迷人的结构!通过标志着首字母之间的休息时间,我们可以更好地看到发生了什么。我们将使用diff命令明白每个单词的第一个字母的变化。

              第九=找到(diff (char (words.extract (1))) ~ = 0);
             

              为i = 1:长度(第九)
             

              参照线(第九(我))
             

              yline(第九(我))
             

              结束
             

              标题(”字连接邻接阴谋”)
             

            800指数中,您可以看到一个非常狭窄的带对应于效率问:只有三个字在这本字典开始问:四、辞职,和测试

            让我们把字母情节的Y轴使这更清楚。

              字母= (“一个”:“z”)”;
             

              第九集(gca, YTick =,…
             

              YTickLabel = cellstr(字母)
             

            使图形对象。

              图g = (adj,单词);
             

            计算所有单词之间的距离。这是魔法发生的地方。这个命令是不可思议的:有效距离是解决每一个潜在的阶梯。这就是常说的利用优秀的库,只是等待中使用MATLAB。任何代码我会想出解决这个问题需要很长时间来编写和运行。相反,轰!一切都完成了。

              d =距离(g);
             

            有些词对相对难以接近,所以他们显示为无限远。

              [word1ix, word2ix] =找到(d = =正);
             

            这里有两个词你将永远无法通过laddergram连接,至少这个字典。

              我= 10;
             

              单词([word1ix (i) word2ix (i)))
             

            或者,正如他们在缅因州说:你无法从这里到达那里。

            让我们取消那些无限的边缘,所以他们不要混淆我们的计算。

              d (d = =正)= 0;
             

            现在看看数字的直方图。

              maxLadderLen = max (d (:))
             

               maxLadderLen = 20

              直方图(d (:), 1: maxLadderLen)
             

              包含(“Laddergram长度”)
             

              ylabel (“双”数量的词)
             

            六是最常见的中间步骤。

            最长的单词是什么梯子吗?

              [word1ix, word2ix] =找到(d = = max (d (:)));
             

              长度(word1ix)
             

               ans = 20

              我= 9;
             

              p = shortestpath (g, word1ix(我),word2ix(我));
             

              为j = 1:长度(p)
             

              流(“% s \ n”、单词(p (j)))
             

              结束
             

                小镇
下来
黎明
该死的
爵士
日期
讨厌
帽子
支安打
位
偏见
胸罩
肝
灰色的
灰色
增长
画了
画
拖
药物
鼓

            有多路领带最长laddergram(20个步骤),但这个冠军的词对从一个城镇到鼓。像往常一样,一切都取决于字典。不同的词典可以给截然不同的结果。

            最后,我们可以解决这个问题,早在1879年就提出刘易斯·卡罗尔。

              p = shortestpath (g,“头”,“尾巴”)”
             

                  p =
                  6×1的字符串
                 

                  “头”
“持有”
“地狱”
“大厅”
“高”
“尾巴”

            我们的语言是不同的,但即使有MATLAB在我们这边,我们不能做的更好比卡罗尔近150年前。但在讨价还价,我们已经解决了每一个laddergram可以在这个字典。

              numLaddergrams = nnz (d) / 2
             

               numLaddergrams = 405591

            所有405591人!我喜欢图算法。

要发表评论,请点击此处登录到您的MathWorks帐户或创建一个新帐户。

MATLAB社区
MATLAB、社区和更多