Idealne palindromy

25

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 aaaawynik 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.

Okx
źródło
Czy pusty ciąg jest prawidłowym wejściem, a jeśli tak, to jakie powinno być wyjście?
Zgarb
8
ababacabi odwrotnie, bacababawydają się to dobre przypadki testowe.
Neil,
@ Nee, a także dobre argumenty, czy możliwy jest algorytm czasu liniowego.
Leaky Nun
@Zgarb Pusty ciąg nie jest prawidłowym wejściem.
Okx
ababacabBACABABAjest również dobrym przypadkiem testowym (niektóre odpowiedzi na nim się nie udają).
Zgarb,

Odpowiedzi:

14

Brachylog , 7 bajtów

~cL↔ᵐLl

Wypróbuj online!

Wyjaśnienie

~cL          Deconcatenate the input into L
  L↔ᵐL       Reversing all elements of L results in L
     Ll      Output = length(L)
Fatalizować
źródło
Pokonałeś mnie ... w moim pierwszym poście lol
Leaky Nun
7
@LeakyNun Wiedziałem, że spróbujesz. W ostatnich miesiącach mogłem odpocząć i poczekać kilka godzin, teraz z tobą muszę odpowiedzieć natychmiast!
Fatalize
9

Galaretka , 13 12 11 bajtów

ŒṖLÞŒḂ € P $ ÐfḢL 
ŒṖLÞṚ € ⁼ $ ÐfḢL
ŒṖṚ € ⁼ $ ÐfL € Ṃ
ŒṖ uzyskać partycje
      Filtr dla partycji, które
  Ṛ € po odwróceniu każdej podsekcji
    ⁼ jest równe partycji
        L € długość każdej udanej partycji
          Ṃ minimum

Wypróbuj online!

Okular

  • Dane wejściowe: "ababacab"(jako argument)
  • Wydajność: 2
Leaky Nun
źródło
3
@Okx cóż, musiałbyś uciec przed nimi.
Leaky Nun
2
Cóż, nie sądzę, że jest to ważne, jeśli nie może zaakceptować ukośników odwrotnych.
Okx,
14
@Okx To jak pisanie łańcucha. Nie można oczekiwać, powiedzmy, programu C działającego z danymi wejściowymi łańcucha "\", ponieważ jest to niepoprawna składnia.
Conor O'Brien
2
Przy okazji, witamy ponownie. :-)
Arnauld
2
Niestety to daje różne odpowiedzi na ababacabi jej wstecznego bacababa.
Neil
6

Pyth, 9 bajtów

lh_I#I#./

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#.

isaacg
źródło
Muszę się wiele nauczyć ...
Leaky Nun
6

Haskell , 83 bajty

f s=minimum[length x|x<-words.concat<$>mapM(\c->[[c],c:" "])s,all((==)=<<reverse)x]

Wypróbuj online!

Wykorzystuje świetną wskazówkę Zgarb do generowania partycji łańcuchowych .

f s = minimum[                               -- take the minimum of the list
    length x |                               -- of the number of partitions in x
    x<-words.concat<$>mapM(\c->[[c],c:" "])s -- where x are all partitions of the input string s
    , all((==)=<<reverse)x                   -- where each partition is a palindrome.
]
Laikoni
źródło
1
Łał! To zadziwiło mnie! Zdecydowanie muszę się dużo nauczyć.
maple_shaft
5

Clojure, 111 bajtów

(defn f[s](if(=()s)0(+(apply min(for[i(range(count s))[a b][(split-at(inc i)s)]:when(=(reverse a)a)](f b)))1)))

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

(defn f [s]
  (if (empty? s)
    0
    (let [results (for[i (range(count s))]
                      (let [[a b] (split-at (inc i) s)]
                         (when (= a (reverse a))
                           (f b))))]
      (->> results        ; Take results (a list of integers and nils),
           (filter some?) ; remove null values (they occur when "a" is not a palindrome)
           (apply min)    ; find the minium value,
           inc))))        ; and increment by one.

