[1313] Regex Golf

Title Text:/bu|[rn]t|[coy]e|[mtg]a|j|iso|n[hl]|[ae]d|lev|sh|[lnd]i|[po]o|ls/ matches the last names of elected US presidents but not their opponents.<

Origin:https://xkcd.com/1313/

https://www.explainxkcd.com/wiki/index.php/1313:_Regex_Golf

漫画谈论正则表达式,这是一种指定文本模式的方式。给定正则表达式,可以搜索它在文本字符串中指定的模式。如果找到模式,则表示模式“匹配”字符串;如果找不到,那就说它不匹配了。

漫画的标题和第一个小组基于“正则表达式高尔夫”,这是一个“代码高尔夫”的学科,一个程序员尝试使用尽可能少的字符解决给定的编程问题的游戏,类似于数字达到目标所需的高尔夫击球次数。在正则表达式高尔夫中,程序员被赋予两组文本片段,并且他或她尝试编写最短的正则表达式,其将匹配一组的所有元素,同时不匹配来自另一组的任何元素。

Megan面临的正则表达式高尔夫挑战包括匹配(当时现存的)星球大战电影的所有字幕,而不匹配星际迷航电影的任何副标题。在“星际迷航:”或“星球大战第N集”之后,字幕是电影的次要标题。例如,在星球大战第一集:幻影威胁中,副标题是幻影威胁。在第一个小组中,她创建了一个12个字符的正则表达式来解决这个挑战。

然后,她继续构建一个工具,可以自动为任意文本列表构建这样的正则表达式,可以将其描述为元正则表达式高尔夫球。但是由于她丢失了这个工具,她需要搜索她的文件并选择一个名为“grep”的工具来查找它。这意味着她需要一个正则表达式,可以找到任何看起来像正则表达式高尔夫生成器的代码,从而导致另一个“元 – ”抽象层。最后,梅根注意到这个元元素的序列可能会变成无限,而Cueball打趣说,由于她的努力,她现在有“无限的问题”;梅根反驳说她已经有了“无限的问题”,因为她很痴迷于自己运行元版本的程序,并且顽固到足以继续直到她失败,排除其他一切。这似乎也是对着名引用的引用(另见1171:Perl问题):

有些人在面对问题时会想“我知道,我会使用正则表达式”。现在他们有两个问题。

正则表达式[编辑]

Megan使用的第一个正则表达式是/m | [tn] | b /,据说与星球大战的字幕相匹配,但不是星际迷航。

正斜杠/只是标记正则表达式的开始和结束。 |字符表示“或”,因此正则表达式匹配包含模式“m”,“[tn]”或“b”(包括空格)的任何字符串。方括号与其中一个包含的字符匹配,这意味着“[tn]”匹配“t”或“n”。正则表达式显然不区分大小写,因为它不会起作用。

星球大战的字幕以下列方式匹配正则表达式的各个部分:

“幻影威胁”与“m”相匹配。

“克隆人的攻击”与“[tn]”相匹配。

“西斯的复仇”与“[tn]”相匹配。

“新希望”与“[tn]”相匹配。

“帝国反击战”与“b”相匹配。

“绝地归来”与“[tn]”相匹配。

请注意,如果其中一部包含动画电影“星球大战:克隆人战争”,它将不会与“[tn]”匹配,因为T是字幕的开头,并且前面没有空格。

自这部漫画(“原力觉醒”,“盗贼一号”,“最后的绝地”,“独奏”和“天行者的崛起”)以来发行的电影都没有与这个正则表达相匹配。

另一方面,Star Trek字幕中没有一个包含M后跟空格,T或N前面有空格,或任何B,因此正则表达式与其中任何一个都不匹配。请注意,在原始系列中,所有字幕都以“T”开头,但它是第一个字符,所以它前面没有空格。

以下是梅根可能使用的列表:

原创系列:

电影

汗之怒

寻找Spock

航程之家

最后的边疆

未被发现的国家

下一代:

第一次接触

起义

复仇者

重启系列:

没有副标题的那个

进入黑暗

