Como não consigo me concentrar em nenhuma tarefa por mais de 5 segundos, geralmente me pego dividindo as palavras em uma sub-string, cada uma com um comprimento diferente e não contém caracteres repetidos. Por exemplo, a palavra "macarrão" pode ser dividida em "passado" e "a", "pas" e "ta" ou "pa" e "sta" e você obtém a imagem.

No entanto, como lembrar de todas as combinações é difícil, geralmente seleciono apenas uma e gosto de selecionar a melhor. Consideramos a melhor maneira de ser a que tem a menor "pontuação". Sua tarefa será, dada uma palavra, imprimir sua pontuação, considerando as seguintes regras complicadas.

Pontuação

Descrição de como marcar uma palavra:

• Uma palavra é uma sequência de caracteres latinos; as letras maiúsculas devem ser substituídas por 2 da mesma letra minúscula (para que "Caixa" se torne "bbox")

• Um segmento é uma substring contígua (estrita) de uma palavra e não deve conter nenhum caractere duas vezes ("her", "re", "h" são todos segmentos válidos de "Here" ("hhere"), mas "hh" e "antes" não são)

• Uma segmentação é um conjunto de segmentos de diferentes comprimentos que, quando unidos, formam a palavra original ("tre" e "e" makes "tree") e que não podem mais ser segmentados dentro da segmentação (ou seja, "ba" possui um único segmentação, "ba" e "alp" e "habet" não são uma segmentação válida de "alfabeto", porque qualquer um desses itens pode ser segmentado posteriormente (por exemplo, em "a" & "lp" & "habet", que agora é uma segmentação válida ("habet" não pode ser segmentado sem formar um segmento de comprimento 2 ou 1)).

• A pontuação de uma segmentação é a soma das pontuações de cada caractere distinto que aparece na palavra original (depois que as maiúsculas são substituídas)

• A pontuação dos personagens é explicada abaixo

• A pontuação de uma palavra é a pontuação da sua melhor segmentação possível (aquela com a pontuação mais baixa)

Se não existir nenhuma segmentação válida para uma palavra (por exemplo, "Brass" ("bbrass"), que não pode ser segmentada porque o primeiro "b" e o último "s" teriam que estar em seus próprios segmentos, o que resultaria em em dois segmentos do mesmo comprimento), então você deve exibir o texto "evil", caso contrário, você deve exibir a pontuação da palavra.

Pontuação dos personagens

A pontuação dos caracteres é baseada em quantas vezes o caractere aparece e nas ponderações dos segmentos em que aparece. As ponderações dos segmentos dependem dos comprimentos do segmento e do menor múltiplo comum comum dos comprimentos de todos os segmentos em a segmentação.

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

Considere a palavra "azeitona", que pode ser segmentada como "ol" e "ive" e visualizada como 2 caixas da mesma área, uma de "ol" com peso 3 e uma de "ive" com peso 2 (LCM de 6).

ol
ol ive
ol ive

Isso pretende representar as duas caixas, uma feita com 3 "ol" s e outra com 2 "ive" s. Como alternativa, pode ser "o" e "ao vivo" (LCM de 4)

o
o
o
o live

A pontuação de cada caractere é então a soma dos pesos dos segmentos em que aparece, multiplicada pelo número de vezes que aparece após a substituição de maiúsculas (portanto, se aparecer duas vezes, você será cobrado duas vezes cada vez que precisar dizer) )

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

Exemplo de pontuação

Pegamos a palavra "cair", que só pode ser segmentada em "fal" e "l". O menor múltiplo comum de 3 e 1 é 3, então "fal" tem peso 1 e "l" tem peso 3.

    l
    l
fal l

Passando por cada personagem ...

• "f" aparece uma vez e está no segmento "fal" com peso 1, então tem pontuação 1 * 1 = 1

• "a" também aparece apenas uma vez, tem soma de pesos de 1, então possui pontuação 1 * 1 = 1

• "l" aparece duas vezes e aparece em "fal" (peso 1) e "l" (peso 3); portanto, possui pontuação 2 * (1 + 3) = 8

A soma destes é 10 (a pontuação da segmentação e da palavra, pois essa é a segmentação mais agradável). Aqui está isso no mesmo formato que os exemplos abaixo:

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

Pontuações de exemplo

Estes exemplos de pontuações podem ou não ajudar:

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

"livro" é uma palavra do mal, então não tem pontuação.

