Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Best known Regex Golf solutions (SPOILERS) - Classic level set - (SPOILERS)

Collected solutions for Regex Golf, Classic level set

See also:
jpsim gist (discussion)
jonathanmorley gist (discussion)
teukon's Draft Regex Golf Bonus Levels
Solutions to teukon's Draft Regex Golf Bonus Levels (SPOILERS! SPOILERS!) and discussion of mathematical regexes
Continued discussion of Regex Golf Bonus Levels and mathematical regexes (SPOILERS! SPOILERS!)

Please let me know if you find any errors here, or can fill in any of the missing data.

Timestamps are in UTC. Be careful when following GitHub comment links – spoilers may be seen for other levels.

If I manage to discover solutions matching the unpublished high-score holders in length, I'm leaning towards publishing them here only as md5sums, so as not to further taint the high-score lists on Regex Golf.

There are some very wide tables below, which are uncomfortably constrained by the GitHub frameworks CSS. So I would suggest using a browser plugin to override the style with gist-wide.css.

Key to credits:

Exact solutions (to the test cases)

Level Length Regex Date Credit
Plain strings 3 [unpublished] before 2013-12-20 alok (RG~)
  3 foo 2013-12-20 11:18:54 Rhomboid (R)
  foo 2013-12-20 14:01:04 ZirconCode (HN)
  f.o 2014-01 Peter Norvig
Anchors 2 k$ before 2013-12-20 alok (RG~)
It never ends 6 u(?!.)
  3 u\b
Ranges 8 [unpublished] before 2013-12-20 alok (RG~)
  ^[a-f]*$ 2013-12-20 11:18:54 Rhomboid (R)
  [a-f]{4} 2013-12-20 14:09:44 Sir_Cmpwn (HN)
  [a-g]{4}
  [a-h]{4}
  ^[a-g]*$ 2013-12-20 15:47:57 chingjun (HN)
  ^[a-f]*$ 2013-12-20 18:09:39 josephlord (HN)
  ^[a-h]*$
Backrefs 9 (...).*\1 before 2013-12-20 alok (RG~)
Abba 14 ^(?!(.)+\1)|ef 2013-12-26 14:37:35 sammiya (GH)
  14 [unpublished] 2014-01-07 12:27:38 cesium (RG~) (discovery date is earlier than indicated date)
  14 ^(?!(.)+\1)|.u 2017-07-27 13:21:15 depperm (GH)
A man, a plan 13 [unpublished] before 2013-12-20 Scott (RG~)
  13 ^(.)[^p].*\1$ 2013-12-20 12:10:04 Bisqwit (R)
  ^(.)[^p].*\1$ 2013-12-20 15:43:30 hyp0 (HN)
  15 ^(\w(?!p)).*\1$ 2013-12-20 18:48:59 Athox (R) - edited 2013-12-20 20:23:59
Prime 14 ^(?!(11+)\1+$)**** 1997-10-22 18:17:07 Abigail (P)
  14 [unpublished] before 2013-12-20 alok (RG~)
  14 ^(?!(xx+)\1+$) 2013-12-20 11:18:54 Rhomboid (R)
  14 ^(?!(xx+)\1+$) 2013-12-20 12:10:04 Bisqwit (R)
  16 ^(?!(..+)(\1)+$) 2013-12-20 16:14:12 josephlord (HN)
Four 11 (.)(.\1){3} before 2013-12-20 alok (RG~)
  14 ([aeio]).{5}\1 2013-12-20 11:18:54 Rhomboid (R)
  11 (.)(.\1){3} 2013-12-20 12:10:04 Bisqwit (R)
  (.)(.\1){3} 2013-12-20 13:13:38 osuushi (R)
  (.)(.\1){3} 2013-12-20 15:05:14 chrismorgan (HN)
Order 11 ^[^o]?.{5}$ before 2013-12-20 andersk (RG~,GH)
  36 ^[ab][cde]|(?!lry|.ss|.e)..[pstwyz]$ 2013-12-20 11:18:54 Rhomboid (R)
  11 ^.{5}[^e]?$ 2013-12-20 12:10:04 Bisqwit (R)
  31 ^([^r]+[^nrem])$|ee.|.[eo]r[ty] 2013-12-20 15:24:00 Overv (R) - edited 2013-12-20 15:56:16; it is unknown if the regex was longer before the edit
  11 ^.{5}[^e]?$ 2013-12-20 16:13:09 noggin-scratcher (R)
  ^.{5}[^e]?$ 2013-12-20 21:50:12 ekke (HN)
  ^[^o]?.{5}$ 2013-12-20 22:13:14 balrok (GH)
Triples 34 [02-5][123][257]|[07][0269]+3?$|55 before 2013-12-20 andersk (RG~,GH)
  56 ^(([147]4|40|3[269]|9[05]|[378]1).+|0[369]*|[81][257])*$ 2013-12-20 12:10:04 Bisqwit (R)
  44 ^[387][12479]|00($|[369]|1[25])|5[54]|2[437] 2013-12-21 10:05:27 grobie (GH)
  40 00($|[369]|1[25])|(^.|9|3)..5|4.2|^[38]1 2013-12-23 03:15:47 alexandrosm (GH)
  39 32|.[25][345].|00([369]|1[25]|$)|[07]2$ 2013-12-23 07:10:33 rabcyr (GH)
  36 00([369]|1[25]|$)|.1.+4|3.*7.|4.2|55 2013-12-23 12:55:08 alexandrosm (GH)
  34 00($|3|6|9|12|15)|4.2|.1.+4|55|.17 2013-12-23 21:02:53 alexandrosm (GH)
