29
\$\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\$
4
  • \$\begingroup\$ Is there a limit on the length of the input? \$\endgroup\$
    – user45941
    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\$
    – user45941
    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\$
7
  • 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\$
0
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\$
4
  • \$\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\$
    – bren
    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
  • 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\$
8
  • \$\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\$
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\$
2
  • 1
    \$\begingroup\$ You can shave off 2 byte if you limit to 99 as the last example is only 99 chars long \$\endgroup\$ 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\$ Jul 4 '16 at 14:05
1
\$\begingroup\$

Husk, 12 bytes

►S=↔ΘmoJ'|½Q

Try it online!

-1 from Leo.

\$\endgroup\$
2
  • \$\begingroup\$ Save 1 byte. I feel like more should be possible but couldn't find anything else \$\endgroup\$
    – Leo
    May 19 at 10:36
  • \$\begingroup\$ Huh. I thought Q didn't order by length and it'd fail for some testcase. Nice. \$\endgroup\$
    – Razetime
    May 19 at 10:38
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.