Observe que "tesouro" pode ser segmentado de várias maneiras, mas a segmentação mostrada se beneficia de ter as letras mais frequentes ("r" e "e") nos segmentos mais longos, para que não tenham tanto peso. A segmentação "t" e "re" e "asure" dariam o mesmo resultado, enquanto "treas" e "ur" e "e" sofreriam, com "e" tendo uma pontuação de 2 * (1 + 10 + 2 ) = 24 por conta própria. Essa observação é realmente o espírito de todo o exercício. Um exemplo de uma pontuação incorreta de "tesouro" (incorreta porque não é derivada da pontuação da segmentação mais agradável (aquela com a pontuação mais baixa)):

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

Entrada

Uma única cadeia contendo apenas caracteres latinos de ambos os casos ("horse", "Horse" e "hOrSe" são todos dados válidos) que podem ser aceitos por STDIN, argumento de linha de comando, argumento de função ou de outra forma, se seu idioma for A escolha não suporta nenhum dos itens mencionados acima.

Resultado

Você deve gerar a pontuação da palavra, que é um número inteiro positivo único maior que 0, ou "mal" se não houver segmentação. A saída deve ser STDOUT ou o argumento de retorno de uma função, a menos que seu idioma de escolha não suporte nenhum deles, nesse caso, faça algo esportivo.

Exemplos

Eu não espero que você imprima todas essas coisas, tudo o que eu quero é a pontuação da palavra ou a saída "evil", por exemplo (entrada seguida por saída)

eye
7

Eel
evil

a
1

Establishments
595

antidisestablishmentarianism
8557

Não estou preocupado com o desempenho, se você consegue pontuar qualquer palavra de 15 letras (depois de substituir maiúsculas) em menos de um minuto em uma máquina sensata (intencionalmente deixada vaga), isso é bom o suficiente para mim.

Este é o código-golfe, que ganhe o menor código.

Agradecemos a PeterTaylor, MartinBüttner e SP3000 por sua ajuda neste desafio

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

Isso é bastante longo ... e também bastante ingênuo. Ele define uma função sem nome que pega a string e retorna pontuação. Demora cerca de 1 segundo para lidar "Establishments", por isso está dentro do prazo. Eu tenho uma versão um pouco mais curta que usa Combinatorica`SetPartitions, mas já leva um minuto para "Establishme".

Aqui está uma versão com espaço em branco:

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

Eu poderia adicionar uma explicação mais detalhada mais tarde. Este código usa a segunda solução desta resposta para obter todas as partições e esta solução para garantir que todas estejam segmentadas ao máximo.

Java 8, 1510 1485 bytes

Este é caminho muito longo. Combinatória nunca é fácil em java. Definitivamente, pode ser reduzido bastante. Ligue com a(string). Isso usa um algoritmo exponencial de memória e tempo; portanto, não espere que ele funcione para entradas longas. Demora cerca de meio segundo para processar Establishments. Falha com um erro de falta de memória 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;}

Tente aqui

Recuado com explicação:

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;
}

Isso também abusa bastante dos genéricos para reduzir a contagem de bytes. Estou bastante surpreso por ter conseguido compilar tudo isso.

Obrigado Ypnypn :)

C # 679 bytes

Essa solução é basicamente baseada na estrutura da minha implementação de teste original e, inicialmente, era apenas uma reescrita de golfe, mas então eu descrevi todas as funções, e agora é horrível. É razoavelmente rápido, resolvendo estabelecimentos em menos de um segundo. É um programa completo que aceita a palavra de entrada como um ú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;}}

o Main método começa criando uma cópia da entrada com as maiúsculas substituídas. Em seguida S, chama o "solucionador", que retorna a pontuação de uma determinada segmentação (a primeira segmentação é aquela com um único segmento que é a palavra inteira). Em seguida, ele imprime "mal" ou a pontuação, dependendo da pontuação.

O "solucionador" (S ) faz todo o material interessante e foi originalmente dividido em quatro métodos, que foram agrupados. Ele funciona primeiro pontuando a segmentação atual, anotando se ela é inválida (e crucialmente, se é tão inválida que não devemos tentar segmentá-la ainda mais (por desempenho), ignorando o restante da computação, se for) . Então, se não tiver sido ignorado, ele divide cada segmento da segmentação em todos os lugares em que pode ser dividido e encontra a melhor pontuação de todos eles (chamada recursivamente S). Por fim, ele retorna a melhor pontuação das segmentações subordinadas; caso contrário, é sua própria pontuação ou é inválida se sua própria segmentação for inválida.

Código com comentários:

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