Regex Golf

http://regex.alf.nu/

by subbz • 13 years ago

285 153 13 years ago

regex.alf.nu

Trufa• 13 years ago

I like the concept but the word choice doesn't seem too "regular", it is more about catching all the particulars rather than finding a pattern as far as I can tell.

ZirconCode2• 13 years ago

There are good patterns, the first regex for me was /foo/, the second /ick$/, for example. They're there.

davidbrent• 13 years ago

I have the most trouble with regex, and something about seeing my matches as I type made this incredibly useful for me!

tokenizerrr• 13 years ago

http://regexpal.com/ or for a paid desktop program http://www.regexbuddy.com/, which is most excellent

rschmitty2• 13 years ago

Regexbuddy is great. Well worth the coin I paid way back when

Inversechi• 13 years ago

The best online tool I've seen is http://www.debuggex.com/

mcescalante• 13 years ago

I've used the previously mentioned regexpal quite often. http://www.rubular.com is another one for Ruby only.

Spittie• 13 years ago

I'll add http://www.regexper.com/ to the various sites everyone posted, I find that this one output the nicer graph.

ToastyMallows• 13 years ago

While people are recommending online regex tools.. http://regex101.com/

lsv1• 13 years ago

Fun learning tool for regex.

chrismorgan2• 13 years ago

Practise, maybe. Learning, probably not so much. Certainly fun, though, if you can cope with them!

zedadex2• 13 years ago

Learning, kinda. I've often been motivated to learn something after being given a problem that can only be solved (or be solved much more easily) using it. Every other Excel trick I know is a result of that.

daGrevis• 13 years ago

I like the idea, but words there seems to be pretty random. I can't figure out the pattern, not even talking about writing regex... :(

maxerickson4• 13 years ago

I got a 3 character pattern for the first puzzle and a 4 character pattern for the second puzzle (and reading a comment here I see there is a 2 char pattern for the second puzzle).

Only used 1 special char between them (anchoring something). So the first two sets have repeated 3 character sequences, and in one of them they follow an additional pattern.

For the third sequence, 8 character solution, lots of specials.

rplnt4• 13 years ago

Read a) name of the puzzle b) the little help below the score. It gives out the pattern you should (not) look for.

edit: Not in Glob. What is Glob about?

schoen• 13 years ago

It's about implementing * as a wildcard character:

https://en.wikipedia.org/wiki/Globbing

I haven't figured out how to solve this with the parts of ERE and PCRE that I know. (I definitely don't know the entirety of PCRE.)

It's straightforward for me to write a substitution using regular expressions to create a pattern-matcher for a given glob (just anchor the ends and replace literal ? with . and literal * with .*) but here we have to do it inside a single regular expression.

I don't think there's a BRE solution if the number of stars is unbounded because I don't think this is a regular language.

bencoder• 13 years ago

what's the pattern on "Abba"? I thought it was just to exclude doubled letters but I have doubles on two words on the left hand side as well (noisefully and effusive, in case the word lists are the same)

shdon• 13 years ago

Excluding doubled consonants that have the same vowel on both sides of the pair:

  ^((?!([aeiou])([^aeiou])\3\2).)*$

The following also works for the testcases and is shorter:

  ^((?!(.)(.)\3\2).)*$

surreal3• 13 years ago

Can get 2 more points with:

  ef|^((?!(.)\2).)*$

But I reckon yours wins for having a pair of breasts in the middle

moron4hire5• 13 years ago

well, if you are strictly interested in matching with the fewest characters, regardless of the apparent pattern:

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

danielweber6• 13 years ago

Your anchors at the end make it match nothing.

abus3• 13 years ago

5. Abba (^unv|.u|z|ph|mi|st|vi|tan)

haha

chaz• 13 years ago

Shouldn't the objective be to get the lowest score if it's called "golf?"

danceonfire2• 13 years ago

The goal in code golf is lower character count, not lower score - which is also the case here.

talmand2• 13 years ago

