Debido a que no puedo concentrarme en ninguna tarea durante más de 5 segundos, a menudo me encuentro separando palabras en subcadenas, cada una de las cuales tiene una longitud diferente y no contiene caracteres repetidos. Por ejemplo, la palabra "pasta" podría estar dividida en "pasado" y "a", "pas" y "ta", o "pa" y "sta" y obtendrá la imagen.

Sin embargo, debido a que recordar todas las combinaciones es difícil, generalmente solo selecciono una, y me gusta seleccionar la más agradable. Consideramos que la mejor manera de ser la que tiene la "puntuación" más baja. Su tarea será, dada una palabra, imprimir su puntaje, dadas las siguientes reglas complicadas.

Puntuación

Descripción de cómo calificar una palabra:

• Una palabra es una cadena de caracteres latinos, las letras mayúsculas deben reemplazarse por 2 de la misma letra minúscula (por lo que "Box" se convierte en "bbox")

• Un segmento es una subcadena contigua (estricta) de una palabra y no debe contener ningún carácter dos veces ("ella", "re", "h" son todos segmentos válidos de "Aquí" ("aquí"), pero "hh" y "ere" no lo son)

• Una segmentación es un conjunto de segmentos de diferentes longitudes que, cuando se unen, forman la palabra original ("tre" y "e" hacen "árbol"), y que no pueden segmentarse más dentro de la segmentación (es decir, "ba" tiene una sola segmentación, "ba", y "alp" y "habet" no es una segmentación válida de "alfabeto", porque cualquiera de estos podría segmentarse aún más (por ejemplo, en "a" & "lp" y "habet", que ahora es una segmentación válida ("habet" no se puede segmentar sin formar un segmento de longitud 2 o 1))).

• El puntaje de una segmentación es la suma de los puntajes de cada carácter distinto que aparece en la palabra original (una vez que se han reemplazado las mayúsculas)

• La puntuación de los personajes se explica a continuación.

• El puntaje de una palabra es el puntaje de su mejor segmentación posible (con el puntaje más bajo)

Si no existen segmentaciones válidas para una palabra (por ejemplo, "Brass" ("bbrass"), que no se puede segmentar porque la primera "b" y la última "s" tendrían que estar en sus propios segmentos, lo que resultaría en dos segmentos de la misma longitud), entonces debe mostrar el texto "mal", de lo contrario, debe mostrar la puntuación de la palabra.

Puntuación de personaje

La puntuación de los caracteres se basa en cuántas veces aparece el carácter y las ponderaciones de los segmentos en los que aparece. Las ponderaciones de los segmentos dependen de las longitudes del segmento y del múltiplo común más bajo de las longitudes de todos los segmentos en La segmentación.

segment weighting = lowest common multiple of lengths segments / length of segment

Considere la palabra "oliva", que podría segmentarse como "ol" y "ive", y visualizarse como 2 cajas de la misma área, una de "ol" con peso 3 y una de "ive" con peso 2 (LCM de 6).

ol
ol ive
ol ive

Esto está destinado a representar las dos cajas, una hecha de 3 "ol" y otra hecha de 2 "ive" s. Alternativamente, podría ser "o" y "en vivo" (MCM de 4)

o
o
o
o live

El puntaje de cada carácter es la suma de los pesos de los segmentos en los que aparece, multiplicado por el número de veces que aparece después de reemplazar las mayúsculas (por lo que si aparece dos veces, se le cobrará el doble por cada vez que tenga que decirlo). )

character score = character count * sum(segment weights in which character appears)

Ejemplo de puntaje

Tomamos la palabra "caer", solo se puede segmentar en "fal" y "l". El mínimo común múltiplo de 3 y 1 es 3, por lo que "fal" tiene peso 1 y "l" tiene peso 3.

    l
    l
fal l

Pasando por cada personaje ...

• "f" aparece una vez, y está en el segmento "fal" con peso 1, por lo que tiene puntaje 1 * 1 = 1

• "a" también aparece solo una vez, tiene una suma de pesos de 1, por lo que tiene una puntuación de 1 * 1 = 1

