Układanka Semi-palindrome

23

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.

Kreator pszenicy
źródło
2
Dlaczego zdefiniowałeś pół-palindromy za pomocą łańcuchów, ale twoje dane wejściowe są tablicami liczb całkowitych? Oprócz tego, że jest mylący, oznacza to, że nie możemy przetestować naszego kodu źródłowego przy użyciu naszego własnego programu.
BradC
@BradC Palindromes i tym podobne są często wyjaśniane słowami, ponieważ jest to trochę łatwiejsze.
Erik the Outgolfer
@BradC Struny mają tendencję do wprowadzania dziwnych przypadków krawędziowych, szczególnie pod względem znaków vs. bajtów. Wybieram liczbę, ponieważ są one prostsze. Myślałem, że słowa będą łatwiejsze do wyjaśnienia.
Wheat Wizard
2
Te typy palindromów są w literaturze znane jako Palindromy uogólnione Smarandache.
boricious
1
@RosLuP Tak, „prawdziwe” palindromy są również pół-palindromami, po prostu traktuj każdą postać / liczbę całkowitą taką, jaka jest, bez dodatkowych „fragmentów”.
BradC,

Odpowiedzi:

6

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.

Neil
źródło
5

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.
Dennis
źródło
4

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!

ovs
źródło
1
Zmień, x==x[::-1]aby len(x)<2zapisać 2 * 2 bajty; 143 bajty
tsh
4

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
Kevin Cruijssen
źródło
Możesz obejść ten problem z listami nieparzystych za pomocą øøε.œ} `, oszczędzając 6 bajtów.
Wygląda
@Emigna no-ops na końcu mają spełnić ograniczone wymagania źródłowe wyzwania
Kamil Drakari
@KamilDrakari: Oh racja. Zapomniałem tej części. Dobra wiadomość jest taka, że ​​6-bajtowy zapis będzie wtedy
wynosił
@Emigna Bardzo inteligentny dzięki sztuczce z podwójnym zamkiem. Nie byłem zadowolony z tej części, ale jest o wiele lepiej! Przy okazji, ponieważ Elixir przepisał 2-bajtowe polecenia, zamiast nich można użyć ε }. :)
Kevin Cruijssen
@KevinCruijssen: Ah cool. Nie wiedziałem tego
Emigna
4

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.

Pan Xcoder
źródło
3

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!

Cowabunghole
źródło
1
Lub po prostu zwróć 1
Jo King
Dlaczego s (x) zdefiniowano dwukrotnie?
Dr Y Wit
Ponieważ mówią, że liczy się jako palindrom ... ale możliwe jest zdefiniowanie jednej funkcji o tej samej nazwie ???
RosLuP
@RosLuP Tak, możesz. Drugi zastępuje pierwszy
Jo King
3

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?
Jonathan Allan
źródło
3

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.

nwellnhof
źródło
2

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!

GB
źródło
1

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!

tsh
źródło
1

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)) //(
eush77
źródło
1

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
Kamil Drakari
źródło
0

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.

Tytus
źródło
0

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
    }
  }
Dr Y Wit
źródło
Wyzwanie wymaga, aby Twój kod był również półpalindromem. To najbardziej zabawne wyzwanie.
Wheat Wizard
@PostLeftGhostHunter, dodałem oryginalny kod źródłowy do komentarza, aby spełnić wymagania. BTW, jaka jest zabawa w tworzenie półpalindromu kodu źródłowego? Jeśli się nie mylę, każde rozwiązanie w tym wątku byłoby dwa razy krótsze bez tego wymogu. Czy znasz jakieś inne rozwiązanie tego typu?
Dr Y Wit
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.

Jo King
źródło