Therefore, the score it provides should be a running tally of how many characters you've used to make it match the scoring system of golf; which is the lowest number of strokes wins.

The scoring system for this is incremental which is the opposite of golf.

A proper scoring system with this would provide a character limit (par) for each section and the goal would be to write a shorter regex formula to complete the task. Final score would be how many characters under or over the total character limits (course par) you scored.

Seems this is more like Regex Darts or something like that.

But it's fun nonetheless.

dfritsch• 13 years ago

The golf part is that you can only get the most points by writing the shortest regex possible. However, I think the game avoids just giving a score based on the number of characters. To do that, you would be required to match all on the left and none on the right (the equivalent of actually getting the golf ball in the hole). This game lets you pick up your ball whenever you want and scores you based on distance to the hole. For the golfers, think of it more like a closest-to-the-hole competition than the more common stroke play.

ZirconCode2• 13 years ago

For "6. A man, a plan", I thought it was impossible to match palindromes with regex, am I wrong?

quarterto• 13 years ago

It gives you hints below the score, for 6 it's:

  You're allowed to cheat a little, since this one is technically impossible.

No idea how you cheat...

EDIT, SPOILERS: I get 170 with ^(.?)(.)(.).?\3\2\1$

mryingster• 13 years ago

176 with ^(.)(.).*\2\1$

Yen• 13 years ago

You're pretty much correct. True regular expressions don't have the expressive power to decide whether arbitrary-length strings are or aren't palindromes.

That said, 'regular expressions', as used in most programming languages, have extensions that extend the expressive power. One such extension is the matched group & backreference, used in other commentor's answers.

From a theoretic stance, these aren't really 'regular expressions', but that's what we call them in practice.

joelanman2• 13 years ago

am I being a bit slow? Why doesn't [^g-z] work on 'ranges'?

martinml• 13 years ago

Because for example "beam" matches [^g-z]. That is, it has a letter somewhere that is not between g and z (namely e and a). I came up with ^[a-f]+$ but I'm guessing it could be shorter :)

Edit: ah, every word in left column has 4 a-f letters. So [a-f]{4} is a shorter match.

joelanman2• 13 years ago

ah you're right :) I was being slow, what I thought I wrote was 'words consisting only of letters that arent g-z'

bluedino2• 13 years ago

Another dumb question - why does 'beam' not match [bdf][ae] ?

maxerickson4• 13 years ago

It's complaining because it does match.

tareqak• 13 years ago

I got Four for 196 with

    (.).*\1.\1.*\1

and Order for 156 with

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

chrismorgan2• 13 years ago

Four: 199

    (.)(.\1){3}

Order: 168

    ^a*b*c*d*e*f*g*h*i*l*m*n*o*p*r*s*t*w*y*z*$