• "l" aparece dos veces y aparece en "fal" (peso 1) y "l" (peso 3), por lo que tiene puntaje 2 * (1 + 3) = 8

La suma de estos es 10 (el puntaje de la segmentación y de la palabra, ya que esta es la mejor segmentación). Aquí está esto en el mismo formato que los ejemplos a continuación:

fall = fal l
2*1 [fa] + 2*(1+3) [ll] = 10

Calificaciones de ejemplo

Estos ejemplos de calificaciones pueden o no ayudar:

class -> clas s
3*1 [cla] + 2*(4+1) [ss] = 13

fish -> fis h
3*1 [fis] + 1*3 [h] = 6

eye -> e ye
1*1 [y] + 2*(1+2) [ee] = 7

treasure -> treas u re
3*2 [tas] + 2*2*(2+5) [rree] + 1*10 [u] = 44

Wolf -> w wolf
3*1 [olf] + 2*(1+4) = 13

book
evil

"libro" es una palabra malvada, por lo que no tiene puntaje.

Tenga en cuenta que el "tesoro" se puede segmentar de varias maneras, pero la segmentación mostrada se beneficia de tener las letras más frecuentes ("r" y "e") en los segmentos más largos, por lo que no tienen tanto peso. La segmentación "t" y "re" y "asure" darían el mismo resultado, mientras que "Treas" y "ur" y "e" sufrirían, con "e" con una puntuación de 2 * (1 + 10 + 2 ) = 24 por sí solo. Esta observación es realmente el espíritu de todo el ejercicio. Un ejemplo de una puntuación incorrecta de "tesoro" (incorrecta porque no se deriva de la puntuación de la mejor segmentación (que con la puntuación más baja)):

treasure = treas ur e
3*2 [tas] + 2*(2+5) [rr] + 1*5 [u] + 2*[2+10] = 49

Entrada

Una sola cadena que contiene solo caracteres latinos de cualquier caso ("caballo", "Caballo" y "hOrSe" son todas entradas válidas) que puede ser aceptada por STDIN, argumento de línea de comando, argumento de función o de otro modo si su idioma de elección no es compatible con ninguno de los mencionados anteriormente.

Salida

Debe generar el puntaje de la palabra, que es un número entero positivo mayor que 0, o "malvado" si no existe segmentación. La salida debe ser STDOUT o el argumento de retorno de una función, a menos que su idioma de elección no soporte ninguno de estos, en cuyo caso haga algo deportivo.

Ejemplos

No espero que imprima todo esto, todo lo que quiero es el puntaje de la palabra, o la salida "mal", por ejemplo (entrada seguida de salida)

eye
7

Eel
evil

a
1

Establishments
595

antidisestablishmentarianism
8557

No me preocupa el rendimiento, si puede anotar casi cualquier palabra de 15 letras (después de reemplazar las mayúsculas) en menos de un minuto en una máquina sensible (intencionalmente vaga), eso es suficiente para mí.

Este es el código de golf, que gane el código más corto.

Gracias a PeterTaylor, MartinBüttner y SP3000 por su ayuda con este desafío.

Mathematica, 373 bytes

If[l=Length;a=Accumulate[l/@#]&;u=Unequal;e=Select;{}==(m=(g=#;Tr[#2Flatten[ConstantArray[#,LCM@@l/@g/l@#]&/@g]~Count~#&@@@Tally@c])&/@e[p=e[c~Internal`PartitionRagged~#&/@Join@@Permutations/@IntegerPartitions[l[c=Characters[s=StringReplace[#,c:"A"~CharacterRange~"Z":>(d=ToLowerCase@c)<>d]]]],u@@l/@#&&And@@u@@@#&],FreeQ[p,l_List/;#!=l&&SubsetQ[a@l,a@#]]&]),"evil",Min@m]&

Esto es bastante largo ... y también bastante ingenuo. Define una función sin nombre que toma la cadena y devuelve la puntuación. Se tarda aproximadamente 1 segundo en manejar "Establishments", por lo que está dentro del límite de tiempo. Tengo una versión un poco más corta que usa Combinatorica`SetPartitions, pero ya lleva un minuto "Establishme".

Aquí hay una versión con espacios en blanco:

If[
  l = Length;
  a = Accumulate[l /@ #] &;
  u = Unequal;
  e = Select;
  {} == (
    m = (
      g = #;
      Tr[
        #2 Flatten[
          ConstantArray[
            #, 
            LCM @@ l /@ g/l@#
          ] & /@ g
        ]~Count~# & @@@ Tally@c
      ]
    ) & /@ e[
      p = e[
        c~Internal`PartitionRagged~# & /@ Join @@ Permutations /@ IntegerPartitions[
          l[
            c = Characters[
              s = StringReplace[
                #, 
                c : "A"~CharacterRange~"Z" :> (d = ToLowerCase@c) <> d
              ]
            ]
          ]
        ], 
        u @@ l /@ # && And @@ u @@@ # &
      ], 
      FreeQ[p, l_List /; # != l && SubsetQ[a@l, a@#]] &
    ]
  ),
  "evil",
  Min@m
] &

