15
\$\begingroup\$

Given a string l, find all palindromic substrings p of l (including duplicates and single character strings). Next, rearrange all sub-strings in p into a valid palindrome (there may be multiple correct answers). If it is not possible to rearrange p into a single palindrome, your program may have undefined behavior (error, stack-overflow, exiting, hanging/untimely murder of John Dvorak, etc...)


Examples

Valid Test Cases

l = anaa
p = ['a', 'n', 'a', 'a', 'aa', 'ana']
result = anaaaaana or aanaaanaa or aaananaaa

l = 1213235
p = ['1', '2', '1', '3', '2', '3', '5', '121', '323']
result = 1213235323121

l = racecar
p = ['r', 'a', 'c', 'e', 'c', 'a', 'r', 'cec', 'aceca', 'racecar']
result = racecarcecaacecracecar (there are others)

l = 11233
p = ['1', '11', '1', '2', '3', '33', '3']
result = 113323311 or 331121133

l = abbccdd
p = ['a', 'b', 'bb', 'b', 'c', 'cc', 'c', 'd', 'dd', 'd']
result = bbccddaddccbb or ccbbddaddbbcc or (etc...)

l = a
p = ['a']
result = a

Invalid Test Cases (Not Possible)

l = 123456789
p = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
result = <not possible, behavior undefined>

l = hjjkl
p = ['h', 'j', 'jj', 'j', 'k', 'l']
result = <not possible, behavior undefined>

l = xjmjj
p = ['x', 'j', 'jmj', 'm', 'j', 'jj', 'j']
result = <not possible, behavior undefined>

Rules

  • If the input word is a palindrome itself, it will always be valid as input.
  • Only one substring should be returned, which one you choose is arbitrary as long as it's valid.
  • If the input has no viable output, your code may have undefined behavior.
  • Inputs will only contain ASCII-Printable characters between 0x20-0x7E.
  • This is , lowest byte-count is the winner.
\$\endgroup\$
7
  • 1
    \$\begingroup\$ The first proposed result for "abbccdd" is wrong: the last two letters should be "bb", not "dd". \$\endgroup\$
    – Fatalize
    Feb 13, 2018 at 15:47
  • \$\begingroup\$ Can we return an array of substrings, rather than a single string? \$\endgroup\$
    – Shaggy
    Feb 13, 2018 at 17:54
  • \$\begingroup\$ Can I take a list of characters as input? \$\endgroup\$
    – alephalpha
    Feb 14, 2018 at 1:49
  • 1
    \$\begingroup\$ By hanging being acceptable behavior, do you mean hanging the person who gave it input? \$\endgroup\$ Feb 14, 2018 at 8:35
  • \$\begingroup\$ @JohnDvorak clarified. \$\endgroup\$ Feb 14, 2018 at 16:52

12 Answers 12

8
\$\begingroup\$

Brachylog, 10 bytes

{s.↔}ᶠpc.↔

Try it online!

Fails (i.e. prints false.) if not possible.

Explanation

{   }ᶠ         Find all…
 s.              …substrings of the input…
  .↔             …which are their own reverse
      p        Take a permutation of this list of palindromes
       c.      The output is the concatenation of this permutation
        .↔     The output is its own reverse
\$\endgroup\$
3
\$\begingroup\$

Coconut, 140 bytes

s->p(map(''.join,permutations(p(v for k in n(s)for v in n(k[::-1])))))[0]
from itertools import*
n=scan$((+))
p=list..filter$(x->x==x[::-1])

Try it online!

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

JavaScript (ES6), 193 bytes

