Da ich mich nicht länger als 5 Sekunden auf eine Aufgabe konzentrieren kann, teile ich Wörter häufig in Teilzeichenfolgen auf, die jeweils eine andere Länge haben und keine wiederholten Zeichen enthalten. Zum Beispiel könnte das Wort "Pasta" in "Past" & "A", "Pas" & "Ta" oder "Pa" & "Sta" aufgeteilt werden und Sie erhalten das Bild.
Da es jedoch schwierig ist, sich an alle Kombinationen zu erinnern, wähle ich im Allgemeinen nur eine aus, und ich wähle gerne die schönste aus. Wir betrachten den schönsten Weg als den mit der niedrigsten "Punktzahl". Ihre Aufgabe wird es sein, ein Wort zu geben, um die Punktzahl unter Berücksichtigung der folgenden komplizierten Regeln auszudrucken.
Wertung
Beschreibung, wie man ein Wort bewertet:
Ein Wort ist eine Folge von lateinischen Zeichen. Großbuchstaben sollten durch zwei gleiche Kleinbuchstaben ersetzt werden (aus "Box" wird "bbox").
Ein Segment ist eine zusammenhängende (strenge) Teilzeichenfolge eines Wortes und darf kein Zeichen zweimal enthalten ("her", "re", "h" sind alle gültigen Segmente von "Here" ("hhere"), aber "hh"). und "ere" sind nicht)
Eine Segmentierung ist eine Menge von Segmenten unterschiedlicher Länge, die beim Verbinden das ursprüngliche Wort bilden ("tre" und "e" ergeben "Baum") und die nicht weiter innerhalb der Segmentierung segmentiert werden können (dh "ba" hat ein einzelnes Segmentierung, "ba"; und "alp" & "habet" ist keine gültige Segmentierung von "alphabet", da beide weiter segmentiert werden könnten (z. B. in "a" & "lp" & "habet", was jetzt ist eine gültige Segmentierung ("habet" kann nicht segmentiert werden, ohne ein Segment der Länge 2 oder 1 zu bilden))).
Die Punktzahl einer Segmentierung ist die Summe der Punktzahlen jedes einzelnen Zeichens, das im ursprünglichen Wort vorkommt (sobald Großbuchstaben ersetzt wurden).
Die Bewertung der Zeichen wird unten erläutert
Die Punktzahl eines Wortes ist die Punktzahl seiner bestmöglichen Segmentierung (die mit der niedrigsten Punktzahl).
Wenn für ein Wort keine gültigen Segmentierungen vorhanden sind (z. B. "Brass" ("bbrass"), die nicht segmentiert werden können, da sich das erste "b" und das letzte "s" in ihren eigenen Segmenten befinden müssten, würde dies resultieren in zwei Segmenten gleicher Länge), dann sollten Sie den Text "böse" ausgeben, andernfalls sollten Sie die Punktzahl des Wortes ausgeben.
Charakterwertung
Die Bewertung von Zeichen basiert auf der Häufigkeit, mit der das Zeichen angezeigt wird, und der Gewichtung der Segmente, in denen es angezeigt wird. Die Gewichtung der Segmente hängt von der Länge des Segments und dem niedrigsten gemeinsamen Vielfachen der Länge aller Segmente in ab die Segmentierung.
segment weighting = lowest common multiple of lengths segments / length of segment
Betrachten Sie das Wort "Olive", das als "ol" & "ive" segmentiert und als 2 Kästchen desselben Bereichs dargestellt werden kann, eines von "ol" mit Gewicht 3 und eines von "ive" mit Gewicht 2 (LCM) von 6).
ol
ol ive
ol ive
Dies soll die zwei Kästchen darstellen, eine aus 3 "ol" und eine aus 2 "ive". Alternativ könnte es "o" & "live" sein (LCM von 4)
o
o
o
o live
Die Punktzahl jedes Zeichens ist dann die Summe der Gewichte der Segmente, in denen es erscheint, multipliziert mit der Häufigkeit, mit der es nach dem Ersetzen von Großbuchstaben erscheint. Wenn es also zweimal erscheint, wird Ihnen für jedes Mal, wenn Sie es sagen müssen, das Doppelte berechnet ).
character score = character count * sum(segment weights in which character appears)
Bewertungsbeispiel
Wir nehmen das Wort "fallen", es kann nur in "fal" und "l" unterteilt werden. Das niedrigste gemeinsame Vielfache von 3 und 1 ist 3, also hat "fal" das Gewicht 1 und "l" das Gewicht 3.
l
l
fal l
Durch jeden Charakter gehen ...
"f" erscheint einmal und befindet sich im Segment "fal" mit Gewicht 1, hat also Punktzahl 1 * 1 = 1
"a" erscheint auch nur einmal, hat die Summe der Gewichte von 1, hat also die Punktzahl 1 * 1 = 1
"l" erscheint zweimal und erscheint in "fal" (Gewicht 1) und "l" (Gewicht 3), hat also Punktzahl 2 * (1 + 3) = 8
Die Summe davon ist 10 (die Punktzahl der Segmentierung und des Wortes, da dies die schönste Segmentierung ist). Hier ist dies im gleichen Format wie in den folgenden Beispielen:
fall = fal l
2*1 [fa] + 2*(1+3) [ll] = 10
Beispiel Scorings
Diese Beispiele für Wertungen können helfen oder auch nicht:
class -> clas s
3*1 [cla] + 2*(4+1) [ss] = 13
fish -> fis h
3*1 [fis] + 1*3 [h] = 6
eye -> e ye
1*1 [y] + 2*(1+2) [ee] = 7
treasure -> treas u re
3*2 [tas] + 2*2*(2+5) [rree] + 1*10 [u] = 44
Wolf -> w wolf
3*1 [olf] + 2*(1+4) = 13
book
evil
"Buch" ist ein böses Wort, hat also keine Punktzahl.
Beachten Sie, dass "Schatz" auf verschiedene Arten segmentiert werden kann. Die gezeigte Segmentierung profitiert jedoch davon, dass die längeren Buchstaben ("r" und "e") in den längeren Segmenten enthalten sind, sodass sie nicht so viel Gewicht haben. Die Segmentierung "t" & "re" & "asure" würde das gleiche Ergebnis liefern, während "Treas" & "ur" & "e" leiden würde, wobei "e" eine Punktzahl von 2 * (1 + 10 + 2) hat ) = 24 alleine. Diese Beobachtung ist wirklich der Geist der gesamten Übung. Ein Beispiel für eine falsche Bewertung von "Schatz" (falsch, weil sie nicht aus der Bewertung der schönsten Segmentierung (der mit der niedrigsten Bewertung) abgeleitet ist):
treasure = treas ur e
3*2 [tas] + 2*(2+5) [rr] + 1*5 [u] + 2*[2+10] = 49
Eingang
Eine einzelne Zeichenfolge, die in beiden Fällen nur lateinische Zeichen enthält ("Pferd", "Pferd" und "hOrSe" sind alle gültigen Eingaben), kann entweder von STDIN, Befehlszeilenargument, Funktionsargument oder auf andere Weise akzeptiert werden, wenn Ihre Sprache von Auswahl unterstützt keine der oben genannten.
Ausgabe
Sie müssen entweder die Punktzahl des Wortes ausgeben, bei der es sich um eine einzelne positive Ganzzahl größer als 0 handelt, oder "böse", wenn keine Segmentierung vorhanden ist. Die Ausgabe sollte an STDOUT oder das Rückgabeargument einer Funktion erfolgen, es sei denn, die Sprache Ihrer Wahl unterstützt keine dieser Funktionen. In diesem Fall sollten Sie etwas Sportliches tun.
Beispiele
Ich erwarte nicht, dass Sie all dieses Zeug drucken, alles was ich will ist die Punktzahl des Wortes oder die Ausgabe "böse" zum Beispiel (Eingabe gefolgt von Ausgabe)
eye
7
Eel
evil
a
1
Establishments
595
antidisestablishmentarianism
8557
Ich mache mir keine Sorgen um die Leistung. Wenn Sie auf einer vernünftigen (absichtlich vagen) Maschine in weniger als einer Minute fast jedes 15-Buchstaben-Wort (nach dem Ersetzen von Großbuchstaben) erzielen können, ist das gut genug für mich.
Dies ist Code-Golf, kann der kürzeste Code gewinnen.
Vielen Dank an Peter Taylor, Martin Büttner und SP3000 für ihre Hilfe bei dieser Herausforderung
quelle
Antworten:
Mathematica, 373 Bytes
Das ist ziemlich lang ... und auch ziemlich naiv. Es definiert eine unbenannte Funktion, die die Zeichenfolge verwendet und die Punktzahl zurückgibt. Die Bearbeitung dauert ungefähr 1 Sekunde
"Establishments"
, liegt also innerhalb des Zeitlimits. Ich habe eine etwas kürzere Version, die verwendetCombinatorica`SetPartitions
, aber es dauert bereits eine Minute für"Establishme"
.Hier ist eine Version mit Leerzeichen:
Ich könnte später eine detailliertere Erklärung hinzufügen. Dieser Code verwendet die zweite Lösung aus dieser Antwort , um alle Partitionen abzurufen, und diese Lösung , um sicherzustellen, dass sie alle maximal segmentiert sind.
quelle
Java 8,
15101485 BytesDas ist viel zu lang. Kombinatorik ist in Java nie einfach. Es kann definitiv einiges gekürzt werden. Rufen Sie an mit
a(string)
. Dies verwendet einen Exponentialspeicher- und Zeitalgorithmus; Erwarten Sie also nicht, dass es für lange Eingaben funktioniert. Die Verarbeitung dauert etwa eine halbe SekundeEstablishments
. Es stürzt mit einem Speicherfehler für abantidisestablishmentarianism
.Versuch es hier
Mit Erklärung eingerückt:
Dies missbraucht auch Generika ziemlich stark, um die Anzahl der Bytes zu reduzieren. Ich bin ziemlich überrascht, dass ich alles zum Kompilieren bringen konnte.
Danke Ypnypn :)
quelle
i.put...
Linie und der while-Schleife; Ich denkewhile(d!=0)
kann seinwhile(d>0)
; es gibt keine Notwendigkeit fürnew ArrayList
am Ende, daArrays.asList
esArrayList
sowieso gibt ; In der letzten Methode können Sieb
als Ebene definierenList
.Arrays.asList
gibt eine nicht veränderbare zurückArrayList
, daher kann ich das nicht verwenden, ohne eine zu bekommenOperationNotSupportedException
.b
kann eine einfache Liste sein, muss aberc
eine bleibenList<List<String>>
. Ich werde nachsehen, ob eswhile(d>0)
morgen funktioniert.C # 679 Bytes
Diese Lösung basiert grob auf der Struktur meiner ursprünglichen Testimplementierung und war anfangs nur ein Golf-Re-Write, aber dann habe ich alle Funktionen eingebunden, und jetzt ist es schrecklich. Es ist ziemlich schnell und löst Establishments in weniger als einer Sekunde. Es ist ein vollständiges Programm, das das Eingabewort als einen einzigen Parameter von ARGV verwendet.
Die
Main
Methode erstellt zunächst eine Kopie der Eingabe, wobei die Großbuchstaben ersetzt werden. Es ruft dannS
den "Löser" auf, der die Punktzahl einer gegebenen Segmentierung zurückgibt (die erste Segmentierung ist die mit einem einzelnen Segment, das das ganze Wort ist). Je nach Punktzahl wird dann entweder "böse" oder die Partitur gedruckt.Der "Solver" (
S
) erledigt alle interessanten Dinge und wurde ursprünglich in 4 Methoden unterteilt, die zusammengerollt wurden. Es funktioniert, indem zuerst die aktuelle Segmentierung bewertet wird und notiert wird, ob sie ungültig ist (und vor allem, ob sie so ungültig ist, dass wir nicht versuchen sollten, sie weiter zu segmentieren (für die Leistung), und den Rest der Berechnung überspringen, wenn dies der Fall ist). . Wenn es dann nicht übersprungen wurde, teilt es jedes Segment in der Segmentierung überall dort auf, wo es geteilt werden kann, und findet die beste Punktzahl von all diesen (rekursiv aufrufendS
). Schließlich wird entweder die beste Punktzahl der untergeordneten Segmentierungen zurückgegeben, andernfalls die eigene Punktzahl, oder sie ist ungültig, wenn die eigene Segmentierung ungültig ist.Code mit Kommentaren:
quelle