30
\$\begingroup\$

This is a mirror: |. I just found out that you can stick a mirror in the middle of a string if the string can be mirrored on itself! For example, the string abccba. If you cut it in half the two halves are mirror images of each other:

abc  <-->  cba

So, we can stick a mirror in the middle of the string, and our new string is abc|cba. Sometimes, only part of the string can be mirrored on itself. For example, the string "mirror". The two r's are mirrored, but the rest of the string isn't. That's OK, we'll just remove the parts of the string that don't mirror each other, and we get the following string:

r|r

Some strings could be mirrored in multiple places. For example, "Hello World, xyzzyx". I like having a lot of text reflected in my mirror, so you need to find the best place to put my mirror. In this case, you should output the longer mirrored string and just like our last example, remove everything else. This string becomes:

xyz|zyx

Some strings look like they can be mirrored, but actually can not. If a string cannot be mirrored anywhere, you should output nothing.

The challenge:

Given a string containing only printable-ascii, find the best place to put my mirror. In other words,

Find the largest even-length palindromic substring, then output it with a pipe character '|' in the middle of it.

The input will be 1-50 characters long.

You can assume that the input will not contain mirrors | or newlines. Beyond that, all printable-ascii characters are fair game. If the longest mirrored substring is tied between two substrings, you can choose which one to output. For example, for the string "abba ollo", you must output "ab|ba" or "ol|lo", but it doesn't matter which one you output. Strings are case-sensitive, e.g. "ABba" should not output "AB|ba", it should output the empty string.

Sample IO:

"Hello World"     --> "l|l"
"Programming Puzzles and Code-Golf"     --> Either "m|m" or "z|z"
"abcba"           --> ""
"Hulluh"          --> "ul|lu"
"abcdefggfedcba"  --> "abcdefg|gfedcba"
"abcdefggfabc"    --> "fg|gf"
"AbbA"            --> "Ab|bA"
"This input is a lot like the last one, but with more characters that don't change the output. AbbA" --> "Ab|bA"

As usual, this is code-golf, so standard loopholes apply, and the shortest answer in bytes wins!

\$\endgroup\$
  • \$\begingroup\$ Is there a limit on the length of the input? \$\endgroup\$ – Mego Jul 4 '16 at 1:27
  • \$\begingroup\$ @Mego As long as your algorithm theoretically works on any input, I don't care how long it takes/how much memory it takes. \$\endgroup\$ – DJMcMayhem Jul 4 '16 at 1:36
  • \$\begingroup\$ I asked because vanilla regex engines are only capable of matching palindromes of length up to a specified, finite value (as opposed to arbitrarily-long palindromes), and the possibility of a regex-based solution would depend on whether or not there is an upper bound on the length of the input. \$\endgroup\$ – Mego Jul 4 '16 at 1:40
  • \$\begingroup\$ @Mego Ah, that makes sense. Let's say the input can be up to 50 characters long. How does that sound? \$\endgroup\$ – DJMcMayhem Jul 4 '16 at 2:03

14 Answers 14

9
\$\begingroup\$

Pyth - 19 17 15 13 bytes

Thanks to @FryAmTheEggman for saving me two bytes.

ARRGH the special case for no answer. Solved that!

e_I#jL\|cL2.:

Test Suite.

e                Last element in list, this works out to longest one
  _I             Invariance under reverse, this detect palindrome
   #             Filter
   jL            Map join
    \|           By "|"
    cL2          Map chop in two pieces
     .:Q)        Substrings. Implicit Q). ) makes it do all substrings.
\$\endgroup\$
  • 2
    \$\begingroup\$ Nooooo! Ninja'd to the pyth answer ;_; \$\endgroup\$ – Downgoat Jul 4 '16 at 1:42
  • \$\begingroup\$ Explanation please? :3 \$\endgroup\$ – Downgoat Jul 4 '16 at 1:43
  • \$\begingroup\$ @Downgoat he took all substrings and chop into two, join each pair with |, filter by symmetry, append that to [k] and get the last element (which is the longest) \$\endgroup\$ – busukxuan Jul 4 '16 at 1:47
  • \$\begingroup\$ @Downgoat done. \$\endgroup\$ – Maltysen Jul 4 '16 at 1:48
  • 2
    \$\begingroup\$ :Q) = Bignose \$\endgroup\$ – gcampbell Jul 4 '16 at 8:57
8
\$\begingroup\$

05AB1E, 19 17 14 bytes

Code:

Œévy2ä'|ý©ÂQi®

Explanation:

Π               # Get all substrings of the input
 é               # Sort by length (shortest first)
  vy             # For each element...
    2ä           # Split into two pieces
      '|ý        # Join by "|"
         ©       # Copy this into the register
          Â      # Bifurcate, pushing a and reversed a
           Q     # Check if it's a palindrome
            i®   # If so, push that string again
                 # Implicit, the top element is outputted

Uses the CP-1252 encoding. Try it online!.

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

Python 2, 102 97 bytes

def f(s):h=len(s)/2;r=s[:h]+'|'+s[h:];return s and max(r*(r==r[::-1]),f(s[1:]),f(s[:-1]),key=len)

Rather slow and inefficient... Verify the smaller test cases on Ideone.

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

JavaScript, 100 99 bytes

s=>eval('for(O=i=0;s[i++];O=O[j+j]?O:o)for(o="|",j=0;(S=s[i-1-j])&&S==s[i+j++];o=S+o+S);O[1]?O:""')

or

s=>eval('for(O="",i=0;s[i++];O=O[j+j]||j<2?O:o)for(o="|",j=0;(S=s[i-1-j])&&S==s[i+j++];o=S+o+S);O')
\$\endgroup\$
  • \$\begingroup\$ Just curious, what's the eval for? \$\endgroup\$ – gcampbell Jul 4 '16 at 8:58
  • \$\begingroup\$ @gcampbell eval to avoid return \$\endgroup\$ – edc65 Jul 4 '16 at 9:05
  • \$\begingroup\$ Can't you use the comma operator to avoid return? \$\endgroup\$ – MayorMonty Jul 6 '16 at 21:45
  • \$\begingroup\$ @SpeedyNinja nope. for is not an expression, so it would normally require braces and a return \$\endgroup\$ – jrich Jul 7 '16 at 14:57
3
\$\begingroup\$

Lua, 133 bytes

s=...for i=#s,1,-1 do for j=1,#s-i do m=j+i/2-i%2/2t=s:sub(j,m).."|"..s:sub(m+1,i+j)if t==t.reverse(t)then print(t)return end end end

Verify all testcases on Ideone.com.

\$\endgroup\$
  • 1
    \$\begingroup\$ Use t==t:reverse() to save a byte :) \$\endgroup\$ – Katenkyo Jul 4 '16 at 9:42
2
\$\begingroup\$

Retina, 66 bytes

Byte count assumes ISO 8859-1 encoding.

