文档章节

正则表达学习之——Regex Golf 解答与分析

德布罗意
 德布罗意
发布于 2017/04/24 10:54
字数 3161
阅读 687
收藏 0

原创声明:严禁抄袭!对本文的一切转载活动均需得到作者的许可注明原文地址和作者名称,否则自动视为侵权并需要公开道歉相应赔偿作者:德布罗意(昵称)
【侵权赔偿暂定人民币100元/千字(符),当然得到允许并按规定方式转载视情况免费都是可以的,分享知识嘛,不过要是觉得帮助到你并表示对作者的鼓励支持,欢迎关注点赞打赏啦哈哈~】
本文同步发于德布罗意(作者昵称)在“segmentfault”的同名个人笔记:正则表达学习之——Regex Golf 解答与分析

##目录##

##写在前面## 最近学习正则表达式,顺藤摸瓜发现了一个测试自己学习成效的网站:Regex Golf,具有闯关性质的答题过程吸引了我。答对题目可以Enter进入下一关,不正确时会把匹配错误或失败的单词列出来。感觉这个答题还是蛮训练思维的,于是想在这里对做题时的一些思考进行一个记录和分享(边做边记)。当然,聪明如你,可能会有比我给出的解答更好的表达式,欢迎与我分享,让我们一起进步! 补充:应该是网站改版了,现在不再显示每题的points值,可以自行按以下公式计算points(正确的匹配对应公式的第二项应该为0):
    Points = (需求列表匹配数 * 10) - (不允许列表匹配数 * 10) - 表达式字符数

##解答和得分## 以下是一些分数按照从高到低排序的解答(在实际应用中分数低的表达式反而可能得到更精确的匹配,因此这里将把最推荐【精确且易推广】的表达式用粗体标记):

  • Warmup

foo (207)

  • Anchors

k$ (208)
ck$ (207)
ick$ (206)

  • It never ends

u\b (27)
fu\b (26)

  • Ranges

**^[a-f]*$**or^[a-g]*$or^[a-h]*$ (202)

  • Backrefs

(...).*\1 (201)
(.{3}).*\1 (200)
(\w{3}).*\1 (199)

  • Abba

^(?!.*(.)\1)|ef (195)
**^(?!.*(.)(.)\2\1)**or^((.)(?!\2))*$|ef (193)

  • A man, a plan

^(.)[^p].*\1$ (177)
^(.)(.).*\2\1$ (176)

  • Prime

**^(?!(xx+)\1+$)**or【“x”换成“.”】 (186)
^(?!(..+?)\1+$) (185)

  • Four

(.)(.\1){3} (199)
(.).\1.\1.\1 (198)

  • Order

^[^o].{5}?$or^.[^r].{4}?$or^.{4}[^l].?$or^.{5}[^e]?$ (199)
a[cdf]|l[lo]|ch|be|os|[st]y (183)
^a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*$ (156)

  • Triples

00($|3|6|9|12|15)|4.2|.1.+4|55|.17 (176)
^([0369]|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258])|[147][0369]*[258])+$ (103)
(^39|^44)|(^([0369]|([147][0369]*[258])|(([258]|[147][0369]*[147])([0369]*|[258][0369]*[147])([147]|[258][0369]*[258])))*$) (87)
^[0369]*(([147][0369]*|[258][0369]*[258][0369]*)([147][0369]*[258][0369]*)*([258][0369]*|[147][0369]*[147][0369]*)|[258][0369]*[147][0369]*)*$ (63)

  • Glob

[bncrw][bporn]|^p|c$|ta (197)
^(.[fvor]|..[ls]|...[t])|[cd]$|rr|pp|ta|ro (168)

  • Balance

.{37}|^(<(..(?!<.>$))*>)*$ (294)
^(<(<(<(<(<(<<>>)*>)*>)*>)*>)*>)*$ (286)
^(<(<(<(<(<(<>|<<>>)*>)*>)*>)*>)*>)*$or**^(<(<(<(<(<(<(<>)*>)*>)*>)*>)*>)*>)*$ (283)**

  • Powers

