Palindromisierung der Saiten

30

Einführung

Für diejenigen, die es nicht wissen, ist ein Palindrom, wenn eine Zeichenfolge der Zeichenfolge in Rückwärtsrichtung entspricht (mit Ausnahme von Interpunction, Leerzeichen usw.). Ein Beispiel für ein Palindrom ist:

abcdcba

Wenn Sie dies umkehren, erhalten Sie:

abcdcba

Welches ist das gleiche. Deshalb nennen wir dies ein Palindrom. Sehen wir uns zum Palindromisieren ein Beispiel für eine Zeichenfolge an:

adbcb

Dies ist kein Palindrom. Um dies zu palindromisieren, müssen wir die umgekehrte Zeichenfolge mit der Anfangszeichenfolge rechts von der Anfangszeichenfolge zusammenführen , wobei beide Versionen intakt bleiben. Je kürzer, desto besser.

Das erste, was wir versuchen können, ist das Folgende:

adbcb
bcbda
^^ ^^

Da nicht alle Zeichen übereinstimmen, ist dies nicht die richtige Position für die umgekehrte Zeichenfolge. Wir gehen einen Schritt nach rechts:

adbcb
 bcbda
 ^^^^

Dies stimmt auch nicht mit allen Zeichen überein. Wir gehen noch einen Schritt nach rechts:

adbcb
  bcbda

Dieses Mal stimmen alle Zeichen überein . Wir können fusionieren beide String Verlassen des intakten . Das Endergebnis ist:

adbcbda

Dies ist die palindromisierte Zeichenfolge .


Die Aufgabe

Wenn eine Zeichenfolge (mit mindestens einem Zeichen) nur Kleinbuchstaben enthält (oder wenn dies besser passt, Großbuchstaben), geben Sie die palindromisierte Zeichenfolge aus .


Testfälle

Input     Output

abcb      abcba
hello     hellolleh
bonobo    bonobonob
radar     radar
hex       hexeh

Das ist , also gewinnt die Einsendung mit der geringsten Anzahl von Bytes!

Adnan
quelle
3
Verbunden.
Zgarb
6
Sie sollten angeben, dass die umgekehrte Zeichenfolge mit der umgekehrten Zeichenfolge rechts in der ursprünglichen Zeichenfolge zusammengeführt werden muss. Wenn es links gehen kann, obonobowäre das eine bessere Lösung für den Testfall.
Level River St
2
Related 2
Sp3000
2
@LevelRiverSt +1 nur weil "obonobo" so ein tolles Wort ist
Nathaniel
1
@ Nathaniel Danke aber bono b o nobist ein ganzer Satz. Was ist der Unterschied zwischen Gott und Bono? Gott irrt nicht durch Dublin und gibt vor, Bono zu sein ;-)
Level River St

Antworten:

5

Jelly, 11 bis 10 Bytes

ṫỤfU$Ḣœ^;U

Probieren Sie es online!

Wie es funktioniert

ṫỤfU$Ḣœ^;U  Main link. Argument: s (string)

 Ụ          Yield all indices of s, sorted by their corr. character values.
ṫ           Tail; for each index n, remove all characters before thr nth.
            This yields the list of suffixes of s, sorted by their first character,
            then (in descending order) by length.
    $       Combine the two links to the left into a chain:
   U        Upend; reverse all suffixes.
  f         Filter; only keep suffixes that are also reversed suffixes.
            This gives the list of all palindromic suffixes. Since all of them
            start with the same letter, they are sorted by length.
     Ḣ      Head; select the first, longest palindromic suffix.
      œ^    Multiset symmetric difference; chop the selected suffix from s.
         U  Upend; yield s, reversed.
        ;   Concatenate the results to the left and to the right.
Dennis
quelle
15

Pyth (Festschreiben von b93a874), 11 Bytes

.VkI_IJ+zbB

Testsuite

