Palindromischer Zweiwege-Verschlussgenerator

24

Einführung

Ein palindromischer Abschluss einer Eingabezeichenfolge ist das kürzeste Palindrom, das aus der Eingabezeichenfolge konstruiert werden kann, wobei das letzte Palindrom mit der Eingabezeichenfolge beginnt.

Für diese Herausforderung werden wir einen Zwei-Wege-Palindromverschluss in Betracht ziehen, so dass

  • Palindrom links Das Schließen einer Eingabezeichenfolge ist das kürzestmögliche Palindrom, das mit der Eingabezeichenfolge beginnt.
  • Right Palindromic Closure einer Eingabezeichenfolge ist das kürzeste mögliche Palindrom, das mit der Eingabezeichenfolge endet.
  • Der bidirektionale palindromische Abschluss einer Eingabezeichenfolge ist der kürzere Wert für den linken oder rechten palindromischen Abschluss der Eingabezeichenfolge.

Aufgabe

Ihre Aufgabe ist einfach. Geben Sie bei einer Zeichenfolge (die nur aus druckbarem ASCII, neuen Zeilen und Leerzeichen besteht) den bidirektionalen palindromischen Abschluss dieser Zeichenfolge aus. Bei Gleichstand ist entweder der linke oder der rechte palindromische Verschluss ein gültiger Ausgang.

Sie können ein Programm oder eine Funktion schreiben, Eingaben über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis entweder an STDOUT (oder die nächstgelegene Alternative) ausgeben oder als Zeichenfolge zurückgeben.

Sie können davon ausgehen, dass die Eingabe niemals eine leere Zeichenfolge sein wird.

Einige Beispiele:

<Input>   -> <Output>
"abcdef"  -> "abcdefedcba"  (or "fedcbabcdef")
"abcba"   -> "abcba"
"abcb"    -> "abcba"
"cbca"    -> "acbca"

Der erste Preis für die Idee geht an VisualMelon, die endgültige Idee mit Hilfe von Martin und Zgarb

Die Begriffe palindromischer Verschluss, links-pallindromischer Verschluss und rechts-palindromischer Verschluss wurden in dieser Arbeit zuerst verwendet und definiert .

Optimierer
quelle
1
Ich würde gerne eine palindromische Lösung sehen ...
17.
2
@ojdo Ich habe darüber nachgedacht, dies als Bonus hinzuzufügen, aber ich bin mir ziemlich sicher, dass die meisten Antworten nur Kommentare verwendet hätten, um das Palindrom zu erstellen. Wenn eine Antwort auch wirklich ein Palindrom sein kann, ohne auf Kommentare angewiesen zu sein, würde ich ein Kopfgeld für diese Antwort hinterlassen!
Optimierer

Antworten:

11

Pyth, 22 19

hfq_TTsm,+z_d+_dzyz

Probieren Sie es online aus .

Erläuterung

Der Zwei-Wege - palindromische Verschluss entweder die Form AXoder XA, wo Xdie Eingabezeichenfolge ist , und Aist eine Teilzeichenfolge X. Ich muss eigentlich eine zusammenhängende Teilzeichenfolge sein X, ein Präfix für die eine Form, ein Suffix für die andere Form. Aber diese Mängel interessieren mich nicht. Ein Teilstring (zusammenhängend oder nicht) ist alles, was ich in Pyth brauche.

                        Implicit: z = raw_input() // Read a string
                 yz     A list with all substrings (contiguous or not) of z
       m                For each of these substrings d, build
        ,                  a pair of two strings:
         +z_d              ( z + inveres(d) ,
             +_dz            inverse(d) + z )
      s                 Sum (put all created pairs into a list)
 fq_TT                  filter elements T, where inverse(T) == T (Palindrom)
h                          Take the first element

Bearbeiten

In der alten Version wurden die Zeichenfolgen nach der Länge sortiert .olN.... Soeben wurde erkannt, dass ydie Teilzeichenfolgen nach Länge sortiert zurückgegeben werden. Diese Palindrome sind also bereits sortiert.

Jakube
quelle
6

Clip , 40

