Palindromizando as cordas

30

Introdução

Para quem não sabe, um palíndromo é quando uma string é igual à string de trás para a frente (com exceção de interpunções, espaços etc.). Um exemplo de um palíndromo é:

abcdcba

Se você reverter isso, você terminará com:

abcdcba

Qual é o mesmo. Portanto, chamamos isso de palíndromo. Para palindromizar as coisas, vamos dar uma olhada no exemplo de uma string:

adbcb

Este não é um palíndromo. Para palindromizar isso, precisamos mesclar a sequência invertida na sequência inicial à direita da sequência inicial , deixando ambas as versões intactas. Quanto menor, melhor.

A primeira coisa que podemos tentar é o seguinte:

adbcb
bcbda
^^ ^^

Nem todos os caracteres correspondem, portanto, essa não é a posição correta para a sequência invertida. Demos um passo à direita:

adbcb
 bcbda
 ^^^^

Isso também não corresponde a todos os caracteres. Vamos mais um passo à direita:

adbcb
  bcbda

Desta vez, todos os caracteres correspondem . Podemos mesclar as duas strings deixando a intacta . O resultado final é:

adbcbda

Esta é a sequência palindromizada .


A tarefa

Dada uma sequência (com pelo menos um caractere) contendo apenas letras minúsculas (ou maiúsculas, se for melhor), produza a sequência palindromizada .


Casos de teste

Input     Output

abcb      abcba
hello     hellolleh
bonobo    bonobonob
radar     radar
hex       hexeh

Isso é , então a submissão com a menor quantidade de bytes ganha!

Adnan
fonte
3
Relacionado.
Zgarb 04/04
6
Você deve especificar que a sequência invertida deve ser mesclada na sequência original com a sequência invertida à direita. Se puder ir à esquerda, obonoboseria uma solução melhor para o caso de teste.
Level River St
2
2
Sp3000:
2
@LevelRiverSt +1 apenas porque "obonobo" é uma palavra tão incrível
Nathaniel
1
@ Nathaniel Obrigado, mas bono b o nobé uma frase inteira. Qual é a diferença entre Deus e Bono? Deus não vaguear Dublin fingindo ser Bono ;-)
Nível River St

Respostas:

5

Geléia, 11 10 bytes

ṫỤfU$Ḣœ^;U

Experimente online!

Como funciona

ṫỤ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
fonte
15

Pyth (confirmação b93a874), 11 bytes

.VkI_IJ+zbB

Suíte de teste

Este código explora um bug na versão atual do Pyth, confirme b93a874 . O erro é que _IJ+zbé analisado como se fosse q_J+zbJ+zb, o que equivale a _I+zb+zb, quando deveria (pela intenção de design do Pyth) ser analisado como q_J+zbJ, o que equivale a _I+zb. Isso me permite salvar um byte - depois que o bug for corrigido, o código correto será .VkI_IJ+zbJB. Vou explicar esse código.

Basicamente, o código bruto força sobre todas as sequências possíveis até encontrar a sequência mais curta que pode ser anexada à entrada para formar um palíndromo e gerar a sequência combinada.

.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
fonte
Como você cria esse código? É dificilmente legível e absolutamente não compreensível por alguém que não conhece Pyth. Qual é o propósito de tal linguagem.
Anukul 06/04/19
5
@momo O objetivo do idioma é escrever código curto, por diversão. É uma atividade recreativa. Eu posso escrever porque tenho muita prática e porque inventei a linguagem. Sei que não é compreensível para alguém que não conhece o idioma, por isso incluí a explicação.
Isaacg #
13

Python, 46 bytes

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

Se a sequência for um palíndromo, retorne-a. Caso contrário, coloque a primeira letra em torno do resultado recursivo do restante da sequência.

Exemplo de detalhamento:

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
fonte
Eu acho que você pode salvar um byte se você usar a condição oposta ( s!=s[::-1])
aditsu
@aditsu Isso funciona, mas usar uma multiplicação é ainda mais curto.
Xnor
9

Haskell, 36 bytes

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

Mais facilmente:

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

Se a sequência for um palíndromo, retorne-a. Caso contrário, coloque a primeira letra em torno do resultado recursivo da cauda da corda.

A corda sé dividida h:tna segunda guarda, evitando um preenchedor 1>0para este caso. Isso é mais curto do que s@(h:t)para a entrada.

xnor
fonte
5

Pitão - 16 12 bytes

4 bytes salvos graças a @FryAmTheEggman.

FGITW, muito golfe possível.

h_I#+R_Q+k._

Conjunto de Teste .

Maltysen
fonte
5

Brachylog , 16 6 5 bytes (Não concorrente)

:Ac.r

Experimente online!

Quando publiquei minha resposta inicial, ela ainda estava na antiga implementação em Java. Desde que reprogramei tudo no Prolog, ele agora funciona como deveria.

Explicação

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

A retropropagação faz com que o primeiro valor válido Aencontrado seja o mais curto que você pode concatenar com a Entrada para torná-la um palíndromo.

Solução alternativa, 5 bytes

