Löse ein Anagramm

9

Siehe auch: Granma liebt Ana

Sie erhalten eine Folge von ASCII-Kleinbuchstaben. Mit dieser Wörterbuchdatei (UPDATED) müssen Sie das Anagramm lösen. Um ein Anagramm zu lösen, müssen Sie alle Wörter oder Wortgruppen, die mit jedem Buchstaben aus der Eingabezeichenfolge gebildet werden können, genau einmal ausgeben, getrennt durch Zeilenumbrüche. Gruppen derselben Wörter in einer anderen Reihenfolge sind nicht eindeutig und sollten nicht separat ausgegeben werden. Die Reihenfolge der Wörter spielt jedoch keine Rolle . Die Reihenfolge der Ausgabelösungen spielt ebenfalls keine Rolle . Wenn die Eingabe kein Wort bilden kann, geben Sie nichts aus.

Einige nützliche Testfälle:

Input:  viinlg
Output: living

Input:  fceodglo
Output: code golf

Input:  flogflog
Output: golf golf

Input:  ahwhygi
Output: highway
        high way

Input:  bbbbbb
Output: 

Regeln / Vorbehalte:

  • Sie können auf die Wörterbuchliste zugreifen, wie Sie möchten. Befehlszeilenargument, stdin, Lesen aus einer Datei oder Lesen aus dem Internet sind zulässig.

  • Die Eingabe besteht nur aus ASCII-Kleinbuchstaben. In bestimmten Fällen müssen Sie keine Ergebnisse ausgeben.

  • Sie erhalten keine Zeichenfolge, die bereits ein gültiges Wort bildet (möglicherweise erhalten Sie jedoch eine Zeichenfolge, die mehrere Wörter bildet , z. B. bluehouse).

  • Nachgestellte Zeilenumbrüche sind zulässig, aber nicht erforderlich.

  • Es gelten Standardlücken.

Das ist . Der kürzeste Code in Bytes gewinnt. Viel Glück!

streuen
quelle
Sollten wir 1 Leerzeichen verwenden, um Wortgruppen zu trennen, oder reicht ein Trennzeichen ohne Buchstaben aus?
Erik der Outgolfer
@EriktheOutgolfer Um Sätze von Wörtern zu trennen , ist jedes Trennzeichen in Ordnung. Sie sollten jedoch Wörter innerhalb einer einzelnen Lösung durch ein Leerzeichen trennen.
Streuung
@Christian Rules besagt jedoch, dass Sie Wortgruppen durch Zeilenumbrüche trennen müssen.
Erik der Outgolfer
@EriktheOutgolfer Warum hast du dann gefragt "Sollten wir 1 Leerzeichen verwenden, um Sätze von Wörtern zu trennen"? Ihre Frage hat mich verwirrt, und es sollte keinen Grund geben, irgendetwas den Zeilenumbrüchen vorzuziehen, um Sätze zu trennen. Ich würde sagen, bleib bei der Spezifikation.
Streuung

Antworten:

2

Python 2 , 341 327 337 320 Bytes

Diese Lösung setzt voraus, dass das Wörterbuch in einer Variablen wals Satz von Zeichenfolgen gespeichert ist . Der erste Satz von combinationsmuss nicht verwendet werden combinations_with_replacement, aber der letztere spart 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))

Probieren Sie es online aus!

Eingabe - Anagrammiertes Wort, gefolgt vom Wörterbuch der Wörter als Satz:

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

Bearbeiten: Eingaben aktualisiert.

Sonniger Patel
quelle
1

Python 3 , 248 202 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)

Probieren Sie es online aus!

Die Eingabe ist wie folgt:

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

Beschleunigen:

Wenn Sie zu Testzwecken von I,*S=iter(input,'')zu wechseln , I=input();S=set(iter(input,''))wird die Laufzeit drastisch reduziert und die Ausgabe bleibt gleich.

Erläuterung:

Bei jeder Permutation der Eingabe wird versucht, die Permutation an allen möglichen Stellen rekursiv aufzuteilen, beginnend von links nach rechts, ohne Buchstaben zu überspringen, mit Wörtern, die sich im Wörterbuch befinden. Wenn eine geteilte Kombination mit der gesamten Eingabepermutation übereinstimmt, werden die geteilten Wörter sortiert und zu einer hinzugefügt, setdie am und der Auswertung gedruckt wird.

Felipe Nardi Batista
quelle
1

Javascript, 139 137 129 Bytes

-2 Bytes dank @FelipeNardiBatista

-8 Bytes dank Lesen der Dokumente;)

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},[])}

Nimmt das Wörterbuch als Eingabe in Form eines Arrays von Zeichenfolgen auf.

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

Erläuterung:

Überprüfen Sie für jedes Wort im Wörterbuch, ob jeder Buchstabe im ausgewählten Wort enthalten ist, und entfernen Sie es gleichzeitig aus dem Wort. Stellen Sie am Ende jedes Wörterbucheintrags den unveränderten Zustand des Wortes wieder her, um nach weiteren Übereinstimmungen zu suchen.

Hankrecords
quelle
@FelipeNardiBatista Du hast recht, ich habe vergessen, diesen Namen zu spielen. Danke :)
Hankrecords