Latin Word Judgment

Question

Because I can't concentrate on any task for more than about 5 seconds, I often find myself breaking up words into a sub-strings, each of which is a different length and doesn't contain any repeated characters. For example, the word "pasta" might be broken up in "past" & "a", "pas" & "ta", or "pa" & "sta" and you get the picture.

However, because remembering all the combinations is hard, I generally only select one, and I like to select the nicest one. We consider the nicest way to be that which has the lowest "score". Your task will be, given a word, to print its score, given the following complicated rules.

Scoring

Description of how to score a word:

• A word is a string of Latin characters, capital letters should be replaced with 2 of the same lowercase letter (so "Box" becomes "bbox")

• A segment is a contiguous (strict) substring of a word, and must not contain any character twice ("her", "re", "h" are all valid segments of "Here" ("hhere"), but "hh" and "ere" are not)

• A segmentation is a set of segments of different lengths which, when joined, form the original word ("tre" and "e" makes "tree"), and that cannot be further segmented within the segmentation (i.e. "ba" has a single segmentation, "ba"; and "alp" & "habet" is not a valid segmentation of "alphabet", because either of these could be further segmented (e.g. into "a" & "lp" & "habet", which is now a valid segmentation ("habet" can't be segmented without forming a segment of length 2 or 1))).

• The score of a segmentation is the sum of the scores of each distinct character that appears in the original word (once capitals have been replaced)

• The scoring of characters is explained below

• The score of a word is the score of its nicest possible segmentation (that with the lowest score)

If no valid segmentations exist for a word (for example, "Brass" ("bbrass"), which can't be segmented because the first "b" and last "s" would have to be in their own segments, which would result in two segments of the same length), then you should output the text "evil", otherwise you should output the score of the word.

Character scoring

The scoring of characters is based on how many times the character appears, and the weightings of the segments it appears in. The weightings of the segments depends on the lengths of the segment, and the lowest common multiple of the lengths of all the segments in the segmentation.

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

Consider the word "olive", which could be segmented as "ol" & "ive", and visualised as 2 boxes of the same area, one of "ol" with weight 3, and one of "ive" with weight 2 (LCM of 6).

ol
ol ive
ol ive

This is meant to depict the two boxes, one made from 3 "ol"s, and one made from 2 "ive"s. Alternativly, it might be "o" & "live" (LCM of 4)

o
o
o
o live

The score of each character is then the sum of the weights of the segments in which it appears, multiplied by the number of times it appears after replacing capitals (so if it appears twice, you are charged double for each time you have to say it).

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

Scoring example

We take the word "fall", it can only be segmented into "fal" and "l". The lowest common multiple of 3 and 1 is 3, so "fal" has weight 1, and "l" has weight 3.

    l
    l
fal l

Going through each character...

• "f" appears once, and is in the segment "fal" with weight 1, so has score 1*1 = 1

• "a" also appears only once, has sum of weights of 1, so has score 1*1 = 1

• "l" appears twice, and appears in "fal" (weight 1) and "l" (weight 3), so has score 2*(1+3) = 8

The sum of these is 10 (the score of the segmentation, and of the word, as this is the nicest segmentation). Here is this in the same format as the examples below:

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

Example Scorings

These examples of scorings may or may not help:

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

"book" is an evil word, so doesn't have a score.

Note that "treasure" can be segmented in a number of ways, but the segmentation shown benefits from having the more frequent letters ("r" and "e") in the longer segments, so they don't have as much weight. The segmentation "t" & "re" & "asure" would give the same result, while "treas" & "ur" & "e" would suffer, with "e" having a score of 2*(1+10+2) = 24 on its own. This observation is really the spirit of the whole exercise. An example of an incorrect score of "treasure" (incorrect because it's not derived from the score of the nicest segmentation (that with the lowest score)):

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

Input

A single string containing only latin characters of either case ("horse", "Horse", and "hOrSe" are all valid inputs) which can be accepted either by STDIN, Command-line argument, function argument, or otherwise if your language of choice doesn't support any of the aforementioned.

Output

You must output either the score of the word, which is a single positive integer greater than 0, or "evil" if no segmentation exists. Output should be to STDOUT or the return argument of a function, unless your language of choice supports neither of these, in which case do something sportsmanly.

Examples

I do not expect you to print all this stuff, all I want is the score of the word, or the output "evil", for example (input followed by output)

eye
7

Eel
evil

a
1

Establishments
595

antidisestablishmentarianism
8557

I'm not concerned about performance, if you can score just about any 15letter word (after replacing capitals) in under a minute on a sensible (intentionally left vague) machine, that's good enough for me.

This is code-golf, may the shortest code win.

Thanks to PeterTaylor, MartinBüttner, and SP3000 for their help with this challenge

Answer 1

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

This is quite long... and also rather naive. It defines an unnamed function that takes the string and returns score. It takes about 1 second to handle "Establishments", so it's well within the time limit. I've got a slightly shorter version that uses Combinatorica`SetPartitions, but it already takes a minute for "Establishme".

Here is a version with whitespace:

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

I might add a more detailed explanation later. This code uses the second solution from this answer to get all the partitions and this solution to make sure they are all maximally segmented.

Answer 2

Java 8, 1510 1485 bytes

This is way too long. Combinatorics are never easy in java. It definitely can be shortened quite a bit. Call with a(string). This uses an exponential memory and time algorithm; so don't expect it to work for long inputs. It takes about half a second to process Establishments. It crashes with an out of memory error for 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;}

Try here

Indented with explanation:

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

This also abuses generics quite a bit to reduce the byte count. I'm pretty surprised I was able to get all of it to compile.

Thanks Ypnypn :)

Answer 3

C# 679 Bytes

This solution is roughly based off my the structure of my original test implementation, and initially was just a golfed re-write, but then I inlined all the functions, and now it's horrifying. It's reasonably fast, solving Establishments in under a second. It's a complete program that takes the input word as a single paramater of 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;}}

The Main method starts by creating a copy of the input with the capitals replaced. It then calls S, the "solver", which returns the score of a given segmentation (the first segmentation being that with a single segment which is the whole word). It then either prints "evil" or the score, depending on the score.

The "solver" (S) does all the interesting stuff, and was originally broken down down into 4 methods, which were rolled together. It works by first scoring the current segmentation, making a note of whether it is invalid (and crucially, whether it is so invalid we shouldn't try to further segment it (for performance), skipping the rest of the computation if it is). Then, if it hasn't been skipped, it splits each segment in the segmentation everywhere it can be split, and finds the best score of all of these (recursively calling S). Finally, it either returns the best score of the subordinate Segmentations, else it's own score, or invalid if it's own segmentation is invalid.

Code with comments:

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