~@[.r

É aproximadamente o mesmo que a resposta acima, exceto que, em vez de declarar "Saída é a concatenação da Entrada com uma sequência A", declaramos que "Saída é uma sequência para a qual a Entrada é um prefixo da Saída".

Fatalizar
fonte
4

JavaScript (ES6), 92 bytes

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

Calcula e corta a sobreposição entre a cadeia original e sua reversão.

Neil
fonte
4

Retina, 29 25

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

Experimente online!

Muito obrigado a Martin por 11 bytes salvos!

Isso apenas cria uma cópia invertida da string e junta-as. A única parte realmente chique disso é o método de reversão:, O^#r`.\Gque é feito usando o modo de classificação. Classificamos as letras da segunda sequência (as que não são novas linhas e são consecutivas a partir do final da sequência, graças ao \G) pelo seu valor numérico, que, como não há números, é 0. Então, invertemos ordem dos resultados dessa classificação estável com a ^opção Todo o crédito pelo uso sofisticado de \Gpertence a Martin :)

FryAmTheEggman
fonte
3

CJam, 18

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

Experimente online

Explicação:

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
fonte
3

Lua, 89 88 bytes

Eu venci o Javascript! \ o / Salvo 1 byte graças a @LeakyNun ^^

É um programa completo, recebe sua entrada como argumento da linha de comando.

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

destroçado

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
fonte
Eu acredito que os parênteses próximos whilepodem ser removidos?
Leaky Nun
@LeakyNun certeza de que pode ^^
Katenkyo
Não pode fazer i=i+1end?
Erik the Outgolfer
1
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Infelizmente, não posso. Ele tentaria avaliar 1endcomo um número hexadecimal. Geralmente, você não pode usar [abcdef]diretamente após um número sem que ele seja considerado um hexadecimal. Existe mais uma exceção 0x.
Katenkyo
3

Prolog, 43 bytes

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

Isso espera uma sequência de códigos como entrada, por exemplo, no SWI-Prolog 7: a(`hello`).

Explicação

Esta é basicamente uma porta da minha resposta 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
Fatalizar
fonte
3

Oitava, 78 75 bytes

Economizou 3 bytes graças a Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ!

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

O ideone ainda falha em funções nomeadas, mas aqui está uma execução de teste do código como um programa.

taça
fonte
2

Perl, 37 bytes

Com base na resposta do xnor.

Inclui +2 para -lp

Execute com entrada no STDIN, por exemplo

palindromize.pl <<< bonobo

palindromize.pl:

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

05AB1E , 18 bytes

Código:

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

Usa a codificação CP-1252 . Experimente online!

Adnan
fonte
1

J, 20 bytes

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

Este é um verbo monádico. Experimente aqui. Uso:

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

Explicação

Estou usando o fato de que a palindromização de S é S + reversa (P) , onde P é o prefixo mais curto de S cuja remoção resulta em um palíndromo. Em J, é um pouco complicado fazer uma pesquisa pelo primeiro elemento de uma matriz que satisfaça um predicado; daí a indexação.

,[|.@{.~(-:|.)\.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
fonte
1

Haskell, 68 bytes

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

Exemplo de uso: f "abcb"-> "abcba".

Pesquise initsa entrada i(por exemplo inits "abcb"- - ["", "a", "ab", "abc", "abcb"]) até encontrar uma em que ela é anexada ao contrário para criar ium palíndromo.

nimi
fonte
Não r=reverseprecisa ir antes f i=...?
Erik the Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ: Não, você pode usar qualquer pedido.
nimi
Eu consegui em 46 bytes. Aposto que isso pode ser feito ainda melhor.
226176 theonlygusti
@theonlygusti: veja a resposta do xnor .
nimi
1

MATL , 17 16 bytes

Inspirado livremente na resposta CJam do @ aditsu .

`xGt@q:)PhttP=A~

Experimente online!

Explicação

`        % 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
fonte
1

Ruby, 44 bytes

Esta resposta é baseada nas soluções Python e Haskell da xnor .

f=->s{s.reverse==s ?s:s[0]+f[s[1..-1]]+s[0]}
Sherlock9
fonte
Não pode fazer ==s?s:?
Erik the Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ irb joga um ataque se eu tentar. Deve ser algo a ver com a forma como ele analisa ?entre ?:para ternário ea ?x == 'x'substituição usado desde Ruby 1.9
Sherlock9
1

Oracle SQL 11.2, 195 bytes

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

Sem golfe

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
fonte
1

Sério, 34 bytes

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

O último caractere é um espaço sem quebra (ASCII 127 ou 0x7F).

Experimente online!

Explicação:

╩╜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
fonte
1

C #, 202 bytes

Eu tentei.

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

}

Alguém pode me fornecer alguma idéia para agrupar as duas chamadas para .Reverse (). ToArray ()? Um método separado é mais bytes.

SkyPharaoh
fonte
0

QBIC , 41 bytes

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

Explicação:

;_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
fonte
0

Haskell, 46 bytes

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

Gostaria de saber se existe uma maneira de remover o parêntese em (f$tail l)++[l!!0]...

theonlygusti
fonte