Palindromizacja strun

30

Wprowadzenie

Dla tych, którzy nie wiedzą, palindrom ma miejsce, gdy ciąg znaków jest równy ciągowi wstecz (z wyjątkiem interpunkcji, spacji itp.). Przykładem palindromu jest:

abcdcba

Jeśli to odwrócisz, otrzymasz:

abcdcba

Który jest taki sam. Dlatego nazywamy to palindromem. Aby palindromize rzeczy, spójrzmy na przykład ciągu:

adbcb

To nie jest palindrom. Aby palindromizować to, musimy scalić odwrócony ciąg w początkowy ciąg po prawej stronie początkowego ciągu , pozostawiając obie wersje nienaruszone. Im krótszy, tym lepiej.

Pierwszą rzeczą, którą możemy wypróbować, jest:

adbcb
bcbda
^^ ^^

Nie wszystkie znaki pasują, więc nie jest to właściwa pozycja dla odwróconego łańcucha. Idziemy o krok w prawo:

adbcb
 bcbda
 ^^^^

To również nie pasuje do wszystkich znaków. Idziemy o krok dalej w prawo:

adbcb
  bcbda

Tym razem wszystkie postacie pasują do siebie . Możemy połączyć oba ciągi, pozostawiając nienaruszone . Ostateczny wynik to:

adbcbda

To jest palindromized string .


Zadanie

Biorąc pod uwagę ciąg (zawierający co najmniej jeden znak) zawierający tylko małe litery (lub wielkie litery, jeśli lepiej to pasuje), wypisz ciąg palindromized .


Przypadki testowe

Input     Output

abcb      abcba
hello     hellolleh
bonobo    bonobonob
radar     radar
hex       hexeh

To jest , więc wygrywanie z najmniejszą ilością bajtów wygrywa!

Adnan
źródło
3
Związane z.
Zgarb
6
Należy określić, że odwrócony ciąg musi zostać scalony w oryginalny ciąg z odwróconym po prawej stronie. Jeśli może pójść w lewo, obonobobyłoby lepszym rozwiązaniem przypadku testowego.
Level River St
2
Powiązane 2
Sp3000,
2
@LevelRiverSt +1 tylko dlatego, że „obonobo” to takie niesamowite słowo
Nathaniel
1
@Nanielski Dzięki, ale bono b o nobto całe zdanie. Jaka jest różnica między Bogiem a Bono? Bóg nie błąka się po Dublinie udając Bono ;-)
Level River St

Odpowiedzi:

5

Galaretka, 11 10 bajtów

ṫỤfU$Ḣœ^;U

Wypróbuj online!

Jak to działa

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

Pyth (commit b93a874), 11 bajtów

.VkI_IJ+zbB

Zestaw testowy

Ten kod wykorzystuje błąd w bieżącej wersji Pyth, zatwierdzenie b93a874 . Błąd polega na tym, że _IJ+zbjest on analizowany tak, jakby był q_J+zbJ+zb, co jest równoważne z tym _I+zb+zb, kiedy powinien (zgodnie z intencją projektu Pyth) być analizowany jako q_J+zbJ, co jest równoważne z _I+zb. To pozwala mi zapisać bajt - po usunięciu błędu poprawny kod będzie .VkI_IJ+zbJB. Zamiast tego wyjaśnię ten kod.

Zasadniczo kod brutalny wymusza na wszystkich możliwych ciągach, dopóki nie znajdzie najkrótszego ciągu, który można dołączyć do danych wejściowych w celu utworzenia palindromu, i wysyła połączony ciąg.

.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
źródło
Jak wymyślić taki kod? Jest ledwo czytelny i absolutnie niezrozumiały dla kogoś, kto nie zna Pytha. Jaki jest cel takiego języka.
anukul
5
@momo Celem tego języka jest pisanie krótkiego kodu dla zabawy. To działalność rekreacyjna. Mogę to napisać, ponieważ mam dużo praktyki i wymyśliłem język. Wiem, że nie jest to zrozumiałe dla kogoś, kto nie zna języka, dlatego zamieściłem wyjaśnienie.
isaacg
13