**^(?!(x(xx)+)\1*$)**or^(?!(.(..)+)\1*$) (93)
**^((x+)(?=\2$))*x$**or【"x"换成"."】 (93)
^(x|(xx){1,9}|x{32}|(x{64})+)$or【"x"换成"."】 (80)
^(((((((((xx?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$or【"x"换成"."】 (60)
^((((((((((x)\10?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$or【"x"换成"."】 (56)

  • Long count

((.+)0\2+1){8} (-4)
((.+)0\2[1]){8} (-5)
^((.+)0 \2+1 ?)*$ (-7)
0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 (-54)

  • Alphabetical

  • Powers 2

^((x+)\2(?=\2$))*x$ (91)
^((((((((x(xx)?)(\8\8)?)(\7\7)?)(\6\6)?)(\5\5)?)(\4\4)?)(\3\3)?)(\2\2)?)(\1\1)?$or【"x"换成"."】 (20)
**^((((((((x(xx)?)(\8{2})?)(\7{2})?)(\6{2})?)(\5{2})?)(\4{2})?)(\3{2})?)(\2{2})?)(\1{2})?$**or【"x"换成"."】 (12)

这些解答除了我自己当时写的答案外,其他则是从各处(如这里这里,还有这里等等)搜集来的,不由得感叹,大神真是多啊!我还要多磨练技艺才是。

##对于解答的说明## 其实每道题目的含义就是很强烈的提示,看来这个网站的宗旨是考察正则表达式的书写而不是找规律,所以想要增加难度的小伙伴请遮住题目作答。 精确匹配的部分将不做语法解释,与之前题目相同并且容易理解的也不做语法解释了。有时候需要对表达式进行详细解读,因为并不那么直观。

  • Warmup

  题目:“热身”
  **评论:**这是一道精确匹配题目,也是一道送分题(热身嘛~)。
  **规律:**不限位置地匹配子串"foo",因此答案为foo
  **语法:**不赘述。
  

  • Anchors

  题目:“锚⚓️”
  **评论:**锚就是停止的意思咯,暗示关注结尾特征。
  **规律:**末尾是“ick”,由于题目特点,最简答案为k$
  语法:$匹配字符串的结束。
  

  • It never ends

  题目:“永不停止”
  **评论:**题目补充说明不允许用$,就是只能做单词边界的匹配,不能做字符串形式的匹配,其实我觉得应该增加一个双单词的匹配(eg. “kongfu action”)。
  **规律:**词尾是“fu”,由于题目特点,最简答案为u\b
  语法:\b匹配单词的开始或结束。
  

  • Ranges

  题目:“区间”
  **评论:**我是学物理的,数学情结让我把它翻译成区间。
  **规律:**整个单词中的字母均为a~f,答案可以是^[a-f]*$,^[a-g]*$,^[a-h]*$
  语法:^$分别匹配字符串的首尾,*匹配换行符外的任意字符,[abc]中的“a”“b”“c”是该位置可匹配字符的集合,-是简记符号,这里[a-f][abcdef]是等价的。
  

  • Backrefs

  题目:“后向引用”
  **评论:**考察分组。
  **规律:**单词的前三个字符后面又集体出现了,由于不允许匹配的也没有中间三个字符再次集体出现的情况,所以(...).*\1即可。
  语法:.匹配换行符以外的任意字符,(exp)小括号指定子表达式"exp"(即该子表达式完成分组)后可做进一步处理,\1代表分组1匹配的文本,.*匹配换行符外的任意字段。
  

  • Abba

  题目:“Abba”
  **评论:**小回文段,仍然考察分组,主要考察负向零宽断言,题目把规律直接写出来了。
  **规律:**不能包含双字符镜像连续字段,即不包含“abba”形式,从词首匹配但允许任意字段开始。
  语法:(?!exp)匹配后面跟的不是exp的位置。默认情况下,每个分组会自动拥有一个组号,规则:从左到右,以分组的左括号为标志,第一个出现的分组的组号为1,第二个为2,以此类推。
  

  • A man, a plan

  题目:“一个人,一个计划”
  **评论:**暂时不理解题目的引申义,仍然考察分组。
  **规律:**回文字符串,特征是至少有两对字符在单词前后相同,注意是整个字符串的匹配,因此答案为^(.)(.).*\2\1$
  **语法:**同之前的题目,不赘述。
  

  • Prime

  题目:“素数”
  **评论:**匹配素数个相同字符,这里的素数的转化是一个小挑战。
  **规律:**就是要匹配非合数个“x”(并不是废话~),也就是如果对字符串分组是不能分成等份的N(N>1)组的;也是要匹配整个字符串,答案为^(?!(xx+)\1+$)^(?!(..+)\1+$)
  语法:(xx+)表示至少两个的连续“x”,由于前面有^,即表示字符串开头至少两个连续的“x”被分组(组号是1);\1+$是前面组号为1的子表达式在当前位置重复至少一次,重复后字符串就结束了。因此如果是要匹配合数而非素数的话,答案是^(xx+)\1+$。反之,我们恰恰是要匹配素数而非合数,因此要利用负向零宽断言((?!exp))完成匹配。

  • Four

  题目:“四”
  **评论:**很容易的一道题。重复即分组。
  **规律:**不仅是有4个相同的字符出现,而且这4个字符之间都要隔着一个其他字符,最简答案为(.)(.\1){3}
  **语法:**其实可以把\1(或其他代表特定分组的匹配)理解为拷贝,{n}为将紧挨着的迁移匹配操作重复n次。

  • Order

    题目:“次序”
    **评论:**脑筋急转弯,按道理和题目的意思来讲答案为^a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*$
    **规律:**明面上是要匹配的每个单词的字符都是按字母表由a到z的次序的,实际上要匹配的单词都是5或6个字符,直接针对唯一的不允许匹配的单词特征即可,共有等价的4种表达。
    语法:[^x]表示这个位置匹配除了“x”和换行符以外的所有字符,|是启用分支条件的间隔符。

  • Triples

    题目:“三的倍数”
    **评论:**感觉难度非常大,不用cheat的方法不会做啊。
    **规律:**长度固定的十进制3的倍数,一般解的方法是由@Belleve在知乎:正则表达式如何匹配3的倍数?里给出的。
    **语法:**同之前的题目,不赘述。

  • Glob

    题目:“全球(罗马尼亚语)”
    **评论:**题目意思不知所云,但是我有“cheat”大法。
    **规律:**每一行都是一个正则匹配的正确陈述,然而要匹配这些陈述根本就没有啥规律好吗?168分那个是我自己糊了一阵糊出来的。。
    **语法:**同之前的题目,不赘述。

  • Balance

    题目:“平衡”
    **评论:**这个题目在匹配代码结构有实用性。
    **规律:**尖括号(<>)要成对出现,所以首先确定是要匹配整个字符串了,然后出现的情形要么是尖括号对并列出现,要么是外层包裹内层。
    **语法:**根据匹配列表结构,这里*对应尖括号对并列出现,()对应外层包裹内层。

  • Powers

    题目:“幂次” **评论:**做完这道题后对于数字的理解有了更深的认识,有机会好好学数论。 规律:匹配2的幂次个”x“,一种理解是将整个字符串二分来看(又分为两种处理:bottom-up地一直翻倍或者top-down地一直对半分,后者为剖分思想(类似分形)更容易推广至任意有限情形,见Powers 2),另一种理解是不匹配所有长度为大于1的奇数的倍数的串(这是因为2的幂次集合的补集为奇素数的倍数集合,而这个集合和所有奇数的倍数集合是一样的)。 语法:^(?!(x(xx)+)\1*$)x(xx)+表示位数为奇数位,\1*表示任意倍,然后用负向零宽断言来取补集;^((x+)(?=\2$))*x$(exp)(?=\1$)表示匹配后一半之前的位置。    ##彩蛋## 在题目补充说明的地方,有时候却是打趣的文字。列于下方:

1.通用说明:

  - Type a regex in the box.     在方框中写下一个正则表达式。   - You are deducted one point per character you use, and ten if you match something you shouldn't.   (表达式中)每有一个字符扣1分,每多匹配一个不该匹配的单词扣10分。

2.单独补充:

  - $ not allowed   不允许使用$   - Let's pretend this one is not a rehash of the last one.   不要用上一题的相同思路。   - You can get an extra point by ignoring the name of this level.     如果忽略题目的提示,你可以多得一分哦。

3.其他(娱乐+提示):

  - The test vectors were generated by grepping /usr/dict/words. Can you tell?   测试向量是通过对/usr/dict/words执行grep命令生成的。你能详述一下吗?【其实有时候是/usr/share/dict/words】   - This doesn't really work as a tutorial. Not really clear what you're supposed to do here.   这里并不能起到教程的作用,你来这儿干嘛?   - You're allowed to cheat a little. Even in hard mode, words will be no longer than 13 characters.   有时候你可以稍微作弊一点,因为即便是困难模式,单词的字符数不会超过13个。【做不出来的话,由于匹配列表容量有限总可以找出其他复杂的规律,最差可以枚举】

TBC

© 著作权归作者所有

德布罗意
粉丝 0
博文 3
码字总数 4252
作品 0
海淀
程序员
私信 提问
正则表达式 (C++) (施工中)

先来看一个例子,要求写一段代码,实现如下功能: 从标准输入中读取一行字符串, 从中读取所有邮箱的格式; 对于这个问题,用传统的方式是可以解决的: 我们可以用解析字符串的方式实现,需要...

shangluyi
2016/12/24
0
0
正则基础之——贪婪与非贪婪模式

1 概述 贪婪与非贪婪模式影响的是被量词修饰的子表达式的匹配行为,贪婪模式在整个表达式匹配成功的前提下,尽可能多的匹配,而非贪婪模式在整个表达式匹配成功的前提下,尽可能少的匹配。非...

pantrick
2013/08/25
0
2
VS2008中使用正则表达式库Boost.Regex

VS2008中使用正则表达式库Boost.Regex 2011-04-14 10:10

香芋
2012/06/08
0
0
C# WinForm开发系列 - Regular Expression

正则表达式用于字符串处理、表单验证等场合,实用高效。现将一些常用的表达式文章收集于此,以备不时之需。正则表达式能让更多的复杂的搜索和替换功能变成简单的操作。基本说来,正则表达式是...

长征2号
2017/11/07
0
0
Java魔法堂:深入正则表达式API

目录                               一、前言 二、正则表达式的使用诉求 三、java.util.regex包 四、java.lang.String实例 五、最短路径实现诉求 六、Java支...

fsjohnhuang
2014/11/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud中Hystrix 线程隔离导致ThreadLocal数据丢失

在Spring Cloud中我们用Hystrix来实现断路器,Zuul中默认是用信号量(Hystrix默认是线程)来进行隔离的,我们可以通过配置使用线程方式隔离。 在使用线程隔离的时候,有个问题是必须要解决的...

xiaomin0322
47分钟前
2
0
使用 Jenkins + Ansible 实现 Spring Boot 自动化部署101

本文首发于:Jenkins 中文社区 本文要点: 设计一条 Spring Boot 最基本的流水线:包括构建、制品上传、部署。 使用 Docker 容器运行构建逻辑。 自动化整个实验环境:包括 Jenkins 的配置,J...

Jenkins中文社区
52分钟前
4
0
springcloud配置中心和消息总线,学习,记录其中的问题

改造配置中心的客户端,接入消息总线 1.增加pom文件的引用 <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/20......

夜中孤影
今天
3
0
gzip压缩

tar -zcvf gz包路径 被压缩的路径 tar -zcvf /home/xxx/test.tar.gz hello gz包的路径可以是 完整的也可以相对 , 被压缩的路径 不要全路径 不然压缩包里也会有全路径...

shzwork
今天
3
0
rancher-1

部署rancher 官方快速部署 https://www.cnrancher.com/quick-start/ 部署命令 mkdir /data/rancher -p# 建立存放rancher数据的目录sudo docker run -d --restart=unless-stopped -v /dat......

以谁为师
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部