(You just didn't remove unused letters.)

spystath• 13 years ago

Or just (.).\1.\1.\1 for Four (198)

MereInterest• 13 years ago

So long as we are going down this route, you can shave off another character with (.)(.\1){3} (199).

maxerickson4• 13 years ago

Can chop out one check to save a character:

(.)...\1.\1

gorhill• 13 years ago

Order for 198:

   ^[^o].....?$

Probably not what was wanted, but it works (or maybe it was to trick people onto a false path)

XaspR8d2• 13 years ago

Makes my similarly off-track score of 184 seem foolish:

  ^[a-g][^airn]|[fs].*y$|ot$

yogo• 13 years ago

Nice, I earned 197 with: ^[a-m].{1,5}$

I must say Regex golf is a lot of fun.

ekke3• 13 years ago

Nice, turn it around for 199:

  ^.{5}[^e]?$

zedadex2• 13 years ago

This right here is why test cases are always blackboxed...

raverbashing2• 13 years ago

or ^[^o].{1,5}$

198 points

ryanthejuggler2• 13 years ago

Order for 170.

  ^([ab][c-gio][^d]|c[ehlo]|d|f[il]|gh|mo)

Not as clever as you guys though!

acln• 13 years ago

Balance (194)

  ^<.*>$|^<<.*>>$|^<<<.*>>>$

nadinengland• 13 years ago

Balance (286)

  ^(<(<(<(<(<(<<>>)*>)*>)*>)*>)*>)*$

If we had named captures:

  ^(((?<P><)|(?<-P>>))*(?(P)(?!)))$

harpastum• 13 years ago

Balance (212)

[<>]{28}

chingjun4• 13 years ago

Order for 195

    ^[a-g]*[^a-g]*$

burke• 13 years ago

Order for 196:

    ^[a-i]*[l-z]*$

The_Double• 13 years ago

Does anybody know how to do math with regex? (triples)

And conditionals don't seem to work?

danielweber6• 13 years ago

My guess is that 147 must appear the same number of times as 258, but I'm not sure if that's even expressible in regexp.

recursive• 13 years ago

No. 111 is a multiple of 3.

johnlbevan23• 13 years ago

Sadly that wouldn't work for: 140091876 147 = 4 times 258 = 1 time

johnlbevan23• 13 years ago

Refined: [0369] can appear any number of times [147] and [258] must appear an equal number of times, or for any remaining: [147] must appear a multiple of 3 times [258] must appear a multiple of 3 times

dudus• 13 years ago

From: http://quaxio.com/triple/

    ^([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])*$

moron4hire5• 13 years ago

569pts: ([^31]0|31|[017]2|[03]03|[^1]4|(900|01|7)5|6|[48]7|[57]8|09)$

raverbashing2• 13 years ago

The idea is as thus:

Remember division rules? If the sum of digits is divisible by 3, then the number is divisible by 3

So, if you have 0, 3, 6, 9, it's as you can remove them, the value won't change

Remaining are the 2, 3, etc digit numbers divisible by 3

tcfunk• 13 years ago

I got 187 with this

  [369](?![7238])|(?:0)12

It's sloppy and certainly not correct, but a decent score.

galen_tyrol3• 13 years ago

^[01349][064] works for 197

easy_rider• 13 years ago

(.+|)foo(.+|)

Lol so awesome this. I oblige. Much love!

ryanthejuggler2• 13 years ago

Powers:

    ^((((((((((x)\10?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$

I feel like there's gotta be a sneakier way of doing this.

rplnt4• 13 years ago

Mine is a bit shorter, though a bit more "meh" as well.

    ^x{32}$|^(x{2}){1,8}$|^(x{64})+$|^x$

danielweber6• 13 years ago

I was working on this pattern:

^(x{1,2}){1,2}$

But it wedged my browser as I started adding more terms. :/

delluminatus• 13 years ago

58 points:

    ^x$|^(x+)\1$

XaspR8d2• 13 years ago

Completely not sneaky at all, but does reasonably well at 71 points:

  ^(x|xx|xxxx|x{8}|x{16}|x{32}|(x{64})+)$

cleaver• 13 years ago

I did similarly, but managed to squeeze out a few more points:

^(((((((((xx?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$

(60 points)

willchang• 13 years ago

A non-cheating solution, 79 points.

  ^((xx?|xxxx)(\2{7})?)(\1{63})?$

Pxtl• 13 years ago

I hit enter and nothing happens.

danielweber6• 13 years ago

Use the yellow box, not the name box that gets your focus when you land on the page.

This confused me for a few minutes.

hadem• 13 years ago

Reminds me of Vim Golf.

http://vimgolf.com/

danielweber6• 13 years ago

Many times I would match the exact opposite opposite of what I wanted. Is there a general rule for inverting regexps? ^ and ?! don't seem general purpose.

josephlord6• 13 years ago

You need to pin the match to the start and end of the string with ^ and $ respectively otherwise the negation just matches an empty string or other irrelevant string.

danielweber6• 13 years ago

Just to follow my thought pattern.

I start with

(.)(.)\2\1

Now to invert I change it to

(?!(.)(.)\3\2)

As you say, the negation matches an empty string. So I put on anchors:

^(?!(.)(.)\3\2)$

But now it matches nothing. I'm not even sure what that regexp says. The entire string is a negation? Would anything match that regexp?

I see elsewhere on this page that the answer involves putting in an extra dummy character, putting that new negation-and-dummy-character in parens, and then requiring that, between the anchors, there be 0-or-more of negation-and-dummy-character.

^((?!(.)(.)\3\2).)∗$

Two questions:

1. Why are my backrefs still \3 and \2? I added another pair of parens. (I thought ?! might not count, but it counted in my second example above.

2. Why does abba no longer match? It has no matches to the negation-and-dummy character construct, which ∗ should match, right?

NB: I used ∗ as my asterisk to avoid bb-code.

criswell2• 13 years ago

Yeah, I couldn't figure out how to invert the abba one (.)(.)\2\1 without help.

josephlord6• 13 years ago

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

Why does that work on primes? I got it by mistake when fiddling with the parenthesis locations but I was expecting to have to deal with xx separately.

surreal3• 13 years ago

Nice find. It works because it rejects "2 or more x's" repeated "2 or more times". So xx doesn't get rejected, but any multiple of that (xxxx, xxxxxx, ...) will be. The same way xxx doesn't get rejected, but any multiple of that (xxxxxx, xxxxxxxxx, ...) will be.

You've solved it using the actual definition of prime numbers, no trickery needed. Well played.

FYI, you don't need brackets around the \1, so can score 286.

josephlord6• 13 years ago

Thanks, I was going for the definition of primes but was just going a bit loopy about the negation. I didn't want to trim surplus characters until I understood it but yes I can see those brackets are unnecessary.

Aissen• 13 years ago

More interesting than the definition of primes, it's almost the definition of multiplication that is embedded in this regex. We have two numbers(of occurrences) being multiplied:

- the first one is represented by the group (..+) it represents the number of occurrences n between 2 and +∞

- the second one is represented by (\1)+. We will repeat the first number m times, between 1 and +∞ times.

So the result of the multiplication is n*(m+1), which cannot be a prime. We just have to take the opposite with negative lookahead. It's very beautiful indeed.

See http://regex101.com/r/qN2fQ8 or http://www.regexper.com/#^%28%3F!%28..%2B%29\1%2B%24%29 to follow the above explanations.

mistermcgruff• 13 years ago

This is amazing.

jhight2• 13 years ago

Spoiler alert (201 points): f[ao][no]

jhight2• 13 years ago

Oh, there's more than one step, I see.

elwell2• 13 years ago

You can just write: foo

onaclov2000• 13 years ago

Glob: 277, it didn't match all and not match the others, but it's reasonably high. ^([bcdlmpwr]|\*[efptv])

moron4hire5• 13 years ago

378:

  ^(\*(er|[fiptv])|b|c(?!a)|do|le|mi|p|re|w)

chingjun4• 13 years ago

379:

  ^\*(er|[fiptv])|^([blpw]|c[hor]|do|re|mi)

and it has "do re mi" in it!

hadrel• 13 years ago

Glob (333) without cheating (replace ⁕s with asterisks, they get turned into italics):

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

Edit: ((.(?!\1))+|\1) is used to conditionally match .+ iff a * has been found. .(?!\1) Matches any character if it is followed by \1. When * has been found then it matches no character, when * is not found it matches every character.

Edit 2: Formatting to avoid the *s becoming italics :/

josephlord6• 13 years ago

  le[^*]|co|ito|dr|^p|su|gi|nr|hw|fa|[eo]b|ide

Glob 376 although it isn't pretty and better may be possible.

Indent two spaces with a blank line above to avoid code mangling.

falsedan• 13 years ago

Glob 380

  ^([wlpb]|c[hor]|do|re|mi|\*[pifvt]|\*er)

GregP91• 13 years ago

en(?!c)|rr|il|eat|^(do|p|b|c(?!a))

Glob 386 although not the cutest way to do it.

jpsim• 13 years ago

Gist with my answers: https://gist.github.com/jpsim/8057500

If you look at the revisions, you'll see my 1st iteration was mostly identifying patterns, then with more and more cheating (and looking at this thread) to squeeze every point possible.

chingjun4• 13 years ago

  5.  193  ^(?!.*(.)(.)\2\1)
  11. 379  ^\*(er|[fiptv])|^([blpw]|c[hor]|do|mi|re)

galen_tyrol3• 13 years ago

https://gist.github.com/jonathanmorley/8058871

3121 points

johnlbevan23• 13 years ago

Ternstroemiaceae contains four es; anyone else hit that issue / know what that's not in the valid results for Four? I'm guessing there's a pun in there that I didn't get :/

elwell2• 13 years ago

I figured out Ranges!

  abac|accede|adead|babe|bead|bebed|bedad|bedded|bedead|bedeaf|caba|caffa|dace|dade|daff|dead|deed|deface|faded|faff|feed

Edit: /s

abus3• 13 years ago

Prime:

    ^x{2,3}$|^x{5}$|^x{7}$|^x{11}$|^x{13}$|^x{17}$|^x{19}$|^x{23}$|^x{29}$|^x{31}$|x{33}

jonahx• 13 years ago

josephlord's solution is much nicer:

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

criswell2• 13 years ago

[a-f]{4,} works as well... but I do like your solution!

danielsamuels• 13 years ago

[a-f]{4} is shorter.

dsschnau• 13 years ago

Me and a coworker totaled 3079 points. Anyone beat it?

ekke3• 13 years ago

Got hooked and to 3202, but ca 10-20 more points could be gained according to answers here and there: https://gist.github.com/jonathanmorley/8058871

Kudos to the author of the game, good job.

PS. http://regexcrossword.com/

endophage• 13 years ago

Seems very very very broken. The regex "[a]" apparently matches "crenel"

pomfpomfpomf3• 13 years ago

It doesn't. The green ✔ indicates that you've completed the task successfully — that is, your regex does not match "crenel".

shawabawa3• 13 years ago

It's a bit confusing. Ticks on the left means it did match, ticks on the right means it didn't

scott_karana2• 13 years ago

For Abba...

Why doesn't (.)(.)\2[^\1] work?

I thought backreferences matched the captured literal, so negating it would match? But this looks the same as (.)(.)\2\1...

annasaru• 13 years ago

(.)(.)\2\1 ?

goldenkey2• 13 years ago

You cannot negate a capture, only a character literal. A capture might only be a character but it is NOT a literal,

scott_karana2• 13 years ago

Gotcha. That makes perfect sense. Thank you! :)

xarien• 13 years ago

Why is Kesha an optimal answer? (#2 k$) ;)

amix• 13 years ago

JavaScript solver: https://gist.github.com/amix/8063003 ;-)

hyp02• 13 years ago

challenge: use machine learning to find the best solutions.

They might improve on those intended by exploiting accidental regularity in the corpus - though charmingly, the golf-cost of regex length helps combat this overfitting. They might also find genuinely cleverer solutions.

cpeterso• 13 years ago

What purpose do the "plain strings" serve?

ColinDabritz• 13 years ago

Hrm, on number 8 "Four" using:

    (.)(.*\1){3,}

I got all but the "do not match" for "Ternstroemiaceae"

The challenge appeared to be to match words with four instances of the same letter. "Ternstroemiaceae" contains four 'e's, and thus should be in the "match" column, instead of the "don't match" column, no? Did I miss something?

denkfaul• 13 years ago

Look closer, there's something different about the matches and this word.

sbirch• 13 years ago

An interesting bit on the computational complexity of solving this problem (with a slightly different scoring function):

http://cstheory.stackexchange.com/questions/1854/is-finding-...

sriharis• 13 years ago

^ answers all questions.

ddebernardy• 13 years ago

Doesn't seem to do anything on an iPad...

JadeNB• 13 years ago

What are the rules? That is, are these Perl regexes, POSIX regexes, …? (Come to that, what is this site? Going up one level to alf.nu gives me a lot of suggestions for what I can do by modifying the address, but no clue of who's doing it on my behalf.)

Regex Golf

Related Stories