# A Semi-palindrome Puzzle

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.

• Why did you define semi-palindromes using strings but your inputs are arrays of integers? In addition to being confusing, this means we can't test our source code using our own program. Oct 15, 2018 at 20:59
• @BradC Palindromes and the like are often explained in terms of words, since it's a bit easier to do so. Oct 15, 2018 at 21:01
• @BradC Strings tend to introduce weird edge cases, particularly in terms of characters vs bytes. I choose number because they are simpler. I thought words would be easier for explanation purposes. Oct 15, 2018 at 21:03
• These types of palindromes are known as Generalized Smarandache Palindromes in the literature. Oct 16, 2018 at 8:32
• @RosLuP Yes, "true" palindromes are also semi-palindromes, just treat each character/integer as-is with no additional "chunking". Oct 18, 2018 at 19:40

# 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. # 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.  # 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! • Change x==x[::-1] to len(x)<2 save 2*2 bytes; 143 bytes – tsh Oct 16, 2018 at 7:18 # 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  • You can get around the issue with odd-length lists with 2äøøε.œ}, saving 6 bytes. You also seem to have left 30 unused bytes in... Oct 15, 2018 at 20:01 • @Emigna the no-ops at the end are to comply with the challenge's restricted source requirement Oct 15, 2018 at 21:44 • @KamilDrakari: Oh right. Forgot that part. Good news is that the 6-byte save will be 12 bytes then :) Oct 16, 2018 at 5:49 • @Emigna Very smart with the double-zip trick. I was not happy about that part, but this is a lot better! Btw, since the Elixir rewrite the 2-byte commands can be used with € instead of ε }. :) Oct 16, 2018 at 6:25 • @KevinCruijssen: Ah cool. I didn't know that. Oct 16, 2018 at 6:30 # 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. # 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 ({3rd & 4th} vs {29th & 30th} 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):
Ẉ              -     length of each

# 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
}
}

• The challenge requires that your code be a semi-palindrome as well. That's most the fun in the challenge. Oct 26, 2018 at 23:19
• @PostLeftGhostHunter, I added original source code into comment to satisfy the requirement. BTW, what is the fun of making source code semi palindrome? If I'm not wrong, every solution in this thread would be two times shorter without this requirement. Are you aware of any solution not like that? Oct 29, 2018 at 16:30