Niejasna wersja, proszę nie pisać takiego kodu: D

(defn f [s]
   (->> (f b)
        (when (= a (reverse a)))
        (let [[a b] (split-at (inc i) s)])
        (for[i (range(count s))])
        (filter some?)
        (apply min)
        inc
        (if (empty? s) 0)))
NikoNyrh
źródło
Czy ta wskazówka pomogłaby? W ogóle nie znam Clojure.
Leaky Nun
Zazwyczaj tak, ale w tym przypadku funkcja fmusi nazywać się w obrębie do: (f b). Na pozycji przywołania ogona możesz użyć recur.
NikoNyrh
Można jeszcze wymienić defnprzy fni po prostu mieć funkcję.
Cliffroot
(fn f[s]( ... ))? Och, prawda. Dzięki temu oszczędzasz 2 znaki.
NikoNyrh
5

JavaScript (ES6), 143 126 124 bajtów

Zaoszczędzono 2 bajty dzięki Neilowi

Inspirowany metodą NikoNyrh .

s=>(r=1/0,F=(s,i=1,p=0)=>s[p++]?([...o=s.slice(0,p)].reverse().join``==o&&(s[p]?F(s.slice(p),i+1):r=r<i?r:i),F(s,i,p)):r)(s)

Sformatowane i skomentowane

s => (                          // given a string 's':
  r = 1 / 0,                    // 'r' = best score, initialized to +Infinity
  F = (                         // 'F' is a recursive function that takes:
    s,                          //   - the current string 's'
    i = 1,                      //   - a substring counter 'i'
    p = 0                       //   - a character pointer 'p'
  ) =>                          //
    s[p++] ? (                  // if we haven't reached the end of the string:
      [...o = s.slice(0, p)]    //   compute 'o' = substring of length 'p'
      .reverse().join`` == o    //   if 'o' is a palindrome,
      && (                      //   then:
        s[p] ?                  //     if there are still characters to process:
          F(s.slice(p), i + 1)  //       do a recursive call on the remaining part
        :                       //     else:
          r = r < i ? r : i     //       update the score with r = min(r, i)
      ),                        //   in all cases:
      F(s, i, p)                //     do a recursive call with a longer substring
    ) :                         // else:
      r                         //   return the final score
  )(s)                          // initial call to F()

Przypadki testowe


Wstępne podejście, 173 168 bajtów

Dość długa funkcja rekurencyjna, która oblicza wszystkie możliwe partycje ciągu wejściowego.

f=(s,b=1/(k=0))=>++k>>(L=s.length)?b:f(s,(k|1<<30).toString(2).slice(-L).match(/(.)\1*/g).some(m=>[...o=s.slice(i,i+=m.length)].reverse(n++).join``!=o,n=i=0)?b:b<n?b:n)

Sformatowane i skomentowane

f = (                           // given:
  s,                            //   - a string 's'
  b = 1 / (k = 0)               //   - a best score 'b' (initialized to +Infinity)
) =>                            //   - a counter 'k' (initialized to 0)
  ++k >> (L = s.length) ?       // if 'k' is greater or equal to 2^(s.length):
    b                           //   stop recursion and return 'b'
  :                             // else:
    f(                          //   do a recursive call:
      s,                        //     using the same string 's'
      (k | 1 << 30)             //     compute an array containing the groups of identical
      .toString(2).slice(-L)    //     digits in the binary representation of 'k', padded
      .match(/(.)\1*/g)         //     with leading zeros and cut to the length of 's'
      .some(g =>                //     for each group 'g' in this array:
        [... o = s.slice(       //       compute 'o' = corresponding substring of 's',
          i, i += g.length      //       starting at position 'i' with the same length
        )]                      //       (e.g. s = 'abcd' / k = 0b1101 => 'ab','c','d')
        .reverse(n++)           //       increment the number of groups 'n'
        .join`` != o,           //       return true if this substring is NOT a palindrome
        n = i = 0               //       initialize 'n' and 'i'
      ) ?                       //     if some() returns true:
        b                       //       invalid partition -> keep the previous score 'b'
      :                         //     else:
        b < n ? b : n           //       valid partition -> use min(b, n)
    )                           //   end of recursive call

