Gdzie mam umieścić lustro?

30

To jest lustro: |. Właśnie dowiedziałem się, że możesz przykleić lustro na środku sznurka, jeśli sznur może być dublowany! Na przykład ciąg abccba. Jeśli przecinasz go na pół, dwie połówki to wzajemne odbicie lustrzane:

abc  <-->  cba

Możemy więc przykleić lustro na środku sznurka, a naszym nowym sznurkiem jest abc|cba. Czasami tylko część ciągu może być dublowana na sobie. Na przykład ciąg „mirror”. Dwa r są dublowane, ale reszta ciągu nie jest. Zgadza się, po prostu usuniemy części ciągu, które się nie odbijają, i otrzymamy następujący ciąg:

r|r

Niektóre ciągi mogą być dublowane w wielu miejscach. Na przykład „Hello World, xyzzyx”. Lubię mieć dużo tekstu odbijanego w moim lustrze, więc musisz znaleźć najlepsze miejsce na umieszczenie mojego lustra. W takim przypadku powinieneś wypisać dłuższy dublowany ciąg i, podobnie jak w naszym ostatnim przykładzie, usunąć wszystko inne. Ten ciąg staje się:

xyz|zyx

Niektóre ciągi wyglądają tak, jakby mogły być dublowane, ale w rzeczywistości nie mogą. Jeśli ciąg nie może być nigdzie dublowany, nie powinieneś nic wyświetlać.

Wyzwanie:

Biorąc pod uwagę ciąg zawierający tylko ascii do wydrukowania, znajdź najlepsze miejsce na umieszczenie mojego lustra. Innymi słowy,

Znajdź największy podciąg palindromowy o równej długości, a następnie wyślij go za pomocą znaku potoku „|” w środku tego.

Dane wejściowe będą miały długość 1-50 znaków.

Możesz założyć, że dane wejściowe nie będą zawierać kopii lustrzanych |ani nowych linii. Poza tym wszystkie postacie ascii do wydrukowania są uczciwą grą. Jeśli najdłuższy dublowany podciąg jest powiązany między dwoma podciągami, możesz wybrać, który ma zostać wydrukowany. Na przykład dla ciągu „abba ollo” musisz wypisać „ab | ba” lub „ol | lo”, ale nie ma znaczenia, który z nich wypisujesz. W łańcuchach rozróżniana jest wielkość liter, np. „ABba” nie powinna wypisywać „AB | ba”, powinna wypisywać pusty ciąg.

Próbka 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"

Jak zwykle jest to gra w golfa, więc obowiązują standardowe luki i wygrywa najkrótsza odpowiedź w bajtach!

DJMcMayhem
źródło
Czy istnieje ograniczenie długości wejścia?
Mego
@Mego Dopóki twój algorytm teoretycznie działa na dowolnym wejściu, nie obchodzi mnie, ile to zajmie / ile zajmie pamięci.
DJMcMayhem
Zapytałem, ponieważ silniki regex waniliowe są w stanie dopasować palindromy o długości do określonej, skończonej wartości (w przeciwieństwie do arbitralnie długich palindromów), a możliwość rozwiązania opartego na regexie zależałaby od tego, czy istnieje górna związany z długością wejścia.
Mego
@Mego Ach, to ma sens. Powiedzmy, że dane wejściowe mogą mieć do 50 znaków. Jak to brzmi?
DJMcMayhem

Odpowiedzi:

9

Pyth - 19 17 15 13 bajtów

Dzięki @FryAmTheEggman za uratowanie mi dwóch bajtów.

ARRGH specjalny przypadek braku odpowiedzi. Rozwiązałem to!

e_I#jL\|cL2.:

Pakiet testowy .

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
źródło
2
Nie! Ninja'd na pytanie pyth; _;
Downgoat
Wyjaśnienie proszę? : 3
Downgoat
@Downgoat wziął wszystkie podciągi i pokroił na dwie części, połączył każdą parę z |, filtrował według symetrii, dołączał do [k] i otrzymywał ostatni element (który jest najdłuższy)
busukxuan
@Downgoat gotowe.
Maltysen
2
:Q)= Bignose
gcampbell
8

05AB1E , 19 17 14 bajtów

Kod:

Œévy2ä'|ý©ÂQi®

Wyjaśnienie:

Œ                # 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

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Adnan
źródło
5

Python 2, 102 97 bajtów

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)

Raczej powolny i nieefektywny ... Sprawdź mniejsze przypadki testowe w Ideone .

Dennis
źródło
4

JavaScript, 100 99 bajtów

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:""')