Glob 17 [unpublished] before 2013-12-20 andersk (RG~,GH)
  23 ai|c$|^p|[bcnrw][bnopr] 2013-12-21 18:37:50 nwellnhof (HN)
  [bncrw][bporn]|^p|c$|ta 2013-12-23 16:04:15 bbarry (GH) - some regexes in this comment were edited after the indicated date; may include this regex
  [bcnrw][bnopr]|^p|t[a*] 2018-12-01 Davidebyzero (GH,RG)
  [bcnrw][bnopr]|^p|en.?t 2018-12-01 Davidebyzero (GH,RG)
  [cnprw][opr]|le\w|ai|c$ 2018-12-08 Davidebyzero (GH,RG)
  [cnprw][opr]|le\w|ta|c$ 2018-12-08 Davidebyzero (GH,RG)
  [cnprw][opr]|le\w|t[a*] 2018-12-08 Davidebyzero (GH,RG)
  [cnprw][opr]|le\w|en.?t 2018-12-08 Davidebyzero (GH,RG)
  60 ^(.*)\*(.*) .* \1.+\2$|^(.+) .* \3$|^.*\*(.*)\*.* .* .+\4.+$ 2014-01-08 18:00:49 sorcio (GH)
  66 ^(.*) .* \1$|^(.*)\*(.*) .* \2.+\3$|(.*)\*(.*)\*(.*) .* \4.+\5.+\6 2014-01-13 04:30:24 sshock (GH)
  54 ^((\w*)( .+ \2$|\*(\w*)( .+ \2.+\4$|\*.* .+ \2.+\4.))) 2014-02-13 04:55:56 Davidebyzero (GH)
  50 ^((.*)(.+ \2$|\*(.*)( .+ \2.+\4$|\*.*.+ \2.+\4.))) 2018-12-11 Davidebyzero (GH)
  22 [unpublished] Gael (RG)
  21 [unpublished, unverified] LLB (RG)
Balance 24 [unpublished] before 2013-12-20 andersk (RG~,GH)
  34 ^(<(<(<(<(<(<.*>)*>)*>)*>)*>)*>)*$ 2013-12-20 15:24:00 Overv (R) - edited 2013-12-20 15:56:16; it is unknown if the regex was longer before the edit
  ^(<(<(<(<(<(<<>>)*>)*>)*>)*>)*>)*$ 2013-12-20 16:13:39 nadinengland (HN)
  33 ^(<(<(<(<(<(<.*)*>)*>)*>)*>)*>)*$ 2013-12-20 18:39:40 jensweh (R)
  32 ^(<(<(<(<(<>)*>|.{9})*>)*>)*>)*$ 2014-01-02 22:55:11 alexandrosm (GH)
  31 ^(<(<(<(<<?>?>|.{9})*>)*>)*>)*$ 2014-01-05 14:04:09 alexandrosm (GH)
  26 .{37}|^(<(..(?!<.>$))*>)*$ 2014-02-27 01:49:48 Davidebyzero (GH,RG)
  22 [unpublished] TH (RG)
