Ваша задача - определить, насколько идеальным является палиндром струны. Ваш типичный палиндром (например, 12321) - идеальный палиндром; его совершенство равно 1.

Чтобы определить идеальность строки, вы видите, сколько разделов вы можете разбить на те, где каждый раздел является палиндромом. Если есть неоднозначности, например, с aaaa, как вы можете разделить его на [aa, aa]или [aaaa]или [a, aaa]или [aaa, a], самый короткий набор будет переопределен, давая aaaaоценку 1, который является длиной самого короткого набора.

Следовательно, вы должны написать программу или функцию, которая будет принимать один непустой ввод и выводить, насколько он совершенен (длина самого короткого набора, на который вы можете разбить его, где каждый элемент в наборе является палиндромом).

Примеры:

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]

Обратите внимание, что в примерах ничего в квадратных скобках не должно быть частью вывода.

Брахилог , 7 байт

~cL↔ᵐLl

Попробуйте онлайн!

объяснение

~cL          Deconcatenate the input into L
  L↔ᵐL       Reversing all elements of L results in L
     Ll      Output = length(L)

Желе , 13 12 11 байт

ŒṖLÞŒḂ € P $ ÐfḢL 
ŒṖLÞṚ € ⁼ $ ÐfḢL
ŒṖṚ € ⁼ $ DFL € ˙M
ŒṖ получить разделы
      Фильтр для разделов, которые
  Ṛ € после изменения каждого подраздела
    Equal равно разделу
        L € длина каждого успешного раздела
          Ṃ минимум

Попробуйте онлайн!

Спекуляции

• Вход: "ababacab"(как аргумент)
• Выход: 2

Pyth, 9 байт

lh_I#I#./

Тестирование

Это формирует все разделы ввода, от самого короткого до самого длинного. Затем он фильтрует эти разбиения на инвариантность при фильтрации элементов на инвариантность при обращении. Наконец, мы берем первый элемент отфильтрованного списка разделов и возвращаем его длину.

Для того, чтобы объяснить , что сложный шаг, давайте начнем с инвариантности относительно обращения: _I. Это проверяет, является ли его ввод палиндромом, потому что он проверяет, меняет ли реверсирование значение.

Далее, для фильтрации палиндромности: _I#. Это сохранит только палиндромные элементы списка.

Далее мы проверяем на инвариантность относительно фильтрации для палиндромности: _I#I. Это верно тогда и только тогда, когда все элементы списка являются палиндромами.

Наконец, мы фильтруем для списков , где все элементы списка являются палиндромов: _I#I#.

Haskell , 83 байта

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

Попробуйте онлайн!

Это использует отличный совет Zgarb для генерации строковых разделов .

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

Clojure, 111 байт

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

Разбивается на все возможные позиции, и когда первая часть представляет собой палиндром, продолжается поиск разбиения для оставшейся части строки.

Попробуйте онлайн .

Ungolfed, использует последний макрос потока ->> .

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

Неизвестная версия, пожалуйста, не пишите такой код: 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)))

JavaScript (ES6), 143 126 124 байт

Сохранено 2 байта благодаря Нейлу

Вдохновленный методом 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)

Отформатировано и прокомментировано

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

Контрольные примеры

let f =

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)

console.log(f('1111'))      // -> 1 [1111]
console.log(f('abcb'))      // -> 2 [a, bcb]
console.log(f('abcbd'))     // -> 3 [a, bcb, d]
console.log(f('abcde'))     // -> 5 [a, b, c, d, e]
console.log(f('66a'))       // -> 2 [66, a]
console.log(f('abcba'))     // -> 1 [abcba]
console.log(f('x'))         // -> 1 [x]
console.log(f('ababacab'))  // -> 2 [aba, bacab]
console.log(f('bacababa'))  // -> 2 [bacab, aba]

Исходный подход, 173 168 байт

