Gerador de fechamento palindrômico bidirecional

24

Introdução

Um fechamento palíndrico de uma sequência de entrada é o palíndromo mais curto que pode ser construído a partir da sequência de entrada em que o palíndromo final começa com a sequência de entrada.

Para esse desafio, consideraremos um fechamento palindrômico bidirecional, de modo que

  • O fechamento palíndrico esquerdo de uma sequência de entrada é o palíndromo mais curto possível que começa com a sequência de entrada.
  • O fechamento palíndrico direito de uma sequência de entrada é o palíndromo mais curto possível que termina com a sequência de entrada.
  • O fechamento palindrômico bidirecional de uma sequência de entrada é o mais curto entre o fechamento palindrômico esquerdo ou direito da sequência de entrada.

Tarefa

Sua tarefa é simples. Dada uma sequência (consistindo apenas em ASCII imprimível, novas linhas e espaços em branco), produza o fechamento palindrômico bidirecional dessa sequência. Em caso de empate, o fechamento palindrômico esquerdo ou direito é uma saída válida.

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento de linha de comando ou argumento de função e imprimindo o resultado em STDOUT (ou alternativa mais próxima) ou retornando-o como uma sequência.

Você pode assumir que a entrada nunca será uma sequência vazia.

Poucos exemplos:

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

O crédito da ideia inicial vai para o VisualMelon, idéia final com a ajuda de Martin e Zgarb

Os termos fechamento palindrômico, fechamento palindrômico esquerdo e fechamento palindrômico direito foram usados ​​pela primeira vez e definidos por este artigo .

Optimizer
fonte
11
Eu gostaria de ver uma solução palindrômica ...
ojdo 17/03/2015
2
@ojdo Pensei em adicionar isso como um bônus, mas tenho certeza de que a maioria das respostas usaria apenas comentários para criar o palíndromo. Se alguma resposta também pode realmente ser um palíndromo, sem depender de comentários, eu deixaria uma recompensa por essa resposta!
Optimizer

Respostas:

11

Pyth, 22 19

hfq_TTsm,+z_d+_dzyz

Tente online .

Explicação

O fechamento palindrômico bidirecional é da forma AXou XA, onde Xé a cadeia de entrada e Aé uma substring de X. Na verdade, eu tenho que ser uma substring contígua de X, um prefixo para uma forma, um sufixo para a outra forma. Mas eu não me importo com essas falhas. Uma substring (contígua ou não) é tudo que eu preciso no 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

Editar

A versão antiga ordenou as strings após a filtragem por comprimento .olN.... Acabei de perceber, que yretorna as substrings ordenadas por comprimento. Portanto, esses palíndromos já estão classificados.

Jakube
fonte
6

Grampo , 40

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

Exemplo

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

Explicação

(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.-.
Ypnypn
fonte
6

CJam, 30 bytes

Estava realmente esperando ver uma resposta CJam agora. Então, aqui vai: P

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

Eu realmente odeio isso {,}$ bloco, mas recebo uma lista desordenada de possíveis palíndromos devido ao algoritmo de geração que estou usando.

Explicação do código

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

Experimente online aqui

Optimizer
fonte
6
Eu realmente odeio esse {,}$bloco lá também! Brincadeirinha, não tenho idéia do que qualquer coisa no CJam faz.
Alex A.
4

Python 2, 115 113 109 105 96 bytes

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]

Espero que possa jogar golfe ainda mais. Bits possivelmente dignos de nota:

  • usando soma para duas compreensões de lista em um
  • construindo termos em ordem classificada para evitar a necessidade de min (sugerido por @Jakube)
Uri Granta
fonte
11
Os itens não estão na ordem de classificação, portanto, isso ocorre para strings como a.
Sp3000 17/03/2015
4

Mathematica, 96 bytes

Deve haver uma maneira mais elegante do que isso ...

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

Isso define uma função sem nome que pega uma string e retorna o resultado.

A ideia básica é

  • Divida a string em Characters.
  • Forme uma matriz com esta lista e seu inverso.
  • Use a correspondência de padrões para encontrar o palíndromo direito de cada um deles:

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

    Observe que isso realmente não retorna uma lista simples. Por exemplo, para {a,b,c}você obter

    {a,b,{c,b,a}}
    
  • Classifique os dois resultados por comprimento.

  • Escolha o menor e junte-o novamente a uma string com ""<>#&@@.
Martin Ender
fonte
Ele sai abacabaquando a entrada é abac. A resposta correta é cabac. Eu acho que você deve achatá-los antes de classificar por comprimento.
alephalpha
11
@alephalpha Encontrei uma correção melhor que não exigia alteração do tamanho do código (e que era realmente minha intenção por não classificá-lo).
Martin Ender
2

Brachylog (2), 6 bytes, desafio de pós-datas no idioma

~{↔?a}

Experimente online!

Como de costume no Brachylog, essa é uma função, não um programa completo.

Explicação

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

Tanto quanto eu sei (não é o meu idioma, mas parece improvável), a não foi adicionado ao Brachylog para esse desafio, mas é realmente útil aqui. Usamos o método "reverse, e afirmamos que não mudou" para afirmar que o valor que encontramos é um palíndromo.

Quanto ao motivo pelo qual isso produz o palíndromo mais curto , a ordem de avaliação de Prolog (e, portanto, de Brachylog) é fortemente influenciada pela primeira coisa que avalia. Nesse caso, é um comando "reverso" e (como a maioria das operações da lista) define uma ordem de avaliação que visa minimizar o tamanho da lista resultante. Como é o mesmo que o tamanho da saída, o programa acaba minimizando exatamente a coisa certa por acaso, o que significa que eu não precisava adicionar nenhuma dica explícita.


fonte
a- O Adfix não foi adicionado para este desafio. Eu não tinha símbolo disponível com bons mnemônicos para prefixo e sufixo; portanto, mesclei ambos no adfix, que pode levar subscritos para selecionar prefixos ou sufixos somente se necessário.
Fatalize 24/02
1

Ruby, 76 + 2 = 78

Com sinalizadores de linha de comando -pl ( lpode não ser necessário, dependendo de como você está fazendo a entrada), execute

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

Dada uma string 'abaa', gera as strings 'cbca 0 acbc' e 'acbc 0 cbca', em que 0 é o caractere não imprimível com código ascii 0. Em seguida, ele exclui uma cópia do enquadramento de sequência repetido mais longo 0 que encontra em cada um, 'a' no primeiro e 'cbc' no segundo, para obter os dois fechamentos. Em seguida, gera o resultado mais curto.

A única coisa realmente estranha sobre o código golfado é que ele encurta as strings no lugar enquanto as classifica, o que podemos evitar porque min_byexecuta o bloco apenas uma vez por elemento sendo comparado (tanto porque é uma transformação schwartziana quanto porque há apenas duas elementos para comparar).

histocrata
fonte
1

Python 3, 107 bytes


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]

Testar:

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

Haskell, 107 bytes

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]

Teste:

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

J, 66 62 bytes

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

Bem direto. Os dois truques que eu uso:

O fechamento palindrômico direito é o fechamento palindrômico esquerdo da corda invertida.

Localizando o comprimento da sequência com comprimento mínimo e palindromidade com a expressão min (is_palindrome / length).

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

   f 'lama'
lamal

Experimente online aqui.

randomra
fonte