23
\$\begingroup\$

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.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – BradC
    Oct 15, 2018 at 20:59
  • \$\begingroup\$ @BradC Palindromes and the like are often explained in terms of words, since it's a bit easier to do so. \$\endgroup\$ Oct 15, 2018 at 21:01
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Wheat Wizard
    Oct 15, 2018 at 21:03
  • 2
    \$\begingroup\$ These types of palindromes are known as Generalized Smarandache Palindromes in the literature. \$\endgroup\$
    – borrible
    Oct 16, 2018 at 8:32
  • 2
    \$\begingroup\$ @RosLuP Yes, "true" palindromes are also semi-palindromes, just treat each character/integer as-is with no additional "chunking". \$\endgroup\$
    – BradC
    Oct 18, 2018 at 19:40

16 Answers 16

6
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Change x==x[::-1] to len(x)<2 save 2*2 bytes; 143 bytes \$\endgroup\$
    – tsh
    Oct 16, 2018 at 7:18
4
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ You can get around the issue with odd-length lists with øøε.œ}`, saving 6 bytes. You also seem to have left 30 unused bytes in... \$\endgroup\$
    – Emigna
    Oct 15, 2018 at 20:01
  • \$\begingroup\$ @Emigna the no-ops at the end are to comply with the challenge's restricted source requirement \$\endgroup\$ Oct 15, 2018 at 21:44
  • \$\begingroup\$ @KamilDrakari: Oh right. Forgot that part. Good news is that the 6-byte save will be 12 bytes then :) \$\endgroup\$
    – Emigna
    Oct 16, 2018 at 5:49
  • \$\begingroup\$ @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 ε }. :) \$\endgroup\$ Oct 16, 2018 at 6:25
  • \$\begingroup\$ @KevinCruijssen: Ah cool. I didn't know that. \$\endgroup\$
    – Emigna
    Oct 16, 2018 at 6:30
4
\$\begingroup\$

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.

\$\endgroup\$
0
4
\$\begingroup\$

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):
          Ɗ      -   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?
\$\endgroup\$
0
4
\$\begingroup\$

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.

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

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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Or just return 1 \$\endgroup\$
    – Jo King
    Oct 16, 2018 at 23:09
  • \$\begingroup\$ Why s(x) defined twice? \$\endgroup\$
    – Dr Y Wit
    Oct 25, 2018 at 16:34
  • \$\begingroup\$ Because they say count as palindrome... but is possible define one function with the same name??? \$\endgroup\$
    – user58988
    Oct 27, 2018 at 13:35
  • \$\begingroup\$ @RosLuP Yes you can. The second one just overwrites the first \$\endgroup\$
    – Jo King
    Oct 27, 2018 at 23:31
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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)) //(
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
    }
  }
\$\endgroup\$
2
  • \$\begingroup\$ The challenge requires that your code be a semi-palindrome as well. That's most the fun in the challenge. \$\endgroup\$
    – Wheat Wizard
    Oct 26, 2018 at 23:19
  • \$\begingroup\$ @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? \$\endgroup\$
    – Dr Y Wit
    Oct 29, 2018 at 16:30

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.