30
\$\begingroup\$

Introduction

For the ones who don't know, a palindrome is when a string is equal to the string backwards (with exception to interpunction, spaces, etc.). An example of a palindrome is:

abcdcba

If you reverse this, you will end up with:

abcdcba

Which is the same. Therefore, we call this a palindrome. To palindromize things, let's take a look at an example of a string:

adbcb

This is not a palindrome. To palindromize this, we need to merge the reversed string into the initial string at the right of the initial string, leaving both versions intact. The shorter, the better.

The first thing we can try is the following:

adbcb
bcbda
^^ ^^

Not all characters match, so this is not the right position for the reversed string. We go one step to the right:

adbcb
 bcbda
 ^^^^

This also doesn't match all characters. We go another step to the right:

adbcb
  bcbda

This time, all characters match. We can merge both string leaving the intact. The final result is:

adbcbda

This is the palindromized string.


The Task

Given a string (with at least one character) containing only lowercase letters (or uppercase, if that fits better), output the palindromized string.


Test cases

Input     Output

abcb      abcba
hello     hellolleh
bonobo    bonobonob
radar     radar
hex       hexeh

This is , so the submission with the least amount of bytes wins!

\$\endgroup\$
7
  • 3
    \$\begingroup\$ Related. \$\endgroup\$
    – Zgarb
    Apr 4 '16 at 18:24
  • 6
    \$\begingroup\$ You should specify that the reversed string has to be merged into the original string with the reversed one at the right. If it can go at left, obonobo would be a better solution to the test case. \$\endgroup\$ Apr 4 '16 at 21:04
  • 2
    \$\begingroup\$ Related 2 \$\endgroup\$
    – Sp3000
    Apr 5 '16 at 1:16
  • 2
    \$\begingroup\$ @LevelRiverSt +1 just because "obonobo" is such an amazing word \$\endgroup\$
    – Nathaniel
    Apr 5 '16 at 12:57
  • 1
    \$\begingroup\$ @Nathaniel Thanks but bono b o nob is an entire sentence. What's the difference between God and Bono? God doesn't wander round Dublin pretending to be Bono ;-) \$\endgroup\$ Apr 5 '16 at 14:07

26 Answers 26

15
\$\begingroup\$

Pyth (commit b93a874), 11 bytes

.VkI_IJ+zbB

Test suite

This code exploits a bug in the current version of Pyth, commit b93a874. The bug is that _IJ+zb is parsed as if it was q_J+zbJ+zb, which is equivalent to _I+zb+zb, when it should (by the design intention of Pyth) be parsed as q_J+zbJ, which is equivalent to _I+zb. This allows me to save a byte - after the bug is fixed, the correct code will be .VkI_IJ+zbJB. I'll explain that code instead.

Basically, the code brute forces over all possible strings until it finds the shortest string that can be appended to the input to form a palindrome, and outputs the combined string.

.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.
\$\endgroup\$
3
  • \$\begingroup\$ How do you come up with such code? It is barely readable and absolutely not understandable by someone who is not acquainted with Pyth. What is the purpose of such a language. \$\endgroup\$
    – anukul
    Apr 6 '16 at 11:20
  • 6
    \$\begingroup\$ @momo The purpose of the language is to write short code in, for fun. It's a recreational activity. I can write it because I have a lot of practice, and because I invented the language. I know it's not understandable to someone who doesn't know the language, which is why I included the explanation. \$\endgroup\$
    – isaacg
    Apr 6 '16 at 15:19
  • \$\begingroup\$ Ah, that explains how you knew of a bug in the language! \$\endgroup\$ Dec 29 '20 at 17:30
13
\$\begingroup\$

Python, 46 bytes

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

If the string is a palindrome, return it. Otherwise, sandwich the first letter around the recursive result for the remainder of the string.

Example breakdown:

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
\$\endgroup\$
2
  • \$\begingroup\$ I think you can save a byte if you use the opposite condition (s!=s[::-1]) \$\endgroup\$ Apr 4 '16 at 21:20
  • \$\begingroup\$ @aditsu That works but using a multiply is yet shorter. \$\endgroup\$
    – xnor
    Apr 4 '16 at 21:25
9
\$\begingroup\$

Haskell, 36 bytes

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

More readably:

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

If the string is a palindrome, return it. Otherwise, sandwich the first letter around the recursive result for the tail of the string.

The string s is split into h:t in the second guard, obviating a filler 1>0 for this case. This is shorter than doing s@(h:t) for the input.

\$\endgroup\$
0
7
\$\begingroup\$

Jelly, 11 10 bytes

ṫỤfU$Ḣœ^;U

Try it online!

How it works

ṫỤ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.
\$\endgroup\$
5
\$\begingroup\$

Pyth - 16 12 bytes

4 bytes saved thanks to @FryAmTheEggman.

FGITW, much golfing possible.

h_I#+R_Q+k._

Test Suite.

\$\endgroup\$
0
5
\$\begingroup\$

Brachylog, 16 6 5 bytes (Non-competing)

:Ac.r

Try it online!

When I posted my initial answer, it was still on the old implementation in Java. Since I have reprogrammed everything in Prolog, it now works as it should have in the first place.

Explanation

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

Backpropagation makes it so that the first valid value for A it will find will be the shortest that you can concatenate to Input to make it a palindrome.

Alternate solution, 5 bytes

~@[.r

This is roughly the same as the above answer, except that instead of stating "Output is the concatenation of the Input with a string A", we state that "Output is a string for which the Input is a prefix of the Output".

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 92 bytes

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

Computes and slices away the overlap between the original string and its reversal.

\$\endgroup\$
4
\$\begingroup\$

Retina, 29 25

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

Try it online!

Big thanks to Martin for 11 bytes saved!

This just creates a reversed copy of the string and smooshes them together. The only really fancy part of this is the reversing method: O^#r`.\G, which is done by using sort mode. We sort the letters of the second string (the ones that aren't newlines and are consecutive from the end of the string, thanks to the \G) by their numeric value, which, since there are no numbers, is 0. Then we reverse the order of the results of this stable sort with the ^ option. All credit for the fancy use of \G belongs to Martin :)

\$\endgroup\$
0
3
\$\begingroup\$

CJam, 18

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

Try it online

Explanation:

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
\$\endgroup\$
3
\$\begingroup\$

Lua, 89 88 Bytes

I beat the Javascript! \o/ Saved 1 byte thanks to @LeakyNun ^^

It's a full program, takes its input as command-line argument.

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

ungolfed

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
\$\endgroup\$
4
  • \$\begingroup\$ I believe the parentheses near while can be removed? \$\endgroup\$
    – Leaky Nun
    Jul 1 '16 at 7:54
  • \$\begingroup\$ @LeakyNun sure they can ^^ \$\endgroup\$
    – Katenkyo
    Jul 1 '16 at 7:58
  • \$\begingroup\$ Can't do i=i+1end? \$\endgroup\$ Jul 2 '16 at 7:02
  • 1
    \$\begingroup\$ @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ Sadly, I can't. It would try to evaluate 1end as an hexadecimal number. Generally, you can't use [abcdef] directly after a number without it being considered an hexadecimal. There's one more exception being 0x. \$\endgroup\$
    – Katenkyo
    Jul 4 '16 at 6:59
3
\$\begingroup\$

Prolog, 43 bytes

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

This expects a codes string as input, e.g. on SWI-Prolog 7: a(`hello`).

Explanation

This is basically a port of my Brachylog answer.

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
\$\endgroup\$
3
\$\begingroup\$

Octave, 78 75 bytes

Saved 3 bytes thanks to Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ!

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

ideone still fails for named functions, but here is a test run of the code as a program.

\$\endgroup\$
0
2
\$\begingroup\$

Perl, 37 bytes

Based on xnor's answer.

Includes +2 for -lp

Run with input on STDIN, e.g.

palindromize.pl <<< bonobo

palindromize.pl:

#!/usr/bin/perl -lp
s/.//,do$0,$_=$&.$_.$&if$_!~reverse
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 18 bytes

Code:

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

Uses CP-1252 encoding. Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pyke, 15 bytes

D_Dlhm>m+#D_q)e

Try it here!

\$\endgroup\$
1
\$\begingroup\$

J, 20 bytes

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

This is a monadic verb. Try it here. Usage:

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

Explanation

I'm using the fact that the palindromization of S is S + reverse(P), where P is the shortest prefix of S whose removal results in a palindrome. In J, it's a little clunky to do a search for the first element of an array that satisfies a predicate; hence the indexing.

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

Haskell, 68 bytes

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

Usage example: f "abcb" -> "abcba".

Search through the inits of the input i (e.g. inits "abcb" -> ["", "a", "ab", "abc", "abcb"]) until you find one where it's reverse appended to i builds a palindrome.

\$\endgroup\$
4
  • \$\begingroup\$ Doesn't r=reverse have to go before f i=...? \$\endgroup\$ Jul 2 '16 at 7:04
  • \$\begingroup\$ @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ: No, you can use any order. \$\endgroup\$
    – nimi
    Jul 3 '16 at 13:28
  • \$\begingroup\$ I managed in 46 bytes. I bet it can be done even better. \$\endgroup\$ Feb 6 '17 at 17:55
  • \$\begingroup\$ @theonlygusti: see xnor's answer. \$\endgroup\$
    – nimi
    Feb 6 '17 at 20:13
1
\$\begingroup\$

MATL, 17 16 bytes

Loosely inspired in @aditsu's CJam answer.

`xGt@q:)PhttP=A~

Try it online!

Explanation

`        % 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
\$\endgroup\$
1
\$\begingroup\$

Ruby, 44 bytes

This answer is based on xnor's Python and Haskell solutions.

f=->s{s.reverse==s ?s:s[0]+f[s[1..-1]]+s[0]}
\$\endgroup\$
2
  • \$\begingroup\$ Can't do ==s?s:? \$\endgroup\$ Jul 2 '16 at 7:05
  • \$\begingroup\$ @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ irb throws a fit if I try it. Must be something to do with how it parses ? between ?: for ternary and the ?x == 'x' substitution used since Ruby 1.9 \$\endgroup\$
    – Sherlock9
    Jul 3 '16 at 16:52
1
\$\begingroup\$

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

Un-golfed

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)
     );