Довольно длинная рекурсивная функция, которая вычисляет все возможные разделы входной строки.

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)

Отформатировано и прокомментировано

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

Контрольные примеры

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)

console.log(f('1111'))      // -> 1 [1111]
console.log(f('abcb'))      // -> 2 [a, bcb]
console.log(f('abcbd'))     // -> 3 [a, bcb, d]
console.log(f('abcde'))     // -> 5 [a, b, c, d, e]
console.log(f('66a'))       // -> 2 [66, a]
console.log(f('abcba'))     // -> 1 [abcba]
console.log(f('x'))         // -> 1 [x]
console.log(f('ababacab'))  // -> 2 [aba, bacab]
console.log(f('bacababa'))  // -> 2 [bacab, aba]

Желе , 10 байт

ŒṖŒḂ€¬$ÞḢL

Попробуйте онлайн!

Как?

Используется тот факт, что
[0]<[0,0]<[0,0,0],...,<[0,...,0,1]<...
- таким образом, если мы сортируем разделы по ключу «не палиндромно для каждой части», первая запись будет палиндромной и минимальной длины.

Примечание: любая непустая строка длины n всегда приводит к такому ключу с n нулями, поскольку все строки длины 1 являются палиндромными.

ŒṖŒḂ€¬$ÞḢ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

Haskell , 69 байт

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

Определяет функцию f. Попробуйте онлайн!

объяснение

Вспомогательная функция infix x ! yвычисляет список целых чисел, которые являются длинами некоторых разбиений reverse x ++ yна палиндромы, где они reverse xостались нетронутыми. Гарантируется, что длина минимального разбиения yбудет непустой. Как это работает?

• Если yне пусто, с него извлекается символ и проталкивается в него x. Еслиx становится палиндромом, мы вызываем основную функцию fна хвосте yи добавляем 1 к учетной записи x. Также мы призываем !к новому xи yне пропускаем ни одного потенциального раскола.
• Если y пусто, мы возвращаем [0](одно разбиение длины 0), если xтакже пусто, и [](без разбиения) в противном случае.

Основная функция fпросто вызывает "" ! xи принимает минимум результатов.

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.

JavaScript (Firefox 30-57), 97 байт

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

Порт 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>

Это кажется таким простым решением, что я продолжаю думать, что что-то забыл, но оно, по крайней мере, проходит все контрольные тесты.

Haskell, 139 116 109 байт

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]

Все еще зеленый в игре в гольф на Haskell, но это моя лучшая попытка, которую я могу придумать быстро.

• h - это функция, которая создает список всех возможных смежных подпоследовательностей списка (например, строки). Он принимает входную строку и разбивает ее на g.
• r простая функция, которая возвращает логическое значение, если список является палиндромом
• g - это основная функция, которая принимает входной список List, вызывает h, чтобы получить список смежных возможностей подпоследовательности, фильтры (and.map r)для удаления подсписков, которые не содержат палиндрома, и в этом случае длина списка применяется к списку, а затем результат отсортировано, чтобы мы могли взять голову, которая является ответом.

Я думал, что лучший ответ мог бы использовать недетерминированную природу списков в Haskell с помощью использования Applicatives. Можно было бы сократить количество байтов функции h с помощью аппликативов, даже если нам нужно импортировать Control.Applicative. Комментарии для улучшения приветствуются.

Update1

Огромная экономия на основе напоминания Лайкони о минимальной функции. Удаление сортировки фактически позволило мне удалить импорт Data.List, потому что минимум определен в Prelude!

UPDATE2

Благодаря предложению nimi об использовании списочных представлений в качестве полезной замены для filter.map. Это спасло мне несколько байтов. Также я позаимствовал аккуратный трюк с разделом String из ответа Laikonis и также сохранил там пару байтов.

PHP, 319 байт

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;

Онлайн версия

расширенный

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

Более длинная версия без E_NOTICE и вывод результирующего массива