# A Semi-palindrome Puzzle

Post Left Ghost Hunter 10/15/2018. 11 answers, 1.299 views

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.

ovs 10/16/2018.

# Python 2, 157153147 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!

Kevin Cruijssen 10/16/2018.

# 05AB1E, 594743 41 bytes

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

-12 bytes thanks to @Emigna.

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

Cowabunghole 10/15/2018.

# Python 2, 275 251 bytes

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

Try it online!

-24 bytes thanks to @Kevin Cruijssen

This feels a little like cheating, but duplicating the program technically makes it a semi-palindrome, though I'm sure doing so increases the byte count more than necessary. Returns 1 for semi-palindrome, and returns None otherwise.

Neil 10/16/2018.

# 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. Mr. Xcoder 10/16/2018. # 05AB1E, 35 bytes Utilizes roughly the same technique Jonathan came up with. .œʒ€gηOZ2÷å}εÂQ}ZqZ}QÂε}å÷2ZOηg€ʒ.œ Try it online! .œʒ€gηOZ2÷å}εÂQ}ZqZ}QÂε}å÷2ZOηg€ʒ.œ Full program. Receives a list from STDIN, outputs 1 or 0 to STDOUT. .œʒ } Filter-keep the partitions that satisfy...  €gηOZ2÷å 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 floored halve of the maximum of that list is pushed onto the stack – but keeping the original list on it as well (Z2÷) 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. Zq Maximum. If any is truthy, then 1 else 0. End execution. Everything that follows is completely ignored. Jonathan Allan 10/16/2018. # Jelly, 33 bytes ẸƇŒḂƇƊ$Ɗ2:ṀċÄẈṖŒ
ŒṖẈÄċṀ:2Ɗ$ƊƇŒḂƇẸ 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 ({3rd & 4th} vs {30th & 31st} bytes). ### How? All the work is performed by the right-hand side of the newline byte (i.e. the bottom line) - the "Main Link": ŒṖẈÄċṀ:2Ɗ$ƊƇŒḂƇẸ - Main Link: list
ŒṖ               - all partitions
Ƈ     - filter keep those for which this is truthy (i.e. non-zero):