M!&`(.)+(?<-1>\1)+(?(1)¶)
O$#`.+
$.&
A-2`
^(.)+?(?=(?<-1>.)+$)
$&|

Try it online! (The first line enables testing of several linefeed-separated test cases at once.)

Hmmm, much longer than I would like...

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

JavaScript (ES6), 91

s=>[...s].map((d,i)=>{for(a='|',j=0;d=s[i-j],d&&d==s[i-~j];r=r[j+++j]?r:a)a=d+a+d},r='')&&r

Less golfed

f=s=>
  [...s].map(
    (d,i) => {
    for(a='|', j=0; d=s[i-j], d&&d==s[i-~j]; r = r[j++ +j]? r : a)
      a = d+a+d
    }, r=''
  ) && r

Test

F=
s=>[...s].map((d,i)=>{for(a='|',j=0;d=s[i-j],d&&d==s[i-~j];r=r[j+++j]?r:a)a=d+a+d},r='')&&r

;[["Hello World", "l|l"]
,["Programming Puzzles and Code-Golf", "m|m"]
,["abcba", ""]
,["Hulluh", "ul|lu"]
,["abcdefggfedcba", "abcdefg|gfedcba"]
,["abcdefggfabc", "fg|gf"]
,["AbbA", "Ab|bA"]
,["This input is a lot like the last one, but with more characters that don't change the output. AbbA", "Ab|bA"]]
.forEach(t=>{
  var i=t[0],k=t[1],r=F(i)
  console.log(k==r?'OK ':'KO ',i+' -> '+r,k!=r?'(check '+k+')':'')
})  

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

Perl 5, 105 100 98 + 1 = 106 101 99 bytes

/(?=((.)(?1)?\2)(?{[push@_,$1})(?!))/;($_)=sort{length$b<=>length$a}@_;substr($_,length>>1,0)='|'if$_

I just wanted to give recursive regexes a go. Needs the -p option. Edit: Saved (crossed out 4) 7 bytes thanks to @msh210. (The missing byte is due to a saving that was superseded by @msh210's latest saving.)

\$\endgroup\$
  • \$\begingroup\$ I haven't tested any of these, but probably this can be abbreviated various ways, including: (1) @_=(@_,$1) can be push@_,$1. (2) Omit the newlines and the final ;. (3) I suspect there's a shorter sort condition you can use (if nothing else then at least --- perhaps --- substitute - for <=>) \$\endgroup\$ – msh210 Jul 4 '16 at 17:47
  • \$\begingroup\$ @msh210 Thanks for the first two points but I already tried - and it didn't work (probably needs parens for precedence which defeats the saving). \$\endgroup\$ – Neil Jul 4 '16 at 18:20
  • \$\begingroup\$ Try y...c>>1 or y...c/2 instead of length>>1. (Untested.) \$\endgroup\$ – msh210 Jul 4 '16 at 18:30
  • \$\begingroup\$ @msh210 I obviously should have read the tips for golfing in Perl first... \$\endgroup\$ – Neil Jul 4 '16 at 19:31
  • \$\begingroup\$ I'm guessing your last pair of parens can go, also. \$\endgroup\$ – msh210 Jul 4 '16 at 19:38
2
\$\begingroup\$

Python 2, 91 bytes

f=lambda s,p='':s and max((''<p<=s<p+'\x7f')*(p[::-1]+'|'+p),f(s[1:]),f(s[1:],s[0]+p),key=len)

Replace \x7f with the actual character DEL, which is ASCII 127 (credit to Dennis).

This follows a similar strategy to Dennis's answer of using max and recursively branching to find the longest palindrome interval. But, instead, it finds the left half, checking that the corresponding mirrored right half comes right after it with a self-made startswith.

The function guesses whether the first character is in the mirrored left half. If not, it just drops it and recurses on the remainder. If it is, it's added to to the stack p of reversed characters. If the string ever starts with the stack, the mirror string is generated and considered as a possible longest mirror. To avoid | as an output, only non-empty stacks are considered.

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

Jelly, 17 bytes

ẆŒḂÐfṪœs2j”|µẋLḂ$

Try it online!

Done with help from Mr. Xcoder and DJMcMayhem in chat

How it works

ẆŒḂÐfṪœs2j”|µẋLḂ$ - Main link. Argument s  e.g.    ; 'AbbA'

Ẇ                 - All contiguous sublists
   Ðf             - Keep elements that are...
 ŒḂ               -  Palindromic                   ; [['A'], ['b'], ['b'], ['A'], ['bb'], ['AbbA']]
     Ṫ            - Final element                  ; 'AbbA'
      œs2         - Split into 2 chunks            ; ['Ab', 'bA']
         j”|      - Join with "|"                  ; 'Ab|bA'
            µ     - New link with ^ as argument
              LḂ$ - Is the length odd?             ; 1
             ẋ    - Repeat the string ^ many times ; 'Ab|bA'
\$\endgroup\$
1
\$\begingroup\$

Haskell, 126 111 bytes

(!)=drop
f s|n<-length s=last$"":[a++'|':b|k<-[1..n],t<-map(!s)[1..n-k],let[a,b]=take k<$>[t,k!t],a==reverse b]
\$\endgroup\$
1
\$\begingroup\$

TSQL 227 223 bytes

I hardcoded the length to max 99 bytes, this saved bytes but made it slower. It still have a decent performance though.

Golfed:

DECLARE @t varchar(99)='AbccbA'

,@z char(99)='',@a INT=0,@ INT=0WHILE @a<LEN(@t)SELECT
@z=IIF(LEN(x)>LEN(@z)/2and @t LIKE'%'+x+REVERSE(x)+'%'COLLATE
Thai_bin,x+'|'+REVERSE(x),@z),@=IIF(@=50,1,@+1),@a+=IIF(@=1,1,0)FROM(SELECT
SUBSTRING(@t,@a,@)x)x PRINT @z

Ungolfed:

DECLARE @t varchar(99)='AbccbA'

,@z char(99)='',
@a INT=0,
@ INT=0
WHILE @a<LEN(@t)
  SELECT
    @z=IIF(LEN(x)>LEN(@z)/2and @t LIKE'%'+x+REVERSE(x)+'%'COLLATE Thai_bin,x+'|'
       +REVERSE(x),@z),
    @=IIF(@=99,1,@+1),
    @a+=IIF(@=1,1,0)
  FROM
    (SELECT SUBSTRING(@t,@a,@)x)x

PRINT @z

Fiddle

\$\endgroup\$
  • 1
    \$\begingroup\$ You can shave off 2 byte if you limit to 99 as the last example is only 99 chars long \$\endgroup\$ – Alex Carlsen Jul 4 '16 at 13:55
  • 1
    \$\begingroup\$ @VisualBean thankyou, changed the script to only allow 99 characters, also changed the collation from Thai_CS_AS to thai_bin \$\endgroup\$ – t-clausen.dk Jul 4 '16 at 14:05
0
\$\begingroup\$

Python 2, 149 bytes

R,L,s=range,len,input()
t=max([s[i:j/2+i/2]for i in R(L(s))for j in R(L(s)+1)if s[i:j]==s[i:j][::-1]and(j-i)%2<1],key=L)
print t+'|'*(L(t)>0)+t[::-1]

Try it online

This program finds the first half of the largest palindromic substring of even length, and prints that string, followed by a |, followed by that string reversed. If there is no suitable string, t will be the empty string, and '|'*(L(t)>0) will evaluate to the empty string.

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

Java 8, 294 283 232 bytes

s->{int l=s.length(),i=0,j,z,y=0;String a,b="";for(;i<l;i++)for(j=0;j<=l-i;)if((a=s.substring(i,i+j++)).equals(new StringBuffer(a).reverse()+"")&(z=a.length())%2<1&z>y){y=z;b=a;}return y>0?b.substring(0,y/=2)+"|"+b.substring(y):"";}

Explanation:

Try it here.

s->{                               // Method with String as both parameter and return-type
  int l=s.length(),                //  Length of the input-String
      i=0,j,                       //  Index-integers
      z,y=0;                       //  Temp-integers
  String a,b="";                   //  Temp-Strings
  for(;i<l;i++)                    //  Loop (1) from 0 to `l` (exclusive)
    for(j=0;j<=l-i;                //   Inner loop (2) from 0 to `l-i` (inclusive)
      if((a=s.substring(i,i+j++))  //    Set the current substring to `a`
          .equals(new StringBuffer(a).reverse()+"")
                                   //    If `a` is a palindrome
         &(z=a.length())%2<1       //    And the length of `a` is even
         &z>y){                    //    And the length of `a` is larger than `y`
        y=z;                       //     Change `y` to `z`
        b=a;}                      //     Change `b` to `a`
                                   //   End of inner loop (2) (implicit / single-line body)
                                   //  End of loop (1) (implicit / single-line body)
  return y>0?                      //  If the result-length is not 0:
    b.substring(0,y/=2)+"|"+b.substring(y)
                                   //   Return the result
   :                               //  Else:
    "";                            //   Return an empty String
}                                  // End of method
\$\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.