Two-way Palindromic Closure Generator

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 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]

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)

Answer 5

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 ""<>#&@@.

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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.