1

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.

5
  • Did you end up getting it working J.T.? Do you have any further questions?
    – Crypteya
    Feb 1, 2019 at 0:04
  • Believe it or not, it's still running. It's been going for about 36 hours now. I'll let you know what develops.
    – J.T.
    Feb 1, 2019 at 9:30
  • 1
    I think something messed up. I just got a message saying cat: dict.txt: No medium found. It's entirely possible that it might be my old external hard drive that I was storing the wordlist on crapping out on me, and I should have moved it to my internal hard drive and run it from there. Grr... Now I have to start all over.
    – J.T.
    Feb 1, 2019 at 19:54
  • that error message sounds like your script couldn't find the file. So a hard drive issue sounds on the money. As for your script, you should be confirming correct operation before allowing a script to run for that long. Did you take Ralph's recommendation regarding timestamps? Are you checking the results that the program is producing periodically?
    – Crypteya
    Feb 3, 2019 at 23:05
  • I, um...I don't know how to make a timestamp like he said.
    – J.T.
    Feb 3, 2019 at 23:47

2 Answers 2

1

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).

5
  • This all looks promising. To make sure I've got it, I would put the eqchar function code in first, then the matches function code, and finally the main function (the bit starting with N=0), correct? But where do I put the wordlist (or rather, the wordlist's .txt path) to start with?
    – J.T.
    Jan 30, 2019 at 20:36
  • the input word list would be a file, which is given on the command line...like $ ./myscript.sh wordlist.dat Jan 30, 2019 at 21:01
  • Okay, cool. Thank you so, so much. I've got it running now; it's been running for about two hours with no results yet. Do you know about how long it should take? For reference, the wordlist contains 1973 words.
    – J.T.
    Jan 30, 2019 at 23:04
  • No I don't know. Perhaps you can change it to make a time stamp to stderr when it increments N, which is when it restarts the word list... off-hand I think it should be the order of 10*(the first word list time). Jan 30, 2019 at 23:37
  • This did end up working. It took several, several days, but I got my answer. Thank you!
    – J.T.
    Feb 18, 2019 at 0:47
1

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.

1
  • All right, it looks like this might work (though it sure takes a while to run). (This isn't homework, for the record; I'm a non-coder looking at a coding puzzle, and all of my coder friends are...well, I don't have any coder friends.) Just to be clear, to nest it, I would repeat the code from "for wordb" to "$wordb" after "$wordb", changing "wordb" to "wordc", "wordd", etc. and adding $secondword, $thirdword, etc. after "grep -v" each time, right?
    – J.T.
    Jan 30, 2019 at 9:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .