Twoim zadaniem jest określenie, ile doskonałego palindromu ma struna. Twój typowy palindrom (np. 12321) to idealny palindrom; jego doskonałość wynosi 1.
Aby określić doskonałość łańcucha, zobaczysz, ile sekcji można podzielić na sekcje, gdzie każda sekcja to palindrom. Jeśli występują niejednoznaczności, takie jak z aaaa
, ponieważ można go podzielić na [aa, aa]
lub [aaaa]
lub [a, aaa]
lub [aaa, a]
, najkrótszy zestaw zastąpi się, dając aaaa
wynik 1, czyli długość najkrótszego zestawu.
Dlatego musisz napisać program lub funkcję, która pobierze jedno niepuste wejście i wyświetli, jaki jest doskonały (czyli długość najkrótszego zestawu, w którym można go podzielić na miejsce, gdzie każdy element w zestawie jest palindromem).
Przykłady:
1111 -> 1 [1111]
abcb -> 2 [a, bcb]
abcbd -> 3 [a, bcb, d]
abcde -> 5 [a, b, c, d, e]
66a -> 2 [66, a]
abcba-> 1 [abcba]
x -> 1 [x]
ababacab -> 2 [aba, bacab]
bacababa -> 2 [bacab, aba]
26600 -> 3 [2, 66, 00] [my user id] [who has a more perfect user id?]
ababacabBACABABA -> 4 [aba, bacab, BACAB, ABA]
Zauważ, że w przykładach nic w nawiasach kwadratowych nie powinno być częścią wyniku.
ababacab
i odwrotnie,bacababa
wydają się to dobre przypadki testowe.ababacabBACABABA
jest również dobrym przypadkiem testowym (niektóre odpowiedzi na nim się nie udają).Odpowiedzi:
Brachylog , 7 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Galaretka ,
131211 bajtówWypróbuj online!
Okular
"ababacab"
(jako argument)2
źródło
"\"
, ponieważ jest to niepoprawna składnia.ababacab
i jej wstecznegobacababa
.Pyth, 9 bajtów
Zestaw testowy
Tworzy to wszystkie partycje danych wejściowych, od najkrótszych do najdłuższych. Następnie filtruje te partycje przy niezmienniczości pod filtrowaniem elementów na niezmienniczości przy odwróceniu. Na koniec bierzemy pierwszy element filtrowanej listy partycji i zwracamy jej długość.
Aby wyjaśnić tę skomplikowaną krok, zacznijmy niezmienności pod odwróceniu:
_I
. To sprawdza, czy jego wejście jest palindromem, ponieważ sprawdza, czy cofanie zmienia wartość.Następnie, filtrowanie palindromicity:
_I#
. Pozwoli to zachować tylko palindromiczne elementy listy.Następnie sprawdzamy niezmienności pod filtrowanie palindromicity:
_I#I
. Jest to prawdą wtedy i tylko wtedy, gdy wszystkie elementy listy są palindromami.Wreszcie możemy filtrować na listach, gdzie wszystkie elementy listy są Palindromy:
_I#I#
.źródło
Haskell , 83 bajty
Wypróbuj online!
Wykorzystuje świetną wskazówkę Zgarb do generowania partycji łańcuchowych .
źródło
Clojure, 111 bajtów
Dzieli się na wszystkich możliwych pozycjach, a gdy pierwsza część jest palindromem, przechodzi do podziału na resztę ciągu.
Wypróbuj online .
Ungolfed, używa makra ostatniego wątku
->>
.Niejasna wersja, proszę nie pisać takiego kodu: D
źródło
f
musi nazywać się w obrębie do:(f b)
. Na pozycji przywołania ogona możesz użyćrecur
.defn
przyfn
i po prostu mieć funkcję.(fn f[s]( ... ))
? Och, prawda. Dzięki temu oszczędzasz 2 znaki.JavaScript (ES6),
143126124 bajtówZaoszczędzono 2 bajty dzięki Neilowi
Inspirowany metodą NikoNyrh .
Sformatowane i skomentowane
Przypadki testowe
Pokaż fragment kodu
Wstępne podejście,
173168 bajtówDość długa funkcja rekurencyjna, która oblicza wszystkie możliwe partycje ciągu wejściowego.
Sformatowane i skomentowane
Przypadki testowe
Pokaż fragment kodu
źródło
,p=0
,s[p++]?
i,F(s,i,p)
.Galaretka , 10 bajtów
Wypróbuj online!
W jaki sposób?
Wykorzystuje fakt, że
[0]<[0,0]<[0,0,0],...,<[0,...,0,1]<...
- w ten sposób, jeśli posortujemy partycje według klucza „nie jest palindromiczny dla każdej części”, pierwszy wpis będzie cały palindromiczny i ma minimalną długość.
Uwaga: każdy niepusty ciąg długości n będzie zawsze prowadzić w taki klucz z n zer, ponieważ wszystkie długości 1 ciągi są palindromiczna.
źródło
Haskell , 69 bajtów
Definiuje funkcję
f
. Wypróbuj online!Wyjaśnienie
Funkcja pomocnicza infix
x ! y
oblicza listę liczb całkowitych, które są długościami niektórych podziałówreverse x ++ y
na palindromy, w którychreverse x
pozostaje nienaruszona. Gwarantuje się, że zawiera długość minimalnego podziału, jeśli niey
jest pusty. Jak to działa?y
jest niepusty, znak char jest zrywany i wpychany dox
. Jeślix
staje się palindromem, wywołujemy główną funkcjęf
na końcuy
i dodajemy 1, aby uwzględnićx
. Wzywamy również!
do nowegox
iy
nie przegap żadnego potencjalnego podziału.y
jest pusty, zwracamy[0]
(jeden podział o długości 0), jeślix
jest również pusty, i[]
(bez podziału) w przeciwnym razie.Główna funkcja
f
po prostu wywołuje"" ! x
i zajmuje minimum wyników.źródło
JavaScript (Firefox 30-57), 97 bajtów
Port ES6:
Wydaje się to tak proste rozwiązanie, że ciągle myślę, że o czymś zapomniałem, ale przynajmniej mija wszystkie testy.
źródło
Haskell,
139116109 bajtówWciąż gra w golfa w Haskell, ale oto moja najlepsza próba, jaką mogę szybko wymyślić.
(and.map r)
aby usunąć listy podrzędne, które nie zawierają palindromu, w którym długość punktu jest stosowana do listy, a następnie wynikiem jest posortowane, abyśmy mogli złapać głowę, która jest odpowiedzią.Myślałem, że lepsza odpowiedź może być w stanie wykorzystać niedeterministyczny charakter list w Haskell poprzez zastosowanie Aplikacji. Możliwe jest, że można ogolić wiele bajtów z funkcji h za pomocą aplikacji, nawet jeśli musimy zaimportować Control.Applicative. Komentarze do ulepszeń są mile widziane.
AKTUALIZACJA 1
Ogromne oszczędności oparte na przypomnieniu Laikoni o minimalnej funkcji. Usunięcie sortowania faktycznie pozwoliło mi upuścić import Data.List, ponieważ minimum jest zdefiniowane w Prelude!
AKTUALIZACJA 2
Dzięki sugestii nich o użyciu wyrażeń listowych jako przydatnego zamiennika filter.map. To zaoszczędziło mi kilka bajtów. Pożyczyłem też schludną sztuczkę dotyczącą partycji String z odpowiedzi Laikonis i zapisałem tam również kilka bajtów.
źródło
h []=[[]]
ih (x:y)=map ([x]:)
zawierają niepotrzebne białe znaki.head.sort
jestminimum
.filter
&map
:g x=head$sort[length y|y<-h x,and$r<$>y]
.PHP, 319 bajtów
Wersja online
Rozszerzony
Dłuższa wersja bez E_NOTICE i wyświetlenie wynikowej tablicy
źródło
ababacabBACABABA