Finden Sie die kürzesten Pangrams aus einer Wortliste

10

Ein pangram ist eine Zeichenfolge , die jeden Buchstaben enthält a- zdie englische Alphabet, Groß- und Kleinschreibung. (Es ist in Ordnung, wenn das Pangram mehr als eine Kopie eines Buchstabens enthält oder wenn es zusätzlich zu den Buchstaben Zeichen enthält, die keine Buchstaben sind.)

Schreiben Sie ein Programm oder eine Funktion, deren Eingabe eine Liste von Zeichenfolgen ist und die eine oder mehrere Zeichenfolgen mit den folgenden Eigenschaften ausgibt:

  • Jede Ausgabezeichenfolge muss ein Pangram sein.
  • Jede Ausgabezeichenfolge muss durch Verketten einer oder mehrerer Zeichenfolgen aus der Eingabeliste gebildet werden, die durch Leerzeichen getrennt sind.
  • Jede Ausgabezeichenfolge muss die kürzeste oder die kürzeste unter allen Zeichenfolgen mit diesen Eigenschaften sein.

Viele Programme geben nur eine Zeichenfolge aus. Sie möchten nur mehr als eine Zeichenfolge ausgeben, wenn Sie ansonsten zusätzlichen Code schreiben müssten, um die Ausgabe zu begrenzen.

Sie können davon ausgehen, dass die Eingabe keine nicht druckbaren Zeichen oder Leerzeichen enthält und dass kein Wort mehr als (26-mal der natürliche Logarithmus der Länge der Liste) Zeichen lang ist. (Sie dürfen jedoch nicht davon ausgehen, dass die Eingabe nur Buchstaben oder nur Kleinbuchstaben enthält. Satzzeichen und Großbuchstaben sind durchaus möglich.)

Eingabe und Ausgabe können in jedem vernünftigen Format erfolgen. Zum Testen Ihres Programms empfehle ich die Verwendung von zwei Testfällen: einem Wörterbuch mit englischen Wörtern (die meisten Computer haben einen) und dem folgenden Fall (für den ein perfektes Pangram (26 Buchstaben) unmöglich ist, sodass Sie einen finden müssen) mit doppelten Buchstaben):

abcdefghi
defghijkl
ijklmnop
lmnopqrs
opqrstuvw
rstuvwxyz

Sie sollten Ihrer Einreichung ein Beispiel der Ausgabe Ihres Programms beifügen. (Dies kann für verschiedene Personen aufgrund der Verwendung unterschiedlicher Wortlisten durchaus unterschiedlich sein.)

Siegbedingung

Dies ist eine Herausforderung mit . Der Gewinner ist das kürzeste Programm (in Bytes), das in Polynomzeit ausgeführt wird . (Eine Zusammenfassung für Personen, die nicht wissen, was das bedeutet: Wenn Sie die Größe der Wortliste verdoppeln, sollte das Programm nur um einen konstanten Faktor langsamer werden. Der betreffende konstante Faktor kann jedoch so groß sein wie Sie Zum Beispiel ist es gültig, dass es viermal langsamer oder achtmal langsamer wird, aber nicht, dass es um einen Faktor der Länge der Wortliste kleiner wird; der Faktor, über den es langsamer wird, muss begrenzt werden.)


