RegEx brain teaser
 

I'm trying to improve my ability to code Regular Expressions. Therefore solutions using awk, perl, ruby, etc. are not relevant.

The InFile is a list of English words, one per line. For testing, we may use this InFile ...
Problem statement: find those words which fit these criteria.

1) The word is six characters long.
2) The letter in position 2 is different from that in position 1.
3) The letter in position 3 is different from those in positions 1 and 2.
4) The letter in position 4 is the same as that in position 1.
5) The letter in position 5 is different from those in positions 1-4.
6) The letter in position 6 is the same as that in position 2.

This sed ...
... produced this OutFile ...
These words satisfy conditions 1,4, and 6. That is to say, all the affirmative criteria are satisfied. None of the negative criteria are satisfied. The correct OutFile would be ...
A second attempt was ...
... but that produced the same OutFile.

Are backreferences not recognized within character classes?

Is there a RegEx to make this word selection with a single sed or grep?

Daniel B. Martin

No. Character classes can only match a single character, whereas a backreference can match anything (that a regex can match).

Certainly not a single grep*. I expect it could be done with a single sed, since sed is a Turing complete language. It would be fairly unreadable, as most sed programs that use branching/looping are.

* Except that, technically, you could use a single regex just by exhaustively listing all the possibilities.

Please feel free to rip the following to shreds. It attempts to take a purely grep approach and goes on the assumption that the only way to implement NOT a AND NOT b in grep is to pipe an inverted grep through another one.

Using a d command for the negative matches, and multiple regex on separate lines, headed with a #rule comment,
and I am done within a few minutes.
Okay, one quick optimization for #5 is possible

You're using resources like these to test your regex, right?

https://regex101.com/
http://regexr.com/

Nice! That's not as bad as I expected. You could make rule#3 a bit more compact too:
Also, with GNU sed you can drop a few backslashes.

Or, applying the same idea as for #5

I believe the very short answer to the initial question is, no there is no single regular expression using especially sed's limited engine to get the answers you want.
This then points to the fact that once again you are trying to use the wrong tool for the job at hand. Essentially if you are making choices of a boolean nature then you will need more than a single pass,
hence all the tools you have tried to omit were created

yes, these are actually "too much" for a single regexp. You ought to implement these requirements separately (probably in groups)

On the other hand there is some fun doing with sed things usually done with other tools. For instance arithmetic operations, at least on integers, or a file format converter, like convtags of which I am guilty. :D

I think it can be done with one PRE (perl regular expression).

Thanks to all who contributed to this thread -- code, comments, and constructive criticisms.

This was a learning exercise and I learned about the power of Regular Expressions and the limits of sed and grep.

Recapitulating the problem statement:
find those words which fit these criteria.
1) The word is six characters long.
2) The letter in position 2 is different from that in position 1.
3) The letter in position 3 is different from those in positions 1 and 2.
4) The letter in position 4 is the same as that in position 1.
5) The letter in position 5 is different from those in positions 1-4.
6) The letter in position 6 is the same as that in position 2.

Combining ideas from the various posts, this is my preferred solution.
This solution (and all others posted in this thread) was tested with the short sample InFile from post #1, and also with a file containing 267,752 different English words. Making these tests teaches something about performance. This egrep ...
... whittles the file down from 267,752 lines to only 44 lines. That makes the subsequent egrep executions take almost no time. The lesson is to make this test first!

Daniel B. Martin

This could probably be made smaller, but this is readable (sorry, it's in Perl):


So you run it against your list:

Yours takes more time though :P

This is kind of interesting...

doing something like:

is much faster than

I guess because starting the regular expression engine is much more time-consuming than just calling length() to filter out all the strings that aren't 6 characters long.