(sl`f[a=ava}+m[i+v+ixx}Rlxm[i+xvu0ix}Rlx

Beispiel

Documents>java -jar Clip4.jar palindrome.clip
abcb
abcba

Erläuterung

(sl`                                        .- The shortest                     -.
    f[a=ava}                                .- palindrome                       -.
            +                               .- among the following two sets:    -.
             m[i      }Rlx                  .- For each number up to length(x)  -.
                +                           .- combine                          -.
                 v+ix                       .- the last i chars of x, reversed  -.
                     x                      .- and x.                           -.
                          m[i       }Rlx    .- For each number up to length(x)  -.
                             +              .- combine                          -.
                              x             .- x and                            -.
                               vu0ix        .- the first i chars of x, reversed.-.
Ypnypn
quelle
6

CJam, 30 Bytes

Ich hatte wirklich gehofft, jetzt eine Antwort von CJam zu sehen

q:Q,{)QW%/(Q+Q@+s}%{,}${_W%=}=

Ich hasse diesen {,}$Block wirklich , aber ich bekomme eine ungeordnete Liste möglicher Palindrome aufgrund des von mir verwendeten Generierungsalgorithmus.

Code Erklärung

q:Q,{            }%             "Read the input string, store in Q, take length and";
                                "run the code block that many times";
     )QW%                       "Increment the iteration index and Put reversed Q on stack";
         /                      "Split reversed Q into parts of incremented iteration index";
          (Q+                   "Take out the first part and prepend it to Q";
             Q@+s               "Take the rest of the parts and append them to Q";
                   {,}$         "At this point, we have all possible prepended and appended";
                                "sequences of the input string. Sort them by length";
                       {_W%=}=  "Take the first sequence which is a palindrome";

Probieren Sie es hier online aus

Optimierer
quelle
6
Ich hasse diesen {,}$Block dort auch wirklich ! Nur ein Scherz, ich habe keine Ahnung, was irgendetwas in CJam macht.
Alex A.
4

Python 2, 115 113 109 105 96 Bytes

f=lambda x:[x for x in sum([[x[:~i:-1]+x,x+x[i::-1]]for i in range(len(x))],[])if x==x[::-1]][0]

Kann hoffentlich weiter Golf spielen. Möglicherweise bemerkenswerte Teile:

  • Verwenden von sum für zwei Listenverständnisse in einem
  • Begriffe in sortierter Reihenfolge konstruieren, um die Notwendigkeit von min zu vermeiden (vorgeschlagen von @Jakube)
Uri Granta
quelle
1
Die Elemente sind nicht ganz in sortierter Reihenfolge, daher schlägt dies für Zeichenfolgen wie fehl a.
Sp3000,
4

Mathematica, 96 Bytes

Es muss einen eleganteren Weg geben als diesen ...

""<>#&@@SortBy[r=Reverse;#/.{b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}&/@{r@#,#}&@Characters@#,Length]&

Dies definiert eine unbenannte Funktion, die eine Zeichenfolge akzeptiert und das Ergebnis zurückgibt.

Die Grundidee ist zu

  • Teilen Sie die Zeichenfolge in Characters.
  • Bilden Sie mit dieser Liste und ihrer Rückseite ein Array.
  • Verwenden Sie die Mustererkennung, um die richtige Palindromie für jeden von ihnen zu finden:

    {b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}
    

    Beachten Sie, dass dies keine flache Liste zurückgibt. Zum Beispiel, weil {a,b,c}du bekommen würdest

    {a,b,{c,b,a}}
    
  • Sortieren Sie die beiden Ergebnisse nach Länge.

  • Wählen Sie den kürzeren und fügen Sie ihn mit wieder zu einer Schnur zusammen ""<>#&@@.
Martin Ender
quelle
Es gibt aus, abacabawenn der Eingang ist abac. Die richtige Antwort lautet cabac. Ich denke, Sie sollten sie abflachen, bevor Sie nach Länge sortieren.
Alephalpha
1
@alephalpha Es wurde eine bessere Lösung gefunden, bei der die Codegröße nicht geändert werden musste (und die eigentlich meine Absicht war, sie nicht zu sortieren).
Martin Ender
2

Brachylog (2), 6 Bytes, Sprachnachstellung

~{↔?a}

Probieren Sie es online!

Wie bei Brachylog üblich, ist dies eine Funktion, kein vollständiges Programm.

Erläuterung

~{↔?a}
~{   }   Find a value that produces {the input} upon doing the following:
  ↔        reversing it;
   ?       asserting that we still have the same value;
    a      and taking either a prefix, or a suffix.

Soweit ich weiß (es ist nicht meine Sprache, aber es scheint unwahrscheinlich), awurde Brachylog für diese Herausforderung nicht hinzugefügt, aber es ist hier sehr praktisch. Wir verwenden die Methode "Umgekehrt und behaupten, sie hat sich nicht geändert", um zu behaupten, dass der gefundene Wert ein Palindrom ist.

Was den Grund für die Entstehung des kürzesten Palindroms betrifft, so wird die Auswertungsreihenfolge von Prolog (und damit auch von Brachylog) stark von der ersten ausgewerteten Sache beeinflusst. In diesem Fall handelt es sich um einen "umgekehrten" Befehl, der (wie die meisten Listenoperationen) eine Auswertungsreihenfolge festlegt, um die Größe der resultierenden Liste zu minimieren. Da dies der Größe der Ausgabe entspricht, minimiert das Programm zufällig genau das Richtige, sodass ich keine expliziten Hinweise hinzufügen musste.


quelle
a- Für diese Herausforderung wurde kein Adfix hinzugefügt. Ich hatte kein verfügbares Symbol mit guten Mnemoniken für Präfix und Suffix, daher habe ich beide in adfix zusammengeführt, das nur bei Bedarf Indizes zum Auswählen von Präfixen oder Suffixen verwenden kann.
Fatalize
1

Rubin, 76 + 2 = 78

Mit Befehlszeilen-Flags -pl(die lmöglicherweise nicht benötigt werden, je nachdem, wie Sie Eingaben vornehmen), führen Sie aus

$_=[[$_,r=$_.reverse]*"\0",r+"\0#$_"].min_by{|s|s.sub!(/(.*)\0\1/){$1}.size}

Wenn eine Zeichenfolge 'abaa' angegeben wird, werden die Zeichenfolgen 'cbca 0 acbc' und 'acbc 0 cbca' generiert, wobei 0 das nicht druckbare Zeichen mit ASCII-Code 0 ist. Anschließend wird eine Kopie der am längsten wiederholten Zeichenfolge gelöscht, die 0 in jeder Zeichenfolge enthält. 'a' in der ersten und 'cbc' in der zweiten, um die beiden Abschlüsse zu bekommen. Es wird dann das kürzeste Ergebnis ausgegeben.

Das einzig wirklich seltsame an dem Code ist, dass er die Strings beim Sortieren verkürzt, was wir vermeiden können, weil min_byder Block nur einmal pro verglichenem Element ausgeführt wird (sowohl weil es sich um eine Schwartzsche Transformation handelt, als auch weil es nur zwei gibt) zu vergleichende Elemente).

Histokrat
quelle
1

Python 3, 107 Bytes


f=lambda a:[i for i in[a[:i:-1]*j+a+a[-1-i::-1]*(1-j)for i in range(len(a))for j in(0,1)]if i==i[::-1]][-1]

Zu testen:

>>> print("\n".join(map(f, ["abcdef", "abcba", "abcb", "cbca"])))
abcdefedcba
abcba
abcba
acbca
Matsjoyce
quelle
1

Haskell, 107 Bytes

import Data.List
r=reverse
f s=snd$minimum[(length x,x)|x<-map(s++)(tails$r s)++map(++s)(inits$r s),x==r x]

Prüfung:

*Main> mapM_ (putStrLn.f) ["abcdef", "abcba", "abcb", "cbca"]
abcdefedcba
abcba
abcba
acbca
nimi
quelle
1

J, 66 62 Bytes

3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

Recht einfach. Die zwei Tricks, die ich benutze:

Der rechte palindromische Verschluss ist der linke palindromische Verschluss der umgekehrten Saite.

Ermitteln der Länge des Strings mit minimaler Länge und Palindromität mit dem Ausdruck min (is_palindrome / length).

   f=.3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

   f 'lama'
lamal

Probieren Sie es hier online aus.

randomra
quelle