Идеальный Палиндром

25

Ваша задача - определить, насколько идеальным является палиндром струны. Ваш типичный палиндром (например, 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]

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

Okx
источник
Является ли пустая строка допустимым вводом, и если да, каким должен быть вывод?
Згарб
8
ababacabи наоборот, bacababaкажется, хорошие тестовые случаи.
Нил
@Neil, а также хорошие аргументы относительно того, возможен ли линейно-временной алгоритм.
Утренняя монахиня
@Zgarb Пустая строка не является допустимым вводом.
Okx
ababacabBACABABAтакже хороший тестовый пример (некоторые ответы на него не срабатывают).
Згарб

Ответы:

14

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

~cL↔ᵐLl

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

объяснение

~cL          Deconcatenate the input into L
  L↔ᵐL       Reversing all elements of L results in L
     Ll      Output = length(L)
Fatalize
источник
Ты победил меня ... в моем первом посте. LOL
Leaky Nun
7
@ LeakyNun Я знал, что ты попробуешь это. В прошлые месяцы я мог расслабиться и подождать несколько часов, теперь, когда вы вернулись, я должен немедленно ответить!
Роковая
9

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

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

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

Спекуляции

  • Вход: "ababacab"(как аргумент)
  • Выход: 2
Дрянная Монахиня
источник
3
@ Ладно, тебе придется убежать от них.
Утренняя монахиня
2
Ну, я не думаю, что это действительно, если он не может принять обратную косую черту.
Okx
14
@Okx Это похоже на написание строки. Вы не можете ожидать, скажем, программы на C для работы со строковым вводом "\", потому что это неверный синтаксис.
Конор О'Брайен
2
С возвращением, кстати. :-)
Arnauld
2
К сожалению, это дает разные ответы ababacabи наоборот bacababa.
Нил
6

Pyth, 9 байт

lh_I#I#./

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

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

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

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

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

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

isaacg
источник
У меня есть
Утренняя монахиня
6

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.
]
Laikoni
источник
1
Вот Это Да! Это взорвало мой разум! Мне определенно есть чему поучиться.
maple_shaft
5

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)))
NikoNyrh
источник
Будет ли этот совет поможет? Я совсем не знаю Clojure.
Утренняя монахиня
Обычно да, но в этом случае функция fдолжна называть себя внутри для: (f b). Вы можете использовать позицию «хвостовой колл» recur.
NikoNyrh
Вы все еще можете заменить defnна fnи просто иметь функцию.
Cliffroot
(fn f[s]( ... ))? О, правда. Вы сохраняете 2 символа с этим.
NikoNyrh
5

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

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


Исходный подход, 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

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

Arnauld
источник
Если я правильно понял ваше объяснение, вы можете сохранить пару байтов, используя ,p=0, s[p++]?и ,F(s,i,p).
Нил
@Neil Да, действительно. :-)
Arnauld
5

Желе , 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
Джонатан Аллан
источник
5

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.
Zgarb
источник
3

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>

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

Нил
источник
1

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 и также сохранил там пару байтов.

maple_shaft
источник
1
h []=[[]]и h (x:y)=map ([x]:)содержат ненужные пробелы. head.sortесть minimum.
Лайкони
@Laikoni Спасибо! Я обновлю, когда вернусь к своему компьютеру!
maple_shaft
1
Список понимание часто короче filterи map: g x=head$sort[length y|y<-h x,and$r<$>y].
Ними
@nimi Спасибо, есть много полезных советов по игре в гольф для Haskell. Я учу новый трюк каждый раз.
maple_shaft
1

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 и вывод результирующего массива

Йорг Хюльсерманн
источник
Это, кажется, дает неправильный результат дляababacabBACABABA
Zgarb
@Zgarb Теперь это работает
Йорг Хюльсерманн