Skip to content

Instantly share code, notes, and snippets.

@jpsim
Last active August 25, 2024 04:30
Show Gist options
  • Save jpsim/8057500 to your computer and use it in GitHub Desktop.
Save jpsim/8057500 to your computer and use it in GitHub Desktop.
  1. Plain Strings (207): foo
  2. Anchors (208): k$
  3. Ranges (202): ^[a-f]*$
  4. Backrefs (201): (...).*\1
  5. Abba (169): ^(.(?!(ll|ss|mm|rr|tt|ff|cc|bb)))*$|^n|ef
  6. A man, a plan (177): ^(.)[^p].*\1$
  7. Prime (286): ^(?!(..+)\1+$)
  8. Four (199): (.)(.\1){3}
  9. Order (198): ^[^o].....?$
  10. Triples (507): (^39|^44)|(^([0369]|([147][0369]*[258])|(([258]|[147][0369]*[147])([0369]*|[258][0369]*[147])([147]|[258][0369]*[258])))*$)
  11. Glob (364): ^((\*(er|f|i|p|t|v))|(b|c(h|o|r)|do|l|mi|p(a|r|u)|re|w))
  12. Balance (286): ^(<(<(<(<(<(<<>>)*>)*>)*>)*>)*>)*$
  13. Powers (56): ^((((((((((x)\10?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$

Total Score: 3060

@Davidebyzero
Copy link

Oh, right. Silly, silly me. You confused me for a second though — I didn't realize at first that you meant ^1110 1111$.

@teukon
Copy link

teukon commented Feb 26, 2014

Don't worry about it. Can you find a counter-example for my 235-point regex?

@Davidebyzero
Copy link

I'm pretty sure your Long Count (235) ^((?=(\S*)0).{4} (?=\2[1])){15}\2.$ is robust.

My regex still beats yours, though. I present to you, Very Long Count: ^(?=0+ )((?=(\S*)01* \2()10*\b)\S{30} )+1+$

^((?=(\S*)0).{30} (?=\2[1])){1073741823}\2.$ would be yours.

@teukon
Copy link

teukon commented Feb 26, 2014

Damn it!

@Davidebyzero
Copy link

I think nobody has been keeping an up-to-date list of the best solutions so far, so:
Best known Regex Golf solutions

Please let me know if I got anything wrong.

@Davidebyzero
Copy link

In all the excitement to get a robust Long Count v2, I think we've lost track of making a robust Long Count.

I would say the domain of Long Count is ^([01]{4}([1 ](?=.)|$)){16}$. Would you agree?
All we actually see is ^[01]{4} ([01]{4}[1 ]([01]{4} ){2}){3}[01]{4}[1 ]([01]{4}( (?=.)|$)){5}$, but it's a limited sample. Arguably the domain could be ^([01]{4}([01 ](?=.)|$)){16}$.

@Davidebyzero
Copy link

I've beaten the published exact-match Balance record:

Balance (292): ^$|.{37}|^<(.(?!><*.>$).)*>$

This also exposes another bug in Opera's ECMAScript engine. Under Opera, only ^$|.{37}|^<(.(?!><*.>$).)*?>$ works, and ^<(?:..)*>$ is equivalent to ^<.*>$.

@teukon
Copy link

teukon commented Feb 27, 2014

Arguably the domain could be ^([01]{4}([01 ](?=.)|$)){16}$.

Ha, I just asserted the possibility of this on your solutions gist. Unfortunately, I'm not much interested in Long Count anymore so I'll leave you to work on this one alone.

Balance (292): ^$|.{37}|^<(.(?!><*.>$).)*>$

Nice work!

@bbarry
Copy link

bbarry commented Mar 4, 2014

tweaking 2 of my top 100 candidates has generated these 596 and 595 point solutions for triples:

00(3|6|9|15|$)|.1.+4|.17|[04].2|55
[07][0269]+3?$|0.2|1.4|3.*7.|58|015

Going off on a tangent and having my machine crash this past week has gotten me off to exhausting an additional 1/14th of my intended search space, but I have increased the speed it traverses it to approximately 1/56ths a day... (as opposed to 1/98ths) or perhaps more (the crash happened sometime during the weekend after I finished the latest improvements when the IT staff decided to update my machine; I am not sure exactly how much faster it is, only that it is somewhere between 1.25x and 3.5x; will know more tomorrow). My database of best matches found so far for any subset is currently at 147,949 solutions after pruning.

@Davidebyzero
Copy link

tweaking 2 of my top 100 candidates has generated these 596 and 595 point solutions for triples:

00(3|6|9|15|$)|.1.+4|.17|[04].2|55
[07][0269]+3?$|0.2|1.4|3.*7.|58|015

Nice work. Makes it look hopeful that you might beat 596.

Here it is compared with the similar published 596 point solution:

00($|3|6|9|15)|[04].2|.1.+4|.17|55
00($|3|6|9|12|15)|4.2|.1.+4|.17|55

And here is your 595 compared with the other published 596:

[07][0269]+3?$|[02-5][123][257]|55
[07][0269]+3?$|0.2|1.4|3.*7.|58|015

@teukon
Copy link

teukon commented Mar 4, 2014

Nice. Making progress bbarry.

I hope this computer search does yield a saving in the end. It certainly seems possible.

@Davidebyzero
Copy link

Balance (454): .{37}|^(<(..(?!<.>$))*>)*$

Edit: Used to score 294, now 454 with new scoring

@hkdobrev
Copy link

hkdobrev commented May 7, 2014

Order (198): ^[^o].{1,5}$

Same points, but a better using shorter negating syntax and numbers instead of multiple dots.

@hkdobrev
Copy link

hkdobrev commented May 7, 2014

Triples (543): ^(0+[0369]|0{7}1[25]|06.*|1.*[60]|3[1269].*[478]|32.*|4[04].*|7[14].*|8[17].*|9[05].*)$

@hkdobrev
Copy link

hkdobrev commented May 7, 2014

Triples (574): ^(.*[07](6|1[25]|[056][^58])|([349][^378]|[78][147]).*)$

@71104
Copy link

71104 commented Jun 15, 2014

Triples (523): ^([0369]|[258][0369]*[147]|([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([147][0369]*[147]|[258]))*$

(I designed a DFA and converted it using Kleene's algorithm, it's the most correct way to do it although not the one that scores the most)

@ranneyd
Copy link

ranneyd commented Jul 3, 2014

Balance (444): ^(<(<(<(<(<(<(<>)>)>)>)>)>)>)$

@71104
Copy link

71104 commented Jul 11, 2014

Balance (446): ^(<(<(<(<(<(<.*>)*>)*>)*>)*>)*>)*$

@wapiflapi
Copy link

Balance (447): ^(<(<(<(<(<(...)*>)*>)*>)*>)*>)*$

@aeieli
Copy link

aeieli commented Jan 29, 2015

Powers 2(82): ^(x{81})+$|^x$|^(x{3}){1,9}$

@welwood08
Copy link

Powers 2: ^(.|(...)+)$ (88)

Matches 1 test that it shouldn't, but still the most points I could get within reasonable time. Several ways to get 86pts otherwise.

@wsergent
Copy link

Long Count = 256 points: ((.+)0\2+1){8}

@nicklister
Copy link

561 on Triples... might need optimized/refined

[0562][04]$|[30]03$|0[4629]$|12$|015$|[48]7$|9005$|7[6825]$|31$|58$

@mlindheimmarx
Copy link

glob-- ^(*(er|f|i|p|t|v)|b|c(?!a)|d(?!i)|l|mi|p|re|w)

@Allypost
Copy link

Allypost commented Jun 6, 2016

Triples (589): 003|009|0.2|015|00$|06|1.4|4.2|55|.17|819

@ShaunDonle
Copy link

Power 2: ^(?!xx$|(x(xxx)+)\1*$)

@leiserfg
Copy link

Power 2:^(?!((xxx)+x|xx)\1*$)

@vinodselvin
Copy link

It never ends: u\b

@Davidebyzero
Copy link

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.

@moon-home
Copy link

Abba (193): ^(?!.*(.)(.)\2\1)

Hi @jonathanmorley, can you enlighten me why (?!(.)(.)\2\1) matches abba? isn't it matching any string that does not have a 4 characters palindrome?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment