Palindromiser les cordes

30

introduction

Pour ceux qui ne savent pas, un palindrome est quand une chaîne est égale à la chaîne en arrière (à l'exception de l'interponction, des espaces, etc.). Un exemple de palindrome est:

abcdcba

Si vous inversez cela, vous vous retrouverez avec:

abcdcba

C'est pareil. Par conséquent, nous appelons cela un palindrome. Pour palindromiser les choses, regardons un exemple de chaîne:

adbcb

Ce n'est pas un palindrome. Pour palindromiser cela, nous devons fusionner la chaîne inversée dans la chaîne initiale à droite de la chaîne initiale , en laissant les deux versions intactes. Plus c'est court, mieux c'est.

La première chose que nous pouvons essayer est la suivante:

adbcb
bcbda
^^ ^^

Tous les caractères ne correspondent pas, ce n'est donc pas la bonne position pour la chaîne inversée. On fait un pas à droite:

adbcb
 bcbda
 ^^^^

Cela ne correspond pas non plus à tous les personnages. On fait un autre pas à droite:

adbcb
  bcbda

Cette fois, tous les personnages correspondent . Nous pouvons fusionner les deux chaînes en laissant intactes . Le résultat final est:

adbcbda

Ceci est la chaîne palindromisée .


La tâche

Étant donné une chaîne (avec au moins un caractère) ne contenant que des lettres minuscules (ou majuscules, si cela convient mieux), sortez la chaîne palindromisée .


Cas de test

Input     Output

abcb      abcba
hello     hellolleh
bonobo    bonobonob
radar     radar
hex       hexeh

C'est du , donc la soumission avec le moins d'octets gagne!

Adnan
la source
3
En relation.
Zgarb
6
Vous devez spécifier que la chaîne inversée doit être fusionnée dans la chaîne d'origine avec celle inversée à droite. Si elle peut aller à gauche, ce obonoboserait une meilleure solution au cas de test.
Level River St
2
Related 2
Sp3000
2
@LevelRiverSt +1 juste parce que "obonobo" est un mot tellement incroyable
Nathaniel
1
@Nathaniel Merci mais bono b o nobc'est une phrase entière. Quelle est la différence entre Dieu et Bono? Dieu ne se promène pas dans Dublin en faisant semblant d'être Bono ;-)
Level River St

Réponses:

5

Gelée, 11 10 octets

ṫỤfU$Ḣœ^;U

Essayez-le en ligne!

Comment ça marche

ṫỤ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
la source
15

Pyth (commit b93a874), 11 octets

.VkI_IJ+zbB

Suite de tests

Ce code exploite un bogue dans la version actuelle de Pyth, commit b93a874 . Le bogue est qui _IJ+zbest analysé comme s'il l'était q_J+zbJ+zb, ce qui équivaut à _I+zb+zbquand il devrait (par l'intention de conception de Pyth) être analysé commeq_J+zbJ , ce qui est équivalent à _I+zb. Cela me permet d'enregistrer un octet - une fois le bug corrigé, le code correct sera .VkI_IJ+zbJB. Je vais plutôt expliquer ce code.

Fondamentalement, la brute de code force toutes les chaînes possibles jusqu'à ce qu'elle trouve la chaîne la plus courte qui peut être ajoutée à l'entrée pour former un palindrome et génère la chaîne combinée.

.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
la source
Comment trouvez-vous un tel code? Il est à peine lisible et absolument incompréhensible par quelqu'un qui ne connaît pas Pyth. Quel est le but d'une telle langue.
anukul
5
@momo Le but du langage est d'écrire du code court pour le plaisir. C'est une activité récréative. Je peux l'écrire parce que j'ai beaucoup de pratique et parce que j'ai inventé la langue. Je sais que ce n'est pas compréhensible pour quelqu'un qui ne connaît pas la langue, c'est pourquoi j'ai inclus l'explication.
isaacg
13

Python, 46 octets

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

Si la chaîne est un palindrome, renvoyez-la. Sinon, placez la première lettre en sandwich autour du résultat récursif pour le reste de la chaîne.

Exemple de ventilation:

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
la source
Je pense que vous pouvez enregistrer un octet si vous utilisez la condition opposée ( s!=s[::-1])
aditsu
@aditsu Cela fonctionne mais l'utilisation d'une multiplication est encore plus courte.
xnor
9

Haskell, 36 octets

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

Plus lisible:

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

Si la chaîne est un palindrome, renvoyez-la. Sinon, placez la première lettre autour du résultat récursif pour la queue de la chaîne.

La chaîne sest divisée en h:tdeuxième garde, ce qui évite un remplissage 1>0pour ce cas. C'est plus court que de le faire s@(h:t)pour l'entrée.

xnor
la source
5

Pyth - 16 12 octets

4 octets enregistrés grâce à @FryAmTheEggman.

FGITW, beaucoup de golf possible.

h_I#+R_Q+k._

Suite de tests .

Maltysen
la source
5

Brachylog , 16 6 5 octets (non concurrent)

:Ac.r

Essayez-le en ligne!

Quand j'ai posté ma réponse initiale, elle était toujours sur l'ancienne implémentation en Java. Comme j'ai tout reprogrammé dans Prolog, cela fonctionne maintenant comme il se doit en premier lieu.

Explication

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

La rétropropagation permet à la première valeur valide de Atrouver la plus courte que vous pouvez concaténer à Input pour en faire un palindrome.

Solution alternative, 5 octets

~@[.r

C'est à peu près la même chose que la réponse ci-dessus, sauf qu'au lieu d'indiquer "la sortie est la concaténation de l'entrée avec une chaîne A", nous déclarons que "la sortie est une chaîne pour laquelle l'entrée est un préfixe de la sortie".

Fatalize
la source
4

JavaScript (ES6), 92 octets

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

Calcule et supprime le chevauchement entre la chaîne d'origine et son inversion.

Neil
la source
4

Rétine, 29 25

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

Essayez-le en ligne!

Un grand merci à Martin pour 11 octets enregistrés!

Cela crée simplement une copie inversée de la chaîne et les étouffe ensemble. La seule partie vraiment fantaisiste de ceci est la méthode d'inversion:, O^#r`.\Gqui se fait en utilisant le mode de tri. Nous trions les lettres de la deuxième chaîne (celles qui ne sont pas des sauts de ligne et qui sont consécutives à la fin de la chaîne, grâce au \G) par leur valeur numérique, qui, puisqu'il n'y a pas de nombre, est 0. Ensuite, nous inversons le ordre des résultats de ce type stable avec le^ option. Tout crédit pour l'utilisation de fantaisie \Gappartient à Martin :)

FryAmTheEggman
la source
3

CJam, 18 ans

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

Essayez-le en ligne

Explication:

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
la source
3

Lua, 89 88 octets

J'ai battu le Javascript! \ o / 1 octet enregistré grâce à @LeakyNun ^^

C'est un programme complet, prend son entrée comme argument de ligne de commande.

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

non golfé

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
la source
Je crois que les parenthèses proches whilepeuvent être supprimées?
Leaky Nun
@LeakyNun sûr qu'ils peuvent ^^
Katenkyo
Tu ne peux pas faire i=i+1end?
Erik the Outgolfer
1
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Malheureusement, je ne peux pas. Il essaierait d'évaluer 1endcomme un nombre hexadécimal. En règle générale, vous ne pouvez pas utiliser [abcdef]directement après un nombre sans qu'il soit considéré comme un hexadécimal. Il y a encore une exception 0x.
Katenkyo
3

Prolog, 43 octets

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

Cela attend une chaîne de codes en entrée, par exemple sur SWI-Prolog 7: a(`hello`).

Explication

Il s'agit essentiellement d'un portage de ma réponse 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
Fatalize
la source
3

Octave, 78 75 octets

Enregistré 3 octets grâce à Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ!

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

ideone échoue toujours pour les fonctions nommées, mais voici un test du code en tant que programme.

gobelet
la source
2

Perl, 37 octets

Basé sur la réponse de xnor.

Comprend +2 pour -lp

Exécuter avec entrée sur STDIN, par exemple

palindromize.pl <<< bonobo

palindromize.pl:

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

05AB1E , 18 octets

Code:

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

Utilise l' encodage CP-1252 . Essayez-le en ligne!

Adnan
la source
1

J, 20 octets

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

Ceci est un verbe monadique. Essayez-le ici. Usage:

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

Explication

J'utilise le fait que la palindromisation de S est S + inverse (P) , où P est le préfixe le plus court de S dont la suppression entraîne un palindrome. En J, c'est un peu maladroit de faire une recherche du premier élément d'un tableau qui satisfait un prédicat; d'où l'indexation.

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

Haskell, 68 octets

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

Exemple d'utilisation: f "abcb"-> "abcba".

Recherchez dans l' initsentrée i(par exemple inits "abcb"-> ["", "a", "ab", "abc", "abcb"]) jusqu'à ce que vous en trouviez une où elle est inversée pour iconstruire un palindrome.

nimi
la source
Ne doit pas r=reversealler avant f i=...?
Erik the Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ: Non, vous pouvez utiliser n'importe quelle commande.
nimi
J'ai réussi en 46 octets. Je parie que cela peut être fait encore mieux.
theonlygusti
@theonlygusti: voir la réponse de xnor .
nimi
1

MATL , 17 16 octets

Librement inspiré de la réponse CJam de @ aditsu .

`xGt@q:)PhttP=A~

Essayez-le en ligne!

Explication

`        % 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
la source
1

Rubis, 44 octets

Cette réponse est basée sur les solutions Python et Haskell de xnor .

f=->s{s.reverse==s ?s:s[0]+f[s[1..-1]]+s[0]}
Sherlock9
la source
Tu ne peux pas faire ==s?s:?
Erik the Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ irb jette un coup si je l'essaye. Doit être quelque chose à voir avec la façon dont il analyse ?entre ?:pour ternaire et la ?x == 'x'substitution utilisée depuis Ruby 1.9
Sherlock9
1

Oracle SQL 11.2, 195 octets

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

Non golfé

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
la source
1

Sérieusement, 34 octets

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

Le dernier caractère est un espace insécable (ASCII 127 ou 0x7F).

Essayez-le en ligne!

Explication:

╩╜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
la source
1

C #, 202 octets

J'ai essayé.

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

Non golfé:

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

}

Quelqu'un peut-il me fournir des idées pour regrouper les deux appels à .Reverse (). ToArray ()? Une méthode distincte est plus d'octets.

SkyPharaoh
la source
0

QBIC , 41 octets

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

Explication:

;_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
la source
0

Haskell, 46 octets

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

Je me demande s'il y a un moyen de supprimer les parenthèses dans (f$tail l)++[l!!0]...

theonlygusti
la source