Przypadki testowe

Arnauld
źródło
Jeśli mam rozumieć swoje wyjaśnienie poprawnie, można zaoszczędzić kilka bajtów korzystających ,p=0, s[p++]?i ,F(s,i,p).
Neil,
@Neil Tak, rzeczywiście. :-)
Arnauld
5

Galaretka , 10 bajtów

ŒṖŒḂ€¬$ÞḢL

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.

ŒṖŒḂ€¬$ÞḢL - Main link: s             e.g. 'abab'
ŒṖ         - partitions of s               [['a','b','a','b'],['a','b','ab'],['a','ba','b'],['a','bab'],['ab','a','b'],['ab','ab'],['aba','b'],['abab']]
       Þ   - sort by (create the following key and sort the partitions by it):
      $    -   last two links as a monad:  (key evaluations aligned with above:)
  ŒḂ€      -     is palindromic? for €ach   [ 1 , 1 , 1 , 1 ] [ 1 , 1 , 0  ] [ 1 , 0  , 1 ] [ 1 , 1   ] [ 0  , 1 , 1 ] [ 0  , 0  ] [ 1   , 1 ] [ 0    ] 
     ¬     -     not                        [ 0 , 0 , 0 , 0 ] [ 0 , 0 , 1  ] [ 0 , 1  , 0 ] [ 0 , 0   ] [ 1  , 0 , 0 ] [ 1  , 1  ] [ 0   , 0 ] [ 1    ]
           - ...i.e.:         
           -       making the sorted keys: [[ 0 , 0   ],[ 0   , 0 ],[ 0 , 0 , 0 , 0 ],[ 0 , 0 , 1  ],[ 0 , 1  , 0 ],[ 1    ],[ 1  , 0 , 0 ],[ 1  , 1  ]]
           -  hence the sorted partitions: [['a','bab'],['aba','b'],['a','b','a','b'],['a','b','ab'],['a','ba','b'],['abab'],['ab','a','b'],['ab','ab']]
        Ḣ  - head of the result             ['a','bab']
         L - length                         2
Jonathan Allan
źródło
5

Haskell , 69 bajtów

x!(a:b)|p<-a:x=p!b++[1+f b|p==reverse p]
x!y=[0|x==y]
f=minimum.(""!)

Definiuje funkcję f. Wypróbuj online!

Wyjaśnienie

Funkcja pomocnicza infix x ! yoblicza listę liczb całkowitych, które są długościami niektórych podziałów reverse x ++ yna palindromy, w których reverse xpozostaje nienaruszona. Gwarantuje się, że zawiera długość minimalnego podziału, jeśli nie yjest pusty. Jak to działa?

  • Jeśli yjest niepusty, znak char jest zrywany i wpychany do x. Jeśli xstaje się palindromem, wywołujemy główną funkcję fna końcu yi dodajemy 1, aby uwzględnić x. Wzywamy również !do nowego xi ynie przegap żadnego potencjalnego podziału.
  • Jeśli yjest pusty, zwracamy [0](jeden podział o długości 0), jeśli xjest również pusty, i [](bez podziału) w przeciwnym razie.

Główna funkcja fpo prostu wywołuje "" ! xi zajmuje minimum wyników.

x!(a:b)|          -- Function ! on inputs x and list with head a and tail b,
  p<-a:x=         -- where p is the list a:x, is
  p!b++           -- the numbers in p!b, and
  [1+f b|         -- 1 + f b,
   p==reverse p]  -- but only if p is a palindrome.