lub

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
źródło
Ciekawe, po co eval?
gcampbell
@gcampbell, evalaby uniknąćreturn
edc65
Nie możesz użyć operatora przecinka, aby uniknąć zwrotu?
MayorMonty,
@SpeedyNinja nope. fornie jest wyrazem, więc byłoby normalnie wymagają szelki orazreturn
jrich
2

Siatkówka , 66 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

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

Wypróbuj online! (Pierwszy wiersz umożliwia testowanie kilku przypadków testowych oddzielonych od linii).

Hmmm, znacznie dłużej niż chciałbym ...

Martin Ender
źródło
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

Mniej golfa

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

Test

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
źródło
2

Perl 5, 105 100 98 + 1 = 106 101 99 bajtów

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

Chciałem tylko wypróbować rekursywne wyrażenia regularne. Potrzebuje -popcji. Edycja: Zapisano (przekreślono 4) 7 bajtów dzięki @ msh210. (Brakujący bajt wynika z zapisania, które zostało zastąpione ostatnim zapisaniem @ msh210).

Neil
źródło
Nie testowałem żadnej z nich, ale prawdopodobnie może to być skracane, w tym różne sposoby: (1) @_=(@_,$1)może być push@_,$1. (2) Pomiń nowe linie i finał ;. (3) Podejrzewam, że jest krótszy warunek sortowania można użyć (jeśli nic innego, to przynajmniej może --- --- substytutem -dla <=>)
msh210
@ msh210 Dzięki za pierwsze dwa punkty, ale już próbowałem -i to nie zadziałało (prawdopodobnie potrzebuje parens dla pierwszeństwa, które pokonuje oszczędności).
Neil
Spróbuj y...c>>1lub y...c/2zamiast length>>1. (Nietestowane.)
msh210
@ msh210 Oczywiście powinienem najpierw przeczytać wskazówki dotyczące gry w golfa w Perlu ...
Neil
Domyślam się, że twoja ostatnia para parenów też może odejść.
msh210
2

Python 2, 91 bajtów

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)

Zamień \x7fna rzeczywisty znak DEL, którym jest ASCII 127 (kredyt dla Dennisa).

Jest to zgodne ze strategią podobną do odpowiedzi Dennisa dotyczącej używania maxi rekurencyjnego rozgałęziania w celu znalezienia najdłuższego przedziału palindromu. Ale zamiast tego znajduje lewą połowę, sprawdzając, czy odpowiadająca jej lustrzana prawa połowa przychodzi zaraz po niej, z własnoręcznie rozpoczętymi początkami .

Funkcja zgaduje, czy pierwszy znak znajduje się w lustrzanej lewej połowie. Jeśli nie, po prostu upuszcza go i powtarza na pozostałej części. Jeśli tak, jest dodawany do stosu podwróconych znaków. Jeśli łańcuch zaczyna się od stosu, łańcuch lustrzany jest generowany i uznawany za możliwe najdłuższe lustro. Aby uniknąć |jako wyjścia, brane są pod uwagę tylko niepuste stosy.

xnor
źródło
2

Galaretka , 17 bajtów

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

Wypróbuj online!

Zrobione z pomocą Mr. Xcodera i DJMcMayhem na czacie

Jak to działa

ẆŒḂÐ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'
Cairney Coheringaahing
źródło
1

Haskell, 126 111 bajtów

(!)=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
źródło
1

TSQL 227 223 bajty

Zaszyfrowałem długość do maks. 99 bajtów, to zapisane bajty, ale spowolniłem. Jednak nadal ma przyzwoitą wydajność.

Gra w golfa:

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

Nie golfowany:

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

Skrzypce

t-clausen.dk
źródło
1
Możesz ogolić 2 bajty, jeśli ograniczysz do 99, ponieważ ostatni przykład ma tylko 99 znaków
Alex Carlsen
1
@VisualBean thankyou, zmieniłem skrypt, aby zezwolić tylko na 99 znaków, zmieniłem także sortowanie z Thai_CS_AS na thai_bin
t-clausen.dk
0

Python 2, 149 bajtów

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]

Wypróbuj online

Ten program znajduje pierwszą połowę największego podłańcucha palindromowego o parzystej długości i wypisuje ten ciąg, a następnie a |, a następnie ten ciąg odwrócony. Jeśli nie ma odpowiedniego ciągu, tbędzie pusty i '|'*(L(t)>0)przejdzie do pustego ciągu.

Mego
źródło
0

Java 8, 294 283 232 bajty

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):"";}

Wyjaśnienie:

Wypróbuj tutaj.

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
źródło