Taciturn

All entries (archive)

Thu 6 Mar 2008

David and I were discussing regexes and he wondered if it was possible to write two regexes so that each one matches the other but not itself. In programmer- and shell-readable terms, given the variables a and b: echo "$a"|(! egrep "$a") && echo "$b"|(! egrep "$b") && echo "$a" |egrep "$b" && echo "$b"|egrep "$a" && echo yeah (Thanks D.). If it says "yeah", you win.

To give it a bit more of a concrete scope, I decided that it should use extended regexes, because they have a good balance of power, usefulness, and sanity. Secondly, to avoid the easy solution of ^a and a$, both regexes must be anchored at both beginning and end.

To give readers a chance to solve this themselves, I'll disguise the spoilers below in white-on-white text. Highlight the text to read it.

The key is to use inverse classes. As a result I came up with ^[^\\]+$ and ^[^[:alpha:]]+$.

I then posed the question to #humbug, Clinton Roy got a solution pretty quickly: ^[^a]*$ and ^[^b]*$.

Doing the same when anchors are prohibited seems to be more difficult, although I haven't thought about it long enough to be satisfied that it's impossible.

By the way, setting GREP_OPTIONS='--color=auto' and optionally also --exclude-dir=.svn is totally awesome.

Comments

There are no comments on this entry.

Comments are disabled on this post.

Also available in RSS.