Powers 17 [unpublished] before 2013-12-20 andersk (RG~,GH)
  54 ^((((((((((x)\10?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$ 2013-12-20 13:26:43 Iwonderifthisistaken (R)
  52 ^xx?$|^((((((((x{4})\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$ 2013-12-20 15:07:07 Hrafnahnef (R)
  52 ^((xx?)\2?|(((((((x{8})\9?)\8?)\7?)\6?)\5?)\4?)\3?)$ 2013-12-20 15:18:10 Bisqwit (R)
  51 ^(x|(xx){1,4}|((((((x{16})\8?)\7?)\6?)\5?)\4?)\3?)$ 2013-12-20 15:26:55 Bisqwit (R)
  41 ^(x|(xx){1,10}|(x{32}){1,4}|(x{32}){6,})$ 2013-12-20 18:16:49 Iwonderifthisistaken (R)
  50 ^(((((((((xx?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$ 2013-12-20 18:39:40 jensweh (R)
  30 ^(((x|x{8}|x{128})\3?)\2?)\1?$ 2013-12-20 18:43:08 pondscum (R)
  17 ^(?!(.(..)+)\1*$) 2013-12-20 19:18:06 plby (GH)
  ^(?!(x(xx)+)\1*$)
  36 ^(x{64})+$|^((((x?x)\5?)\4?)\3?)\2?$ 2013-12-20 23:36:55 q1u2acker (R)
  33 ^((x{8}){1,5}|(x{64})+|xx?|xxxx)$ 2014-01-12 23:07:15 sneakyruds (R)
  31 ^(((x|x{16}|x{256})\3?)\2?)\1?$ 2014-02-12 16:09:28 Davidebyzero (GH)
  17 ^((x+)(?=\2$))*x$ 2014-02-21 21:30:06 Davidebyzero (GH,RG)
Long count 14 [unpublished] 2014-01-07 12:27:38 timloh (RG~) (discovery date is earlier than indicated date)
  15 ((.+)0\2[1]){8} 2014-01-15 06:28:48 abjr (GH)
  14 ((.+)0\2+1){8} 2014-01-15 12:04:50 hugetoon (GH)
Alphabetical 78 ^(?!.*(rne|eet |e.r...t|er.{6}r$))(a\S+\s)*(e\S+\s)*(r\S+\s)*([st]\S+(\s|$))*$ 2013-12-25 05:25:31 muxrwc (GH)
  46 [^et] ren|[er]( \w+)\1|tate r|a t| ae|rt r|e e 2013-12-25 15:31:12 alexandrosm (GH)
  45 [^et] ren|[er]( \w+)\1|(tat|r). r|a t| ae|e e 2013-12-25 16:26:59 alexandrosm (GH)
  41 s ren|[er]( \w+)\1|(tat|r). r|a t| ae|e e 2013-12-25 16:59:02 alexandrosm (GH)
  37 r sn|( t\w+)\1|(tat|r). r|a t| ae|e e 2013-12-25 23:45:16 alexandrosm (GH)
  36 ( .+[ts]..)\1|(tat|r). r|a t| ae|e e 2013-12-27 21:56:51 bbarry (GH)
  33 ( .+[ts]..)\1|(tat|r). r|a t|e .r 2013-12-30 00:22:58 alexandrosm (GH)
  23 .r.{32}r|a.{10}te|n.n.. 2013-12-31 17:04:35 alexandrosm (GH)
  23 [unpublished] 2014-01-07 12:27:38 timloh (RG~) - probably copied alexandrosm's solution
  54 ^(?!.* ((.*)t.* \2[es]|(.*)s.* \3[nr]|(.*)r.* \4[en])) 2014-01-13 00:25:24 dcwarwick (GH)
  43 ^(?!.*( .*)(t.*\1[es]|s.*\1[nr]|r.*\1[en])) 2014-02-15 04:48:38 Davidebyzero (GH) - optimization of dcwarwick's solution
  22 [unpublished, unverified] LLB (RG)
Powers 2 19 ^((x+)\2(?=\2$))*x$ 2014-04-25 22:45:17 Davidebyzero (GH,RG)
  22 ^(?!((xxx)+x|xx|)\1*$) 2014-09-18 03:05:37 muxrwc (GH)
  21 ^(?!(x(xxx)+|xx)\1*$) TH (RG), Davidebyzero (GH,RG)

Robust solutions

Level Length Regex Domain Date Credit
Plain strings 3 foo ^[A-Za-z][a-z]*$
Anchors 4 ick$ ^[A-Za-z][a-z]*ick[a-z]*$
Ranges 8 ^[a-f]*$ ^[a-z]+$
Backrefs 9 (...).*\1 ^[a-z]+$
Abba 17 ^(?!.*(.)(.)\2\1) ^[a-z]+$
A man, a plan 14 ^(.)(.).*\2\1$
  40 ^(.?)(.?)(.?)(.?)(.?)(.?).?\6\5\4\3\2\1$ ^[a-z]+$*
Prime 14 ^(?!(11+)\1+$)**** ^11+$ 1997-10-22 18:17:07 Abigail (P)
  - ^(11+?)\1+$***** ^11+$ 1997-10-23 17:53:10 John L. Allen (P)
  14 ^(?!(xx+)\1+$) ^xx+$
  15 ^(?!(xx+|)\1+$) ^x*$*** 2014-03-13 14:12:05 Davidebyzero (GH)
  - ^1?$|^(11+?)\1+$***** ^1*$ 1997-11-19 Abigail (P)
  16 ^(?!(xx+)\1+$)xx ^x*$ 2014-03-13 14:50:18 teukon (GH)
  18 ^(?=(xx+?)\1*$)\1$****** ^x*$ 2018-12-07 Davidebyzero (GH)
  18 ^(?>(x(x*))\1+$)\2****** ^x*$ 2018-12-07 Davidebyzero (GH)
Four 11 (.)(.\1){3} ^[A-Za-z][a-z]*$
Order 54 ^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]+$
Triples 107 ^([0369]|[258][0369]*[147]|([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147]))*$ ^.+$ 2013-03-27 21:49:49 joel
  107 ^([0369]|[147][0369]*[258]|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))*$ ^.+$
  106 ^(?=((.*?[147]){3})*((.*?[147]|){2}))(?=((.*?[258]){3})*((.*?[258]|){2})).*$(\3\7|\4\8(?!\3|\7)|(?!\4|\8)) ^[0-9]+$ 2014-02-14 to 2014-02-25 Davidebyzero & teukon (GH) (for full history, see below)
Glob 81 ^(\*?)(\w*)(\*?)(\w*)(\*?)(\w*) .* ((?!\1).+|\1)\2((?!\3).+|\3)\4((?!\5).+|\5)\6$ 2014-01-07 10:52:43 DiEvAl (GH) - created before hard mode; didn't match the domain of hard mode
  78 ^(\*?)(.*)(\*?)(.*)(\*?)(.*) .* ((?!\1).+|\1)\2((?!\3).+|\3)\4((?!\5).+|\5)\6$ 2014-01-15 20:35:11 teukon (GH) - DiEvAl's solution modified to assume that * never occurs to the right of matches
  84 ^(.*)(\*?)(.*)(\*?)(.*)(\*?)(.*) .* \1((?!\2).+|\2)\3((?!\4).+|\4)\5((?!\6).+|\6)\7$ see below 2014-04-26 02:26:43 Davidebyzero (GH) - DiEvAl's solution modified to assume that * never occurs to the right of matches, and to match hard mode
Balance 37 ^(<(<(<(<(<(<(<>)*>)*>)*>)*>)*>)*>)*$ ^[<>]*$**
Powers 17 ^(?!(x(xx)+)\1*$) ^x+$
  17 ^((x+)(?=\2$))*x$ ^x*$ 2014-02-21 21:30:06 Davidebyzero (GH,RG)
  17 ^(?!(x*)(\1\1)+$) ^x*$ 2019-02-05 Grimy (GH)
Long count 31 ^((?=(\S*)0).{4} (?=\2[1]))+1+$ ^([01]{4}([1 [(?!$)|$)){16}$ 2014-02-25 Davidebyzero (GH)
  35 ^((?=(\S*)0).{4} (?=\2[1])){15}\2.$ ^[01 ]{79}$ or ^.*$ 2014-02-25 22:33:53 teukon (GH)
Alphabetical 76 ^(?!.*\b((.*)n.*\b\2[e]|(.*)r.*\b\3[ne]|(.*)s.*\b\4[rne]|(.*)t.*\b\5[srne])) ^([aenrst]{6}( (?!$)|$)){7}$ 2014-01-09 06:49:57 AlanDeSmet (GH)
  58 ^(?!.*\b(.*)(e|(n|r|(s|t))).* \1(a|(?!\3)[en]|(?!\4)[rs])) ^([aenrst]{6}( (?!$)|$)){7}$ 2014-01-15 23:57:01 teukon (GH)
Powers 2 19 ^((x+)\2(?=\2$))*x$ ^x*$ 2014-04-25 22:45:17 Davidebyzero (GH,RG)
  23 ^(?!(x(xxx)+x?|xx)\1*$) ^x+$ 2018-12-05 Davidebyzero (GH)
  24 ^(?!(x(xxx)+x?|xx|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)

* A man, a plan - impossible in the general case, so this solution has a maximum robust length of 13 letters.
** Balance - impossible in the general case, so this solution has a maximum depth of 7 nesting levels.
*** If 1 is considered to be a prime number.
**** Included for historical purposes. Not technically a valid solution to this level since it works on 1s instead of xs.
***** Included for historical purposes. Not technically a valid solution to this level since it matches non-primes instead of primes and works on 1s instead of xs.
****** Of interest because of the implicit rather than explicit rejection of 0 and 1 as primes.

Robust solutions for Triples

Length Regex Domain Date Credit
  229 ^([0369]|[258][0369]*[147]|[147]([0369]|[147][0369]*[258])*[258]|[258][0369]*[258]([0369]|[147][0369]*[258])*[258]|[147]([0369]|[147][0369]*[258])*[147][0369]*[147]|[258][0369]*[258]([0369]|[147][0369]*[258])*[147][0369]*[147])*$ ^.+$ 2013-03-27 20:58:04 Alok Menghrajani
  107 ^([0369]|[258][0369]*[147]|([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147]))*$ ^.+$ 2013-03-27 21:49:49 joel
  ^([0369]|[147][0369]*[258]|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))*$ ^.+$
  255 ^((?=(([^147]*[147]){3})*[^147]*$)(?=(([^258]*[258]){3})*[^258]*$)|(?=(([^147]*[147]){3})*[^147]*[147][^147]*$)(?=(([^258]*[258]){3})*[^258]*[258][^258]*$)|(?=(([^147]*[147]){3})*([^147]*[147]){2}[^147]*$)(?=(([^258]*[258]){3})*([^258]*[258]){2}[^258]*$)) ^[0-9]+$ 2014-02-13 07:11:40 Davidebyzero (GH)
  241 ^((?=(([^258]*[258]){3})*[^258]*$)(([^147]*[147]){3})*[^147]*|(?=(([^258]*[258]){3})*[^258]*[258][^258]*$)(([^147]*[147]){3})*[^147]*[147][^147]*|(?=(([^258]*[258]){3})*([^258]*[258]){2}[^258]*$)(([^147]*[147]){3})*([^147]*[147]){2}[^147]*)$ ^[0-9]+$ 2014-02-13 07:36:23 Davidebyzero (GH)
  227 ^((?=(([^258]*[258]){3})*[^258]*$)(([^147]*[147]){3})*|(?=(([^258]*[258]){3})*[^258]*[258][^258]*$)(([^147]*[147]){3})*[^147]*[147]|(?=(([^258]*[258]){3})*([^258]*[258]){2}[^258]*$)(([^147]*[147]){3})*([^147]*[147]){2})[^147]*$ ^[0-9]+$ 2014-02-13 09:52:00 Davidebyzero (GH)
  222 ^((?=(((([^258]*[258]){3})*[^258]*)|((([^258]*[258]){3})*[^258]*[258][^258]*)|((([^258]*[258]){3})*([^258]*[258]){2}[^258]*)|([^258]*))$)(([^147]*[147]){3})*(\6\6\9\9|\3\3\13\13[^147]*[147](\9\9|\6\6[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 14:43:43 Davidebyzero (GH)
  180 ^((?=((([^258]*[258]){3})*[^258]*))(?=((\2)|(\2[258][^258]*)|(\2([258][^258]*){2})|([^258]*))$)(([^147]*[147]){3})*(\7\7\8\8|\6\6\10\10[^147]*[147](\8\8|\7\7[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 14:51:01 Davidebyzero (GH)
  ^((?=((([^258]*[258]){3})*[^258]*)(.*)$)(?=((\2)|(\2[258][^258]*)|(\2([258][^258]*){2})|(\3))$)(([^147]*[147]){3})*(\8\8\9\9|\7\7\11\11[^147]*[147](\9\9|\8\8[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 15:08:35 Davidebyzero (GH)
  176 ^((?=((([^258]*[258]){3})*[^258]*))(?=((\2)|(\2[258][^258]*)|\2([258][^258]*){2}|([^258]*))$)(([^147]*[147]){3})*(\7\7\8\8|\6\6\9\9[^147]*[147](\8\8|\7\7[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 15:29:20 Davidebyzero (GH)
  170 ^((?=((([^258]*[258]){3})*[^258]*))(?=((\2)|(\2[258][^258]*)|\2([258][^258]*){2}|([^258]*))$)(([^147]*[147]){3})*(\7\7\8\8|\6\9[^147]*[147](\8\8|\7[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 15:36:30 Davidebyzero (GH)
  169 ^((?=((([^258]*[258]){3})*[^258]*))(?=((\2)|((\2[258][^258]*)|\2([258][^258]*){2})|([^258]*))$)(([^147]*[147]){3})*(\7\7|\6\10[^147]*[147](\9\9|\8[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 15:47:33 Davidebyzero (GH)
  168 ^((?=((([^258]*[258]){3})*[^258]*))(?=(((\2[258][^258]*)|\2([258][^258]*){2})|((\2)|([^258]*)))$)(([^147]*[147]){3})*(\6\6|\9[^147]*[147](\8\8|\7[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 15:52:22 Davidebyzero (GH)
  164 ^((?=((([^258]*[258]){3})*[^258]*))(?=(((\2[258][^258]*)|\2([258][^258]*){2})|(\2|[^258]*))$)(([^147]*[147]){3})*(\6\6|\9[^147]*[147](\8\8|\7[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 15:53:11 Davidebyzero (GH)
  163 ^((?=((([^258]*[258]){3})*[^258]*))(?=(((\2[258][^258]*)|\2([258][^258]*){2})|(\2[^258]*))$)(([^147]*[147]){3})*(\6\6|\9[^147]*[147](\8\8|\7[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 15:59:11 Davidebyzero (GH)
  156 ^((?=((([^258]*[258]){3})*[^258]*))(?=(((\2[258][^258]*)|\2([258][^258]*){2})|(\2))$)(([^147]*[147]){3})*(\6\6|\9[^147]*[147](\8\8|\7[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 16:02:02 Davidebyzero (GH)
  156 ^((?=((([^258]*[258]){3})*[^258]*))(?=((\2([258][^258]*)|\2([258][^258]*){2})|(\2))$)(([^147]*[147]){3})*(\6\6|\9[^147]*[147](\8\8|\7[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 16:09:21 Davidebyzero (GH)
  158 ^((?=((([^258]*[258]){3})*[^258]*))(?=((\2)|((\2[258][^258]*)|(\2([258][^258]*){2})))$)(([^147]*[147]){3})*(\7\7|\6[^147]*[147](\9\9|\8[^147]*[147]))[^147]*)$ ^[0-9]+$ 2014-02-13 16:15:43 Davidebyzero (GH)
  156 ^(?=((([^258]*[258]){3})*[^258]*))(?=((\1)|((\1[258][^258]*)|(\1([258][^258]*){2})))$)(([^147]*[147]){3})*(\6\6|\5[^147]*[147](\8\8|\7[^147]*[147]))[^147]*$ ^[0-9]+$ 2014-02-14 13:29:23 Davidebyzero (GH)
  153 ^(?=(([^258]*[258]){3})*[^258]*([258][^258]*([258][^258]*)?)?$)(([^147]*[147]){3})*(?=([^147]*))\7((?!\3)(?=([147][^147]*))\9((?!\4)[147][^147]*|\4)|\3)$ ^[0-9]+$ 2014-02-15 06:45:47 Davidebyzero (GH)
  157 ^(?=[^147]*([147]?)[^147]*([147]?)[^147]*(([147][^147]*){3})*$)[^258]*((?=.*$\1)|(?!.*$\1)[258])[^258]*((?=.*$\2)|(?!.*$\2)[258])[^258]*(([258][^258]*){3})*$ ^[0-9]+$ 2014-02-16 20:55:58 teukon (GH) (discovery date is probably earlier)
  153 ^(?=(([^258]*[258]){3})*[^258]*([258]?)[^258]*([258]?)[^258]*$)(([^147]*[147]){3})*(?=([^147]*))\7((?!\3)(?=([147][^147]*))\9((?!\4)[147][^147]*|\4)|\3)$ ^[0-9]+$ 2014-02-17 11:36:59 Davidebyzero (GH)
  145 ^(?=(([^258]*[258]){3})*[^258]*([258]?)[^258]*([258]?)[^258]*$)(([^147]*[147]){3})*(?=([^147]*))\7((?!\3)(?=(.[^147]*))\9((?!\4).[^147]*|\4)|\3)$ ^[0-9]+$ 2014-02-17 20:23:11 teukon (GH)
  ^(?=[^147]*([147]?)[^147]*([147]?)[^147]*(([147][^147]*){3})*$)(?=([^258]*))\5(\1|(?!\1).)(?=([^258]*))\7(\2|(?!\2).)[^258]*(([258][^258]*){3})*$ ^[0-9]+$ 2014-02-17 20:23:11 teukon (GH)
  137 ^(?=(([^258]*[258]){3})*[^258]*(.?)[^258]*(.?)[^258]*$)(([^147]*[147]){3})*(?=([^147]*))\7((?!\3).|\3)(?=([^147]*))\9((?!\4).|\4)[^147]*$ ^[0-9]+$ 2014-02-18 08:01:51 Davidebyzero (GH)
  ^(?=[^147]*(.?)[^147]*(.?)[^147]*(([147][^147]*){3})*$)(?=([^258]*))\5(\1|(?!\1).)(?=([^258]*))\7(\2|(?!\2).)[^258]*(([258][^258]*){3})*$ ^[0-9]+$ 2014-02-18 08:01:51 Davidebyzero (GH)
  ^(?=[^147]*(.?)[^147]*(.?)[^147]*(([147][^147]*){3})*$)(?=([^258]*))\5(?=(\1|.))\6(?=([^258]*))\7(?=(\2|.))\8[^258]*(([258][^258]*){3})*$ ^[0-9]+$ 2014-02-18 08:01:51 Davidebyzero (GH)
  127 ^(?=(([^147]*[147]){3})*[^147]*(.?)[^147]*(.?))(?=(([^258]*[258]){3})*[^258]*(.?)[^258]*(.?))\d+$(\3\7|\4\8(?!\3|\7)|(?!\4|\8)) ^.*$ 2014-02-18 12:23:02 Davidebyzero (GH)
  126 ^(?=(([^147]*[147]){3})*[^147]*(.?)[^147]*(.?))(?=(([^258]*[258]){3})*[^258]*(.?)[^258]*(.?)).+$(\3\7|\4\8(?!\3|\7)|(?!\4|\8)) ^[0-9]*$ 2014-02-18 12:23:02 Davidebyzero (GH)
  119 ^(?=((.*?[147]){3})*[^147]*(.?)[^147]*(.?))(?=((.*?[258]){3})*[^258]*(.?)[^258]*(.?))\d+$(\3\7|(?!\3|\7)\4\8|(?!\4|\8)) ^.*$ 2014-02-18 18:55:50 teukon (GH)
  118 ^(?=((.*?[147]){3})*[^147]*(.?)[^147]*(.?))(?=((.*?[258]){3})*[^258]*(.?)[^258]*(.?)).*$(\3\7|(?!\3|\7)\4\8|(?!\4|\8)) ^[0-9]*$ 2014-02-18 18:55:50 teukon (GH)
  111 ^(?=((.*?[147]){3})*(((.*?[147])?){2}))(?=((.*?[258]){3})*(((.*?[258])?){2}))\d+$(\3\8|\4\9(?!\3|\8)|(?!\4|\9)) ^.*$
  110 ^(?=((.*?[147]){3})*(((.*?[147])?){2}))(?=((.*?[258]){3})*(((.*?[258])?){2})).*$(\3\8|\4\9(?!\3|\8)|(?!\4|\9)) ^[0-9]+$ 2014-02-19 10:48:11 Davidebyzero (GH)
  107 ^(?=((.*?[147]){3})*((.*?[147]|){2}))(?=((.*?[258]){3})*((.*?[258]|){2}))\d+$(\3\7|\4\8(?!\3|\7)|(?!\4|\8)) ^.*$
  106 (?=((.*?[147]){3})*((.*?[147]|){2}))(?=((.*?[258]){3})*((.*?[258]|){2}))^.*$(\3\7|(?!\3|\7)\4\8|(?!\4|\8)) ^[0-9]+$ 2014-02-25 01:50:02 teukon (GH)
  106 ^(?=((.*?[147]){3})*((.*?[147]|){2}))(?=((.*?[258]){3})*((.*?[258]|){2})).*$(\3\7|\4\8(?!\3|\7)|(?!\4|\8)) ^[0-9]+$

Robust solutions for Powers of various bases

Base Length Regex Domain Date Credit
  0 2 ^$ ^x*$
  1 3 ^x$ ^x*$
  2 17 ^((x+)(?=\2$))*x$ ^x*$ 2014-02-21 21:30:06 Davidebyzero (GH,RG)
  17 ^(?!(.(..)+)\1*$) ^x+$ 2013-12-20 19:18:06 plby (GH)
  17 ^(?!(x(xx)+)\1*$) ^x+$
  18 ^(?!(x(xx)+|)\1*$) ^x*$ 2014-03-13 13:21:03 Davidebyzero (GH)
  17 ^(?!(x*)(\1\1)+$) ^x*$ 2019-02-05 Grimy (GH)
  3 19 ^((x+)\2(?=\2$))*x$ ^x*$ 2014-04-25 22:45:17 Davidebyzero (GH,RG)
  23 ^(?!(x(xxx)+x?|xx)\1*$) ^x+$ 2018-12-05 Davidebyzero (GH)
  24 ^(?!(x(xxx)+x?|xx|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)
  25 ^(?!((xxx)*(xx)\3?|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)
  31 ^(?!(x*)(?!(\1\1)(\1\2)*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  30 ^(?!(x*)(?!\1\1(\1{3})*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  26 ^(?!(x*)(\1|(\1{3})+\1?)$) ^x*$ 2019-02-08 Davidebyzero (GH)
  4 21 ^((x+)\2\2(?=\2$))*x$ ^x*$ 2018-12-05 Davidebyzero (GH)
  5 22 ^((x+)\2{3}(?=\2$))*x$ ^x*$ 2018-12-05 Davidebyzero (GH)
  33 ^(?!(x(x{5})+x?x?x?|xxx?x?|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)
  33 ^(?!(x(x{5})+x{0,3}|x{2,4}|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)
  31 ^(?!(xx(x{5})*(x{4}|x?x?))\1*$) ^x+$ 2018-12-05 Davidebyzero (GH)
  32 ^(?!(xx(x{5})*(x{4}|x?x?)|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)
  32 ^(?!(x*)(?!(\1{4})(\1\2)*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  31 ^(?!(x*)(?!\1{4}(\1{5})*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  34 ^(?!(x*)(\1?\1?(\1|(\1{5})+\1?))$) ^x*$ 2019-02-08 Davidebyzero (GH)
  35 ^(?!(x*)(\1{1,3}|(\1{5})+\1{0,3})$) ^x*$ 2019-02-08 Davidebyzero (GH)
  6 22 ^((x+)\2{4}(?=\2$))*x$ ^x*$ 2014-02-21 21:40:31 teukon (GH)
  7 22 ^((x+)\2{5}(?=\2$))*x$ ^x*$ 2018-12-05 Davidebyzero (GH)
  32 ^(?!(x(x{7})+x{0,5}|x{2,6})\1*$) ^x+$ 2018-12-05 Davidebyzero (GH)
  33 ^(?!(x(x{7})+x{0,5}|x{2,6}|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)
  34 ^(?!(xx(x{7})*(x{6}|x{0,4})|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)
  32 ^(?!(x*)(?!(\1{6})(\1\2)*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  31 ^(?!(x*)(?!\1{6}(\1{7})*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  35 ^(?!(x*)(\1{0,4}(\1|(\1{7})+\1?))$) ^x*$ 2019-02-08 Davidebyzero (GH)
  35 ^(?!(x*)(\1{1,5}|(\1{7})+\1{0,5})$) ^x*$ 2019-02-08 Davidebyzero (GH)
  8 22 ^((x+)\2{6}(?=\2$))*x$ ^x*$ 2018-12-05 Davidebyzero (GH)
  9 22 ^((x+)\2{7}(?=\2$))*x$ ^x*$ 2018-12-05 Davidebyzero (GH)
  10 22 ^((x+)\2{8}(?=\2$))*x$ ^x*$ 2018-12-05 Davidebyzero (GH)
  11 22 ^((x+)\2{9}(?=\2$))*x$ ^x*$ 2018-12-05 Davidebyzero (GH)
  34 ^(?!(x(x{11})+x{0,9}|x{2,10})\1*$) ^x+$ 2018-12-05 Davidebyzero (GH)
  35 ^(?!(x(x{11})+x{0,9}|x{2,10}|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)
  33 ^(?!(x*)(?!(\1{10})(\1\2)*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  33 ^(?!(x*)(?!\1{10}(\1{11})*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  36 ^(?!(x*)(\1{0,8}(\1|(\1{11})+\1?))$) ^x*$ 2019-02-08 Davidebyzero (GH)
  36 ^(?!(x*)(\1{1,9}|(\1{11})+\1{0,9})$) ^x*$ 2019-02-08 Davidebyzero (GH)
  12 23 ^((x+)\2{10}(?=\2$))*x$ ^x*$ 2018-12-05 Davidebyzero (GH)
  13 23 ^((x+)\2{11}(?=\2$))*x$ ^x*$ 2018-12-05 Davidebyzero (GH)
  35 ^(?!(x(x{13})+x{0,11}|x{2,12})\1*$) ^x+$ 2018-12-05 Davidebyzero (GH)
  36 ^(?!(x(x{13})+x{0,11}|x{2,12}|)\1*$) ^x*$ 2018-12-05 Davidebyzero (GH)
  33 ^(?!(x*)(?!(\1{12})(\1\2)*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  33 ^(?!(x*)(?!\1{12}(\1{13})*$)\1+$) ^x+$ 2019-02-08 Davidebyzero (GH)
  37 ^(?!(x*)(\1{0,10}(\1|(\1{13})+\1?))$) ^x*$ 2019-02-08 Davidebyzero (GH)
  38 ^(?!(x*)(\1{1,11}|(\1{13})+\1{0,11})$) ^x*$ 2019-02-08 Davidebyzero (GH)

If the domain of Glob must be stated in a single regex, it would be:
^([a-z]*)\*?([a-z]*)\*?([a-z]*)\*?([a-z]*) matches \1[a-z]*\2[a-z]*\3[a-z]*\4$
However, it may actually have 4 domains:
^([a-z]*)\*([a-z]+)\*([a-z]*) matches \1[a-z]*\2[a-z]*\3$
^\*([a-z]+)\*([a-z]+)\* matches [a-z]+\1[a-z]+\2[a-z]+$ (left only)
^([a-z]+)\*([a-z]+) matches [a-z]*\1[a-z]+\2[a-z]*$ (right only)
^\*?([a-z]+)\*? matches [a-z]*\1[a-z]*$

The domains above may be controversial, as we have a limited sampling. Feel free to discuss them in this Gist.

Triples (107) DFA solution, pretty-printed:

^( [0369] | [258][0369]*[147] |
  ( [147] | [258][0369]*[258])
  ([0369] | [147][0369]*[258])*
  ( [258] | [147][0369]*[147]))*$

Triples (106) lookahead + backreferences solution, pretty-printed:

^(?=((.*?[147]){3})*((.*?[147]|){2}))
 (?=((.*?[258]){3})*((.*?[258]|){2}))
 .*$(\3\7 | \4\8(?!\3|\7) | (?!\4|\8))

Glob (84), pretty-printed:

^(.*)(\*?)
 (.*)(\*?)
 (.*)(\*?)(.*) .* \1((?!\2).+|\2)
                  \3((?!\4).+|\4)
                  \5((?!\6).+|\6)\7$
@teukon

This comment has been minimized.

Copy link

commented Feb 26, 2014

I'd argue that the domains for Long count and Long count v2 are both ^.*$, particularly given hint for Long count v2: "This is a bit of a spoiler for the previous level". At the very least, I might consider the domain ^[01 ]*$ or ^[01 ]{79}$.

Also, you've got instances of \| in your domain strings which should be |.

Nice to see my solution to Anchors mentioned. My own interpretation of the problem is that the domain would include strings like "Nickleback" but that these should not be matched against. I admit that the problem is ambiguous.

I'm sure I have much more to say but I'm in a hurry this morning and will be out all day. More to come.

@Davidebyzero

This comment has been minimized.

Copy link
Owner Author

commented Feb 26, 2014

Also, you've got instances of \| in your domain strings which should be |.

Oops, thanks. This was because the |s broke the table, and I tried to remedy that by escaping them but it didn't work. So I took them out of the table, but forgot to un-escape them. Fixed.

@Davidebyzero

This comment has been minimized.

Copy link
Owner Author

commented Feb 26, 2014

I'd argue that the domains for Long count and Long count v2 are both ^.*$, particularly given hint for Long count v2: "This is a bit of a spoiler for the previous level".

I don't understand your logic here. Could you please explain why you think the comment means this?

I think there's no evidence that Long Count has a domain anywhere close to ^.*$ or even ^[01 ]{79}$. There's also the fact that it's much more interesting to treat them as having different domains, so that they can have different robust solutions.

Though, if I were playing devil's advocate against myself, I would say that there's evidence that [01] instead of or instead of [01] is an error with low probability, given that each error occurs only once in Long Count v2, and that given this low probability, it may just be chance that they didn't occur in Long Count. Then I would refute this by saying that it's most likely that Erling created Long Count v2 to make the problem harder, and deliberately added these two extra types of errors. Then the devil's advocate version of myself would say, maybe the chance for those errors was in the cards all along, and Erling merely rolled the dice again because the first rolling resulted in too easy a problem. Then I would refute this again by saying, if the easiness of the first Long Count had occurred by chance, he would have re-rolled to get it right the first time — and that this is a specious argument anyway, because he most likely created it by hand, not with a random problem set generator.

Actually I think the domain of Long Count v2 may even be ^([01 ]{79}|suffusion of yellow)$, especially given what the Dirk Gently's Holistic Detective Agency reference actually refers to. It's just that it makes the problem more interesting to call it ^.*$.

@Davidebyzero

This comment has been minimized.

Copy link
Owner Author

commented Feb 26, 2014

Nice to see my solution to Anchors mentioned. My own interpretation of the problem is that the domain would include strings like "Nickleback" but that these should not be matched against. I admit that the problem is ambiguous.

Yes, I totally agree; I think it's much more likely the robust solution is ick$. This regex dictionary returns only 10 words for ick(?!.*ick$).*k$ (incidentally the same result as ick.*k$), whereas it returns 313 words for ick. This places the probability at about 49% that out of the 21 ick words chosen, none of them would have k$.

@teukon

This comment has been minimized.

Copy link

commented Feb 27, 2014

I'd argue that the domains for Long count and Long count v2 are both ^.*$, particularly given hint for Long count v2: "This is a bit of a spoiler for the previous level".

I don't understand your logic here. Could you please explain why you think the comment means this?

I've thought about this and revised my opinion. I'd been assuming that the hint of Long Count v2 was to signal to the player that the point of the problem (both problems) was to construct a regex which matched the given string and that string alone. The first time I saw Long Count I immediately assumed that was the task (so I've been operating with some bias).

However, on reflection, it does seem that perhaps the hint was to signal to the player that they didn't have to do this for Long Count; that they could assume a restricted domain of strings. Unfortunately, that domain is highly ambiguous.

I think there's no evidence that Long Count has a domain anywhere close to ^.*$ or even ^[01 ]{79}$.

From a random mutations point of view, the same could be said of Abba's domain (which is nothing like ^[a-b]+$).

I suggested these domains because they were simple and contained all the given strings. I didn't give it much thought simply because, anything more complex than ^[01 ]{79}$ would be too arbitrary to consider (and make for a highly dissatisfying problem).

There's also the fact that it's much more interesting to treat them as having different domains, so that they can have different robust solutions.

Good point.

Then I would refute this by saying that it's most likely that Erling created Long Count v2 to make the problem harder, and deliberately added these two extra types of errors.

This is based on an opinion of Erling. I don't know him well enough to decide this one way or the other, but I know that my own aversion to creating an invoking such an arbitrary mutation rule is so strong that I'd put down to coincidence the only mutations concerning being from to1(which occurred 4 times). A domain of^([01]{4}[01 ]){15}[01]{4}$ seems more likely to me.

Personally, I would "re-roll the dice" as it were, because I'd not want my right-side strings to be random, but random subject to conveying a clear domain.

Actually I think the domain of Long Count v2 may even be ^([01 ]{79}|suffusion of yellow)$, especially given what the Dirk Gently's Holistic Detective Agency reference actually refers to. It's just that it makes the problem more interesting to call it ^.*$.

If the given strings do not clearly convey a simple, non-arbitrary domain then perhaps flag the problem with "unknown domain" or similar, perhaps fielding some suggestions. A solution would then not be robust but "robust with respect to domain X".

@teukon

This comment has been minimized.

Copy link

commented Feb 27, 2014

Oh, the Alphabetical domain string is slightly off. It should be something like ^([aenrst]{6} ){6}[aenrst]{6}$ or ^([aenrst]{6}( (?!$)|$)){7}$.

@teukon

This comment has been minimized.

Copy link

commented Feb 27, 2014

Surely, for Glob, the domain is something like:

^(?! )([a-z]*\*)*[a-z]* matches [a-z]+$

or one I like less but you may well prefer:

^([a-z]+|\*)+ matches [a-z]+$
@Davidebyzero

This comment has been minimized.

Copy link
Owner Author

commented Feb 28, 2014

A solution would then not be robust but "robust with respect to domain X".

I like this idea. :)

Oh, the Alphabetical domain string is slightly off. It should be something like ^([aenrst]{6}( (?!$)|$)){7}$.

I put the domain as ^([aenrst]{6}( (?=.)|$)){7}$ at first, but after some thought I simplified it because it seemed to me that the lookahead wasn't needed. But now I realize that I was right the first time, not the second.

I like your (?!$) better than my (?=.), so I will use it.

^(?! )([a-z]*\*)*[a-z]* matches [a-z]+$
^([a-z]+|\*)+ matches [a-z]+$

What is the purpose of the (?! )?

I don't think either of these domains would be possible to solve robustly in an ECMAScript style regex.

Although at some point we might want to start expanding our game to include more powerful regex variants (i.e. PCRE). But not yet. There's still more we can do inside the limits imposed by ECMAScript.

@teukon

This comment has been minimized.

Copy link

commented Feb 28, 2014

What is the purpose of the (?! )?

Just to keep the left-part non-empty. I've noticed we often dodge the empty string. These are just suggested domains. If you think that matches is in the domain or that b**n matches begin is not in the domain, you'd need something different.

As before, I'm not intending to resolve ambiguities, but simply appreciate that different people can have different, consistent ideas about the pattern/domain. This is why I was so careful with my own problems, selecting right-side strings to kill off natural alternative patterns (Matryoshka) and to clarify the domain as much as possible (Latin squares). I also prioritised domain simplicity over other factors (in Tic-tac-toe, I opted for the domain of random boards of O, X, and ., rather than the more complex domain of valid game positions). Even after all this I decided it would be best to give domain regexes at the outset and hope that the pattern in each problem is reasonably unambiguous.

I don't think either of these domains would be possible to solve robustly in an ECMAScript style regex.

Nor do I, which is why I say this problem is impossible, along with Balance and "A man, a plan". I think the best one can do is a schema of regexes, based on some simple parameter (where the function taking a value of the parameter and returning a corresponding regex should be as simple as possible).

For "Balance" and "A man, a plan", you've already done this by selecting parameters, respectively nesting depth and string length, and giving an example for each.

This can be done for "Glob" too. The number of asterisks would be my parameter of choice, but I think I'm in the minority here.

Of course, things get really subjective here. Personally, I'd be tempted to flag each of these problems as having "no known robust solution", allowing each to score 0 for the purposes of the robust total. I'd then go on to briefly discuss each problem below. However, I certainly understand you wanting to put seemingly natural bounded-robust solutions in for the sake of completeness.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.