25
\$\begingroup\$

Introduction

A palindromic closure of an input string is the shortest palindrome that can be constructed out of the input string where the final palindrome starts with the input string.

For this challenge, we will consider a two-way palindromic closure such that

  • Left Palindromic Closure of an input string is the shortest palindrome possible that starts with the input string.
  • Right Palindromic Closure of an input string is the shortest palindrome possible that ends with the input string.
  • Two-way Palindromic Closure of an input string is the shorter of either of Left or Right Palindromic Closure of the input string.

Task

Your task is simple. Given a string (consisting only of printable ASCII, new lines and white spaces), output the two-way palindromic closure of that string. In case of tie, either of the left or right palindromic closures are valid output.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument, and either printing the result to STDOUT (or closest alternative) or returning it as a string.

You can assume that the input will never be an empty string.

Few examples:

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

Initial Idea credit goes to VisualMelon, final idea with help from Martin and Zgarb

The terms palindromic closure, left-pallindromic closure and right-palindromic closure were first used and defined by this paper.

Improve this question
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I would like to see a palindromic solution... \$\endgroup\$
    – ojdo
    Commented Mar 17, 2015 at 11:48
  • 2
    \$\begingroup\$ @ojdo I thought of adding that as a bonus, but I am pretty sure most of the answers would have just used comments to create the palindrome. If some answer can really be a palindrome too, without relying on comments, I would leave a bounty for that answer! \$\endgroup\$
    – Optimizer
    Commented Mar 17, 2015 at 11:49

10 Answers 10

Reset to default
11
\$\begingroup\$

Pyth, 22 19

hfq_TTsm,+z_d+_dzyz

Try it online.

Explanation

The two-way palindromic closure is either of the form AX or XA, where X is the input string and A is a substring of X. I actually has to be a contiguous substring of X, a prefix for the one form, a suffix for the other form. But I don't care about these defails. A substring (contiguous or not) is all I need in 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

Edit

The old version ordered the the strings after filtering by length .olN.... Just realized, that y returns the substrings ordered by length. So these palindromes are already sorted.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Clip, 40

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

Example

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

Explanation

(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.-.
Improve this answer
\$\endgroup\$
0
6
\$\begingroup\$

CJam, 30 bytes

Was really hoping to see a CJam answer by now.. So here it goes :P

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

I really hate that {,}$ block in there, but I get an unordered list of possible palindromes due to the generation algorithm I am using.

Code explanation

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

Try it online here

Improve this answer
\$\endgroup\$
1
  • 6
    \$\begingroup\$ I really hate that {,}$ block in there too! Just kidding, I have no idea what anything in CJam does. \$\endgroup\$
    – Alex A.
    Commented Mar 17, 2015 at 3:31
4
\$\begingroup\$

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]

Can hopefully golf down further. Bits possibly worthy of note:

  • using sum for two list comprehensions in one
  • constructing terms in sorted order to avoid the need for min (suggested by @Jakube)
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The items aren't quite in sorted order, so this fails for strings like a. \$\endgroup\$
    – Sp3000
    Commented Mar 17, 2015 at 1:03
4
\$\begingroup\$

Mathematica, 96 bytes

There must be a more elegant way than this...

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

This defines an unnamed function which takes a string and returns the result.

The basic idea is to

  • Split the string into Characters.
  • Form an array with this list and its reverse.

  • Use pattern matching to find the right palindromic of each of them:

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

    Note that this doesn't actually return a flat list. E.g. for {a,b,c} you'd get

    {a,b,{c,b,a}}

  • Sort the two results by length.

  • Pick the shorter and join it back into a string with ""<>#&@@.
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ It outputs abacaba when the input is abac. The correct answer is cabac. I think you should flatten them before sorting by length. \$\endgroup\$
    – alephalpha
    Commented Mar 17, 2015 at 15:55
  • 1
    \$\begingroup\$ @alephalpha Found a better fix that didn't require changing the code size (and which was actually my intention behind not sorting it). \$\endgroup\$
    – Martin Ender
    Commented Mar 17, 2015 at 16:10
2
\$\begingroup\$

Brachylog (2), 6 bytes, language postdates challenge

~{↔?a}

Try it online!

As usual for Brachylog, this is a function, not a full program.

Explanation

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

As far as I know (it's not my language, but it seems unlikely), a wasn't added to Brachylog for this challenge, but it comes in really handy here. We use the "reverse, and assert it hasn't changed" method to assert that the value we find is a palindrome.

As for why this produces the shortest palindrome, Prolog's (and hence Brachylog's) evaluation order is heavily influenced by the first thing it evaluates. In this case, that's a "reverse" command, and (like most list operations) it sets an evaluation order that aims to minimize the size of the resulting list. As that's the same as the size of the output, the program happily ends up minimizing exactly the right thing by chance, meaning that I didn't need to add any explicit hints.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ a - Adfix wasn't added for this challenge. I had no available symbol with good mnemonics for prefix and suffix, therefore I merged both into adfix which can take subscripts to select prefixes or suffixes only if needed. \$\endgroup\$
    – Fatalize
    Commented Feb 24, 2017 at 13:02
1
\$\begingroup\$

Ruby, 76 + 2 = 78

With command-line flags -pl (the l may not be needed depending on how you're doing input), run

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

Given a string 'abaa', generates the strings 'cbca0acbc' and 'acbc0cbca', where 0 is the unprintable character with ascii code 0. It then deletes one copy of the longest repeated string framing 0 it finds in each, 'a' in the first and 'cbc' in the second, to get the two closures. It then outputs the shortest result.

The only really weird thing about the golfed code is that it shortens the strings in place while sorting them, which we can get away with because min_by only executes the block once per element being compared (both because it's a Schwartzian transform and because there are only two elements to compare).

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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]

To test:

>>> print("\n".join(map(f, ["abcdef", "abcba", "abcb", "cbca"])))
abcdefedcba
abcba
abcba
acbca
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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]

Test:

*Main> mapM_ (putStrLn.f) ["abcdef", "abcba", "abcb", "cbca"]
abcdefedcba
abcba
abcba
acbca
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

J, 66 62 bytes

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

Quite straightforward. The two tricks I use:

The right palindromic closure is the left palindromic closure of the reversed string.

Finding the length of the string with minimum length and palindromity with the expression min(is_palindrome / length).

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

   f 'lama'
lamal

Try it online here.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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