Palíndromos perfectos

25

Su tarea es determinar qué tan palíndromo perfecto es una cuerda. Su palíndromo típico (por ejemplo, 12321) es un palíndromo perfecto; su perfección es 1.

Para determinar la perfección de una cadena, puede ver cuántas secciones puede dividir en donde cada sección es un palíndromo. Si hay ambigüedades, como con aaaa, como se puede dividirlo en [aa, aa]o [aaaa], o [a, aaa], o [aaa, a], el conjunto más corto anulará, dando aaaauna puntuación de 1, que es la longitud de la serie más corta.

Por lo tanto, debe escribir un programa o función que tome una entrada y salida no vacía y cuán perfecta sea (que es la longitud del conjunto más corto que puede dividir en donde cada elemento del conjunto es un palíndromo).

Ejemplos:

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]

Tenga en cuenta que en los ejemplos, cualquier cosa entre corchetes no debería ser parte de la salida.

Okx
fuente
¿Es la cadena vacía una entrada válida, y si es así, cuál debería ser la salida?
Zgarb
8
ababacaby su reverso, bacababaparecen ser buenos casos de prueba.
Neil
@Neil, así como buenos argumentos sobre si es posible un algoritmo de tiempo lineal.
Leaky Nun
@Zgarb La cadena vacía no es una entrada válida.
Okx
ababacabBACABABATambién es un buen caso de prueba (algunas respuestas fallan).
Zgarb

Respuestas:

14

Brachylog , 7 bytes

~cL↔ᵐLl

Pruébalo en línea!

Explicación

~cL          Deconcatenate the input into L
  L↔ᵐL       Reversing all elements of L results in L
     Ll      Output = length(L)
Fatalizar
fuente
Me ganaste ... en mi primer post jajaja
Leaky Nun
77
@LeakyNun Sabía que lo probarías. Los últimos meses pude relajarme y esperar unas horas, ahora contigo de vuelta, ¡tengo que responder de inmediato!
Fatalize
9

Jalea , 13 12 11 bytes

ŒṖLÞŒḂ € P $ ÐfḢL 
ŒṖLÞṚ € ⁼ $ ÐfḢL
ŒṖṚ € ⁼ $ ÐfL € Ṃ
ŒṖ obtener particiones
      Ðf filtro para particiones que
  Ṛ € después de invertir cada subpartición
    ⁼ es igual a la partición
        L € longitud de cada partición exitosa
          Ṃ mínimo

Pruébalo en línea!

Especificaciones

  • Entrada: "ababacab"(como argumento)
  • Salida: 2
Monja permeable
fuente
3
@Okx bueno, tendrías que escapar de esos.
Leaky Nun
2
Bueno, no creo que sea válido si no puede aceptar barras diagonales inversas.
Okx
14
@Okx Es como escribir una cadena. No puede esperar, por ejemplo, que un programa en C funcione con una entrada de cadena "\", porque esa es una sintaxis no válida.
Conor O'Brien
2
Bienvenido de nuevo, por cierto. :-)
Arnauld
2
Lamentablemente esto da diferentes respuestas para ababacaby su reverso, bacababa.
Neil
6

Pyth, 9 bytes

lh_I#I#./

Banco de pruebas

Esto forma todas las particiones de la entrada, desde la más corta hasta la más larga. Luego, filtra esas particiones en invariancia bajo filtrado de los elementos en invariancia bajo inversión. Finalmente, tomamos el primer elemento de la lista filtrada de particiones y devolvemos su longitud.

Para explicar tan complicado paso, vamos a empezar con la invariancia bajo la inversión: _I. Eso verifica si su entrada es un palíndromo, porque verifica si la inversión cambia el valor.

A continuación, el filtrado de palindromía: _I#. Esto mantendrá solo los elementos palindrómicos de la lista.

A continuación, comprobar si hay invariancia bajo el filtrado para palindromía: _I#I. Esto es verdad si y solo si todos los elementos de la lista son palíndromos.

Por último, vamos a filtrar para las listas donde todos los elementos de la lista son palíndromos: _I#I#.

isaacg
fuente
Tengo mucho que aprender ...
Leaky Nun
6

Haskell , 83 bytes

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

Pruébalo en línea!

Esto utiliza el gran consejo de Zgarb para generar particiones de cadena .

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
fuente
1
¡Guauu! Esto me voló la cabeza! Definitivamente tengo mucho que aprender.
maple_shaft
5

Clojure, 111 bytes

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

Se divide en todas las posiciones posibles, y cuando la primera parte es un palíndromo, procede a encontrar una partición para el resto de la cadena.

Pruébalo en línea .

Ungolfed, usa macro de último hilo ->> .

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

Una versión oscura, por favor no escriba código como este: 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
fuente
¿ Te ayudaría este consejo ? No sé Clojure en absoluto.
Leaky Nun
Por lo general sí, pero en este caso la función fha de llamarse a sí mismo dentro de la para: (f b). En una posición de cola puede usar recur.
NikoNyrh
Todavía puede reemplazar defncon fny solo tener una función.
cliffroot
(fn f[s]( ... ))? Oh verdad. Ahorras 2 personajes con eso.
NikoNyrh
5

