Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Best possible answers collected so far for [Regex golf](http://regex.alf.nu/). === WARNING: SPOILERS ===

See Also:

Normal

Level Score Regex Credit
Warmup 207 foo
Anchors 208 k$
Ranges 202 ^[a-f]*$
Backrefs 201 (...).*\1 gorhill (HN)
Abba 195 ^(?!.*(.)\1)|ef BeniaminK (GH)
A man, a plan 177 ^(.)[^p].*\1$ hyp0 (HN)
Prime 286 ^(?!(..+)\1+$) josephlord (HN)
Four 199 (.)(.\1){3} chrismorgan (HN) / MereInterest (HN)
Order 199 ^.{5}[^e]?$ ekke (HN)
Triples 596 00($|3|6|9|12|15)|4.2|.1.+4|55|.17 alexandrosm (GH)
Glob 397 ai|c$|^p|[bcnrw][bnopr] nwellnhof (HN)
Balance 454 .{37}|^(<(..(?!<.>$))*>)*$ Davidebyzero (GH)
Powers 93 ^(?!(.(..)+)\1*$) plby (GH)
Long count 256 ((.+)0\2+1){8} Davidebyzero (GH)
Alphabetical 317 .r.{32}r|a.{10}te|n.n.. alexandrosm (GH)
Powers 2 88 ^(?!((xxx)+x|xx|)\1*$) muxrwc (GH)
Total 4075
Subtraction 180 ^(.+)(.+) - \1 = \2$ jonathanmorley (GH)
Typist 181 ^[adresbtcfxzgvw]+$ jonathanmorley (GH)

Hard Mode

Level Score Regex Credit
Warmup 207 foo
Anchors 206 ick$ Davidebyzero (GH)
Ranges 202 ^[a-f]*$
Backrefs 201 (...).*\1 gorhill (HN)
Abba 193 ^(?!.*(.)(.)\2\1) chingjun (HN) / josephlord (HN)
A man, a plan 150 ^(.?)(.?)(.?)(.?)(.?)(.?).?\6\5\4\3\2\1$ jonathanmorley (GH)
Prime 284 ^(?!(xx+)\1+$)xx Davidebyzero (GH)
Four 199 (.)(.\1){3} chrismorgan (HN) / MereInterest (HN)
Order 156 ^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*$ Davidebyzero (GH)
Triples 524 (?=((.*?[147]){3})*((.*?[147]|){2}))(?=((.*?[258]){3})*((.*?[258]|){2}))^.*$(\3\7|(?!\3|\7)\4\8|(?!\4|\8)) teukon (GH)
Glob 297 ai|c$|^p|[bcnrw][bnopr] nwellnhof (HN)
Balance 443 ^(<(<(<(<(<(<(<>)*>)*>)*>)*>)*>)*>)*$ gkucmierz (GH)
Powers 93 ^(?!(.(..)+)\1*$) plby (GH)
Long count 239 ^((?=(\S*)0).{4} (?=\2[1]))+1+$ Davidebyzero (GH)
Alphabetical 282 ^(?!.*\b(.*)(e|(n|r|(s|t))).* \1(a|(?!\3)[en]|(?!\4)[rs])) teukon (GH)
Powers 2 -12 ^(?!((xxx)+x|xx|)\1*$) muxrwc (GH)
Total 3664
Subtraction 180 ^(.+)(.+) - \1 = \2$ jonathanmorley (GH)
Typist 180 ^[adresbtcfxzgvwq]+$ jonathanmorley (GH)
@tfausak

This comment has been minimized.

Copy link

commented Dec 20, 2013

  1. Powers (69): ^(..?|(.{4}){1,2}|(.{16}){1,2}|(.{64})+)$
@plby

This comment has been minimized.

Copy link

commented Dec 20, 2013

  1. Powers (93): ^(?!(.(..)+)\1*$)
    Doesn't even "cheat".
@jonathanmorley

This comment has been minimized.

Copy link
Owner Author

commented Dec 20, 2013

Thanks, updated

@grobie

This comment has been minimized.

Copy link

commented Dec 21, 2013

#10 Tripes (586): ^[387][12479]|00($|[369]|1[25])|5[54]|2[437]

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 21, 2013

#10 Triples (587): 00($|[369]|1[25])|5[58]|24|4.2|9..5|878|819

@romanandreev

This comment has been minimized.

Copy link

commented Dec 21, 2013

#12 Balance (288): ^(<(<(<(..)>)>)>)$

It doesn't pass all tests, but score is greater=)

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 22, 2013

10 Triples (588): 00($|[369]|1[25])|5[58]|24|4.2|9..5|^8[17]

I feel triples, being the longest, still has room for improvement.

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 23, 2013

#10 Triples (590): 00($|[369]|1[25])|(^.|9|3)..5|4.2|^[38]1

@rabcyr

This comment has been minimized.

Copy link

commented Dec 23, 2013

aww yeah!
triples (590): 32|.[25][345].|00([369]|$)|01[25]|[07]2$

wait... how did i not see the comment before mine? i swear i refreshed.

@rabcyr

This comment has been minimized.

Copy link

commented Dec 23, 2013

make that 591: 32|.[25][345].|00([369]|1[25]|$)|[07]2$

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 23, 2013

594 for #10: 00([369]|1[25]|$)|.1.+4|3.*7.|4.2|55

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 23, 2013

596 for #10: 00($|3|6|9|12|15)|4.2|.1.+4|55|.17

I had to write code for this one, the previous were by hand and excel. While there's still more space to search, I'm starting to think this is as good as a solution can get. At this point, after the preamble 00($|3|6|9|12|15) we're using 17 characters |4.2|.1.+4|55|.17 to match 13 lines, including the lead(ing) pipe.

Possible room for improvement:

  1. Maybe the preamble can be improved (17 chars for 8 lines)
  2. Maybe there's more regex tricks to add when looking for solutions
  3. My greedy algo is getting trapped in some local maximum
  4. I don't take into consideration cross-optimisations between expressions in the cost function
  5. I only use two numbers to find an ensemble member, maybe with three there's better possibilities?

I'll go try #5 now.

@muxrwc

This comment has been minimized.

Copy link

commented Dec 25, 2013

16: 262 points

^(?!.*(rne|eet |e.r...t|er.{6}r$))(a\S+\s)*(e\S+\s)*(r\S+\s)*([st]\S+(\s|$))*$
@alexandrosm

This comment has been minimized.

Copy link

commented Dec 25, 2013

16: 294
[^et] ren|[er]( \w+)\1|tate r|a t| ae|rt r|e e

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 25, 2013

16: 295
[^et] ren|[er]( \w+)\1|(tat|r). r|a t| ae|e e

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 25, 2013

16: 299
s ren|[er]( \w+)\1|(tat|r). r|a t| ae|e e

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 25, 2013

16: 303
r sn|( t\w+)\1|(tat|r). r|a t| ae|e e

@bbarry

This comment has been minimized.

Copy link

commented Dec 27, 2013

16: 304
( .+[ts]..)\1|(tat|r). r|a t| ae|e e

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 29, 2013

nice one @bbarry. love the technique you used. I'll try and beat it of course, but very nice :)

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 30, 2013

16: 307 -- phew!
( .+[ts]..)\1|(tat|r). r|a t|e .r

@alexandrosm

This comment has been minimized.

Copy link

commented Dec 31, 2013

16: 317
.r.{32}r|a.{10}te|n.n..

Thought I'd give code a try. Nothing too elegant but definitely produced something no human would come up with.

@jonathanmorley

This comment has been minimized.

Copy link
Owner Author

commented Dec 31, 2013

That is a crazy solution, I am impressed. Mind sharing your code? I'm curious how you did it.

@alexandrosm

This comment has been minimized.

Copy link

commented Jan 1, 2014

hey @jonathanmorley , here's my code it's coffeescript. It just iterates through some predefined pattern families to produce subexpressions that match many lines. Then I hand-tune and combine with other expressions. As I said, nothing too impressive, but it's fun to play with. I used a variation of this for #10 as well.

https://gist.github.com/alexandrosm/8204709

@alexandrosm

This comment has been minimized.

Copy link

commented Jan 2, 2014

A solution for 12 that gets 288 points, same as the current one, and is a perfect match at the same time:

^(<(<(<(<(<>)*>|.{9})*>)*>)*>)*$

This one is by hand.

@alexandrosm

This comment has been minimized.

Copy link

commented Jan 5, 2014

289 for 12. Minor-ish tweak on the last one
^(<(<(<(<<?>?>|.{9})*>)*>)*>)*$

@andersk

This comment has been minimized.

Copy link

commented Jan 7, 2014

According to the site’s built-in high scores list, which isn’t published yet, the first discoverers of the best solutions (minus obvious cheaters with impossible scores) were

  1. Plain strings (207) by alok
  2. Anchors (208) by alok
  3. Ranges (202) by alok
  4. Backrefs (201) by alok
  5. Abba (195) by cesium
  6. A man, a plan (177) by Scott
  7. Prime (286) by alok
  8. Four (199) by alok
  9. Order (199) by andersk
  10. Triples (596) by andersk
  11. Glob (403) by andersk
  12. Balance (296) by andersk
  13. Powers (93) by andersk
  14. Long count (256) by timloh
  15. Long count v2 (256) by timloh
  16. Alphabetical (317) by Jon

With the exception of Abba (195) and the last three new levels, these all predate the HN post.

My Order (199) and Triples (596) solutions were different:
^[^o]?.{5}$
[02-5][123][257]|[07][0269]+3?$|55
I’ll leave Glob (403) and Balance (296) as a challenge for now.

@bbarry

This comment has been minimized.

Copy link

commented Jan 7, 2014

I am convinced I can do better with Triples (and glob but I haven't started on that one yet), I have nearly 1 billion regexes that are potential parts of the answer in a database and I am only part way through searching with a program similar to @alexandrosm's using an alphabet that is the power set of [0123456789] and some fancy footwork to avoid duplicates and shorten potential regexes (and a few more generation schemes).

Already it has revealed interesting candidates such as: [03][^1348]..+[23679] and [03].[1258][2578] (it hasn't crossed the [06] first letter yet or [02-5]).

@senegrom

This comment has been minimized.

Copy link

commented Jan 8, 2014

14 and 15 with 254:
((.+)0 \2?1 ){7}

@bbarry

This comment has been minimized.

Copy link

commented Feb 14, 2014

I rewrote my program nearly 4 weeks ago because it was running out of memory and had to deal with server restarts and issues like that so now it is simply counting in a base of around 14k and then translating each number into a regex and is about 1/14 of the way done with the 3 "digit" regexes.


If anyone was wondering, my search (for shortest exact solution on triples) through all alternations of sequences of set items from the set generated by the powerset of [0-9] with the repetition modifiers {a,b} where 0 <= a <= b <= 9 (basically counting through a space containing 14k items) is currently around the sequences *, 7500: [03568]+, 1099: [^059]+ (I say around because it is doing about 200k per second and is operating on 8 sequences at the same time; each thread doing the whole round of 14k before taking the next available one from the queue) which in that case are the 3 item regexes ending in [03568]+[^059]+.

So far the best it has done is 538 - [^07]{4}[47]|[036]{3}$|009|9...$ (I constrained it to search for solutions shorter than 36 characters).

My best that matches for case 5 (0012) and 6 (0015) is 536 - [03-6]{2}[^07][^0146]|[07][^3578]$. These cases are special in that they require a more complex expression than the rest of them (all others can be solved by 2 item sequences where these require 3 items to match). I should be through the 3 item sequences (which I know at least contains a 596 point solution that will cross) in another month or two (based on how long it ran to get to 0,0,1k and a coded theory that as it continues to find better matches it should move through the space faster by being able to discard potential sets earlier). At that point (exhausting the 3 item space) I will be uploading the program for anyone to play with ( ~500 lines C# code+mssql storage, could easily be converted to something else), potentially with the (currently 22k rows) table of best exact matches for subsets of the problem or the (currently 4k rows) best subset-robust rows (the former contains things that are over specified but were best found for that particular subset while the latter contains only rows that could potentially be in a solution). Or I can add the subset of the latter row set that does not contain alternations.

@senegrom

This comment has been minimized.

Copy link

commented Apr 24, 2014

For the new "Power 2"
^(.|...|.{9}|(.{27})+)$ gives 87
^(.|(...)+)$ (non-perfect) gives 88

@BeniaminK

This comment has been minimized.

Copy link

commented Jun 6, 2014

Abba: ^(?!.*(.)\1)|ef gives 195

@muxrwc

This comment has been minimized.

Copy link

commented Sep 18, 2014

Power 2 : 88

^(?!((xxx)+x|xx|)\1*$)
@TedYBear

This comment has been minimized.

Copy link

commented Oct 23, 2014

would be interesting to have the best scores for hard mode too

@mattchainsaw

This comment has been minimized.

Copy link

commented Dec 17, 2014

Balance 336 points
^<.*>$|^$
Matches add but also matches some of the others sides.

@gkucmierz

This comment has been minimized.

Copy link

commented Feb 16, 2015

Is Balance input updated?
^(<(<(<(<(<(<(<>)>)>)>)>)>)>)*$
443 points

@cartmanez

This comment has been minimized.

Copy link

commented Mar 9, 2015

Powers 2(hard mode): ^(?!((xxx)+(x|xx)|xx|)\1*$)
83 points

@hyeonjae

This comment has been minimized.

Copy link

commented Mar 19, 2015

Typist 189 points
^[^h-puy]+$

@altoo

This comment has been minimized.

Copy link

commented Mar 19, 2015

Powers 2(hard mod): ^(?!((xxx)+xx?|xx|)\1*$)
86 points

@hyeonjae

This comment has been minimized.

Copy link

commented Mar 19, 2015

Addition 165 points
^(x_)(x_)...(x_)(x_)...\1\3...\2\4$

@Dinoguy1000

This comment has been minimized.

Copy link

commented Mar 26, 2015

I can't figure out how you're supposed to cancel formatting inline; any pointers?

Glob (336 - hard)

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

Powers 2 (86 - hard)

^(?!((...)+..?|..|)\1*$)

It seems like

^(?!((...)*..?|)\1*$)

should work, but it doesn't match anything and I can't figure out why.

Note: the following are obsoleted by https://gist.github.com/Davidebyzero/9090628, so I won't bother reporting any more solutions, but I'll leave these here anyways since they represent solutions I developed myself or tweaks/optimizations I made to others' solutions.

Subtraction (182 - both)

^(.*)(.*)- \2= \1$

Addition (167 - both)

^(.*)(.+) .(.+)(.*) =\3\1 . \2\4$

or

^(.+)(.*) .(.*)(.+) =\3\1 . \2\4$

or

^(.+)(.*) .(.+)(.*) =\3\1 . \2\4$

or

^(.+)(.*) .(.+)(.+) =\3\1 . \2\4$

Or if you're boring, you can just do this 👅

^(.*)(.*) .(.*)(.*) =\3\1 . \2\4$

Anyway (168 - normal; 68 - hard)

^[aeiouy]?(.[aeiouy])+[^aeiou]?$

This works for normal mode, but fails the extended cases for hard. I feel like I'm missing something obvious here.

Tic-tac-toe (142 - normal; 42 - hard)

(([OX])\2\2|([OX])...\3...\3|([OX])....\4....\4)

This doesn't match "OXX OX. XO.", but that doesn't look like a won/winnable tic-tac-toe game.

Edit: My current totals, after reading through a lot of comments, are: default levels: 4075 (normal), 3801 (hard); bonus levels: 1736 (normal), 1731 (hard). As far as I can tell, these are the best possible scores given currently known regexes.

@madeinqc

This comment has been minimized.

Copy link

commented Apr 22, 2015

Abba's max is 196:
^(?!(.)+\1)|ef

@zogwarg

This comment has been minimized.

Copy link

commented Jun 24, 2015

Anyway (191 - HARD) based on @Dinoguy1000:
^[aeiouy]?([^aeiou][aeiouy])*[^aeiou]?$

@micheljung

This comment has been minimized.

Copy link

commented Jul 18, 2015

Typist in normal (185): ^[a-grstvwxz]+$

@ngc696

This comment has been minimized.

Copy link

commented Nov 30, 2015

Powers 2 (87 - hard):
^((?=(x_)\2\2$)\2\2)_x$

@zeshanlb

This comment has been minimized.

Copy link

commented Jan 8, 2016

Tic-tac-toe (N:153) : XXX|OOO|X...X...X|O...O...O|X..X..X|X....X....X
Tic-tac-toe (H:133) : XXX|OOO|X...X...X|O...O...O|X..X..X|O..O..O|X....X....X|O....O....O

@frankbryce

This comment has been minimized.

Copy link

commented Feb 11, 2016

Based on @zeshanlb's last answer
Tic-tac-toe (N:156) : XXX|OOO|([OX])...\1...\1|X..X..X|X....X....X
Tic-tac-toe (H:142) : XXX|OOO|([XO])...\1...\1|X..X..X|O..O..O|([XO])(....\2){2}

@thebigbadbobby

This comment has been minimized.

Copy link

commented Mar 2, 2016

Powers 2 (86) ^(?!((xxx)+xx?|xx)\1*$). Hard mode.

@CatsAreFluffy

This comment has been minimized.

Copy link

commented Mar 20, 2016

Correct Powers 2: ^(?!(|xx|xx?(xxx)+)\1*$) 86
Tic-tac-toe: ([OX])\1\1|([OX])..\2..\2|([OX])...\3...\3|([OX])....\4....\4 139 Hard mode
Addition: ^(.*)(.*).(.*)(.*) .\3\2. \1\4$ Both 169

@JacobMathBoy

This comment has been minimized.

Copy link

commented Mar 30, 2016

Excuse me, but whoever got 180 points on Typist, can't I just use a few ranges to improve that? ^[a-gq-tvwxz]+$
(sings while looking at keyboard) A, B, C, D, E, F, G. H, I, J, K, LMNOP. Q, R, S. T, U, V. W, X, Y, Z.
Sorry. I just had to tell you that you could get five more points. 😄 👍

EDIT: You had 180, not 181. Sorry.

@The-Snide-Sniper

This comment has been minimized.

Copy link

commented May 8, 2016

Glob - Hard (341): ^(.*)(?=.*( .* \1))(\2|\*(.*)(\2.+\4|\*(.*)(\2.+\4.+\6|\*(.*)\2.+\4.+\6.+\8)))$
Long Count - Hard (245): ^((\d*)01* (?=\2(1)))*1*$
Powers 2 - Hard (76): x{16385}|^(?!(xx(xx)?(xxx)*)\1*$)x
Subtraction - Normal, Subtraction - Hard (182): ^(.+)(.+)- \2= \1
Typist - Normal, Typist - Hard (189): ^[^h-puy]*$

@micsthepick

This comment has been minimized.

Copy link

commented Jun 7, 2016

No-one thought of these yet?
Tic-tac-toe: (Hard or robust) (168) (X|O)(\1|..(\1|.\1.|..\1..)..)\1
Powers 2: (Hard/robust) (89) ^((x+)\2(?=\2$)|x$)+$

@teukon

This comment has been minimized.

Copy link

commented Sep 9, 2016

Addition (robust) (177): ^(.*)(.*)(.*) = \3\2\1$ (credit to Davidebyzero)
Tic-tac-toe (robust) (169): (\w)(\1|..(\1|.\1.|..\1..)..)\1 (nice work micsthepick!)

Each of the bonus problems can be done with fewer than 40 characters. Most can be done using no more than 30 characters.

@eromoe

This comment has been minimized.

Copy link

commented Apr 19, 2017

Any idea about this https://alf.nu/RegexGolf#accesstoken=Da3Q/rKFFqZwSic2o5Rt ?

It never ends – $ not allowed

Match all of these…
✔fu
✔tofu
✔snafu
and none of these…
✕futz
✕fusillade
✕functional
✕discombobulated

@altair21

This comment has been minimized.

Copy link

commented Apr 20, 2017

For It never ends - $ not allowed:
u\b

@thamizh85

This comment has been minimized.

Copy link

commented May 19, 2017

A man, a plan: ^(.)(.).*\2\1$

@depperm

This comment has been minimized.

Copy link

commented Jul 27, 2017

Abba: ^(?!(.)+\1)|.u

@Davidebyzero

This comment has been minimized.

Copy link

commented Dec 13, 2018

I've updated Best known Regex Golf solutions. The current Classic level set is fully covered. It's now in table format, including full credits and date-time stamps, a history of gradual improvements for most of the levels, and some extra bonus information.

I have intentionally not updated the Teukon level set solutions compilation, nor posted one for Holiday, as with the release of functioning high score lists in the newly brought back Regex Golf site, to do so would further taint the high scores with people who simply Google it and copy the solutions. This is not an ideal situation by any means, as I'd really like for everyone to be able to benefit from this knowledge if they so desire, but given the way the on-site high score lists currently function, I see no alternative. Having date-time stamps in the on-site high score lists would be a good start towards fixing this problem.

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.