Regex Golf Answers (http://regex.alf.nu/) HN: https://news.ycombinator.com/item?id=6941231

answers.md

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

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

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

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.

Damn it!

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.

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}$.

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 ^<.*>$.

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!

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.

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

Nice. Making progress bbarry.

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

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

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

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

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

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

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

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)

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

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

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

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

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.

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

561 on Triples... might need optimized/refined

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

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

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

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

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

It never ends: u\b

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.

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?