A Semi-palindrome Puzzle

Question

An palindrome is a word that is its own reverse.

Now there are some words that might look like palindromes but are not. For example consider the word sheesh, sheesh is not a palindrome because its reverse is hseehs which is different, however if we consider sh to be a single letter, then it's reverse is sheesh. This kind of word we will call a semi-palindrome.

Specifically a word is a semi-palindrome if we can split up the word in to some number of chunks such that when the order of the chunks are reversed the original word is formed. (For sheesh those chunks are sh e e sh) We will also require no chunk contains letters from both halves of the word (otherwise every word would be a semi-palindrome). For example rear is not a semi-palindrome because r ea r has a chunk (ea) that contains letters from both sides of the original word. We consider the central character in an odd length word to be on neither side of the word, thus for words with odd length the center character must always be in it's own chunk.

Your task will be to take a list of positive integers and determine if they are a semi-palindrome. Your code should output two consistent unequal values, one if the input is a semi-palindrome and the other otherwise. However the byte sequence of your code must be a semi-palindrome itself.

Answers will be scored in bytes with fewer bytes being better.

Test-cases

[] -> True
[1] -> True
[2,1,2] -> True
[3,4,2,2,3,4] -> True
[3,5,1,3,5] -> True
[1,2,3,1] -> False
[1,2,3,3,4,1] -> False
[11,44,1,1] -> False
[1,3,2,4,1,2,3] -> False

Program to generate more testcases.

---

borrible pointed out that these are similar to generalized Smarandache palindromes. So if you want to do some further reading that's one place to start.

Answer 1

Retina 0.8.2, 85 69 bytes

M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)|M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)

Try it online! Explanation:

M`

Selects Match mode. In fact, Retina defaults to Match mode for a single-line program, but the second copy of the code would always match if not for these extra characters.

^

Match must start at the beginning.

(.+,)*

Capture a number of runs of characters. Each run must end in a comma.

(\d+,)?

Optionally match a run of digits and a comma.

(?<-1>\1)*

Optionally match all of the captures in reverse order, popping each one as it is matched.

$

Match must end at the end.

(?(1)^)

Backtrack unless all of the captures were popped. It works by requiring the match to still be at the start of the string if we have an unpopped capture, which is impossible.

Answer 2

Jelly, 27 23 bytes

ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ

Returns 1 for semi-palindromes, 0 otherwise.

Try it online!

How it works

ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ  Main link. Argument: A (array)

          Π             Invalid token. Everything to its left is ignored.
           ŒH            Halve; divide A into two halves similar lengths. The middle
                         element (if there is one) goes into the first half.
             Ḣ           Head; extract the first half.
              ŒṖ         Generate all partitions of the first half.
                U        Upend; reverse each chunk of each partition.
                         Let's call the result C.

                     Ṛ   Yield R, A reversed.
                   Ƒ€    Fixed each; for each array P in C, call the link to the left
                         with arguments P and R.
                         Return 1 if the result is P, 0 if not.
                 ṁ@          Mold swapped; replace the n integers of C, in reading
                             order, with the first n integers of R.
                     Ẹ   Exists; check if one of the calls returned 1.

Answer 3

Python 2, 157 153 147 143 bytes

-4 bytes thanks to tsh.

s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)
s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)

Try it online!

Answer 4

05AB1E, 59 47 43 41 bytes

2äøø€.œ`âʒ`RQ}gĀIg_^q2äøø€.œ`âʒ`RQ}gĀIg_^

-12 bytes thanks to @Emigna.

Try it online or verify all test cases.

Explanation:

2ä               # Split the input into two parts
                 #  i.e. [3,4,2,0,2,3,4] → [[3,4,2,0],[2,3,4]]
  øø             # Zip twice without filler
                 # This will remove the middle item for odd-length inputs
                 #  i.e. [[3,4,2,0],[2,3,4]] → [[3,2],[4,3],[2,4]] → [[3,4,2],[2,3,4]]
    €.œ          #  Then take all possible partitions for each inner list
                 #   i.e. [[3,4,2],[2,3,4]]
                 #    → [[[[3],[4],[2]],[[3],[4,2]],[[3,4],[2]],[[3,4,2]]],
                 #       [[[2],[3],[4]],[[2],[3,4]],[[2,3],[4]],[[2,3,4]]]]
`                # Push both lists of partitions to the stack
 â               # Take the cartesian product (all possible combinations) of the partitions
                 #  i.e. [[[[3],[4],[2]],[[2],[3],[4]]],
                 #        [[[3],[4],[2]],[[2],[3,4]]],
                 #        ...,
                 #        [[[3,4,2]],[[2,3,4]]]]
  ʒ   }          # Filter this list of combinations by:
   `             #  Push both parts to the stack
    RQ           #  Check if the second list reversed, is equal to the first
                 #   i.e. [[3,4],[2]] and [[2],[3,4]] → 1 (truthy)
       gĀ        # After the filter, check if there are any combinations left
                 #  i.e. [[[[3,4],[2]],[[2],[3,4]]]] → 1 (truthy)
         Ig_     # Check if the length of the input was 0 (empty input-list edge-case)
                 #  i.e. [3,4,2,0,2,3,4] → 7 → 0 (falsey)
            ^    # Bitwise-XOR
                 #  i.e. 1 XOR 0 → 1 (truthy)
             q   # Stop the program (and then implicitly output the top of the stack)
2äøø€.œ`âʒ`RQ}gĀIg_^
                 # Everything after the `q` are no-ops to comply to the challenge rules

Answer 5

05AB1E, 37 bytes

Utilizes roughly the same technique Jonathan came up with.

.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

Try it online!

---

.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

Full program. Receives a list from STDIN, outputs 1 or 0 to STDOUT.

.œʒ        }

Filter-keep the partitions that satisfy...

   €gηOZ;îå

This condition: The lengths of each (€g) are stored in a list, whose prefixes (η) are then summed (O), hence giving us the cumulative sums of the lengths list. Then, the ceiled halve of the maximum of that list is pushed onto the stack – but keeping the original list on it as well (Z;î) and if it occurs (å) in the cumulative sums then the function returns truthy.

εÂQ}

For each, compare (Q) a with a reversed, which are pushed separately on the stack by Â. Returns a list of 0s and 1s.

ZĀq

Maximum. If any is truthy, then 1 else 0. End execution. Everything that follows is completely ignored.

Answer 6

Jelly,  33  32 bytes

-1 Thanks to Erik the Outgolfer
Thanks also to Dennis for a bug fix and looking into changing an implementation detail in Jelly.

ẸƇŒḂƇƊ$ƊĊHṀċÄẈṖŒŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ

Semi-palindromes yield 1, others yield 0.

Try it online! (slow as it's \$O(2^n)\$ in input length)

Or see the test-suite.

The only chunks are the ŒḂs ({3^rd & 4^th} vs {29^th & 30^th} bytes), just to allow the code to parse.

How?

All the work is performed by the right-hand side - the "Main Link":

ŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ - Main Link: list
ŒṖ               - all partitions
           Ƈ     - filter keep those for which this is truthy (i.e. non-zero):
          Ɗ      -   last three links as a monad:
  Ẉ              -     length of each
         $       -     last two links as a monad:
   Ä             -       cumulative addition
        Ɗ        -       last three links as a monad:
     Ṁ           -         maximum
      H          -         halve
       Ċ         -         ceiling
    ċ            -     count
              Ƈ  - filter keep those for which this is truthy:
            ŒḂ   -   is palindrome?
               Ẹ - any?

Answer 7

Perl 6, 87 79 bytes

-8 bytes with some tricks from Jo King's answer

$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}#$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}

Try it online!

Port of tsh's JavaScript answer. Returns two different Regex objects.

Answer 8

Python 2, 275 251 205 bytes

-24 bytes thanks to @KevinCruijssen

-44 bytes thanks to @PostLeftGhostHunter

-2 more bytes thanks to @KevinCruijssen

def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])
def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])

Returns True for semi-palindrome, None otherwise

Try it online!

Answer 9

Ruby, 129 bytes

f=->l{!l[1]||(1...l.size).any?{|x|l[0,x]==l[-x,x]&&f[l[x..~x]]}}#f=->l{!l[1]||(1...l.size).any?{|x|l[0,x]==l[-x,x]&&f[l[x..~x]]}}

Try it online!

Answer 10

JavaScript (Node.js), 139 bytes

f=a=>(s=(''+a).replace(/^(.*),((.*),)?\1$/,'$3'))!=a?f(s):/,/.test(s)//^(.*),((.*),)?\1$/,'$3'))!=a?f(s):/,/.test(s)f=a=>(s=(''+a).replace(

Try it online!

Answer 11

C (gcc) (X86), 216 bytes

p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)//p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)

Try it online!

p(L,a,n) returns 0 if array a of length L is a semi-palindrome, 1 otherwise. Given that all prefixes of length >n are already checked, it compares the prefix of length n with the suffix of length n. p(L,a) is the entry point.

Unfortunately, the more interesting solution is longer:

224 bytes

(f(L,a,n))//#define p(L,a)(n=L/2,
int*a,n;
{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}//{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n))//(

Try it online!

Ungolfed:

(f(L,a,n)) //#define p(L,a)(n=L/2,
int*a,n;
{
  return n 
    ? (memcmp(a, a+L-n, n*4) | f(L-2*n, a+n, L/2-n)) &&
      f(L,a,n-1)
    : 1 < L;
} // { ... } 
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n)) //(

Answer 12

Japt, 66 bytes

@¯X eUsXn}a1 "
ʧV?UÊ<2:ßUéV sVÑ
@¯X eUsXn}a1 "
ʧV?UÊ<2:ßUéV sVÑ

Japt Interpreter

Big improvement this version, it actually beats most of the practical languages now. Now operates on an array of integers since the previous method had a bug.

Explanation:

@        }a1         Find the first number n > 0 such that...
 ¯X                   the first n elements
     UsXn             and the last n elements
    e                 are the same

"
ʧV?UÊ<2:ßUéV sVÑ    String literal to make it a Semi-palindrome
@¯X eUsXn}a1 "

ʧV?                 If n >= length of input...
    UÊ<2              return true if the length is less than 2
        :            Otherwise...
          UéV         move n elements from the end of the input to the start
              sVÑ     remove the first 2*n elements
         ß            and repeat on the remaining elements

Answer 13

Perl 6, 81 bytes

($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs#($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs

Try it online!

Returns the regex /../ for True and the regex /^(.+)(.*)$0$/ for False. Works similarly to nwellnhof's answer, but converts the list to a string beforehand.

Answer 14

Brachylog, 21 bytes

ḍ{|b}ᵗ~cᵐ↔ᵈḍ{|b}ᵗ~cᵐ↔

Try it online!

ḍ              Split the input in half, with the second half longer if uneven.
 {|b}ᵗ         Maybe remove the first element of the second half.
      ~cᵐ      Partition both halves.
         ↔ᵈ    Is it possible for one to be the other's reverse?
ḍ{|b}ᵗ~cᵐ↔     The remainder of the program always succeeds.

Answer 15

PHP 237 bytes

function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}#function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}

recursive function, returns true (for input containing less than two elements) or 1 for truthy,
0 for falsy. Try it online (contains breakdown).

Actual code length is 118 bytes; semi-palindrome created via code duplication.

For better performance, replace & with && and insert !$x&& before ++$i.

Answer 16

Scala, 252 bytes

def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}//def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}

Try it online!

PS. Apparently, solution is 2 times longer just to satisfy a requirement that source code is semi palindrome as well.

PPS. Not a code-golf candidate but purely functional solution using pattern matching:

  def f(s:Seq[Int], i:Int=1):Int = {
    (s, i) match {
      case (Nil ,_) => 1
      case (Seq(_), _) => 1
      case (l, _) if l.take(i) == l.takeRight(i) => f(l.slice(i,l.size-i), 1)
      case (l, j) if j < l.size/2 => f(l, i+1)
      case (_, _) => 0
    }
  }