Como encontrar palavras que seguem uma ordem específica

Question

Estou tentando escrever um script (script1.sh) que encontre todas as palavras possíveis quando receber uma confusão de letras.

• As palavras devem começar com a primeira letra da confusão e terminar com a última letra.

• As letras da palavra precisam seguir a ordem das letras da confusão.

• Cada letra da confusão pode ser usada mais de uma vez.

Então, é isso

./script1.sh "qwertyuytresdftyuiokn"

deve gerar queene, questionmas não "quieten" porque "e" vem antes de "u" e "i" na confusão.

Tentei atribuir a primeira, a última e as letras restantes às variáveis ​​e depois usar egrep para encontrar as palavras, mas não consegui encontrar uma maneira de usar a ordem das letras. Portanto, este também me dá palavras inválidas.

#!/bin/bash

first_letter=$(echo $@ | cut -c1)
last_letter=$(echo $@ |rev| cut -c1)
remaining_letters=$(echo $@ | cut -c2- | rev | cut -c2-)

grep -E "^$first_letter[$remaining_letters]*$last_letter$" /usr/share/dict/words

Então tentei transformar a confusão em uma matriz, mas novamente não consegui encontrar uma maneira de encontrar palavras que obedecessem à ordem da confusão.

Answer 1

#!/bin/sh
pttrn="^$(printf '%s' "$1" | sed -e 's/\(.\)/\1*/g' -e 's/\*/\\+/' -e 's/\*$/\\+/')"'$'
grep "$pttrn" /usr/share/dict/words

Um padrão é obtido a partir do primeiro argumento injetando *após cada caractere. Então o primeiro *é alterado para \+; assim é o último *. Além disso ^e $são adicionados. Sua entrada de exemplo gera o seguinte padrão:

^q\+w*e*r*t*y*u*y*t*r*e*s*d*f*t*y*u*i*o*k*n\+$

Este padrão é o padrão certo para grep. qdeve aparecer pelo menos uma vez no início, ndeve aparecer pelo menos uma vez no final. Cada letra do meio pode aparecer zero ou mais vezes, a ordem é mantida.

Observe que o script é idiota. Se você fornecer entrada com ., ou algo assim [, ]obterá uma expressão regular além da especificação. Forneça informações sensatas ou expanda o script para validá-lo.

---

Exemplos:

$ ./script1.sh qwertyuytresdftyuiokn
queen
question
$ ./script1.sh te
tee
$ ./script1.sh superuser
seer
serer
spur
super
supper
surer
$

Answer 2

Esta é uma maneira de abordar isso

Primeiro, filtre a lista de palavras apenas para aquelas palavras que começam e terminam com as mesmas letras da confusão. Por exemplo, se a confusão for passada como parâmetro posicional $1(e assumindo um bashshell recente)

grep -x "${1:0:1}.*${1:(-1):1}" /usr/share/dict/words

Então pegue cada uma dessas palavras e transforme-as em um regex - não consigo pensar em uma maneira "legal" de fazer isso, mas com o GNU sed você poderia fazer, por exemplo

$ sed -E 's/(.)\1*/+.*\1/2g' <<< "queen"
q+.*u+.*e+.*n

Agora teste a confusão em relação a cada padrão gerado.

Juntando tudo:

$ cat script1 
#!/bin/bash

wordlist=/usr/share/dict/words

while IFS= read -r word; do 
  grep -qEx "$(sed -E 's/(.)\1*/+.*\1/2g' <<< "$word")" <<< "$1" && printf '%s\n' "$word"
done < <(grep -x "${1:0:1}.*${1:(-1):1}" "$wordlist")

então

$ ./script1 qwertyuytresdftyuiokn
queen
question

Answer 3

Aqui está outro (executado em bash) O pythoncódigo gera a expressão regular e a alimenta grep. grepem seguida, trabalha na saída do venerável lookutilitário, que executa uma pesquisa binária para recuperar todas as /usr/share/dict/wordspalavras que começam qno exemplo. grepportanto, tem um conjunto bastante reduzido de palavras para pesquisar

python3 -c 'import sys
arr = list(sys.argv[1])
print(*arr, sep="*")
' $1 | grep -x -f - <(look ${1:0:1})

Como alternativa, uma solução look+ python3que evita expressões regulares

look q | ./finder.py "qwertyuytresdftyuiokn"

onde finder.pyé o seguinte:

#!/usr/bin/env python3
import sys
from itertools import groupby

seek_word = sys.argv[1]
for word in sys.stdin:
    orig_word = word.strip()
    word = ''.join(k for k, g in groupby(orig_word)) 
    s_w = iter(seek_word)
    i_word = iter(word)
    if all(c in s_w for c in i_word) and not next(s_w, None):
        print(orig_word)