在最后一个“超越”的面板中,Megan使用正则表达式/(meta – )* regex golf /来描述她的问题。 *表示前面字符/组的“零或更多”(括号()组字符)。因此,这个正则表达式匹配“正则表达式高尔夫”,“元正则表达高尔夫”,“元元正则表达式高尔夫”等。在某种程度上,这是正则表达式高尔夫本身,匹配所有级别的元正则表达式高尔夫,而不匹配任何其他。在标题文本中,有一个很长的正则表达式是另一个正则表达式高尔夫挑战的解决方案:匹配所有当选美国总统的姓氏,但不匹配他们的对手。请注意,反对者名单中包括一些以前或以后成为总统的人,或其姓氏与其他总统候选人的名字相匹配,因此从字面上看这是不可能的。为了使这项工作,反对者的名单必须排除任何总统的名字。正则表达式本身的工作方式与星球大战/迷航方式非常相似,包括由|分隔的几种不同的模式。每个当选总统都匹配一种模式,而每个对手都没有匹配。

2016年的选举与这个正则表达不符。事实上,由于唐纳德特朗普的对手(希拉里克林顿)与之前当选的总统(比尔克林顿)具有相同的姓氏,因此不可能修改正则表达式来解释2016年大选。

以下是选举产生的总统名单及其匹配的模式:

主席

匹配表达

1

乔治华盛顿

SH

2

约翰亚当斯

[AE] d

3

托马斯·杰斐逊

Ĵ

4

詹姆斯麦迪逊

[MTG]一

詹姆斯门罗

[COY]ë

6

约翰昆西亚当斯

[AE] d

7

安德鲁杰克逊

Ĵ

8

马丁范布伦

BU

9

威廉亨利哈里森

11

詹姆斯K.波尔克

[便便

12

扎卡里泰勒

[MTG]一

14

富兰克林皮尔斯

[COY]ë

15

詹姆斯布坎南

BU

16

亚伯拉罕·林肯

[LND] i的

17

安德鲁约翰逊

Ĵ

18

尤利西斯·S·格兰特

[RN]吨

19

卢瑟福B.海耶斯

[COY]ë

20

詹姆斯加菲尔德

[MTG]一

22

格罗弗克利夫兰

列弗

23

本杰明哈里森

24

格罗弗克利夫兰

列弗

25

威廉麦金利

N [HL]

26

西奥多·罗斯福

[便便

27

威廉霍华德塔夫脱

[MTG]一

28

伍德罗·威尔逊

LS

29

沃伦G.哈丁

[LND] i的

三十

卡尔文柯立芝

[LND] i的

31

赫伯特胡佛

[便便

32

富兰克林D.罗斯福

[便便

33

哈里·杜鲁门

[MTG]一

34

德怀特·艾森豪威尔

N [HL]

35

约翰肯尼迪

[AE] d

36

林登B.约翰逊

Ĵ

37

理查德尼克松

[LND] i的

39

吉米卡特

[RN]吨

40

罗纳德里根

[MTG]一

41

乔治H. W.布什

BU

42

比尔·克林顿

[RN]吨

43

乔治W.布什

BU

44

巴拉克奥巴马

[MTG]一

一些总统失踪是因为他们没有当选,而是在他们的前辈辞职/去世后成为总统。

这里列出了每个表达式匹配的唯一姓氏数:

表达

比赛计数

 BU

 3

 [RN]吨

 3

 [COY]ë

 3

 [MTG]一

 7

 Ĵ

 3

 异

 1

 N [HL]

 2

 [AE] d

 2

 列弗

 1

 SH

 1

 [LND] i的

 4

 [便便

 3

 LS

 1

兰德尔的正则表达必须略微修改,因为它也与1856年詹姆斯布坎南的亚军约翰·C·弗里蒙特相匹配,正如彼得·诺维格在xkcd 1313:Regex Golf所讨论的那样。请注意,Norvig提供了少量的Python代码,实际上使用任意列表进行正则表达式高尔夫,并且发现了比Randall的星球大战与星际迷航游戏更短的解决方案。

正则表达与唐纳德特朗普不匹配,唐纳德特朗普在2016年赢得希拉里克林顿,因此需要更新。正则表达式确实与希拉里克林顿的姓氏相匹配,但由于姓氏相同的人(比尔克林顿)是总统,这不算错。在1792年和1812年,已经有一个名叫乔治克林顿的失败对手。

Leave a Reply

Your email address will not be published. Required fields are marked *

Categories