Podría agregar una explicación más detallada más adelante. Este código usa la segunda solución de esta respuesta para obtener todas las particiones y esta solución para asegurarse de que todas estén segmentadas al máximo.

Java 8, 1510 1485 bytes

Esto es así por mucho tiempo. La combinatoria nunca es fácil en Java. Definitivamente se puede acortar un poco. Llamada con a(string). Esto utiliza un algoritmo exponencial de memoria y tiempo; así que no esperes que funcione para entradas largas. Tarda aproximadamente medio segundo en procesarse Establishments. Se bloquea con un error de falta de memoria para antidisestablishmentarianism.

import java.util.*;import java.util.stream.*;void a(String a){a=a.replaceAll("\\p{Upper}","$0$0").toLowerCase();List<List<String>>b=b(a),c;b.removeIf(d->d.stream().anyMatch(e->e.matches(".*(.).*\\1.*")));b.removeIf(d->{for(String e:d)for(String f:d)if(e!=f&e.length()==f.length())return 1>0;return 1<0;});c=new ArrayList(b);for(List<String>d:b)for(List<String>e:b){if(d==e)continue;int f=0,g=0;List h=new ArrayList(),i=new ArrayList();for(String j:d)h.add(f+=j.length());for(String k:e)i.add(g+=k.length());if(i.containsAll(h))c.remove(d);else if(h.containsAll(i))c.remove(e);}b=c;int d=-1;for(List e:b)d=d<0?c(e):Math.min(c(e),d);System.out.println(d<0?"evil":d);}int c(List<String>a){List<Integer>b=a.stream().map(c->c.length()).collect(Collectors.toList()),d;int e=d(b.toArray(new Integer[0])),f=0,g=0,h;d=b.stream().map(A->e/A).collect(Collectors.toList());Map<Character,Integer>i=new HashMap(),j=new HashMap();for(;g<a.size();g++){h=d.get(g);String k=a.get(g);for(char l:k.toCharArray()){i.put(l,i.getOrDefault(l,0)+1);j.put(l,j.getOrDefault(l,0)+h);}}for(char k:i.keySet())f+=i.get(k)*j.get(k);return f;}int d(Integer...a){int b=a.length,c,d,e;if(b<2)return a[0];if(b>2)return d(a[b-1],d(Arrays.copyOf(a,b-1)));c=a[0];d=a[1];for(;d>0;d=c%d,c=e)e=d;return a[0]*a[1]/c;}List b(String a){List<List>b=new ArrayList(),c;for(int i=0;++i<a.length();b.addAll(c)){String d=a.substring(0,i),e=a.substring(i);c=b(e);for(List f:c)f.add(0,d);}b.add(new ArrayList(Arrays.asList(a)));return b;}

Intenta aquí

Sangrado con explicación:

void a(String a){
    a = a.replaceAll("\\p{Upper}", "$0$0").toLowerCase();                //Replace all uppercase letters with two lowercase letters

    List<List<String>> b = b(a), c;                                      //Generate partitions
    b.removeIf(d -> d.stream().anyMatch(e -> e.matches(".*(.).*\\1.*")));//Remove partitions that contains duplicate letters

    b.removeIf(d -> {                                                    //Remove partitions that have equal length parts
        for (String e : d)
            for (String f : d)
                if (e != f & e.length() == f.length())
                    return 1 > 0;
        return 1 < 0;
    });

    c = new ArrayList(b);                                                //Remove partitions that can be partitioned further
    for (List<String> d : b)                                             //Uses Martin's technique
        for (List<String> e : b){
            if (d == e)
                continue;
            int f = 0, g = 0;
            List h = new ArrayList(), i = new ArrayList();
            for (String j : d)
                h.add(f += j.length());
            for (String k : e)
                i.add(g += k.length());
            if (i.containsAll(h))
                c.remove(d);
            else if (h.containsAll(i))
                c.remove(e);
        }

    b = c;

    int d = -1;
    for (List e : b)
        d = d < 0 ? c(e) : Math.min(c(e), d);                            //Find nicest partition

    System.out.println(d < 0 ? "evil" : d);
}

int c(List<String> a) {                                                  //Grade a partition
    List<Integer> b = a.stream().map(c->c.length()).collect(Collectors.toList()), d; //Map to length of parts

    int e = d(b.toArray(new Integer[0])), f = 0, g = 0, h;

    d = b.stream().map(A -> e / A).collect(Collectors.toList());         //Figure out the weight of each part

    Map<Character, Integer> i = new HashMap(), j = new HashMap();

    for (; g < a.size(); g++){                                           //Count instances of each character and
        h = d.get(g);                                                    //weight of each character
        String k = a.get(g);
        for (char l : k.toCharArray()){
            i.put(l, i.getOrDefault(l, 0) + 1);
            j.put(l, j.getOrDefault(l, 0) + h);
        }
    }

    for (char k : i.keySet())
        f += i.get(k) * j.get(k);                                        //Sum cost of each character

    return f;
}

int d(Integer... a) {                                                    //Find lcm
    int b = a.length, c, d, e;
    if (b < 2)
        return a[0];
    if (b > 2)
        return d(a[b - 1], d(Arrays.copyOf(a, b - 1)));
    c = a[0];
    d = a[1];
    for (;d > 0;d = c % d, c = e)
        e = d;
    return a[0] * a[1] / c;
}

List b(String a) {                                                       //Find all partitions of a string
    List<List> b = new ArrayList(), c;                                   //Uses recursion
    for (int i = 0; ++i < a.length();b.addAll(c)){
        String d = a.substring(0, i), e = a.substring(i);
        c = b(e);
        for (List f : c)
            f.add(0, d);
    }
    b.add(new ArrayList(Arrays.asList(a)));
    return b;
}

Esto también abusa bastante de los genéricos para reducir el recuento de bytes. Estoy bastante sorprendido de haber podido compilarlo todo.

Gracias Ypnypn :)

C # 679 bytes

Esta solución se basa más o menos en la estructura de mi implementación de prueba original, e inicialmente fue solo una reescritura de golf, pero luego incluí todas las funciones, y ahora es horrible. Es razonablemente rápido, resolviendo establecimientos en menos de un segundo. Es un programa completo que toma la palabra de entrada como un único parámetro de ARGV.

using Q=System.String;class P{static void Main(Q[]A){Q s="";foreach(var c in A[0]){var z=(char)(c|32);if(c<z)s+=z;A[0]=s+=z;}int r=S(A);System.Console.WriteLine(r<1?"evil":""+r);}static int S(Q[]s){int r=0,t,j,k,L=1,Z=s.Length,i=Z,T=0,R=2;for(;i-->0;R=t<1?0:R){t=s[i].Length;k=L;for(j=2;t>1;)if(t%j++<1){t/=--j;if(k%j<1)k/=j;else L*=j;}}foreach(var C in Q.Join("",s))for(i=Z;i-->0;){for(k=s[j=i].Length;j-->0;)R=k==s[j].Length?0:R;j=s[i].IndexOf(C)+1;R=j*R*s[i].IndexOf(C,j)>1?1:R;T+=j>0?L/k:0;}i=R<1?0:Z;for(var U=new Q[Z+1];i-->0;)for(j=s[i].Length;j-->1;r=r<1|((t=S(U))>0&t<r)?t:r)for(U[k=Z]=s[i].Substring(j);k-->0;U[i]=s[i].Substring(0,j))U[k]=s[k];return r<1?R<2?R-1:T:r;}}

