Wprowadzenie

Zamknięcie palindromiczne ciągu wejściowego jest najkrótszym palindromem, który można zbudować z ciągu wejściowego, w którym końcowy palindrom rozpoczyna się od ciągu wejściowego.

W przypadku tego wyzwania rozważymy dwukierunkowe zamknięcie palindromiczne, takie jak

• Lewe palindromiczne zamknięcie ciągu wejściowego jest najkrótszym możliwym palindromem, który zaczyna się od ciągu wejściowego.
• Prawe palindromiczne zamknięcie ciągu wejściowego jest najkrótszym możliwym palindromem, który kończy się na ciągu wejściowym.
• Dwukierunkowe zamknięcie palindromiczne ciągu wejściowego jest krótsze z lewego lub prawego zamknięcia palindromowego ciągu wejściowego.

Zadanie

Twoje zadanie jest proste. Biorąc pod uwagę ciąg znaków (składający się tylko z drukowalnego ASCII, nowych wierszy i białych znaków), należy wygenerować dwukierunkowe palindromiczne zamknięcie tego ciągu. W przypadku remisu jedno lub drugie lewe lub prawe zamknięcie palindromiczne jest prawidłowym wyjściem.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i albo drukując wynik do STDOUT (lub najbliższej alternatywy), albo zwracając go jako ciąg znaków.

Możesz założyć, że wejście nigdy nie będzie pustym ciągiem.

Kilka przykładów:

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

Pierwotny pomysł na pomysł trafia do VisualMelon, ostatni pomysł z pomocą Martina i Zgarba

Terminy zamknięcie palindromowe, zamknięcie lewopalindromowe i zamknięcie prawopalindromowe zostały po raz pierwszy użyte i zdefiniowane w tym artykule .

Pyth, 22 19

hfq_TTsm,+z_d+_dzyz

Wypróbuj online .

Wyjaśnienie

Dwukierunkowe zamknięcie palindromowe ma albo postać, AXalbo XAgdzie Xjest łańcuchem wejściowym i Ajest podłańcuchem X. Właściwie to muszę być ciągłym podciągiem X, prefiksem jednej formy, sufiksem drugiej formy. Ale mnie to nie obchodzi. Podciąg (ciągły lub nie) jest wszystkim, czego potrzebuję w Pyth.

                        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

Edytować

Stara wersja uporządkowała ciągi po filtrowaniu według długości .olN.... Właśnie zdałem sobie sprawę, że yzwraca podłańcuchy uporządkowane według długości. Więc te palindromy są już posortowane.

Klip , 40

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

Przykład

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

Wyjaśnienie

(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.-.

CJam, 30 bajtów

Naprawdę miałem nadzieję, że zobaczę odpowiedź CJam. Więc proszę: P

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

Naprawdę nienawidzę tego {,}$bloku, ale otrzymuję nieuporządkowaną listę możliwych palindromów z powodu algorytmu generowania, którego używam.

Wyjaśnienie kodu

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";

Wypróbuj online tutaj

Python 2, 115 113 109 105 96 bajtów

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]

Mam nadzieję, że golf dalej. Warto zwrócić uwagę na bity:

• użycie sumy dla dwóch wyrażeń listowych w jednym
• konstruowanie terminów w posortowanej kolejności, aby uniknąć potrzeby stosowania min (sugerowane przez @Jakube)

Mathematica, 96 bajtów

Musi być bardziej elegancki sposób niż ten ...

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

Definiuje nienazwaną funkcję, która pobiera ciąg znaków i zwraca wynik.

Podstawową ideą jest

• Podziel ciąg na Characters.
• Utwórz tablicę z tą listą i jej odwrotnością.

• Użyj dopasowania wzorca, aby znaleźć odpowiednią palindromikę każdego z nich:

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

  Zauważ, że tak naprawdę to nie zwraca płaskiej listy. Np. Za {a,b,c}dostaniesz

  {a,b,{c,b,a}}
  

• Posortuj dwa wyniki według długości.

• Wybierz krótszy i połącz go z powrotem w ciąg z ""<>#&@@.

Brachylog (2), 6 bajtów, wyzwanie dotyczące postdatacji języka

~{↔?a}

Wypróbuj online!

Jak zwykle w przypadku Brachylog, jest to funkcja, a nie pełny program.

Wyjaśnienie

~{↔?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.

O ile mi wiadomo (to nie jest mój język, ale wydaje się mało prawdopodobny), anie został dodany do Brachylog do tego wyzwania, ale przydaje się tutaj naprawdę. Używamy metody „odwróć i stwierdzamy, że się nie zmieniła”, aby stwierdzić, że znalezioną przez nas wartością jest palindrom.

Jeśli chodzi o to, dlaczego powoduje to powstanie najkrótszego palindromu, na pierwszą kolejność oceny ma duży wpływ na kolejność oceny Prologa (a więc i Brachyloga). W tym przypadku jest to polecenie „odwrotne” i (podobnie jak większość operacji na liście) ustawia kolejność oceny, której celem jest zminimalizowanie rozmiaru wynikowej listy. Ponieważ jest to to samo, co rozmiar wyjścia, program szczęśliwie kończy przypadkiem minimalizację dokładnie właściwej rzeczy, co oznacza, że ​​nie musiałem dodawać żadnych wyraźnych wskazówek.

Rubin, 76 + 2 = 78

Z flagami wiersza polecenia -pl( lmogą nie być potrzebne w zależności od tego, jak robisz wprowadzanie danych), uruchom

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

Biorąc pod uwagę ciąg „abaa”, generuje ciągi „cbca 0 acbc” i „acbc 0 cbca”, gdzie 0 to niedrukowalny znak z kodem ascii 0. Następnie usuwa jedną kopię najdłuższej powtarzającej się ramki 0, którą znajdzie w każdym, „a” w pierwszym i „cbc” w drugim, aby uzyskać dwa zamknięcia. Następnie wyświetla najkrótszy wynik.

Jedyną naprawdę dziwną rzeczą w kodzie golfowym jest to, że skraca ciągi w miejscu podczas sortowania, co możemy uniknąć, ponieważ min_bywykonuje blok tylko raz na porównywany element (zarówno dlatego, że jest to transformacja Schwartziana, jak i ponieważ są tylko dwa elementy do porównania).

Python 3, 107 bajtów

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]

Testować:

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

Haskell, 107 bajtów

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]

Test:

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

J, 66 62 bajtów

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

Całkiem proste. Dwie sztuczki, których używam:

Prawe zamknięcie palindromowe to lewe zamknięcie palindromowe odwróconego łańcucha.

Znalezienie długości łańcucha o minimalnej długości i palindromity za pomocą wyrażenia min (is_palindrome / length).

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

   f 'lama'
lamal

Wypróbuj online tutaj.