Python, 46 bajtów

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

Jeśli ciąg znaków jest palindromem, zwróć go. W przeciwnym razie umieść pierwszą literę wokół wyniku rekurencyjnego dla pozostałej części ciągu.

Przykładowy podział:

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
źródło
Myślę, że możesz zapisać bajt, jeśli użyjesz przeciwnego warunku ( s!=s[::-1])
aditsu
@aditsu To działa, ale mnożenie jest jeszcze krótsze.
xnor
9

Haskell, 36 bajtów

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

Bardziej czytelnie:

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

Jeśli ciąg znaków jest palindromem, zwróć go. W przeciwnym razie umieść pierwszą literę wokół wyniku rekurencyjnego dla końca łańcucha.

Sznurek sjest podzielony na h:tdrugą osłonę, eliminując wypełniacz 1>0w tym przypadku. Jest to krótsze niż s@(h:t)wprowadzanie danych wejściowych.

xnor
źródło
5

Pyth - 16 12 bajtów

4 bajty zapisane dzięki @FryAmTheEggman.

FGITW, możliwe dużo golfa.

h_I#+R_Q+k._

Pakiet testowy .

Maltysen
źródło
5

Brachylog , 16 6 5 bajtów (niekonkurencyjny)

:Ac.r

Wypróbuj online!

Kiedy zamieściłem moją wstępną odpowiedź, wciąż była na starej implementacji w Javie. Ponieważ przeprogramowałem wszystko w Prologu, teraz działa ono tak, jak powinno.

Wyjaśnienie

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

Propagacja wsteczna sprawia, że ​​pierwsza Aznaleziona dla niej prawidłowa wartość będzie najkrótsza, jaką można połączyć z Input, aby uczynić z niej palindrom.

Alternatywne rozwiązanie, 5 bajtów

~@[.r

Jest to mniej więcej taka sama jak powyższa odpowiedź, z tym wyjątkiem, że zamiast stwierdzenia „Dane wyjściowe to konkatenacja danych wejściowych za pomocą ciągu znaków A”, stwierdzamy, że „Dane wyjściowe to ciągi znaków, dla których dane wejściowe są przedrostkiem danych wyjściowych”.

Fatalizować
źródło
4

JavaScript (ES6), 92 bajty

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

Oblicza i odcina nakładanie się oryginalnego ciągu znaków i jego odwrócenie.

Neil
źródło
4

Siatkówka oka, 29 25

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

Wypróbuj online!

Wielkie dzięki Martinowi za 11 bajtów zapisanych!

To po prostu tworzy odwróconą kopię łańcucha i wygładza je razem. Jedyną naprawdę wymyślną częścią tego jest metoda odwracania: O^#r`.\Gktóra odbywa się za pomocą trybu sortowania. Sortujemy litery drugiego łańcucha (te, które nie są znakami nowej linii i są kolejne od końca łańcucha, dzięki \G)) według ich wartości liczbowej, która, ponieważ nie ma liczb, wynosi 0. Następnie odwracamy kolejność wyników tego stabilnego sortowania z ^opcją. Wszystkie zasługi za fantazyjne użycie \Gnależy do Martina :)

FryAmTheEggman
źródło
3

CJam, 18 lat

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

Wypróbuj online

Wyjaśnienie:

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

Lua, 89 88 bajtów

Pokonałem Javascript! \ o / Zapisano 1 bajt dzięki @LeakyNun ^^

Jest to pełny program, który przyjmuje dane wejściowe jako argument wiersza poleceń.

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))

bez golfa

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
źródło
Wierzę, że nawiasy znajdujące się w pobliżu whilemożna usunąć?
Leaky Nun
@LeakyNun na pewno mogą ^ ^
Katenkyo
Nie można zrobić i=i+1end?
Erik the Outgolfer,
1
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Niestety nie mogę. Próbowałby być oceniany 1endjako liczba szesnastkowa. Zasadniczo nie można używać [abcdef]bezpośrednio po liczbie, bez uznania jej za szesnastkową. Jest jeszcze jeden wyjątek 0x.
Katenkyo
3

