Resolver un anagrama

9

Ver también: Granma ama a Ana

Se le dará una cadena de letras minúsculas ASCII. Usando este archivo de diccionario (ACTUALIZADO), su tarea es resolver el anagrama. Para resolver un anagrama, debe generar todas las palabras o grupos de palabras que se pueden formar usando cada letra de la cadena de entrada exactamente una vez, separadas por nuevas líneas. Los grupos de las mismas palabras en un orden diferente no son únicos y no se deben generar por separado; sin embargo, el orden de las palabras no importa . El orden de las soluciones de salida tampoco importa . Si la entrada no puede formar una palabra, no genera nada.

Algunos casos de prueba útiles:

Input:  viinlg
Output: living

Input:  fceodglo
Output: code golf

Input:  flogflog
Output: golf golf

Input:  ahwhygi
Output: highway
        high way

Input:  bbbbbb
Output: 

Reglas / advertencias:

  • Puede acceder a la lista de diccionarios de la forma que desee. Se aceptan argumentos de línea de comando, stdin, lectura de archivos o lectura de internet.

  • La entrada consistirá únicamente en letras minúsculas ASCII. No es necesario que genere resultados en ningún caso en particular.

  • No se le dará una cadena que ya forma una palabra válida (sin embargo, se le puede dar una cadena que forma varias palabras, como bluehouse).

  • Las nuevas líneas finales están permitidas pero no son obligatorias.

  • Se aplican lagunas estándar.

Este es el . El código más corto en bytes gana. ¡Buena suerte!

dispersión
fuente
Puesto de sandbox.
dispersión
¿Deberíamos usar 1 espacio para separar conjuntos de palabras o cualquier separador que no sea letra es suficiente?
Erik the Outgolfer
@EriktheOutgolfer Para separar conjuntos de palabras, cualquier separador está bien; sin embargo, aún debe separar las palabras dentro de una única solución con un espacio.
dispersión
Sin embargo, las Reglas cristianas dicen que debe separar conjuntos de palabras con líneas nuevas.
Erik the Outgolfer
@EriktheOutgolfer Entonces, ¿por qué preguntaste "Deberíamos usar 1 espacio para separar conjuntos de palabras"? Su pregunta me confundió, y no debería haber ninguna razón para preferir algo sobre las nuevas líneas para separar conjuntos. Yo diría que atenerse a las especificaciones.
dispersión

Respuestas:

2

Python 2 , 341 327 337 320 bytes

Esta solución supone que el diccionario se almacena en una variable wcomo un conjunto de cadenas. combinationsNo es necesario usar el primer conjunto de combinations_with_replacement, pero el uso de este último ahorra bytes.

from itertools import*
d,o,j,c={},sorted,''.join,combinations_with_replacement
s,w=o(raw_input()),input()
l=len(s)
r=range(l)
for x in w:d.setdefault(j(o(x)),[]).append(x)
b=set(chain(*[d[j(x)]for y in r for x in c(s,y+1)if j(x) in d]))
print'\n'.join(' '.join(x)for y in r for x in c(b,y+1)if(len(j(x)),o(j(x)))==(l,s))

Pruébalo en línea!

Entrada: palabra anagramada seguida del diccionario de palabras como un conjunto:

anagram_word
{'entry1', 'entry2', ...., 'entryN'}

Editar: entradas actualizadas.

Sunny Patel
fuente
1

Python 3 , 248202 bytes

from itertools import*
A=set()
def f(s,*G,i=1,A=A):
 if' '>s:A|={' '.join(sorted(G))}
 for _ in s:s[:i]in S and f(s[i:],s[:i],*G);i+=1
I,*S=iter(input,'')
for p in permutations(I):f(''.join(p))
print(A)

Pruébalo en línea!

La entrada es la siguiente:

word_input
dic_entry_1
dic_entry_2
....
dic_entry_N
                 # <<< empty line + \n

Acelerándolo:

Para fines de prueba, si cambia de I,*S=iter(input,'')a I=input();S=set(iter(input,'')), el tiempo de ejecución se reducirá drásticamente y la salida será la misma.

Explicación:

En cada permutación de la entrada, intenta dividir recursivamente la permutación en todas las ubicaciones posibles, comenzando de izquierda a derecha, sin omitir letras, con palabras que están en el diccionario. Si una combinación dividida coincide con toda la permutación de entrada, las palabras divididas se ordenan y se agregan a una setque se imprimirá en y de la evaluación.

Felipe Nardi Batista
fuente
1

Javascript, 139 137 129 Bytes

-2 Bytes gracias a @FelipeNardiBatista

-8 Bytes gracias a la lectura de los documentos;)

k=>w=>{t=w;return k.reduce((a,v)=>{r=([...v].every(c=>w.includes(c)&&((w=w.replace(c,""))||!0)))?a.concat(v):a;w=t;return r},[])}

Toma el diccionario como entrada en forma de una matriz de cadenas.

var arr = ["living", "code", "golf", "highway", "high", "way"];

var _=
k=>w=>{t=w;return k.reduce((a,v)=>{r=([...v].every(c=>w.includes(c)&&((w=w.replace(c,""))||!0)))?a.concat(v):a;w=t;return r},[])};

console.log(_(arr)("viinlg"));
console.log(_(arr)("fceodglo"));

Explicación:

Para cada palabra en el diccionario, verifique si cada letra está contenida en la palabra elegida, al tiempo que la elimina de la palabra. Al final de cada entrada del diccionario, restaure la palabra a su estado inalterado para verificar si hay más coincidencias.

Hankrecords
fuente
@FelipeNardiBatista Tienes razón, olvidé jugar ese nombre. Gracias :)
Hankrecords