"Look Ma, no permutation built-in!" (So yes ... it's long ...)

Returns an empty array if there's no solution.

f=(s,a=[].concat(...[...s].map((_,i,a)=>a.map((_,j)=>s.slice(i,j+1)))).filter(P=s=>[...s].reverse().join``==s&&s),m=S=[])=>S=a.map((_,i)=>f(s,b=[...a],[...m,b.splice(i,1)]))>''?S:P(m.join``)||S

Demo

f=(s,a=[].concat(...[...s].map((_,i,a)=>a.map((_,j)=>s.slice(i,j+1)))).filter(P=s=>[...s].reverse().join``==s&&s),m=S=[])=>S=a.map((_,i)=>f(s,b=[...a],[...m,b.splice(i,1)]))>''?S:P(m.join``)||S

console.log(f('anaa'))
console.log(f('1213235'))
console.log(f('hjjkl'))
console.log(f('a'))

How?

Let's split the code into smaller parts.

We define P(), a function that returns s if s is a palindrome, or false otherwise.

P = s => [...s].reverse().join`` == s && s

We compute all substrings of the input string s. Using P(), we isolate the non-empty palindromes and store them in the array a.

a = [].concat(...[...s].map((_, i, a) => a.map((_, j) => s.slice(i, j + 1)))).filter(P)

The main recursive function f() takes a as input and compute all its permutations. It updates S whenever the permutation itself is a palindrome (once joined), and eventually returns the final value of S.

f = (                        // given:
  a,                         //   a[] = input array
  m = S = []                 //   m[] = current permutation of a[]
) =>                         //   and S initialized to []
  S = a.map((_, i) =>        // for each element at position i in a[]:
    f(                       //   do a recursive call with:
      b = [...a],            //     b[] = copy of a[] without the i-th element
      [...m, b.splice(i, 1)] //     the element extracted from a[] added to m[]
    )                        //   end of recursive call
  ) > '' ?                   // if a[] was not empty:
    S                        //   let S unchanged
  :                          // else:
    P(m.join``) || S         //   update S to m.join('') if it's a palindrome
\$\endgroup\$
2
\$\begingroup\$

Jelly, 13 bytes

ŒḂÐf
ẆÇŒ!F€ÇḢ

Try it online!

Prints 0 in the invalid case.

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

Stax, 13 bytes

绬►Ö∞j∞:Æ╘τδ

Run test cases (It takes about 10 seconds on my current machine)

This is the corresponding ascii representation of the same program.

:e{cr=fw|Nc$cr=!

It's not quite pure brute-force, but it's just as small as the brute-force implementation I wrote. That one crashed my browser after about 10 minutes. Anyway, here's how it works.

:e                  Get all contiguous substrings
  {cr=f             Keep only those that are palindromes
       w            Run the rest of the program repeatedly while a truth value is produced.
        |N          Get the next permutation.
          c$        Copy and flatten the permutation.
            cr=!    Test if it's palindrome.  If not, repeat.
                    The last permutation produced will be implicitly printed.
\$\endgroup\$
2
\$\begingroup\$

Ruby, 131 123 120 bytes

->s{m=->t{t==t.reverse}
(1..z=s.size).flat_map{|l|(0..z-l).map{|i|s[i,l]}}.select(&m).permutation.map(&:join).detect &m}

Try it online!

A lambda accepting a string and returning a string. Returns nil when no solution exists.

-5 bytes: Replace select{|t|l[t]} with select(&l)

-3 bytes: Replace map{..}.flatten with flat_map{...}

-1 bytes: Loop over substring length and substring start, instead of over substring start and substring end

-2 bytes: Declare z at first use instead of beforehand

->s{
  l=->t{t==t.reverse}        # Lambda to test for palindromes
  (1..z=s.size).flat_map{|l| # For each substring length
    (0..z-l).map{|i|         # For each substring start index
      s[i,l]                 # Take the substring
    }
  }                          # flat_map flattens the list of lists of substrings
  .select(&l)                # Filter to include only palindromic substrings
  .permutation               # Take all orderings of substrings
  .map(&:join)               # Flatten each substring ordering into a string
  .detect &l                 # Find the first palindrome
}
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 13 12 bytes

ŒʒÂQ}œJʒÂQ}¤

Try it online!

-1 byte thanks to Magic Octopus Urn and Emigna.

\$\endgroup\$
5
  • \$\begingroup\$ J automatically factorizes so you don't need €J just J; also, you're supposed to return one of the palindromes, not all. Try it online! is valid for the same byte-count. \$\endgroup\$ Feb 13, 2018 at 15:49
  • \$\begingroup\$ @MagicOctopusUrn Fixed, thanks ! \$\endgroup\$ Feb 13, 2018 at 15:53
  • \$\begingroup\$ Ùć could be ¤ (or a number of other options) \$\endgroup\$
    – Emigna
    Feb 13, 2018 at 17:26
  • \$\begingroup\$ @Emigna not sure why I didn't see the Ù wasn't needed. \$\endgroup\$ Feb 13, 2018 at 17:44
  • \$\begingroup\$ Enigma My bad, for an unknown reason I thought we were supposed to display all of the unique palindromes, hence the original Ù. Thanks for the tip, fixed ! \$\endgroup\$ Feb 14, 2018 at 9:24
1
\$\begingroup\$

Pyth, 13 bytes

h_I#sM.p_I#.:

Try it online!

-1 byte thanks to Mr. Xcoder

\$\endgroup\$
2
  • \$\begingroup\$ Lol I was so sure nobody else uses Pyth that I submitted my own separate answer (now deleted) prior to seeing yours. You can use h_I#sM.p_I#.: or e_IDsM.p_I#.: for 13 bytes. \$\endgroup\$
    – Mr. Xcoder
    Feb 13, 2018 at 16:25
  • \$\begingroup\$ @Mr.Xcoder Oh haha :P yeah I hardly ever use Pyth, don't know why I decided to use it. Thanks! \$\endgroup\$
    – hyper-neutrino
    Feb 13, 2018 at 16:51
1
\$\begingroup\$

Python 3, 167 bytes

lambda a:g(sum(k,[])for k in permutations(g(a[i:j+1]for i in range(len(a))for j in range(i,len(a)))))[0]
g=lambda k:[e for e in k if e==e[::-1]]
from itertools import*

Try it online!

-2 bytes thanks to Mr. Xcoder

\$\endgroup\$
1
  • \$\begingroup\$ You can use a[i:j+1] if you then use for j in range(i,len(a)) instead, for -2 bytes. \$\endgroup\$
    – Mr. Xcoder
    Feb 13, 2018 at 16:41
1
\$\begingroup\$

Japt, 19 bytes

Hampered by Japt not (yet) being able to get all substrings of a string (and partly by my current levels of exhaustion!).

Outputs undefined if there's no solution.

Êõ@ãX fêQÃc á m¬æêQ

Try it


Explanation

                        :Implicit input of string U
Ê                       :Length of U
 õ                      :Range [1,Ê]
  @      Ã              :Pass each X through a function
   ãX                   :  Substrings of U of length X
      f                 :  Filter
       êQ               :    Is it a palindrome?
          c             :Flatten
            á           :Permutations
              m         :Map
               ¬        :  Join to a string
                æêQ     :Get first element that is a palindrome
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Is your question about a list of substring simply to remove ¬ from your answer :P? \$\endgroup\$ Feb 13, 2018 at 18:37
  • 1
    \$\begingroup\$ Thought I could remove but then I would have needed æ_¬êQ so it wouldn't have saved any bytes anyway! \$\endgroup\$
    – Shaggy
    Feb 13, 2018 at 20:13
  • \$\begingroup\$ Hahaha, I'll ensure to be wary of your byte-saving ways from now on ;). I tried removing it myself to check, but realized japt commands don't work like I think they work lol. \$\endgroup\$ Feb 13, 2018 at 20:28
1
\$\begingroup\$

Husk, 12 bytes

ḟS=↔mΣPfS=↔Q

Try it online!

Explanation

ḟS=↔mΣPfS=↔Q  Implicit input, a string.
           Q  List of substrings.
       f      Keep those
        S=↔   that are palindromic (equal to their reversal).
      P       Permutations of this list.
    mΣ        Flatten each.
ḟ             Find an element
 S=↔          that is palindromic.
\$\endgroup\$
0
\$\begingroup\$

J, 53 bytes

[:{:@(#~b"1)@(i.@!@#;@A.])@(#~(0<#*b=.]-:|.)&>)@,<\\.

Try it online!

\$\endgroup\$

Your Answer

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

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