Grep filtering of the dictionary

Question

I'm having a hard time getting a grasp of using grep for a class i am in was hoping someone could help guide me in this assignment. The Assignment is as follows.

Using grep print all 5 letter lower case words from the linux dictionary that have a single letter duplicated one time (aabbe or ababe not valid because both a and b are in the word twice). Next to that print the duplicated letter followed buy the non-duplicated letters in alphabetically ascending order.

The Teacher noted that we will need to use several (6) grep statements (piping the results to the next grep) and a sed statement (String Editor) to reformat the final set of words, then pipe them into a read loop where you tear apart the three non-dup letters and sort them.

Sample Output:
aback a bck 
abaft a bft 
abase a bes 
abash a bhs 
abask a bks 
abate a bet 

I haven't figured out how to do more then printing 5 character words,

grep "^.....$" /usr/share/dict/words |

Answer 1

All in one sed

sed -n '
# filter 5 letter word
/[a-zA-Z]\{5\}/ {

# lower letters
      y/ABCDEFGHIJKLMNOPQRSTUVWXYZ/abcdefghijklmnopqrstuvwxya/

# filter non single double letter
      /\(.\).*\1/ !b
      /\(.\).*\(.\).*\1.*\1/ b
      /\(.\).*\(.\).*\1.*\2/ b
      /\(.\).*\(.\).*\2.*\1/ b

# extract peer and single
      s/\(.\)*\(.\)\(.*\)\2\(.*\)/a & \2:\1\3\4/
# sort singles
:sort
      s/:\([^a]*\)a\(.*\)$/:\1\2a/
      y/abcdefghijklmnopqrstuvwxyz/zabcdefghijklmnopqrstuvwxy/
      /^a/ !b sort

# clean and print
      s/..//
      s/:/ /p
      }' YourFile

posix sed so --posix on GNU sed

Answer 2

Note that the dictionary contains capital letters and also non-letter characters, plus that strange characters used in Southern Europe. say "è".

If you want to distinguish "A" and "a", it's automatic, on the other hand if "A" and "a" are the same letter, in ALL grep invocations you must use the -i option, to instruct grep to ignore case.

Next, you always want to pass the -E option, to avoid the so called backslashitis gravis in the regexp that you want to pass to grep.

Further, if you want to exclude the lines matching a regexp from the output, the correct option is -v.

Eventually, if you want to specify many different regexes to a single grep invocation, this is the way (just an example btw)

grep -E -i -v -e 'regexp_1' -e 'regexp_2' ... -e 'regexp_n'

The preliminaries are after us, let's look forward, use the answer from chiastic-security as a reference to understand the procedings

1. There are only these possibilities to find a duplicate in a 5 character string

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

   grep -E -i -e 'regexp_1' ...

2. Now you have all the doubles, but this doesn't exclude triples etc that are identified by the following patterns (Edit added a cople of additional matching triples patterns)

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

   you want to exclude these patterns, so grep -E -i -v -e 'regexp_1' ...

3. at his point, you have a list of words with at least a couple of the same character, and no triples, etc and you want to drop double doubles, these are the regexes that match double doubles

   (.)(.)\1\2
   (.)(.)\2\1
   (.).(.)\1\2
   (.).(.)\2\1
   (.)(.).\1\2
   (.)(.).\2\1
   (.)(.)\1.\2
   (.)(.)\2.\1
   

   and you want to exclude the lines with these patterns, so its grep -E -i -v ...

A final hint, to play with my answer copy a few hundred lines of the dictionary in your working directory, head -n 3000 /usr/share/dict/words | tail -n 300 > ./300words so that you can really understand what you're doing, avoiding to be overwhelmed by the volume of the output.

And yes, this is not a complete answer, but it is maybe too much, isn't it?

Answer 3

Didn't check it thoroughly, but this might work

tr '[:upper:]' '[:lower:]' | egrep -x '[a-z]{5}' | sed -r 's/^(.*)(.)(.*)\2(.*)$/\2 \1\3\4/' | grep " " | egrep -v "(.).*\1"

But do your way because someone might see it here.

Answer 4

Your next step should be to find the 5-letter words containing a duplicate letter. To do that, you will need to use back-references. Example:

grep "[a-z]*\([a-z]\)[a-z]*\$1[a-z]*"

The $1 picks up the contents of the first parenthesized group and expects to match that group again. In this case, it matches a single letter. See: http://www.thegeekstuff.com/2011/01/advanced-regular-expressions-in-grep-command-with-10-examples--part-ii/ for more description of this capability.

You will next need to filter out those cases that have either a letter repeated 3 times or a word with 2 letters repeated. You will need to use the same sort of back-reference trick, but you can use grep -v to filter the results.

sed can be used for the final display. Grep will merely allow you to construct the correct lines to consider.

Answer 5

The first bit, obviously, is to use grep to get it down to just the words that have a single duplication in. I will give you some clues on how to do that.

The key is to use backreferences, which allow you to specify that something that matched a previous expression should appear again. So if you write

grep -E "^(.)...\1...\1$"

then you'll get all the words that have the starting letter reappearing in fifth and ninth positions. The point of the brackets is to allow you to refer later to whatever matched the thing in brackets; you do that with a \1 (to match the thing in the first lot of brackets).

You want to say that there should be a duplicate anywhere in the word, which is slightly more complicated, but not much. You want a character in brackets, then any number of characters, then the repeated character (with no ^ or $ specified).

That will also include ones where there are two or more duplicates, so the next stage is to filter them out. You can do that by a grep -v invocation. Once you've got your list of 5-character words that have at least one duplicate, pipe them through a grep -v call that strips out anything with two (or more) duplicates in. That'll have a (.), and another (.), and a \1, and a \2, and these might appear in several different orders.

You'll also need to strip out anything that has a (.) and a \1 and another \1, since that will have a letter with three occurrences.

That should be enough to get you started, at any rate.