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