Grube palindromy

15

Palindromy są zabawne, ale niektóre inne łańcuchy zaczynają czuć się pominięte. Możemy przekształcić te struny w masywne palindromy , dzieląc je na palindromiczne tablice kawałków.

Na przykład ciąg "abcabca"nie jest palindromem, jeśli czytamy go znak po znaku, ale mamy trzy różne sposoby, aby uczynić go masywnym palindromem:

["abcabca"]
["a" "bcabc" "a"]
["a" "bc" "a" "bc" "a"]

Jak widać, masywna palindromiczność jest pojęciem bardzo inkluzywnym; każdy łańcuch można przekształcić w masywny palindrom na co najmniej jeden sposób.

Zadanie

Napisz program lub funkcję, która odbiera ciąg jako dane wejściowe i zwraca jego masę palindromiczną , tj. Liczbę jego partycji, które są tablicami palindromicznymi.

Przypadki testowe

 OUTPUT | INPUT
--------+---------------------------------------------
      1 | ""                                          
      1 | "a"                                         
      1 | "ab"                                        
      2 | "aa"                                        
      2 | "aaa"                                       
      3 | "abcabca"                                   
      4 | "abababab"                                  
     28 | "abcabcaabababababcabca"                    
      1 | "bbbbabababbbbababbbaaaaa"                  
     20 | "ababbaaaabababbbaaabbbaa"                  
      5 | "baaabaabababaababaaabbaab"                 
     62 | "bbaaababbabbabbbabaabaabb"                 
      2 | "a man a plan a canal panama"               
     25 | "ama nap lan aca nal pan ama"               
     93 | "SATOR   AREPO   TENET   OPERA   ROTAS"     
    976 | "abcabcaabcabcaabcabcaabcabcaabcabcaabcabca"
  28657 | "ababababababababababaababababababababababa"
2097152 | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

Dodatkowe zasady

  • Możesz założyć, że dane wejściowe będą się składały z 42 lub mniej znaków ASCII do wydrukowania, opcjonalnie otoczonych ogranicznikami napisów w Twoim języku i / lub po których będzie następował nowy wiersz.

  • Dla każdego prawidłowego ciągu wejściowego kod musi zakończyć się w ciągu mniej niż jednej minuty na moim komputerze (Intel Core i7-3770, 16 GiB RAM, Fedora 21).

    Przy odpowiednim algorytmie przestrzeganie tego terminu powinno być łatwe. Jednak najprawdopodobniej nie będziesz mógł iterować wszystkich partycji ciągu wejściowego.

  • Jeśli zdecydujesz się wydrukować wyjście do STDOUT, po nim może być pojedyncza nowa linia.

  • Obowiązują standardowe zasady .

Dennis
źródło

Odpowiedzi:

4

Pyth, 40 34 27 22 bajtów

Lhsmy:bd_df!xb>TbS/lb2

Wypróbuj w tłumaczu online .

Mocno grał w golfa od początkowej 40-bajtowej wersji. Dzięki FryAmTheEggman za wskazanie kilku przydatnych operatorów (dokumentów trudno przeszukiwać!), Które zaoszczędziły mi łącznie 6 bajtów. Dzięki Dennisowi za sprytną oszczędność jednego bajtu, interpretując wynik xjako wartość prawdziwości / fałszu, a nie jako indeks - !xb>Tbzamiast q<bT>Tb.


Jak to działa:

Definiujemy funkcję, yktóra określa wielkość łańcucha bprzez rekurencyjne wywoływanie się na podciągach b. Funkcje są automatycznie zapamiętywane w Pyth, więc rekursja ma bardzo małe obciążenie czasowe.

L                              def y(b): return ___
                 S/lb2         The range [1,2,...,len(b)/2]
          f!xb>Tb              Filter n for which b[:n] == b[-n:]
   m                           Map each n in the list to...
    y:bd_d                     y(b[d:-d])       
 hs                            Take the sum and add one (implicit return)
Sam Cappleman-Lynes
źródło
Tak, większość nauki Pyth jest wspólna / próba i błąd / czytanie leksykonu, dobra praca z golfem to dużo więcej! :)
FryAmTheEggman
1
1. Możesz zapisać dwa bajty, przesyłając funkcję. Nie trzeba z tym dzwonić yz. 2. Zamiast dwóch map i filtra można użyć jednej mapy i warunkowego ( link ), który oszczędza trzy bajty.
Dennis
2

CJam ( 41 39 bajtów)

qM{_,2/,\f{\~_2$>@2$<@~)/(@=\M*j*}1b)}j

Demo online

Jest to „chętne” w tym sensie, że znajduje liczbę masywnych palindromów dla każdego „centralnego” łańcucha (tj. Wynik usunięcia tej samej liczby znaków z obu końców oryginalnego łańcucha), ale ponieważ korzysta z automatycznego zapamiętywania jkażdy operator jest obliczany tylko raz, co daje bardzo szybki program (i pozwala zaoszczędzić kilka znaków na implementacji niepamiętanej).

Dzięki Dennisowi za oszczędność jednego bajtu.

Peter Taylor
źródło
1

Mathematica, 77 72 57 bajtów

1+Tr[#0/@ReplaceList[#,{a__,b___,a__}:>{b}]]&@*Characters
alephalpha
źródło
1

Perl, 86 bajtów

Kod 84 bajtów + 2 przełączniki

Musi być krótsza metoda, ale oto:

perl -lpe 'sub c{my($x,$i)=@_;$x=~/^(.{$i})(.*)\1$/&&c($2,0*++$s)while++$i<length$x}c$_;$_=++$s'

Pobiera dane wejściowe ze STDIN, jeden ciąg w wierszu.

Objaśnienie: W przypadku wartości 1<=$i<length(input string)używa wyrażenia regularnego, /^(.{$i})(.*)\1$/aby uzyskać lewą i prawą porcję i zwiększa liczbę. Następnie rekurencyjnie robi to samo dla środkowej części łańcucha.

svsd
źródło