\$\endgroup\$
1
\$\begingroup\$

Seriously, 34 bytes

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

The last character is a non-breaking space (ASCII 127 or 0x7F).

Try it online!

Explanation:

╩╜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
\$\endgroup\$
1
\$\begingroup\$

C#, 202 bytes

I tried.

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

}

Can anyone provide me with any ideas to group the two calls to .Reverse().ToArray() ? A separate method is more bytes.

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 24 bytes

{t@*&{x~|x}'t:x,/:|',\x}

Try it online!

Feels like it could be golfed more...

  • ,\x make list of prefixes of input
  • t:x,/:\' append the reverse of each prefix to the original input, storing in t
  • *&{x~|x}' identify the index of the first item in the list that is a palindrome
  • t@ retrieve that list item and return it from the function
\$\endgroup\$
0
\$\begingroup\$

QBIC, 41 bytes

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

Explanation:

;_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
\$\endgroup\$
0
\$\begingroup\$

Haskell, 46 bytes

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

I'm wondering if there's a way to remove the parenthesis in (f$tail l)++[l!!0]...

\$\endgroup\$
0
\$\begingroup\$

Jelly, 9 bytes

Ṗ;¥ƤUŒḂƇḢ

Try it online!

How it works

Ṗ;¥ƤUŒḂƇḢ - Main link. Takes a string S on the left
    U     - Reverse s
  ¥       - Group the previous 2 links into a dyad f(p, r):
Ṗ         -   Remove the last element of p
 ;        -   Concatenate the truncated p to r
   Ƥ      - Over each prefix p of s, yield f(p, rev(s))
       Ƈ  - Keep those for which the following is true:
     ŒḂ   -   Is a palindrome?
        Ḣ - Take the first
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.