A Semi-palindrome Puzzle

Post Left Ghost Hunter 10/15/2018. 11 answers, 1.299 views
code-golf decision-problem restricted-source

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.

11 Answers


ovs 10/16/2018.

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!


Kevin Cruijssen 10/16/2018.

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

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):
          Ɗ      -   last three links as a monad:
  Ẉ              -     length of each
         $       -     last two links as a monad:
   Ä             -       cumulative addition
        Ɗ        -       last three links as a monad:
     Ṁ           -         maximum
      :2         -         integer divide by two
    ċ            -         count
              Ƈ  - filter keep those for which this is truthy:
            ŒḂ   -   is palindrome?
               Ẹ - any?

G B 10/16/2018.

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!


tsh 10/16/2018.

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!


nwellnhof 10/16/2018.

Perl 6, 87 bytes

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

Try it online!

Port of tsh's JavaScript answer.


Kamil Drakari 10/16/2018.

Japt, 92 bytes

å+ íUÔå+ mÔ,È¥YÃbÈÃÄ"
Ê<2?1:UÊ¥V?0:ßUsV ÔsV Ô
å+ íUÔå+ mÔ,È¥YÃbÈÃÄ"
Ê<2?1:UÊ¥V?0:ßUsV ÔsV Ô

Japt Interpreter

Not great, but I'm just happy it works. Takes input as a comma-delimited string (or any other delimiter).

Explanation:

                bÈÃÄ       Find the first number n
å+ íUÔå+ mÔ                such that the first n and last n characters
           ,È¥YÃ           are the same

"                            
Ê<2?1:UÊ¥V?0:ßUsV ÔsV Ô    String literal to make it a Semi-palindrome
å+ íUÔå+ mÔ,È¥YÃbÈÃÄ"

Ê<2?1                      If the input was 0 or 1 characters long, then it's a Semi-palindrome
     :UÊ¥V?0               Else if the "match" was the whole input then it's not a Semi-palindrome
            :ßUsV ÔsV Ô    Else remove the matched portion and check the rest

Titus 10/16/2018.

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.


HighResolutionMusic.com - Download Hi-Res Songs

1 (G)I-DLE

POP/STARS flac

(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
2 The Chainsmokers

Beach House flac

The Chainsmokers. 2018. Writer: Andrew Taggart.
3 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
4 Nicki Minaj

No Candle No Light flac

Nicki Minaj. 2018. Writer: Denisia “Blu June” Andrews;Kathryn Ostenberg;Brittany "Chi" Coney;Brian Lee;TJ Routon;Tushar Apte;ZAYN;Nicki Minaj.
5 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
6 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.
7 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
8 BTS

Waste It On Me flac

BTS. 2018. Writer: Steve Aoki;Jeff Halavacs;Ryan Ogren;Michael Gazzo;Nate Cyphert;Sean Foreman;RM.
9 BlackPink

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
10 Fitz And The Tantrums

HandClap flac

Fitz And The Tantrums. 2017. Writer: Fitz And The Tantrums;Eric Frederic;Sam Hollander.
11 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
12 Kelly Clarkson

Never Enough flac

Kelly Clarkson. 2018. Writer: Benj Pasek;Justin Paul.
13 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
14 Anne-Marie

Rewrite The Stars flac

Anne-Marie. 2018. Writer: Benj Pasek;Justin Paul.
15 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
16 Imagine Dragons

Machine flac

Imagine Dragons. 2018. Writer: Wayne Sermon;Daniel Platzman;Dan Reynolds;Ben McKee;Alex Da Kid.
17 Little Mix

The Cure flac

Little Mix. 2018.
18 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
19 Rita Ora

Velvet Rope flac

Rita Ora. 2018.
20 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.

Related questions

Hot questions

Language

Popular Tags