¡Aquí hay uno para todos ustedes, forjadores de palabras! Escriba un programa o función que tome una lista de palabras y produzca una lista de todas las posibles descomposiciones concatenantes para cada palabra. Por ejemplo:

(Nota: este es solo un pequeño muestreo con fines ilustrativos. La producción real es mucho más voluminosa).

afterglow = after + glow
afterglow = aft + erg + low
alienation = a + lie + nation
alienation = a + lien + at + i + on
alienation = a + lien + at + ion
alienation = alien + at + i + on
alienation = alien + at + ion
archer = arc + her
assassinate = ass + as + sin + ate
assassinate = ass + ass + in + ate
assassinate = assassin + ate
backpedalled = back + pedal + led
backpedalled = back + pedalled
backpedalled = backpedal + led
goatskin = go + at + skin
goatskin = goat + skin
goatskin = goats + kin
hospitable = ho + spit + able
temporally = tempo + rally
windowed = win + do + wed
windowed = wind + owed
weatherproof = we + at + her + pro + of
yeasty = ye + a + sty

Ok, ya tienes la idea. :-)

Reglas

• Use cualquier lenguaje de programación de su elección. El código más corto por conteo de caracteres para cada idioma gana. Esto significa que hay un ganador por cada idioma utilizado. El ganador general será simplemente el código más corto de todos los presentados.
• La lista de entrada puede ser un archivo de texto, entrada estándar o cualquier estructura de lista que proporcione su idioma (lista, matriz, diccionario, conjunto, etc.). Las palabras pueden ser inglés o cualquier otro idioma natural. (Si la lista es palabras en inglés, querrá ignorar o filtrar previamente los elementos de una sola letra, excepto "a" e "i". Del mismo modo, para otros idiomas, querrá ignorar los elementos sin sentido si aparecer en el archivo)
• La lista de salida puede ser un archivo de texto, salida estándar o cualquier estructura de lista que utilice su idioma.
• Puede usar cualquier diccionario de entrada que desee, pero probablemente desee usar uno que proporcione palabras sensatas en lugar de uno que proporcione demasiadas palabras oscuras, arcanas u obnubiladas. Este es el archivo que utilicé: la lista de Corncob de más de 58000 palabras en inglés

Preguntas

Este desafío se trata principalmente de escribir el código para realizar la tarea, pero también es divertido analizar los resultados ...

1. ¿Qué subpalabras ocurren más comúnmente?
2. ¿Qué palabra se puede descomponer en la mayor cantidad de subpalabras?
3. ¿Qué palabra se puede descomponer de las maneras más diferentes?
4. ¿Qué palabras se componen de las subpalabras más grandes?
5. ¿Qué descomposiciones encontraste que fueron las más divertidas?

Python 186

a=open(raw_input()).read().split()
def W(r):
 if r:
    for i in range(1,len(r)+1):
     if r[:i]in a:
        for w in W(r[i:]):yield[r[:i]]+w
 else:yield[]
while 1:
 for f in W(raw_input()):print f

No es particularmente eficiente pero en realidad no es terriblemente lento. Simplemente ingenuamente (supongo que es posible, aunque creo que es poco probable que Python haga algunas optimizaciones inteligentes) comprueba que las sub-palabras están en el diccionario de mazorcas de maíz y encuentra recursivamente tantas palabras como sea posible. Por supuesto, este diccionario es bastante extenso y puede probar uno que no incluya varias abreviaturas y siglas (que conducen a cosas como bedridden: be dr id den). Además, el diccionario vinculado no parecía tener 'A' o 'I' enlistadas como palabras, así que las agregué manualmente.

Editar:

Ahora la primera entrada es el nombre de archivo del diccionario a utilizar, y cada uno adicional es una palabra.

Cobra - 160

sig Z(x,y)
def f(b)
    c as Z=do(x,y)
        if x.length<1,print y
        for z in File.readLines('t'),if z==x[:e=z.length].toLower,c(x[e:],y+' '+z)
    for t in b,c(t,'[t]:')

Esta es una función (tipo de dos funciones) que toma un List<of String> * e imprime las cadenas que contienen los posibles arreglos de subpalabras para cada cadena en la lista de argumentos.

* el tipo es en realidad List<of dynamic?>, pero proporcionar algo más que List<of String>probablemente lo romperá.

Scala, 132 129

Editar: ligeramente más corto como una lectura de bucle de stdin que una función

while(true)print(readLine.:\(Seq(List(""))){(c,l)=>l.flatMap{m=>Seq(c+""::m,c+m.head::m.tail)}}filter(_.forall(args contains _)))

correr como

scala decompose.scala aft after erg glow low

(o use una lista de palabras más larga :))

Original:

def f(s:Seq[String])=s.map{_.:\(Seq(List(""))){(c,l)=>l.flatMap{m=>Seq(c+""::m,c+m.head::m.tail)}}filter(_.forall(args contains _))}

Función de Seq [String] a Seq [Seq [List [String]]]. Toma el diccionario como los argumentos de la línea de comando.

Sin golf:

def decompose(wordList: Seq[String]) =
  wordList.map{ word =>                              // for each word
    word.foldRight(Seq(List(""))){ (char, accum) =>  // for each character
      accum.flatMap{list =>
        Seq(char+""::list,char+list.head::list.tail) // add it as both a new list and 
      }                                              // the to start of the first list
    }.filter(_.forall(args contains _))              // filter out lists w/ invalid words
  }

El enfoque consiste en generar todas las listas posibles de subcadenas y filtrar aquellas que contienen una cadena que no está en el diccionario. Tenga en cuenta que algunas de las subcadenas generadas contienen una cadena vacía adicional, supongo que la cadena vacía no estará en el diccionario (de todos modos, no hay forma de pasarla en la línea de comando).