Décomposer les mots en d'autres mots (par exemple, «rémanence» = «arrière» + «erg» + «faible»)

13

En voici un pour tous les forgerons de mots! Écrivez un programme ou une fonction qui prend une liste de mots et produit une liste de toutes les décompositions concaténatives possibles pour chaque mot. Par exemple:

(Remarque: Il ne s'agit que d'un petit échantillonnage à des fins d'illustration. La production réelle est beaucoup plus volumineuse.)

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, vous avez l'idée. :-)

Règles

  • Utilisez n'importe quel langage de programmation de votre choix. Le code le plus court par nombre de caractères pour chaque langue gagne. Cela signifie qu'il y a un gagnant pour chaque langue utilisée. Le gagnant général sera simplement le code le plus court de tous les soumissions.
  • La liste d'entrée peut être un fichier texte, une entrée standard ou toute structure de liste fournie par votre langue (liste, tableau, dictionnaire, ensemble, etc.). Les mots peuvent être l'anglais ou toute autre langue naturelle. (Si la liste contient des mots anglais, vous voudrez ignorer ou pré-filtrer les éléments à une seule lettre, sauf pour "a" et "i". De même, pour les autres langues, vous voudrez ignorer les éléments absurdes s'ils apparaissent dans le fichier.)
  • La liste de sortie peut être un fichier texte, une sortie standard ou toute structure de liste utilisée par votre langue.
  • Vous pouvez utiliser n'importe quel dictionnaire d'entrée que vous aimez, mais vous voudrez probablement en utiliser un qui fournit des mots sensés plutôt qu'un dictionnaire qui fournit trop de mots obscurs, obscurs ou obnubilés. Voici le fichier que j'ai utilisé: la liste Corncob de plus de 58000 mots anglais

Des questions

Ce défi consiste principalement à écrire le code pour accomplir la tâche, mais c'est aussi amusant de parcourir les résultats ...

  1. Quels sous-mots apparaissent le plus souvent?
  2. Quel mot peut être décomposé en le plus grand nombre de sous-mots?
  3. Quel mot peut être décomposé de différentes manières?
  4. Quels mots sont composés des plus grands sous-mots?
  5. Quelles décompositions avez-vous trouvées les plus amusantes?
Todd Lehman
la source
@Geobits - Ah, merci! J'ai raté deux décompositions alienationquand j'ai coupé et collé ça. Fixé maintenant. Pour les autres, la liste ci-dessus n'est qu'un petit échantillon. Mon programme de test a généré des dizaines de milliers de réponses lorsqu'il a reçu la liste Corncob.
Todd Lehman
1
"Quels sous-mots apparaissent le plus souvent?" Je vais jeter une supposition sauvage et dire que «a» pourrait être près du sommet.
Sellyme
@SebastianLamerichs - Je ne sais pas ... Peut-être, peut-être pas. :)
Todd Lehman
@ToddLehman cette phrase contient exactement 0 sous-mots, donc 'a' est toujours égal en premier: P
Sellyme
@SebastianLamerichs si vous faisiez référence à la réponse de Todd à vous, "dunno" peut être divisé en "dun" + "no". ;)
j'ai alarmé un extraterrestre le

Réponses:

3

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

Pas particulièrement efficace mais en fait pas terriblement lent. Il naïvement (je suppose que c'est possible, bien que je pense peu probable que python fasse des optimisations intelligentes) vérifie que les sous-mots sont dans le dictionnaire corncob et trouve récursivement autant de mots que possible. Bien sûr, ce dictionnaire est assez complet et vous pouvez en essayer un qui ne comprend pas diverses abréviations et acronymes (conduisant à des choses comme bedridden: be dr id den). De plus, le dictionnaire lié ne semblait pas avoir de «A» ou de «I» comme mots, donc je les ai ajoutés manuellement.

Éditer:

Maintenant, la première entrée est le nom de fichier du dictionnaire à utiliser, et chaque autre est un mot.

KSab
la source
Il vaut la peine d'indiquer qu'il s'agit de Python 2, car le code ne s'exécute pas en Python 3, car il print fdevrait êtreprint(f)
De plus, comment puis-je exécuter cela? echo archer|python2 filename.pygénère une erreur EOFErrr pour la dernière ligne
Certaines choses que vous pourriez encore changer (je ne les ai pas testées, mais je suis sûr que cela fonctionnerait): for f in W(raw_input()):print f=> ''.join(W(raw_input()); a=open('c').read().split('\n')=>a=open('c').readlines()
ɐɔıʇǝɥʇuʎs
@ ɐɔıʇǝɥʇuʎs Votre premier fonctionnerait mais readlinesconserve les caractères de nouvelle ligne à la fin des lignes, c'est pourquoi je l'ai fait comme je l'ai fait.
KSab
@ ɐɔıʇǝɥʇuʎs Oh en fait, il semble joinque tous les éléments soient des chaînes et je ne peux pas les obtenir sous une forme plus petite que ce que j'ai déjà.
KSab
2

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

Il s'agit d'une fonction (sorte de deux fonctions) qui prend un List<of String>* et affiche les chaînes contenant les arrangements de sous-mots possibles pour chaque chaîne de la liste d'arguments.

* le type est en fait List<of dynamic?>, mais fournir autre chose que List<of String>le cassera probablement.

Οurous
la source
2

Scala, 132 129

Edit: légèrement plus court comme une lecture de boucle depuis stdin qu'une fonction

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

courir comme

scala decompose.scala aft after erg glow low

(ou utilisez une liste de mots plus longue :))

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

Fonction de Seq [String] à Seq [Seq [List [String]]]. Prend le dictionnaire comme arguments de ligne de commande.

Non 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
  }

L'approche consiste à générer toutes les listes possibles de sous-chaînes et à filtrer celles qui contiennent une chaîne qui n'est pas dans le dictionnaire. Notez que certaines des sous-chaînes générées contiennent une chaîne vide supplémentaire, je suppose que la chaîne vide ne sera pas dans le dictionnaire (il n'y a aucun moyen de la transmettre de toute façon sur la ligne de commande).

paradigmsort
la source