Wo soll ich meinen Spiegel hinstellen?

30

Dies ist ein Spiegel: |. Ich habe gerade herausgefunden, dass man einen Spiegel in die Mitte eines Strings stecken kann, wenn der String auf sich selbst gespiegelt werden kann! Zum Beispiel die Zeichenfolge abccba. Wenn Sie es in zwei Hälften schneiden, sind die beiden Hälften Spiegelbilder voneinander:

abc  <-->  cba

Wir können also einen Spiegel in die Mitte der Saite stecken, und unsere neue Saite ist abc|cba. Manchmal kann nur ein Teil der Zeichenfolge auf sich selbst gespiegelt werden. Zum Beispiel die Zeichenfolge "mirror". Die beiden Rs werden gespiegelt, der Rest der Zeichenfolge jedoch nicht. Das ist in Ordnung, wir entfernen nur die Teile der Zeichenfolge, die sich nicht spiegeln, und wir erhalten die folgende Zeichenfolge:

r|r

Einige Zeichenfolgen können an mehreren Stellen gespiegelt werden. Zum Beispiel "Hallo Welt, xyzzyx". Ich mag es, wenn viel Text in meinem Spiegel reflektiert wird. Deshalb müssen Sie den besten Ort finden, an dem Sie meinen Spiegel platzieren können. In diesem Fall sollten Sie den längeren gespiegelten String ausgeben und wie in unserem letzten Beispiel alles andere entfernen. Diese Zeichenfolge wird:

xyz|zyx

Einige Zeichenfolgen sehen so aus, als könnten sie gespiegelt werden, können dies jedoch nicht. Wenn eine Zeichenfolge nirgendwo gespiegelt werden kann, sollten Sie nichts ausgeben.

Die Herausforderung:

Suchen Sie bei einer Zeichenfolge, die nur printable-ascii enthält, den besten Platz für meinen Spiegel. Mit anderen Worten,

Suchen Sie den größten geraden palindromischen Teilstring und geben Sie ihn mit einem Pipe-Zeichen '|' aus. mittendrin.

Die Eingabe wird 1-50 Zeichen lang sein.

Sie können davon ausgehen, dass die Eingabe keine |Spiegelungen oder Zeilenumbrüche enthält. Darüber hinaus sind alle druckbaren ASCII-Charaktere Freiwild. Wenn die längste gespiegelte Teilzeichenfolge zwischen zwei Teilzeichenfolgen gebunden ist, können Sie auswählen, welche ausgegeben werden soll. Für die Zeichenfolge "abba ollo" müssen Sie beispielsweise "ab | ba" oder "ol | lo" ausgeben, aber es spielt keine Rolle, welche Sie ausgeben. Bei Strings wird zwischen Groß- und Kleinschreibung unterschieden, z. B. sollte "ABba" nicht "AB | ba" ausgeben, sondern den leeren String.

Beispiel IO:

"Hello World"     --> "l|l"
"Programming Puzzles and Code-Golf"     --> Either "m|m" or "z|z"
"abcba"           --> ""
"Hulluh"          --> "ul|lu"
"abcdefggfedcba"  --> "abcdefg|gfedcba"
"abcdefggfabc"    --> "fg|gf"
"AbbA"            --> "Ab|bA"
"This input is a lot like the last one, but with more characters that don't change the output. AbbA" --> "Ab|bA"

Wie üblich ist dies Codegolf, daher gelten Standardlücken, und die kürzeste Antwort in Bytes gewinnt!

DJMcMayhem
quelle
Gibt es eine Begrenzung für die Länge der Eingabe?
Mego
@Mego Solange Ihr Algorithmus theoretisch mit Eingaben arbeitet, ist es mir egal, wie lange es dauert / wie viel Speicher es benötigt.
DJMcMayhem
Ich habe gefragt, weil Vanilla-Regex-Engines nur Palindrome mit einer Länge bis zu einem bestimmten, endlichen Wert zuordnen können (im Gegensatz zu beliebig langen Palindromen), und die Möglichkeit einer Lösung auf Regex-Basis davon abhängen würde, ob es einen oberen Wert gibt oder nicht an die Länge der Eingabe gebunden.
Mego
@Mego Ah, das macht Sinn. Angenommen, die Eingabe kann bis zu 50 Zeichen lang sein. Wie klingt das?
DJMcMayhem

Antworten:

9

Pyth - 19 17 15 13 Bytes

Vielen Dank an @FryAmTheEggman, der mir zwei Bytes gespart hat.