quelle
Können wir bei der Bestimmung der Komplexität die Tatsache verwenden, dass jedes Wort höchstens 26 Buchstaben lang ist? Dass die Alphabetgröße eine Konstante von 26 ist?
xnor
Ja. Ich habe diese Einschränkung der Eingabe dort teilweise auferlegt, um die Komplexität leichter zu definieren / berechnen zu können.
Ich denke, das stößt auf eine technische Frage. Wenn Sie wiederholte Eingabewörter ignorieren, gibt es höchstens 27 ^ 26 mögliche Eingabewörter und somit höchstens 2 ^ (27 ^ 26) mögliche Teilmengen davon als mögliche Eingaben. Das ist riesig, aber eine Konstante. Jedes Programm auf dieser endlichen Menge ist also zeitkonstant, wobei die Konstante die maximale Anzahl von Schritten ist, die über alle möglichen Eingaben ausgeführt werden.
xnor
Ich habe nicht gesagt, dass die Eingabe keine doppelten Wörter enthält. Ich denke, Sie könnten das Programm in einer "technischen" O (n) -Zeit ausführen, indem Sie Satzzeichen herausfiltern und zuerst die Eingabe deduplizieren (oder wahrscheinlicher O (n log n), was viel weniger Speicher als ein Radix verbrauchen würde deduplizieren würde). Dann müssten Sie von der gefilterten Version zur ursprünglichen Wortliste zurückkehren. Sie können die fragliche Polynomzeit nur beanspruchen, wenn Sie tatsächlich alle diese Schritte durchlaufen haben!
Ich hatte Nicht-Briefe vergessen. Können wir annehmen, dass dies ASCII ist oder auf andere Weise innerhalb einer endlichen Menge? Wenn ja, kann jeder Algorithmus, der mit der Deduplizierung beginnt, als Polynomzeit gelten.
xnor

Antworten:

3

Ruby 159 (iterativ)

Rubin 227 220 229 227 221 (rekursiv)

Neue iterative Lösung (basierend auf dem von @Niel beschriebenen Algorithmus):

c={('A'..'Z').to_a=>""}
while l=gets
d=c.clone
c.map{|k,v|j=k-l.upcase.chars
w=v+" "+l.strip
d[j]=w if !c[j]||c[j].size<w.size}
c=d
end
x=c[[]]
p x[1..-1] if x

Alte rekursive Lösung:

W=[]
while l=gets
W<<l.strip
end
I=W.join(" ")+"!!"
C={[]=>""}
def o(r)if C[r]
C[r]
else
b=I
W.map{|x|s=r-x.upcase.chars
if s!=r
c=x+" "+o(s)
b=c if c.size<b.size
end}
C[r]=b
end
end
r=o ('A'..'Z').to_a
p r[0..-2] if r!=I

Die Bytemessung basiert darauf, dass die letzte neue Zeile in der Datei weggelassen wird, was nicht wichtig ist ruby 2.3.1p112. Die Anzahl der Bytes stieg wieder an, nachdem ein kleiner Fehler behoben wurde (Hinzufügen.downcase .upcase für Groß- und Kleinschreibung, wie in der Problemstellung gefordert).

Hier ist eine frühere Version von vor dem Kürzen von Bezeichnern und dergleichen:

#!/usr/bin/env ruby

$words = [];

while (line=gets)
  $words << line[0..-2];
end

$impossible = $words.join(" ")+"!!";

$cache = {};

def optimize(remaining)
  return $cache[remaining] if ($cache[remaining]);
  return "" if (remaining == []);

  best = $impossible;

  $words.each{|word|
    remaining2 = remaining - word.chars;
    if (remaining2 != remaining)
      curr = word + " " + optimize(remaining2);
      best = curr if (curr.length < best.length);
    end
  };

  $stderr.puts("optimize(#{remaining.inspect})=#{best.inspect}");

  return $cache[remaining] = best;
end

result = optimize(('a'..'z').to_a);

puts(result[0..-1]);

Wie funktioniert es? Grundsätzlich werden eine Reihe von Zeichen beibehalten, die noch abgedeckt werden müssen, und es wird nur dann auf ein Wort zurückgegriffen, wenn dies die nicht abgedeckte Menge reduzieren würde. Zusätzlich werden die Ergebnisse der Rekursion gespeichert. Jede Teilmenge von 2 ^ 26 entspricht einem Memoisierungstabelleneintrag. Jeder solche Eintrag wird zeitlich proportional zur Größe der Eingabedatei berechnet. Das Ganze ist also O(N)(wo Nist die Größe der Eingabedatei), wenn auch mit einer riesigen Konstante.

DepressedDaniel
quelle
1

JavaScript (ES6), 249 248 Bytes, möglicherweise konkurrierend

