mjhjmtu

I have a very large wordlist. How can I use Unix to find instances of multiple words fitting specific character-sharing criteria? For example, I want Words 1 and 2 to have the same fourth and seventh characters, Words 2 and 3 to have the same fourth and ninth characters, and Words 3 and 4 to have the same second, fourth, and ninth characters.

Example:

aaadiigjlf
abcdefghij
aswdofflle
bbbbbbbbbb
bisofmlwpa
fsbdfopkld
gikfkwpspa
hogkellgis

might return

abcdefghij
aaadiigjlf
fsbdfopkld
aswdofflle

For clarification, I need the code to return any words that share the same characters in given positions; I don't have specific characters (like "d" and "g" as given in the example) in mind. Also, I'd like it to be able to return words that don't fit ALL of the criteria; e.g. in the example given, Words 1 and 4 share a fourth character, but not necessarily the second, seventh, and ninth. With the program I'm running in its finished form, I'm expecting it to return a very small list of words (probably only ten) based on nine strict character-sharing criteria.

EDIT: All right, cards on the table. Here's the problem exactly how I was given it.

I am given a wordlist and told that there are ten ten-letter words in the list that can fit into a grid like so:

-112--3---
---2--3-4-
-5-2----4-
-5-2--6-4-
75-2--6---
75---8----
7----8----
79---8----
-9--0-----
-9--0---xx

Every word reads across. Every space with the same digit (and x) occupying it (all the 1s, all the 2s, etc.) is the same letter (different digits could potentially be the same letter, though not necessarily).

UPDATE: I'm still running Ralph's code. It might have been done by now, but after my external hard drive failed, I had to restart the process. It's been almost 48 hours, but it's still puttering along.

It's difficult to avoid processing the file list many times, but once for each rule should be enough. The main processing would be over the words, repeated 10 times, whilst extending possible "word lists" where for each list, the i:th word matches the i:th rule with respect to that list. Each word is added to extend a list when it matches accordingly for that list.

bash is a little bit weak for keeping this data structure, but you may chose to represent a "word list" as a sequence of comma-separated words, ended with :R to indicate the next rule R to apply for extending the list. That R is of course the same as the number of words in the list plus 1. With that as main data structure, you might arrive at the following main procedure:

N=0
M=0
cat $1 $1 $1 $1 $1 $1 $1 $1 $1 $1 | while read w || ending ; do
 [ -z "$F" ] && F=$w # capture the first word 
 [ "$F" = "$w" ] && N=$((N+1)) # count first word appearances 
 Q=( )
 matches $w 1 "" && Q=( $w:2 )
 for p in $P[@] ; do
 A="$Q[@]" && [ "$A/$p/" = "$A" ] || continue # if duplicate 
 R=$p#*: && [ $R -lt $M ] && continue # if path too short 
 Q=( $Q[@] $p ) # preserve this path for next word 
 [ "$p/$w/" = "$p" ] || continue # if word already in path 
 p=$p%:* # p is now the word list only 
 if matches $w $R $p ; then
 Q=( $Q[@] $p,$w:$((R+1)) )
 M=$N
 fi
 done
 P=( $Q[@] )
done

The matches function would be an operational representation of the rules, to determine whether a word w is an appropriate extension for list p with respect to rule R, or not. Something like the following (placed before the main procedure ):

matches() 
 local w=$1
 local p=$3
 case $2 in
 1) # -112--3---
 eqchar $w 2 $w 3
 ;;
 2) # ---2--3-4-
 eqchar $w 4 $p 4 && eqchar $w 7 $p 7
 ;;
 3) # -5-2----4-
 eqchar $w 4 $p 4 && eqchar $w 9 $p $((11+9))
 ;;
 4) # -5-2--6-4-
 eqchar $w 2 $p $((22+2)) && eqchar $w 4 $p 4 &&
 eqchar $w 9 $p $((11+9))
 ;;
 5) # 75-2--6---
 eqchar $w 2 $p $((22+2)) && eqchar $w 4 $p 4 &&
 eqchar $w 7 $p $((11+7))
 ;;
 6) # 6: 75---8----
 eqchar $w 1 $p $((44+1)) && eqchar $w 2 $p $((22+2)) &&
 eqchar $w 7 $p $((33+7))
 ;;
 7) # 7: 7----8----
 eqchar $w 1 $p $((44+1)) && eqchar $w 6 $p $((55+6))
 ;;
 8) # 8: 79---8----
 eqchar $w 1 $p $((44+1)) && eqchar $w 6 $p $((55+6))
 ;;
 9) # 9: -9--0-----
 eqchar $w 2 $p $((77+2))
 ;;
 10) # 10: -9--0---xx
 eqchar $w 2 $p $((77+2)) && eqchar $w 5 $p $((88+5)) &&
 [ -z "$1#*xx" ]
 ;;
 *)
 return 1
 ;;
 esac

The eqchar function just test whether a character of the first string, at given position, matches a character of the second string at a position. The latter string is the prior words in order with comma separation, allowing the indexing scheme of i*11+j for the j:th character (1 based) of the i:th word (0 based). E.g. the index $((77+2)) is the second character of the 8:th word.

eqchar() 
 local w=$1
 local p=$3
 [ "$w:$(($2-1)):1" = "$p:$(($4-1)):1" ]

The eqchar function should be declared before the matches function, or certainly before the main procedure.

Finally, the main procedure includes an ending function to print the result at end. The expected result would be the P holds a single "word list" of length 10, but in general, P will actually hold all the longest possible word lists appropriate for the matches rules. The ending function should make the desired printout, then return 1 so as to terminate the while clause.

Note that this is a "pure" bash solution, with O(N) (or O(N*T) where T is the number of matches to the first rule, if significantly high).

I created a words file with the example text.

-bash-4.2$ cat words
aaadiigjlf
abcdefghij
aswdofflle
bbbbbbbbbb
bisofmlwpa
fsbdfopkld
gikfkwpspa
hogkellgis

This script iterates over the wordlist setting the first word each time, and then iterates through the contents of the word file and compares the 4th and 7th characters. When it finds a match it sets this match to the second word and echos the solution so far. This script is a template and you will need to add in each of the additional constraints in subsequent nested loops:

-bash-4.2$ cat script
#!/bin/bash

for worda in $(cat ./words ); do
 firstword=$worda
 for wordb in $(cat ./words | grep -v $firstword); do
 if [ $(echo $firstword | cut -c 4,7) = $(echo $wordb | cut -c 4,7) ]; then
 secondword=$wordb
 echo "$firstword $secondword"
 fi
 done
done

Here is the output of the script:

bash-4.2$ ./script
aaadiigjlf abcdefghij
abcdefghij aaadiigjlf

Hint: Try changing the two occurrences of 4,7 to 4,9 and see what this does to the output. You can try nesting additional for loops.

I don't want to do it all for you (as it appears to be homework) but this should be more than enough to get you on the right track. You could do it manually from here with just what I've given you and plugging each constraint into the comparisson.