JavaScript (ES6), 143 126 124 bytes

Guardado 2 bytes gracias a Neil

Inspirado en el método 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)

Formateado y comentado

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

Casos de prueba


Enfoque inicial, 173168 bytes

Una función recursiva bastante larga que calcula todas las particiones posibles de la cadena de entrada.

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)

Formateado y comentado

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

Casos de prueba

Arnauld
fuente
Si he entendido su explicación correctamente, puede guardar un par de bytes usando ,p=0, s[p++]?y ,F(s,i,p).
Neil
@Neil Sí, de hecho. :-)
Arnauld
5

Jalea , 10 bytes

ŒṖŒḂ€¬$ÞḢL

Pruébalo en línea!

¿Cómo?

Utiliza el hecho de que
[0]<[0,0]<[0,0,0],...,<[0,...,0,1]<...
, por lo tanto, si clasificamos las particiones por una clave "no es palindrómica para cada parte", la primera entrada será totalmente palindrómica y de longitud mínima.

Nota: cualquier cadena de longitud n no vacía siempre dará como resultado una clave con n ceros, ya que todas las cadenas de longitud 1 son palindrómicas.

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

Haskell , 69 bytes

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

Define una función f. Pruébalo en línea!

Explicación

La función auxiliar infija x ! ycalcula una lista de enteros, que son las longitudes de algunas divisiones reverse x ++ yen palíndromos donde reverse xse deja intacta. Se garantiza que contiene la longitud de la división mínima si yno está vacía. Cómo funciona es esto.

  • Si y no está vacío, se saca un char y se empuja hacia adentro x. Si se xconvierte en un palíndromo, llamamos a la función principal fen la cola de yy agregamos 1 para tener en cuenta x. Además, pedimos !lo nuevo xy yno perder ninguna división potencial.
  • Si yestá vacío, devolvemos [0](una división de longitud 0) si xtambién está vacío, y [](sin división) de lo contrario.

La función principal fsolo llama "" ! xy toma el mínimo de los resultados.

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
fuente
3

JavaScript (Firefox 30-57), 97 bytes

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

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

Parece una solución tan simple que sigo pensando que he olvidado algo, pero al menos pasa todos los casos de prueba.

Neil
fuente
1

Haskell, 139 116 109 bytes

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]

Todavía verde en el golf de Haskell, pero este es mi mejor intento que puedo encontrar rápidamente.

  • h es una función que crea una Lista de todas las subsecuencias contiguas posibles de una Lista (como una cadena). Toma la cadena de entrada y la divide para g.
  • r es una función simple que devuelve un booleano para si una lista es un palíndromo
  • g es la función principal que toma una lista de entrada, llama a h para obtener la lista de posibilidades de subsecuencia contigua, filtra (and.map r)para eliminar sublistas que no contienen un palíndromo, en cuyo punto se aplica la longitud a la lista, y luego el resultado es ordenado para que podamos agarrar la cabeza, que es la respuesta.

Estaba pensando que una mejor respuesta podría ser capaz de aprovechar la naturaleza no determinista de las Listas en Haskell mediante el uso de Solicitantes. Podría ser posible eliminar muchos bytes de la función h usando aplicativos, incluso si tenemos que importar Control.Applicative. Comentarios para mejorar son bienvenidos.

ACTUALIZACIÓN1

Grandes ahorros basados ​​en el recordatorio de Laikoni sobre la función mínima. Eliminar la clasificación en realidad me permitió eliminar la importación de Data.List porque el mínimo se define en Prelude!

ACTUALIZACIÓN2

Gracias a la sugerencia de nimi sobre el uso de las comprensiones de listas como un reemplazo útil para filter.map. Eso me ahorró algunos bytes. También tomé prestado el truco ordenado de partición de cadenas de la respuesta de Laikonis y también guardé un par de bytes allí.

eje de arce
fuente
1
h []=[[]]y h (x:y)=map ([x]:)contienen espacios en blanco innecesarios. head.sortes minimum.
Laikoni
@Laikoni ¡Gracias! ¡Actualizaré cuando vuelva a mi computadora!
maple_shaft
1
Una lista por comprensión a menudo es más corto que filterY map: g x=head$sort[length y|y<-h x,and$r<$>y].
nimi
@nimi Gracias, hay muchos consejos útiles de golf para Haskell. Aprendo un nuevo truco cada vez.
maple_shaft el
1

PHP, 319 bytes

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;

Versión en línea

Expandido

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

Versión más larga sin E_NOTICE y salida de la matriz resultante

Jörg Hülsermann
fuente
Esto parece dar un resultado incorrecto paraababacabBACABABA
Zgarb
@Zgarb Ahora funciona
Jörg Hülsermann