x!y=              -- Function ! on inputs x and (empty) list y is
  [0|             -- 0,
   x==y]          -- but only if x is also empty.
f=                -- Function f is:
  minimum.(""!)   -- evaluate ! on empty string and input, then take minimum.
Zgarb
źródło
3

JavaScript (Firefox 30-57), 97 bajtów

f=(s,t=``,i=0)=>s?Math.min(...(for(c of s)if([...t+=c].reverse(++i).join``==t)1+f(s.slice(i)))):0

Port ES6:

f=(s,t=``)=>s?Math.min(...[...s].map((c,i)=>[...t+=c].reverse().join``==t?1+f(s.slice(i+1)):1/0)):0
<input oninput=o.textContent=f(this.value)><pre id=o>

Wydaje się to tak proste rozwiązanie, że ciągle myślę, że o czymś zapomniałem, ale przynajmniej mija wszystkie testy.

Neil
źródło
1

Haskell, 139 116 109 bajtów

h[]=[[]]
h x=words.concat<$>mapM(\c->[[c],c:" "])x
r x=reverse x==x
g x=minimum[length y|y<-h x,and$r<$>y]

Wciąż gra w golfa w Haskell, ale oto moja najlepsza próba, jaką mogę szybko wymyślić.

  • h jest funkcją, która tworzy listę wszystkich możliwych ciągłych podciągów listy (jak ciąg znaków). Pobiera wejściowy ciąg znaków i dzieli go na g.
  • r jest prostą funkcją zwracającą wartość logiczną, jeśli lista jest palindromem
  • g jest główną funkcją, która pobiera listę wejściową, wywołuje h, aby uzyskać listę ciągłych możliwości podsekwencji, filtruje, (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.

wałek klonowy
źródło
1
h []=[[]]i h (x:y)=map ([x]:)zawierają niepotrzebne białe znaki. head.sortjest minimum.
Laikoni
@Laikoni Thanks! Zaktualizuję się, kiedy wrócę do komputera!
maple_shaft
1
Lista zrozumienie jest często krótszy niż filter& map: g x=head$sort[length y|y<-h x,and$r<$>y].
nimi 24.04.17
@nimi Dziękuję, istnieje tak wiele przydatnych wskazówek golfowych dla Haskell. Uczę się nowej sztuczki za każdym razem.
maple_shaft
1

PHP, 319 bajtów

for(;$i<$l=strlen($s=$argn);$i++)for($j=$l-$i;$j;$j--)strrev($r=substr($s,$i,$j))!=$r?:$e[+$i][]=$r;uasort($e,function($a,$b){return strlen($b[0])<=>strlen($a[0])?:count($a)<=>count($b);});foreach($e as$p=>$v)foreach($v as$w){$s=preg_replace("#^(.{{$p}})$w#","$1".str_pad("",strlen($w),"ö"),$s,1,$c);!$c?:++$d;}echo$d;

Wersja online

Rozszerzony

for(;$i<$l=strlen($s=$argn);$i++)
for($j=$l-$i;$j;$j--)strrev($r=substr($s,$i,$j))!=$r?:$e[+$i][]=$r; #Make all substrings that are palindromes for each position
uasort($e,function($a,$b){return strlen($b[0])<=>strlen($a[0])?:count($a)<=>count($b);}); # sort palindrome list high strlen lowest count for each position
foreach($e as$p=>$v)
foreach($v as$w){
    $s=preg_replace("#^(.{{$p}})$w#","$1".str_pad("",strlen($w),"ö"),$s,1,$c);
    !$c?:++$d; # raise count
}
echo$d; # Output

Dłuższa wersja bez E_NOTICE i wyświetlenie wynikowej tablicy

Jörg Hülsermann
źródło
To wydaje się dawać niepoprawny wynik dlaababacabBACABABA
Zgarb,
@Zgarb Teraz to działa
Jörg Hülsermann 25.04.17