ARRGH der Sonderfall für keine Antwort. Gelöst das!

e_I#jL\|cL2.:

Test Suite .

e                Last element in list, this works out to longest one
  _I             Invariance under reverse, this detect palindrome
   #             Filter
   jL            Map join
    \|           By "|"
    cL2          Map chop in two pieces
     .:Q)        Substrings. Implicit Q). ) makes it do all substrings.
Maltysen
quelle
2
Nooooo! Ninja'd auf die Pyth-Antwort; _;
Downgoat
Erklärung bitte? : 3
Downgoat
@Downgoat er nahm alle Teilstrings und zerhackte in zwei, verband jedes Paar mit |, filterte nach Symmetrie, fügte das zu [k] hinzu und erhielt das letzte Element (welches das längste ist)
busukxuan
@Downgoat erledigt.
Maltysen
2
:Q)= Bignose
Gcampbell
8

05AB1E , 19 17 14 Bytes

Code:

Œévy2ä'|ý©ÂQi®

Erläuterung:

Œ                # Get all substrings of the input
 é               # Sort by length (shortest first)
  vy             # For each element...
    2ä           # Split into two pieces
      '|ý        # Join by "|"
         ©       # Copy this into the register
          Â      # Bifurcate, pushing a and reversed a
           Q     # Check if it's a palindrome
            i®   # If so, push that string again
                 # Implicit, the top element is outputted

Verwendet die CP-1252- Codierung. Probieren Sie es online! .

Adnan
quelle
5

Python 2, 102 97 Bytes

def f(s):h=len(s)/2;r=s[:h]+'|'+s[h:];return s and max(r*(r==r[::-1]),f(s[1:]),f(s[:-1]),key=len)

Eher langsam und ineffizient ... Überprüfen Sie die kleineren Testfälle auf Ideone .

Dennis
quelle
4

JavaScript, 100 bis 99 Bytes

s=>eval('for(O=i=0;s[i++];O=O[j+j]?O:o)for(o="|",j=0;(S=s[i-1-j])&&S==s[i+j++];o=S+o+S);O[1]?O:""')

oder

s=>eval('for(O="",i=0;s[i++];O=O[j+j]||j<2?O:o)for(o="|",j=0;(S=s[i-1-j])&&S==s[i+j++];o=S+o+S);O')
jrich
quelle
Nur neugierig, wozu eval?
Gcampbell
@ gcampbell evalzu vermeidenreturn
edc65
Können Sie den Komma-Operator nicht verwenden, um eine Rückgabe zu vermeiden?
MayorMonty
@SpeedyNinja Nein. forist kein Ausdruck, daher sind normalerweise geschweifte Klammern erforderlich. areturn
jrich
3

Lua, 133 Bytes

s=...for i=#s,1,-1 do for j=1,#s-i do m=j+i/2-i%2/2t=s:sub(j,m).."|"..s:sub(m+1,i+j)if t==t.reverse(t)then print(t)return end end end

Überprüfen Sie alle Testfälle auf Ideone.com .

Undichte Nonne
quelle
1
Verwenden Sie t==t:reverse(), um ein Byte zu speichern :)
Katenkyo
2

Netzhaut , 66 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

