☰

Cómo encontrar palabras que sigan un orden específico

tag-icon • tag-icon bash shell-script scripting
Cómo encontrar palabras que sigan un orden específico

Estoy intentando escribir un script (script1.sh) que encuentre todas las palabras posibles cuando se le presente un revoltijo de letras.

  • Las palabras deben comenzar con la primera letra del revoltijo y terminar con la última letra.

  • Las letras de la palabra deben seguir el orden de las letras en el revoltijo.

  • Cada letra del revoltijo se puede utilizar más de una vez.

Así que esto

./script1.sh "qwertyuytresdftyuiokn"

debería salir queenpero questionno "silenciarse" porque "e" viene antes que "u" e "i" en el revoltijo.

Intenté asignar la primera, la última y las letras restantes a variables, luego usé egrep para encontrar las palabras, pero no pude encontrar una manera de usar el orden de las letras. Entonces este también me da palabras 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

Luego intenté convertir el revoltijo en una matriz, pero nuevamente no pude encontrar la manera de encontrar palabras que obedecieran el orden en el revoltijo.

Respuesta1

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

Se obtiene un patrón a partir del primer argumento inyectando *después de cada carácter. Luego el primero *se cambia a \+; también lo es el último *. Además ^y $se agregan. Su entrada de ejemplo genera el siguiente patrón:

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

Este patrón es el patrón correcto para grep. qdebe aparecer al menos una vez al principio, ndebe aparecer al menos una vez al final. Cada letra del medio puede aparecer cero o más veces, el orden se mantiene.

Tenga en cuenta que el guión es tonto. Si proporciona información con , .o algo así, obtendrá una expresión regular más allá de la especificación. Proporcione información sensata o expanda el script para validarlo.[]

Ejemplos:

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

Respuesta2

He aquí una forma de abordarlo

Primero, filtre la lista de palabras solo para aquellas palabras que comienzan y terminan con las mismas letras que el revoltijo. Por ejemplo, si el revoltijo se pasa como parámetro posicional (y suponiendo un shell $1reciente )bash

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

Luego, toma cada una de estas palabras y desmenúzalas en una expresión regular. No se me ocurre una manera "agradable" de hacerlo, pero con GNU sed podrías hacerlo, por ejemplo.

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

Ahora pruebe el revoltijo con cada patrón generado.

Poniendolo todo junto:

$ 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")

entonces

$ ./script1 qwertyuytresdftyuiokn
queen
question

Respuesta3

Aquí hay otro (ejecutado en bash). El pythoncódigo genera la expresión regular y se la envía grep. grepluego trabaja con la salida de la venerable lookutilidad, que realiza una búsqueda binaria para recuperar todas las /usr/share/dict/wordspalabras que comienzan con qen el ejemplo. greppor lo tanto, tiene un conjunto muy reducido de palabras para buscar

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

Alternativamente, una solución look+ python3que evita expresiones regulares.

look q | ./finder.py "qwertyuytresdftyuiokn"

donde finder.pyes el siguiente:

#!/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)

información relacionada