Ihre Aufgabe ist es, zu bestimmen, wie viel von einem perfekten Palindrom eine Zeichenfolge ist. Ihr typisches Palindrom (zB 12321) ist ein perfektes Palindrom; seine Vollkommenheit ist 1.
Um die Perfektion einer Zeichenfolge zu bestimmen, sehen Sie, in wie viele Abschnitte Sie sie aufteilen können, wobei jeder Abschnitt ein Palindrom ist. Wenn es Unklarheiten gibt, wie z. B. mit aaaa
, wie Sie es in [aa, aa]
oder [aaaa]
oder [a, aaa]
oder aufteilen können [aaa, a]
, hat die kürzeste Menge Vorrang und ergibt aaaa
eine Punktzahl von 1, was der Länge der kürzesten Menge entspricht.
Aus diesem Grund müssen Sie ein Programm oder eine Funktion schreiben, die eine nicht leere Eingabe verwendet und ausgibt, wie perfekt sie ist (dies ist die Länge der kürzesten Menge, in die Sie sie aufteilen können, wobei jedes Element in der Menge ein Palindrom ist).
Beispiele:
1111 -> 1 [1111]
abcb -> 2 [a, bcb]
abcbd -> 3 [a, bcb, d]
abcde -> 5 [a, b, c, d, e]
66a -> 2 [66, a]
abcba-> 1 [abcba]
x -> 1 [x]
ababacab -> 2 [aba, bacab]
bacababa -> 2 [bacab, aba]
26600 -> 3 [2, 66, 00] [my user id] [who has a more perfect user id?]
ababacabBACABABA -> 4 [aba, bacab, BACAB, ABA]
Beachten Sie, dass in den Beispielen alles in eckigen Klammern nicht Teil der Ausgabe sein sollte.
ababacab
und sein Gegenteilbacababa
scheinen gute Testfälle zu sein.ababacabBACABABA
ist auch ein guter Testfall (einige Antworten scheitern daran).Antworten:
Brachylog , 7 Bytes
Probieren Sie es online!
Erläuterung
quelle
Jelly ,
131211 BytesProbieren Sie es online!
Technische Daten
"ababacab"
(als Argument)2
quelle
"\"
, da dies eine ungültige Syntax ist.ababacab
und sein Gegenteilbacababa
.Pyth, 9 Bytes
Testsuite
Dies bildet alle Partitionen der Eingabe, von der kürzesten bis zur längsten. Dann filtert es diese Partitionen nach Invarianz unter Filtern der Elemente nach Invarianz unter Umkehrung. Schließlich nehmen wir das erste Element der gefilterten Partitionsliste und geben dessen Länge zurück.
Um diesen komplizierten Schritt zu erklären, lassen Sie sich mit Invarianz unter Umkehrung beginnen:
_I
. Dadurch wird überprüft, ob es sich bei der Eingabe um ein Palindrom handelt, da überprüft wird, ob durch Umkehren der Wert geändert wird.Als nächstes Filterung für palindromicity:
_I#
. Dadurch bleiben nur die palindromischen Elemente der Liste erhalten.Als nächstes überprüfen wir für Invarianz Filterung für palindromicity:
_I#I
. Dies ist nur dann wahr, wenn alle Elemente der Liste Palindrome sind.Schließlich haben wir für Listen filtern , wo alle Elemente der Liste sind Palindrome:
_I#I#
.quelle
Haskell , 83 Bytes
Probieren Sie es online!
Hierbei wird Zgarbs großartiger Tipp zum Generieren von Zeichenfolgenpartitionen verwendet .
quelle
Clojure, 111 Bytes
Teilt an allen möglichen Positionen, und wenn der erste Teil ein Palindrom ist, sucht er nach einer Unterteilung für den verbleibenden Teil der Zeichenfolge.
Probieren Sie es online aus .
Ungolfed, verwendet Thread-Last-Makro
->>
.Eine obskure Version, bitte schreibe keinen Code wie diesen: D
quelle
f
innerhalb des for: aufrufen(f b)
. Auf einer Tail-Call-Position können Sie verwendenrecur
.defn
mitfn
und nur eine Funktion haben.(fn f[s]( ... ))
? Oh, das ist wahr. Sie sparen damit 2 Zeichen.JavaScript (ES6),
143126124 Byte2 Bytes gespart dank Neil
Inspiriert von der NikoNyrh- Methode.
Formatiert und kommentiert
Testfälle
Code-Snippet anzeigen
Anfängliche Ansatz
173168 BytesEine ziemlich lange rekursive Funktion, die alle möglichen Partitionen der Eingabezeichenfolge berechnet.
Formatiert und kommentiert
Testfälle
Code-Snippet anzeigen
quelle
,p=0
,s[p++]?
und,F(s,i,p)
.Gelee , 10 Bytes
Probieren Sie es online!
Wie?
Verwendet die Tatsache, dass
[0]<[0,0]<[0,0,0],...,<[0,...,0,1]<...
- wenn wir also die Partitionen nach einem Schlüssel sortieren "ist nicht für jeden Teil palindromisch", der erste Eintrag alle palindromisch und von minimaler Länge ist.
Hinweis: Eine nicht leere Zeichenfolge der Länge n führt immer zu einem solchen Schlüssel mit n Nullen, da alle Zeichenfolgen der Länge 1 palindrom sind.
quelle
Haskell , 69 Bytes
Definiert eine Funktion
f
. Probieren Sie es online!Erläuterung
Die Infix-Hilfsfunktion
x ! y
berechnet eine Liste von Ganzzahlen, die die Länge einiger Aufteilungenreverse x ++ y
in Palindrome sind, bei denenreverse x
sie intakt bleiben. Es ist garantiert, dass die Länge der minimalen Aufteilung enthalten ist, wenn siey
nicht leer ist. Wie es funktioniert ist dies.y
es nicht leer ist, wird ein Zeichen entfernt und hineingeschobenx
. Wennx
ein Palindrom wird, rufen wir die Hauptfunktionf
am Ende von aufy
und addieren 1, um dies zu berücksichtigenx
. Auch wir fordern!
das Neue aufx
undy
verpassen keine mögliche Spaltung.y
leer ist, geben wir zurück[0]
(eine Aufteilung der Länge 0), wennx
ebenfalls leer ist, und[]
(keine Aufteilungen), wenn nicht.Die Hauptfunktion
f
ruft nur auf"" ! x
und nimmt das Minimum der Ergebnisse.quelle
JavaScript (Firefox 30-57), 97 Byte
ES6-Port:
Es scheint eine so einfache Lösung zu sein, dass ich immer wieder denke, ich habe etwas vergessen, aber es besteht zumindest alle Testfälle.
quelle
Haskell,
139116109 BytesImmer noch grün bei Haskell Golf, aber hier ist mein bester Versuch, den ich schnell finden kann.
(and.map r)
, um Teillisten zu entfernen, die kein Palindrom enthalten. Ab diesem Zeitpunkt wird die Liste mit der folgenden Länge versehen: sortiert, damit wir den Kopf greifen können, der die Antwort ist.Ich dachte, eine bessere Antwort könnte den nicht deterministischen Charakter von Listen in Haskell durch die Verwendung von Anwendern nutzen. Es ist möglicherweise möglich, mithilfe von Anwendern viele Bytes der Funktion h zu entfernen, selbst wenn Control.Applicative importiert werden muss. Verbesserungsvorschläge sind willkommen.
UPDATE1
Riesige Einsparungen aufgrund der Erinnerung von Laikoni an die Mindestfunktion. Durch das Entfernen der Sortierung konnte ich den Data.List-Import tatsächlich löschen, da das Minimum in Prelude!
UPDATE2
Dank Nimis Vorschlag, Listenverständnisse als nützlichen Ersatz für filter.map zu verwenden. Das hat mir ein paar Bytes erspart. Außerdem habe ich mir von Laikonis answer den netten String-Partitionstrick ausgeliehen und dort auch ein paar Bytes gespart.
quelle
h []=[[]]
undh (x:y)=map ([x]:)
unnötigen Leerraum enthalten.head.sort
istminimum
.filter
&map
:g x=head$sort[length y|y<-h x,and$r<$>y]
.PHP, 319 Bytes
Online Version
Erweitert
Längere Version ohne E_NOTICE und Ausgabe des resultierenden Arrays
quelle
ababacabBACABABA