M!&`(.)+(?<-1>\1)+(?(1)¶)
O$#`.+
$.&
A-2`
^(.)+?(?=(?<-1>.)+$)
$&|

Probieren Sie es online! (In der ersten Zeile können mehrere durch Zeilenvorschub getrennte Testfälle gleichzeitig getestet werden.)

Hmmm, viel länger als ich möchte ...

Martin Ender
quelle
2

JavaScript (ES6), 91

s=>[...s].map((d,i)=>{for(a='|',j=0;d=s[i-j],d&&d==s[i-~j];r=r[j+++j]?r:a)a=d+a+d},r='')&&r

Weniger golfen

f=s=>
  [...s].map(
    (d,i) => {
    for(a='|', j=0; d=s[i-j], d&&d==s[i-~j]; r = r[j++ +j]? r : a)
      a = d+a+d
    }, r=''
  ) && r

Prüfung

F=
s=>[...s].map((d,i)=>{for(a='|',j=0;d=s[i-j],d&&d==s[i-~j];r=r[j+++j]?r:a)a=d+a+d},r='')&&r

;[["Hello World", "l|l"]
,["Programming Puzzles and Code-Golf", "m|m"]
,["abcba", ""]
,["Hulluh", "ul|lu"]
,["abcdefggfedcba", "abcdefg|gfedcba"]
,["abcdefggfabc", "fg|gf"]
,["AbbA", "Ab|bA"]
,["This input is a lot like the last one, but with more characters that don't change the output. AbbA", "Ab|bA"]]
.forEach(t=>{
  var i=t[0],k=t[1],r=F(i)
  console.log(k==r?'OK ':'KO ',i+' -> '+r,k!=r?'(check '+k+')':'')
})  

edc65
quelle
2

Perl 5, 105 100 98 + 1 = 106 101 99 Bytes

/(?=((.)(?1)?\2)(?{[push@_,$1})(?!))/;($_)=sort{length$b<=>length$a}@_;substr($_,length>>1,0)='|'if$_

Ich wollte rekursiven Regexen nur einen Versuch geben. Benötigt die -pOption. Edit: Gespeichert (durchgestrichen 4) 7 Bytes dank @ msh210. (Das fehlende Byte ist auf eine Speicherung zurückzuführen, die durch die letzte Speicherung von @ msh210 ersetzt wurde.)

Neil
quelle
Ich habe nicht eine dieser getestet, aber wahrscheinlich kann dies verschiedene Weise abgekürzt werden, einschließlich: (1) @_=(@_,$1)sein kann push@_,$1. (2) Lassen Sie die Zeilenumbrüche und das Finale weg ;. (3) Ich vermute, es gibt eine kürzere Sortierbedingung, die Sie verwenden können (wenn nichts anderes als mindestens --- vielleicht --- Ersatz -für <=>)
msh210
@ msh210 Danke für die ersten beiden Punkte, aber ich habe es bereits versucht -und es hat nicht funktioniert (benötigt wahrscheinlich Parens für den Vorrang, der die Speicherung besiegt).
Neil
Versuchen Sie y...c>>1oder y...c/2statt length>>1. (Ungetestet)
msh210
@ msh210 Ich hätte natürlich zuerst die Tipps zum Golfen in Perl lesen sollen ...
Neil
Ich gehe davon aus, dass Ihre letzten Elternteile auch gehen können.
msh210
2

Python 2, 91 Bytes

f=lambda s,p='':s and max((''<p<=s<p+'\x7f')*(p[::-1]+'|'+p),f(s[1:]),f(s[1:],s[0]+p),key=len)

Ersetzen Sie \x7fmit dem tatsächlichen Zeichen DEL, das ASCII 127 ist (Gutschrift an Dennis).

Dies folgt einer ähnlichen Strategie wie Dennis 'Antwort : Verwenden maxund rekursives Verzweigen, um das längste Palindromintervall zu finden. Stattdessen findet es die linke Hälfte und prüft, ob die entsprechende gespiegelte rechte Hälfte mit einem selbst erstellten Startsymbol direkt danach kommt .

Die Funktion errät, ob sich das erste Zeichen in der gespiegelten linken Hälfte befindet. Wenn nicht, wird es einfach fallen gelassen und der Rest wird wiederholt. Wenn dies der Fall ist, wird es dem Stapel pumgekehrter Zeichen hinzugefügt . Wenn die Zeichenfolge jemals mit dem Stapel beginnt, wird die Spiegelzeichenfolge generiert und als ein möglichst langer Spiegel betrachtet. Um dies |als Ausgabe zu vermeiden , werden nur nicht leere Stapel berücksichtigt.

xnor
quelle
2

Gelee , 17 Bytes

ẆŒḂÐfṪœs2j”|µẋLḂ$

Probieren Sie es online!

Geschehen mit Hilfe von Mr. Xcoder und DJMcMayhem im Chat erledigt

Wie es funktioniert

ẆŒḂÐfṪœs2j”|µẋLḂ$ - Main link. Argument s  e.g.    ; 'AbbA'

Ẇ                 - All contiguous sublists
   Ðf             - Keep elements that are...
 ŒḂ               -  Palindromic                   ; [['A'], ['b'], ['b'], ['A'], ['bb'], ['AbbA']]
     Ṫ            - Final element                  ; 'AbbA'
      œs2         - Split into 2 chunks            ; ['Ab', 'bA']
         j”|      - Join with "|"                  ; 'Ab|bA'
            µ     - New link with ^ as argument
              LḂ$ - Is the length odd?             ; 1
             ẋ    - Repeat the string ^ many times ; 'Ab|bA'
Caird Coinheringaahing
quelle
1

Haskell, 126 111 Bytes

(!)=drop
f s|n<-length s=last$"":[a++'|':b|k<-[1..n],t<-map(!s)[1..n-k],let[a,b]=take k<$>[t,k!t],a==reverse b]
Lynn
quelle
1

TSQL 227 223 Bytes

Ich habe die Länge auf maximal 99 Bytes fest codiert, dies sparte Bytes, machte es aber langsamer. Es hat immer noch eine anständige Leistung.

Golf gespielt:

DECLARE @t varchar(99)='AbccbA'

,@z char(99)='',@a INT=0,@ INT=0WHILE @a<LEN(@t)SELECT
@z=IIF(LEN(x)>LEN(@z)/2and @t LIKE'%'+x+REVERSE(x)+'%'COLLATE
Thai_bin,x+'|'+REVERSE(x),@z),@=IIF(@=50,1,@+1),@a+=IIF(@=1,1,0)FROM(SELECT
SUBSTRING(@t,@a,@)x)x PRINT @z

Ungolfed:

DECLARE @t varchar(99)='AbccbA'

,@z char(99)='',
@a INT=0,
@ INT=0
WHILE @a<LEN(@t)
  SELECT
    @z=IIF(LEN(x)>LEN(@z)/2and @t LIKE'%'+x+REVERSE(x)+'%'COLLATE Thai_bin,x+'|'
       +REVERSE(x),@z),
    @=IIF(@=99,1,@+1),
    @a+=IIF(@=1,1,0)
  FROM
    (SELECT SUBSTRING(@t,@a,@)x)x

PRINT @z

Geige

t-clausen.dk
quelle
1
Sie können 2 Byte abschneiden, wenn Sie auf 99 begrenzen, da das letzte Beispiel nur 99 Zeichen lang ist
Alex Carlsen
1
@VisualBean Dankeschön, das Skript wurde so geändert, dass nur 99 Zeichen zulässig sind. Außerdem wurde die Sortierung von Thai_CS_AS in thai_bin
t-clausen.dk geändert.
0

Python 2, 149 Bytes

R,L,s=range,len,input()
t=max([s[i:j/2+i/2]for i in R(L(s))for j in R(L(s)+1)if s[i:j]==s[i:j][::-1]and(j-i)%2<1],key=L)
print t+'|'*(L(t)>0)+t[::-1]

Probieren Sie es online aus

Dieses Programm findet die erste Hälfte des größten palindromischen Teilstrings mit gerader Länge und gibt diesen String aus, gefolgt von einem |, gefolgt von diesem String in umgekehrter Reihenfolge. Wenn es keine geeignete Zeichenfolge gibt, twird die leere Zeichenfolge verwendet und als leere Zeichenfolge '|'*(L(t)>0)ausgewertet.

Mego
quelle
0

Java 8, 294 283 232 Bytes

s->{int l=s.length(),i=0,j,z,y=0;String a,b="";for(;i<l;i++)for(j=0;j<=l-i;)if((a=s.substring(i,i+j++)).equals(new StringBuffer(a).reverse()+"")&(z=a.length())%2<1&z>y){y=z;b=a;}return y>0?b.substring(0,y/=2)+"|"+b.substring(y):"";}

Erläuterung:

Probieren Sie es hier aus.

s->{                               // Method with String as both parameter and return-type
  int l=s.length(),                //  Length of the input-String
      i=0,j,                       //  Index-integers
      z,y=0;                       //  Temp-integers
  String a,b="";                   //  Temp-Strings
  for(;i<l;i++)                    //  Loop (1) from 0 to `l` (exclusive)
    for(j=0;j<=l-i;                //   Inner loop (2) from 0 to `l-i` (inclusive)
      if((a=s.substring(i,i+j++))  //    Set the current substring to `a`
          .equals(new StringBuffer(a).reverse()+"")
                                   //    If `a` is a palindrome
         &(z=a.length())%2<1       //    And the length of `a` is even
         &z>y){                    //    And the length of `a` is larger than `y`
        y=z;                       //     Change `y` to `z`
        b=a;}                      //     Change `b` to `a`
                                   //   End of inner loop (2) (implicit / single-line body)
                                   //  End of loop (1) (implicit / single-line body)
  return y>0?                      //  If the result-length is not 0:
    b.substring(0,y/=2)+"|"+b.substring(y)
                                   //   Return the result
   :                               //  Else:
    "";                            //   Return an empty String
}                                  // End of method
Kevin Cruijssen
quelle