Aqui está um para todos os que você ama por aí! Escreva um programa ou função que pegue uma lista de palavras e produza uma lista de todas as decomposições concatenativas possíveis para cada palavra. Por exemplo:

(Nota: esta é apenas uma pequena amostra para fins ilustrativos. A produção real é muito mais volumosa.)

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, você entendeu a ideia. :-)

Regras

• Use qualquer linguagem de programação de sua escolha. O código mais curto por contagem de caracteres para cada idioma vence. Isso significa que há um vencedor para cada idioma usado. O vencedor geral será simplesmente o código mais curto de todos os inscritos.
• A lista de entrada pode ser um arquivo de texto, entrada padrão ou qualquer estrutura de lista fornecida pelo seu idioma (lista, matriz, dicionário, conjunto, etc.). As palavras podem ser em inglês ou em qualquer outro idioma natural. (Se a lista for em inglês, convém ignorar ou pré-filtrar itens de uma letra, exceto "a" e "i". Da mesma forma, em outros idiomas, você deverá ignorar itens sem sentido, se eles aparecer no arquivo.)
• A lista de saída pode ser um arquivo de texto, saída padrão ou qualquer estrutura de lista usada pelo seu idioma.
• Você pode usar qualquer dicionário de entrada que desejar, mas provavelmente desejará usar um que forneça palavras sensíveis, em vez de um que forneça muitas palavras obscuras, misteriosas ou obnubiladas. Este é o arquivo que eu usei: A lista de sabugo de milho com mais de 58000 palavras em inglês

Questões

Esse desafio é principalmente sobre escrever o código para realizar a tarefa, mas também é divertido analisar os resultados ...

1. Quais subpalavras ocorrem com mais frequência?
2. Que palavra pode ser decomposta no maior número de subpalavras?
3. Que palavra pode ser decomposta das maneiras mais diferentes?
4. Quais palavras são compostas das maiores subpalavras?
5. Que decomposições você achou mais 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

Não é particularmente eficiente, mas na verdade não é muito lento. É ingênuo (suponho que seja possível, embora eu ache improvável que o python faça algumas otimizações inteligentes) verifica se as subpalavras estão no dicionário da espiga de milho e encontra recursivamente o máximo de palavras possível. É claro que este dicionário é bastante extenso e você pode tentar um que não inclua várias abreviações e acrônimos (levando a coisas como bedridden: be dr id den). Além disso, o dicionário vinculado não parecia ter 'A' ou 'I' listado como palavras, então eu as adicionei manualmente.

Editar:

Agora, a primeira entrada é o nome do arquivo do dicionário a ser usado, e cada entrada adicional é uma palavra.

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]:')

Essa é uma função (que classifica duas funções) que recebe um List<of String>* e imprime as strings que contêm os possíveis arranjos de sub-palavras para cada string na lista de argumentos.

* o tipo é realmente List<of dynamic?>, mas fornecer algo diferente List<of String>provavelmente irá quebrá-lo.

Scala, 132 129

Edit: ligeiramente mais curto como uma leitura de loop do stdin do que uma função

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

(ou use uma lista de palavras mais longa :))

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 _))}

Função de Seq [String] para Seq [Seq [List [String]]]. Leva o dicionário como os argumentos da linha de comando.

Ungolfed:

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
  }

A abordagem é gerar todas as listas possíveis de substrings e filtrar as que contêm uma string que não está no dicionário. Observe que algumas das substrings geradas contêm uma string vazia extra, presumo que a string vazia não esteja no dicionário (não há como passar a linha de comando de qualquer maneira).