Dieser Code nutzt einen Fehler in der aktuellen Version von Pyth, Commit b93a874 . Der Fehler ist, dass _IJ+zbanalysiert wird, als wäre es q_J+zbJ+zb, was äquivalent zu ist _I+zb+zb, wenn es (nach der Entwurfsabsicht von Pyth) analysiert werden sollte q_J+zbJ, was äquivalent zu ist _I+zb. Auf diese Weise kann ich ein Byte speichern. Nachdem der Fehler behoben wurde, wird der richtige Code angezeigt .VkI_IJ+zbJB. Ich werde diesen Code stattdessen erklären.

Grundsätzlich überlagert der Code brute alle möglichen Zeichenfolgen, bis er die kürzeste Zeichenfolge findet, die zur Bildung eines Palindroms an die Eingabe angehängt werden kann, und gibt die kombinierte Zeichenfolge aus.

.VkI_IJ+zbJB
                z = input()
.Vk             For b in possible strings ordered by length,
       +zb      Add z and b,
      J         Store it in J,
    _I          Check if the result is a palindrome,
   I            If so,
          J     Print J (This line doesn't actually exist, gets added by the bug.
          B     Break.
isaacg
quelle
Wie kommst du auf einen solchen Code? Es ist kaum lesbar und für jemanden, der Pyth nicht kennt, absolut unverständlich. Was ist der Zweck einer solchen Sprache?
Anukul
5
@momo Der Zweck der Sprache besteht darin, zum Spaß einen kurzen Code einzugeben. Es ist eine Freizeitbeschäftigung. Ich kann es schreiben, weil ich viel Übung habe und weil ich die Sprache erfunden habe. Ich weiß, dass es für jemanden, der die Sprache nicht kennt, nicht verständlich ist. Deshalb habe ich die Erklärung beigefügt.
Isaacg
13

Python, 46 Bytes

f=lambda s:s*(s==s[::-1])or s[0]+f(s[1:])+s[0]

Wenn die Zeichenfolge ein Palindrom ist, geben Sie es zurück. Andernfalls setzen Sie den ersten Buchstaben für den Rest der Zeichenfolge um das rekursive Ergebnis.

Beispiel Aufschlüsselung:

f(bonobo)
b  f(onobo) b
b o f(nobo) o b 
b o n f(obo) n o b
b o n obo n o b
xnor
quelle
Ich denke, Sie können ein Byte speichern, wenn Sie die gegenteilige Bedingung ( s!=s[::-1]) verwenden
aditsu
@aditsu Das funktioniert, aber die Verwendung eines Multiplikators ist noch kürzer.
XNOR
9

Haskell, 36 Bytes

f s|s==reverse s=s|h:t<-s=h:f t++[h]

Besser lesbar:

f s
 |s==reverse s = s
 |(h:t)<-s     = h:(f t)++[h]

Wenn die Zeichenfolge ein Palindrom ist, geben Sie es zurück. Andernfalls setzen Sie den ersten Buchstaben um das rekursive Ergebnis für das Ende der Zeichenfolge.

Die Zeichenfolge sist h:tin der zweiten Schutzvorrichtung aufgeteilt, sodass in 1>0diesem Fall kein Füllelement erforderlich ist. Dies ist kürzer als s@(h:t)bei der Eingabe.

xnor
quelle
5

Pyth - 16 12 Bytes

4 Bytes gespart dank @FryAmTheEggman.

FGITW, viel Golfen möglich.

h_I#+R_Q+k._

Test Suite .

Maltysen
quelle
5

Brachylog , 16 6 5 Bytes (nicht konkurrierend)

:Ac.r

Probieren Sie es online!

Als ich meine erste Antwort veröffentlichte, befand sie sich noch in der alten Implementierung in Java. Da ich in Prolog alles neu programmiert habe, funktioniert es jetzt so, wie es eigentlich sein sollte.

Erläuterung

(?):Ac.        Output is the concatenation of Input with another unknown string A
      .r(.)    The reverse of the Output is the Output

Backpropagation bewirkt, dass der erste gültige Wert für Adiesen Wert der kürzeste ist, den Sie mit Input verknüpfen können, um ihn zu einem Palindrom zu machen.

Alternative Lösung, 5 Bytes

~@[.r

Dies entspricht in etwa der obigen Antwort, mit der Ausnahme, dass anstelle von "Ausgabe ist die Verkettung der Eingabe mit einer Zeichenfolge A" angegeben wird, dass "Ausgabe eine Zeichenfolge ist, für die die Eingabe ein Präfix der Ausgabe ist".

Tödlich
quelle
4

JavaScript (ES6), 92 Byte

(s,a=[...s],r=a.reverse().join``)=>s.slice(0,a.findIndex((_,i)=>r.startsWith(s.slice(i))))+r

Berechnet und schneidet die Überlappung zwischen der ursprünglichen Zeichenfolge und ihrer Umkehrung.

Neil
quelle
4

Retina, 29 25

$
¶$_
O^#r`.\G
(.+)¶\1
$1

Probieren Sie es online!

Vielen Dank an Martin für 11 Bytes gespart!

Dadurch wird lediglich eine umgekehrte Kopie der Zeichenfolge erstellt und zusammengeführt. Das einzig ausgefallene daran ist die Umkehrmethode:, O^#r`.\Gdie im Sortiermodus ausgeführt wird. Wir sortieren die Buchstaben der zweiten Zeichenfolge (die keine Zeilenumbrüche sind und dank der nacheinander am Ende der Zeichenfolge stehen \G) nach ihrem numerischen Wert, der, da es keine Zahlen gibt, 0 ist. Dann kehren wir den Wert um Reihenfolge der Ergebnisse dieser stabilen Sortierung mit der ^Option. Alle Kredite für die ausgefallene Verwendung von \Ggehören Martin :)

FryAmTheEggman
quelle
3

CJam, 18

q__,,{1$>_W%=}#<W%

Probieren Sie es online aus

Erläuterung:

q         read the input
__        make 2 copies
,,        convert the last one to a range [0 … length-1]
{…}#      find the first index that satisfies the condition:
  1$>     copy the input string and take the suffix from that position
  _W%=    duplicate, reverse and compare (palindrome check)
<         take the prefix before the found index
W%        reverse that prefix
          at the end, the stack contains the input string and that reversed prefix
aditsu
quelle
3

Lua, 89 88 Bytes

Ich habe das Javascript geschlagen! \ o / 1 Byte dank @LeakyNun ^^ gespeichert

Es ist ein vollständiges Programm, dessen Eingabe als Befehlszeilenargument dient.

i=1s=...r=s:reverse()while s:sub(i)~=r:sub(0,#r-i+1)do i=i+1 end print(s..r:sub(#r-i+2))

ungolfed

i=1                             -- initialise i at 1 as string are 1-indexed in lua
s=...                           -- use s as a shorthand for the first argument
r=s:reverse()                   -- reverse the string s and save it into r
while(s:sub(i)~=r:sub(0,#r-i+1))-- iterate while the last i characters of s
do                              -- aren't equals to the first i characters of r
  i=i+1                         -- increment the number of character to skip
end
print(s..r:sub(#r-i+2))         -- output the merged string
Katenkyo
quelle
Ich glaube, die Klammern in der Nähe whilekönnen entfernt werden?
Undichte Nonne
@LeakyNun sicher, dass sie ^^
Katenkyo
Kann nicht tun i=i+1end?
Erik der Outgolfer
1
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Leider kann ich nicht. Es würde versuchen, 1endals Hexadezimalzahl auszuwerten . Im Allgemeinen können Sie [abcdef]eine Zahl nicht direkt nach einer Zahl verwenden, ohne sie als Hexadezimalzahl zu betrachten. Es gibt noch eine Ausnahme 0x.
Katenkyo
3

Prolog, 43 Bytes

a(S):-append(S,_,U),reverse(U,U),writef(U).

Dies erwartet einen Code-String als Eingabe, zB bei SWI-Prolog 7: a(`hello`).

Erläuterung

Dies ist im Grunde eine Portierung meiner Brachylog-Antwort.

a(S) :-               % S is the input string as a list of codes
    append(S,_,U),    % U is a list of codes resulting in appending an unknown list to S
    reverse(U,U),     % The reverse of U is U
    writef(U).        % Write U to STDOUT as a list of codes
Tödlich
quelle
3

Oktave, 78 75 Bytes

3 Bytes gespart dank Eʀɪᴋ ʀɪᴋ Gᴛʜᴇ!

function p=L(s)d=0;while~all(diag(s==rot90(s),d++))p=[s fliplr(s(1:d))];end

ideone schlägt für benannte Funktionen immer noch fehl, aber hier ist ein Testlauf des Codes als Programm.

Becherglas
quelle
2

Perl, 37 Bytes

Basierend auf der Antwort von xnor.

Beinhaltet +2 für -lp

Mit Eingabe auf STDIN ausführen, z

palindromize.pl <<< bonobo

palindromize.pl:

#!/usr/bin/perl -lp
s/.//,do$0,$_=$&.$_.$&if$_!~reverse
Tonne Hospel
quelle
1

J, 20 Bytes

,[|.@{.~(-:|.)\.i.1:

Dies ist ein monadisches Verb. Probieren Sie es hier aus. Verwendung:

   f =: ,[|.@{.~(-:|.)\.i.1:
   f 'race'
'racecar'

Erläuterung

Ich verwende die Tatsache , dass die palindromization von S ist S + reverse (P) , wo P der kürzeste Präfix ist S , deren Entfernung resultiert in einem Palindrom. In J ist es etwas umständlich, nach dem ersten Element eines Arrays zu suchen, das ein Prädikat erfüllt. daher die Indizierung.

,[|.@{.~(-:|.)\.i.1:  Input is S.
        (    )\.      Map over suffixes of S:
         -:             Does it match
           |.           its reversal? This gives 1 for palindromic suffixes and 0 for others.
                i.1:  Take the first (0-based) index of 1 in that array.
 [   {.~              Take a prefix of S of that length: this is P.
  |.@                 Reverse of P.
,                     Concatenate it to S.
Zgarb
quelle
1

Haskell, 68 Bytes

import Data.List
f i=[i++r x|x<-inits i,i++r x==x++r i]!!0
r=reverse

Anwendungsbeispiel: f "abcb"->"abcba" .

Durchsuchen Sie initsdie Eingabe i(z. B. inits "abcb"-> ["", "a", "ab", "abc", "abcb"]), bis Sie eine finden, an die umgekehrt iein Palindrom angehängt ist .

nimi
quelle
Muss nicht r=reversevorher gehen f i=...?
Erik der Outgolfer
@EʀɪᴋᴛʜᴇGᴏʟғᴇʀ: Nein, du kannst jede Bestellung verwenden.
nimi
Ich habe es in 46 Bytes geschafft. Ich wette, es geht noch besser.
theonlygusti
@theonlygusti: Siehe Antwort von xnor .
nimi
1

MATL , 17 16 Bytes

Locker inspiriert von @ aditsus CJam-Antwort .

`xGt@q:)PhttP=A~

Probieren Sie es online!

Erläuterung

`        % Do...while loop
  x      %   Delete top of stack, which contains a not useful result from the
         %   iteration. Takes input implicitly on first iteration, and deletes it
  G      %   Push input
  t      %   Duplicate
  @q:    %   Generate range [1,...,n-1], where n is iteration index. On the  first
         %   iteration this is an empty array
  )      %   Use that as index into copy of input string: get its first n elements
  Ph     %   Flip and concatenate to input string
  t      %   Duplicate. This will be the final result, or will be deleted at the
         %   beginning of next iteration
  tP     %   Duplicate and flip
  =A~    %   Compare element-wise. Is there some element different? If so, the
         %   result is true. This is the loop condition, so go there will be a 
         %   new iteration. Else the loop is exited with the stack containing
         %   the contatenated string
         % End loop implicitly
         % Display stack contents implicitly
Luis Mendo
quelle
1

Ruby, 44 Bytes

Diese Antwort basiert auf den Python- und Haskell- Lösungen von xnor .

f=->s{s.reverse==s ?s:s[0]+f[s[1..-1]]+s[0]}
Sherlock9
quelle
Kann nicht tun ==s?s:?
Erik der Outgolfer
@EʀɪᴋᴛʜᴇGʀɪᴋᴛʜᴇ irb wirft einen Anfall, wenn ich es versuche. Muss etwas damit zu tun haben, wie es ?zwischen ?:ternär und der ?x == 'x'seit Ruby 1.9
Sherlock9
1

Oracle SQL 11.2, 195 Byte

SELECT MIN(p)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(p))FROM(SELECT:1||SUBSTR(REVERSE(:1),LEVEL+1)p FROM DUAL WHERE SUBSTR(:1,-LEVEL,LEVEL)=SUBSTR(REVERSE(:1),1,LEVEL)CONNECT BY LEVEL<=LENGTH(:1));

Nicht golfen

SELECT MIN(p)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(p))
FROM (
       SELECT :1||SUBSTR(REVERSE(:1),LEVEL+1)p 
       FROM   DUAL 
       WHERE  SUBSTR(:1,-LEVEL,LEVEL)=SUBSTR(REVERSE(:1),1,LEVEL)
       CONNECT BY LEVEL<=LENGTH(:1)
     );
Jeto
quelle
1

Im Ernst, 34 Bytes

╩╜lur`╜╨"Σ╜+;;R=*"£M`MΣ;░p╜;;R=I.

Das letzte Zeichen ist ein nicht unterbrechendes Leerzeichen (ASCII 127 oder 0x7F).

Probieren Sie es online!

Erläuterung:

╩╜lur`╜╨"Σ╜+;;R=*"£M`MΣ;░p╜;;R=I.<NBSP>
╩                                        push inputs to registers (call the value in register 0 "s" for this explanation)
 ╜lur                                    push range(0, len(s)+1)
     `              `M                   map (for i in a):
      ╜╨                                   push all i-length permutations of s
        "        "£M                       map (for k in perms):
         Σ╜+                                 push s+''.join(k) (call it p)
            ;;R=                             palindrome test
                *                            multiply (push p if palindrome else '')
                      Σ                  summation (flatten lists into list of strings)
                       ;░                filter truthy values
                         p               pop first element (guaranteed to be shortest, call it x)
                          ╜;;R=I         pop x, push s if s is palindromic else x
                                .<NBSP>  print and quit
Mego
quelle
1

202 Bytes

Ich habe es versucht.

class P{static void Main(string[]a){string s=Console.ReadLine(),o=new string(s.Reverse().ToArray()),w=s;for(int i=0;w!=new string(w.Reverse().ToArray());){w=s.Substring(0,i++)+o;}Console.WriteLine(w);}}

Ungolfed:

class P
{
    static void Main(string[] a)
    {
        string s = Console.ReadLine(), o = new string(s.Reverse().ToArray()), w = s;
        for(int i = 0; w!=new string(w.Reverse().ToArray());)
        {
            w = s.Substring(0, i++) + o;
        }
        Console.WriteLine(w);
        Console.ReadKey();
    }

}

Kann mir jemand eine Idee geben, wie ich die beiden Aufrufe von .Reverse (). ToArray () gruppieren kann? Eine separate Methode besteht aus mehr Bytes.

SkyPharaoh
quelle
0

QBIC , 41 Bytes

;_FA|C=A{a=a+1~C=_fC||_XC\C=A+right$(B,a)

Erläuterung:

;_FA|    Read A$ from the cmd line, then flip it to create B$
C=A      Set C$ to be A$
{        Start an infinite DO-loop
a=a+1    Increment a (not to be confused with A$...)
~C=_fC|  If C$ is equal to its own reversed version
|_XC     THEN end, printing C$
\C=A+    ELSE, C$ is reset to the base A$, with
right$(B the right part of its own reversal
,a)      for length a (remember, we increment this each iteration
         DO and IF implicitly closed at EOF
steenbergh
quelle
0

Haskell, 46 Bytes

f l|l==reverse l=l|(h:t)<-l=l!!0:(f$tail l)++[l!!0]

Ich frage mich, ob es eine Möglichkeit gibt, die Klammer in (f$tail l)++[l!!0]... zu entfernen.

theonlygusti
quelle