Prolog, 43 bajty

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

Oczekiwany jest ciąg kodów jako dane wejściowe, np. W SWI-Prolog 7: a(`hello`).

Wyjaśnienie

Jest to w zasadzie port mojej odpowiedzi Brachylog.

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

Oktawa, 78 75 bajtów

Zaoszczędzono 3 bajty dzięki Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ!

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

ideone wciąż zawodzi dla nazwanych funkcji, ale tutaj jest testowe uruchomienie kodu jako programu.

zlewka
źródło
2

Perl, 37 bajtów

Na podstawie odpowiedzi xnora.

Obejmuje +2 za -lp

Uruchom z wejściem na STDIN, np

palindromize.pl <<< bonobo

palindromize.pl:

#!/usr/bin/perl -lp
s/.//,do$0,$_=$&.$_.$&if$_!~reverse
Ton Hospel
źródło
1

05AB1E , 18 bajtów

Kod:

©gF¹ðN×®«ðñD®åi,q

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!

Adnan
źródło
1

J, 20 bajtów

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

To jest czasownik monadyczny. Wypróbuj tutaj. Stosowanie:

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

Wyjaśnienie

Używam faktu, że palindromizacja S to S + rewers (P) , gdzie P jest najkrótszym prefiksem S, którego usunięcie powoduje palindrom. W J trochę niezgrabne jest wyszukiwanie pierwszego elementu tablicy, który spełnia predykat; stąd indeksowanie.

,[|.@{.~(-:|.)\.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
źródło
1

Haskell, 68 bajtów

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

Przykład użycia: f "abcb"-> "abcba".

Przeszukuj initsdane wejściowe i(np. inits "abcb"-> ["", "a", "ab", "abc", "abcb"]), aż znajdziesz takie, w którym jest ono dołączane odwrotnie, aby izbudować palindrom.

nimi
źródło
Nie r=reversemusisz iść wcześniej f i=...?
Erik the Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ: Nie, możesz użyć dowolnego zamówienia.
nimi
Udało mi się w 46 bajtach. Założę się, że można to zrobić jeszcze lepiej.
theonlygusti
@theonlygusti: patrz odpowiedź Xnora .
nimi
1

MATL , 17 16 bajtów

Luźno zainspirowany odpowiedzią CJam @ aditsu .

`xGt@q:)PhttP=A~

Wypróbuj online!

Wyjaśnienie

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

Rubinowy, 44 bajty

Ta odpowiedź oparta jest na rozwiązaniach Python i Haskell xnor .

f=->s{s.reverse==s ?s:s[0]+f[s[1..-1]]+s[0]}
Sherlock9
źródło
Nie można zrobić ==s?s:?
Erik the Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ irb rzuca napad, jeśli spróbuję. Musi mieć coś wspólnego z tym, jak to analizuje ?między ?:dla trójskładnikowego i ?x == 'x'substytucja stosowany od Ruby 1.9
Sherlock9
1

Oracle SQL 11.2, 195 bajtów

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

Bez golfa

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

Poważnie, 34 bajty

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

Ostatni znak to spacja niełamliwa (ASCII 127 lub 0x7F).

Wypróbuj online!

Wyjaśnienie:

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

C #, 202 bajtów

Próbowałem.

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

Nie golfowany:

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();
    }

}

Czy ktoś może dostarczyć mi jakieś pomysły na grupowanie dwóch wywołań funkcji .Reverse (). ToArray ()? Oddzielna metoda to więcej bajtów.

SkyPharaoh
źródło
0

QBIC , 41 bajtów

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

Wyjaśnienie:

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

Haskell, 46 bajtów

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

Zastanawiam się, czy istnieje sposób na usunięcie nawiasu w (f$tail l)++[l!!0]...

theonlygusti
źródło