Match Editorial

This was one of the harder problem sets, though the examples on the easy problem were sufficiently comprehensive to ensure that almost the full 100 advanced. lingo took top honors, with a narrow victory over Jan_Kupiers.

The Problems

Value	250
Submission Rate	123 / 162 (75.93%)
Success Rate	89 / 123 (72.36%)
High Score	Per for 234.32 points (5 mins 57 secs)
Average Score	159.84 (for 89 correct submissions)

For those who had never heard of the ash and thorn characters, they are æ and þ, respectively, and occur often in most old germanic languages.

The best way to solve this problem is to use the built-in sort method that your language of choice provides. Then, all you have to do is write a comparator that tells which of two words should come first. There are a lot of different ways to write the comparator, but one observation will simplify things a little. You don't really need to worry about the fact that the escaped sequences count only as a single letter. If you are comparing "/ae" or "/th" to an unescaped sequence, the rest of the letters don't matter. Therefore, you can write the comparator with a single for loop:

int value(string a, int idx){
    if(a.charAt(idx) == '/')return a.charAt(idx+1)*2+1;
    else return a.charAt(idx)*2;
}
int compare(string a, string b){
    for(int i = 0; i<min(a.length(),b.length()); i++){
        if(a.charAt(i) != b.charAt(i)){
            int v1 = value(a,i);
            int v2 = value(b,i);
            return v1-v2;
        }
    }
    return a.length()-b.length();
}

RuleBasedCollator r = (RuleBasedCollator)
    Collator.getInstance(new Locale("en","US",""));
Comparator c = new RuleBasedCollator(r.getRules() + 
    " & a < '/'ae < b & t < '/'th < u");
Arrays.sort(words,c);
return words;

Value	1000
Submission Rate	44 / 162 (27.16%)
Success Rate	27 / 44 (61.36%)
High Score	dgarthur for 668.55 points (18 mins 0 secs)
Average Score	488.23 (for 27 correct submissions)

This problem can best be broken into two parts. First, parse the expression, and calculate the result in nanoseconds. Then, pick the correct units, and adjust the result. The grammar for the equation was fairly simple, since it didn't have any parentheses in it (the ones from lg() don't really count, since they can only have a variable inside them). If there is a '+' in the eqation, you should split the equation at the plus, then recursively evaluate the two halves, and add the results together. Otherwise, if there is no plus, but there is an '*', you should again split the equation in half, recursively evaluate, and then multiply the results. If the equation has neither '*' nor '+' in it, then it must have one of the 4 possible TERM forms, each of which is relatively easy to evaluate (just be careful to do everything using doubles):

double evaluate(string equation){
    if(equation.contains('+')){
        int idx = equation.indexOf('+');
        string a = equation.substring(0,idx);
        string b = equation.substring(idx+1);
        return evaluate(a)+evaluate(b);
    }else if(equation.contains('*')){
        int idx = equation.indexOf('*');
        string a = equation.substring(0,idx);
        string b = equation.substring(idx+1);
        return evaluate(a)*evaluate(b);
    }else{
        return term(equation);
    }
}

int[] factors = {1000,1000,1000,60,60,24,365};
String[] units = {
    "nanoseconds",
    "microseconds",
    "milliseconds",
    "seconds",
    "minutes",
    "hours",
    "days",
    "years"};
for(int i = 0; i < units.length; i++){
    if(ops<factors[i]){
        return (int)ops + " " + units[i];
    }
    ops /= factors[i];
}
return (int)ops+" years";