a=>a.map(w=>w.replace(/[a-z]/gi,c=>b|=1<<parseInt(c,36)-9,b=0,l=w.length)&&(m.get(b)||[])[0]<l||m.set(b,[l,w]),m=new Map)&&[...m].map(([b,[l,w]])=>m.forEach(([t,s],e)=>(m.get(e|=b)||[])[0]<=t+l||m.set(e,[t+l+1,s+' '+w])))&&(m.get(-2^-1<<27)||[])[1]

Erläuterung: Transformiert das Array, indem die Buchstaben in eine Bitmaske konvertiert werden, wobei nur das kürzeste Wort für jede Bitmaske in einer Karte gespeichert wird. Wenn Sie dann eine Kopie der Karte durchlaufen, erweitern Sie die Karte, indem Sie jede kombinierte Bitmaske hinzufügen, wenn die resultierende Zeichenfolge kürzer wäre. Geben Sie schließlich die Zeichenfolge zurück, die für die Bitmap gespeichert wurde, die einem Pangram entspricht. (Gibt zurück, undefinedwenn keine solche Zeichenfolge vorhanden ist.)

Neil
quelle
Interessant. Könnten Sie mehr darüber erfahren, wie es funktioniert, und, falls verfügbar, den ungolfed Code veröffentlichen?
DepressedDaniel
1
Dies sollte ein gültiger / konkurrierender Eintrag sein. Ich denke, das läuft tatsächlich in O ( n log n )! (Die Karte hat ein festes Limit von 2²⁶ Einträgen und wird daher nicht in der Komplexität
Ich habe gerade die Beschreibung noch einmal gelesen und verstehe, wie es jetzt funktioniert. Ordentlich. +1 ... Hmm, wann wird entschieden, nicht mehr zu versuchen, die Karte zu erweitern, indem Paare berücksichtigt werden? Es sollte so lange weitergehen, bis keine Entspannung mehr möglich ist.
DepressedDaniel
@DepressedDaniel Für jede aus der ursprünglichen Wortliste extrahierte Bitmaske werden alle bisher gefundenen Teil-Pangrams überprüft und ob durch Hinzufügen des Wortes ein Pangram erstellt wird, das kürzer ist als das derzeit für die kombinierte Bitmaske bekannte.
Neil
@ ais523 Bei großen Eingaben (> 1000 Wörter) scheint die meiste Zeit mit dem Tauschen verbracht zu werden. Ich habe versucht, von einer Karte zu einem Array zu wechseln, und es wurde noch langsamer!
Neil
-1

Python 3, 98 , 94 , 92 Bytes

print([s for s in input().split()if sum([1 for c in range(65,91)if chr(c)in s.upper()])>25])

Durchläuft die ASCII-Darstellung des Alphabets und fügt einer Liste eine 1 hinzu, wenn der Buchstabe in der Zeichenfolge gefunden wird. Wenn die Summe der Liste größer als 25 ist, enthält sie alle Buchstaben des Alphabets und wird gedruckt.

Erich
quelle
Ich denke, Sie können ein Leerzeichen zwischen (' ')und entfernen if. Sie können auch ändern ord(i) in range(65,91)zu 91>x>=65. Was ist auch die Komplexität?
NoOneIsHere
1
Was ist die Komplexität dieser Lösung? Es ist erforderlich, dass die Antwort eine polynomielle Komplexität aufweist, andernfalls ist sie nicht konkurrierend.
NoOneIsHere
Sorry, ich denke es ist O (n), weil die Eingabeliste in der Länge variieren kann aber
Erich
Entschuldigung, ich denke es ist O (n), da die Eingabeliste unterschiedlich lang sein kann, aber die zweite Schleife immer von 65 bis 90 reicht. Aber ich habe sie nicht getestet.
Erich
Nicht sicher, ob dies erfüllt ist. "Jede Ausgabezeichenfolge muss die kürzeste oder die kürzeste unter allen Zeichenfolgen mit diesen Eigenschaften sein."
DepressedDaniel