Palindrom to słowo, które jest jego własną odwrotnością.

Teraz są słowa, które mogą wyglądać jak palindromy, ale nie są. Na przykład rozważ słowo sheesh, sheeshnie jest palindromem, ponieważ jego odwrotność jest hseehsinna, jednak jeśli uważamy, że shjest to jedna litera, to odwrotnie sheesh. Tego rodzaju słowo nazwiemy półpalindromem.

W szczególności słowo jest pół-palindromem, jeśli możemy podzielić je na pewną liczbę fragmentów, tak że gdy kolejność fragmentów zostanie odwrócona, powstanie oryginalne słowo. (Dla sheeshtych fragmentów są sh e e sh) Będziemy również wymagać, aby żaden fragment nie zawierał liter z obu połówek słowa (w przeciwnym razie każde słowo byłoby pół-palindromem). Na przykład rearnie jest pół-palindromem, ponieważ r ea rma fragment ( ea), który zawiera litery z obu stron oryginalnego słowa. Uważamy, że centralny znak słowa o nieparzystej długości nie znajduje się po żadnej stronie słowa, dlatego w przypadku słów o nieparzystej długości znak środkowy musi zawsze znajdować się we własnej części.

Twoim zadaniem będzie sporządzenie listy liczb całkowitych dodatnich i ustalenie, czy są one półpalindromem. Twój kod powinien wypisywać dwie spójne nierówne wartości, jedną, jeśli dane wejściowe są semi-palindromem, a drugą w przeciwnym razie. Jednak sekwencja bajtów kodu musi być sama w sobie półpalindromem .

Odpowiedzi będą oceniane w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

[] -> 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 do generowania większej liczby przypadków testowych.

Borious zauważył, że są one podobne do uogólnionych palindromów Smarandache . Więc jeśli chcesz trochę dalej czytać, to jedno miejsce na początek.

Retina 0.8.2 , 85 69 bajtów

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

Wypróbuj online! Wyjaśnienie:

M`

Wybiera tryb dopasowania. W rzeczywistości Retina domyślnie ustawia tryb dopasowania dla programu jednowierszowego, ale druga kopia kodu zawsze by pasowała, gdyby nie te dodatkowe znaki.

^

Mecz musi zaczynać się od początku.

(.+,)*

Uchwyć kilka serii znaków. Każdy bieg musi kończyć się przecinkiem.

(\d+,)?

Opcjonalnie dopasuj ciąg cyfr i przecinek.

(?<-1>\1)*

Opcjonalnie dopasuj wszystkie przechwytywania w odwrotnej kolejności, wyświetlając każdy dopasowany.

$

Mecz musi kończyć się na końcu.

(?(1)^)

Cofnij, chyba że wszystkie przechwyty zostały przerwane. Działa, wymagając, aby dopasowanie wciąż znajdowało się na początku łańcucha, jeśli mamy przechwycone niepowodzenie, co jest niemożliwe.

Galaretka , 27 23 bajtów

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

Zwraca 1 dla półpalindromów, 0 w przeciwnym razie.

Wypróbuj online!

Jak to działa

Ṗ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 , 157 153 147 143 bajtów

-4 bajty dzięki 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)

Wypróbuj online!

05AB1E , 59 47 43 41 bajtów

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

-12 bajtów dzięki @Emigna .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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

05AB1E , 37 bajtów

Wykorzystuje w przybliżeniu tę samą technikę, którą wymyślił Jonathan .

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

Wypróbuj online!

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

Pełny program Pobiera listę ze STDIN, wysyła 1 lub 0 do STDOUT.

.œʒ        }

Filtruj zachowaj partycje, które spełniają ...

   €gηOZ;îå

Ten warunek: długości każdego ( €g) są przechowywane na liście, której prefiksy ( η) są następnie sumowane ( O), co daje nam skumulowane sumy listy długości. Następnie pułapowa połowa maksimum tej listy jest wypychana na stos - ale z zachowaniem również oryginalnej listy ( Z;î), a jeśli występuje ( å) w sumach sumarycznych, funkcja zwraca wartość true.

εÂQ}

Dla każdego, porównanie ( Q) z odwrócone, które są wypychane oddzielnie na stosie przez . Zwraca listę 0 i 1 s.Â

ZĀq

Maksymalny. Jeśli coś jest prawdą, to 1 jeszcze 0 . Zakończ wykonywanie. Wszystko, co następuje, jest całkowicie ignorowane.

Python 2 , 275 251 205 bajtów

-24 bajty dzięki @KevinCruijssen

-44 bajty dzięki @PostLeftGhostHunter

-2 więcej bajtów dzięki @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])

Zwraca wartość True dla pół-palindromu, w przeciwnym razie Brak

Wypróbuj online!

Galaretka ,  33  32 bajty

-1 Dzięki Erik the Outgolfer
Podziękowania również dla Dennisa za naprawę błędu i rozważenie zmiany szczegółów implementacji w Jelly.

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

Wydajność półpalindromów, wydajność 1innych 0.

$O(2^n)$

Lub zobacz zestaw testowy .

Tylko kawałki są ŒḂS ({3 ^III -4 ^p } {vs 29 ^p -30 ^p } bajtów), tak aby umożliwić kodu do analizowania.

W jaki sposób?

Cała praca wykonywana jest po prawej stronie - „Główny 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?

Perl 6 , 87 79 bajtów

-8 bajtów z kilkoma sztuczkami z odpowiedzi Jo Kinga

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

Wypróbuj online!

Odpowiedź portu JavaScript w tsh. Zwraca dwa różne obiekty Regex.

Ruby , 129 bajtów

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

Wypróbuj online!

JavaScript (Node.js) , 139 bajtów

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

Wypróbuj online!

C (gcc) (X86), 216 bajtów

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)

Wypróbuj online!

p(L,a,n)zwraca 0, jeśli tablica adługości Ljest półpalindromem, 1 w przeciwnym razie. Biorąc pod uwagę, że wszystkie prefiksy długości >nsą już sprawdzone, porównuje prefiks długości nz sufiksem długości n. p(L,a)jest punktem wejścia.

Niestety, bardziej interesujące rozwiązanie jest dłuższe:

224 bajty

(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))//(

Wypróbuj online!

Nie golfowany:

(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)) //(

Japt , 66 bajtów

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

Japt Interpreter

Duże ulepszenie tej wersji, w rzeczywistości bije teraz większość praktycznych języków. Teraz działa na tablicy liczb całkowitych, ponieważ poprzednia metoda miała błąd.

Wyjaśnienie:

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

PHP 237 bajtów

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

funkcja rekurencyjna, zwraca true(dla danych wejściowych zawierających mniej niż dwa elementy) lub 1dla prawdy,
0dla fałszu. Wypróbuj online (zawiera podział).

Rzeczywista długość kodu wynosi 118 bajtów; półpalindrom utworzony przez duplikację kodu.

Dla lepszej wydajności, należy wymienić &z &&i wstawić !$x&&przed ++$i.

Scala, 252 bajty

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}

Wypróbuj online!

PS. Najwyraźniej rozwiązanie jest 2 razy dłuższe tylko po to, aby spełnić wymóg, że kod źródłowy jest również półpalindromem.

PPS. Nie kandydat na golfa, ale czysto funkcjonalne rozwiązanie wykorzystujące dopasowanie wzorca:

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

Perl 6 , 81 bajtów

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

Wypróbuj online!

Zwraca wyrażenie regularne /../dla wartości True i wyrażenie regularne /^(.+)(.*)$0$/dla wartości False. Działa podobnie do odpowiedzi nwellnhof , ale wcześniej konwertuje listę na ciąg znaków.