El Mainmétodo comienza creando una copia de la entrada con las mayúsculas reemplazadas. Luego llama Sal "solucionador", que devuelve el puntaje de una segmentación dada (la primera segmentación es aquella con un solo segmento que es la palabra completa). Luego imprime "mal" o el puntaje, dependiendo del puntaje.

El "solucionador" ( S) hace todas las cosas interesantes, y originalmente se desglosó en 4 métodos, que se combinaron. Funciona primero puntuando la segmentación actual, tomando nota de si es inválida (y crucialmente, si es tan inválida que no deberíamos intentar segmentarla más (por rendimiento), omitiendo el resto del cálculo si lo es) . Luego, si no se ha omitido, divide cada segmento de la segmentación en todas partes donde se puede dividir, y encuentra la mejor puntuación de todos estos (llamadas recursivas S). Finalmente, devuelve el mejor puntaje de las segmentaciones subordinadas, de lo contrario, es su propio puntaje o no es válido si su propia segmentación es inválida.

Código con comentarios:

using Q=System.String; // this saves no bytes now

class P
{
    // boring
    static void Main(Q[]A)
    {
        // this can surely be shorter
        // replace capitals
        // I refuse to put this in S (would give us a Q, but we'd have to pay for the Action=null)
        Q s="";

        foreach(var c in A[0])
        {
            var z=(char)(c|32); // ugly
            if(c<z)
                s+=z; // ugly
            A[0]=s+=z; // reuse the array
        }

        int r=S(A); // reuse the array
        System.Console.WriteLine(r<1?"evil":""+r);
    }

    // solve
    static int S(Q[]s) // s is current solution
    {        
        int r=0,t,j,k,
        L=1,Z=s.Length,i=Z,
        T=0, // is score for this solution (segmentation)
        R=2; // R is current return value, as such, 0 -> return -1, 1 -> return 0, 2 -> return T

        // score first
        // factorise stuff, L is LCM
        for(;
            i-->0; // for each segment
            R=t<1?0:R) // segment too short (skip)
        {
            t=s[i].Length;

            k=L; // we cut up k as we cut up c, when we can't cut up k, we need to build up L
            for(j=2;t>1;)
                if(t%j++<1) // j goes into t
                {
                    t/=--j; // cut up t
                    if(k%j<1) // j goes into k
                        k/=j; // cut up k
                    else
                        L*=j; // j does not go into k, build up L
                }
        }

        // recycle i, j, k, (t)

        foreach(var C in Q.Join("",s)) // for each character
            for(i=Z;i-->0;) // for each segment
            {
                for(k=s[j=i].Length;
                    j-->0;) // for all the segments that follow
                    R=k==s[j].Length?0:R; // repeat length (skip)

                j=s[i].IndexOf(C)+1;

                // these both check if this segment contains the char (j > 0)
                R=j*R*s[i].IndexOf(C,j)>1?1:R; // duplicate char (allow)

                T+=j>0?L/k:0; // add on the segment weight
            }

        // R is whether we are invalid or not
        // T is our score

        i=R<1?0:Z; // if segmentation invalid and can't be segmented, skip everything (performance)

        // recycle i, j, k, t
        // first use of r=0

        for(var U=new Q[Z+1];
            i-->0;) // for each segment
            for(j=s[i].Length;
                j-->1; // for each place we can split it
                r=r<1|((t=S(U))>0&t<r)?t:r) // solve where we split thing at i at position j, if this score is better than r, replace r with it
                for(U[k=Z]=s[i].Substring(j); // put second half of s[i] in last position (order doesn't matter)
                    k-->0; // for each char in s[i]
                    U[i]=s[i].Substring(0,j)) // put first half of s[i] in p position
                    U[k]=s[k]; // copy across everything else

        return r<1?R<2?R-1:T:r; // if we didn't find a valid solution more segmented than this, return our score (unless we are invalid, in which case, return R-1), else the score for the more segmentation solution
    }
}