Qualification Problem Set 3 January 1112, 2005 Summary 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 ProblemsDictionarySorterUsed as: Division One  Level One:
For those who had never heard of the ash and thorn characters, they are æ
and þ, respectively, and occur often in most old germanic
languages. 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 v1v2; } } return a.length()b.length(); }Finally, if you really knew your Java API well, you could use the relatively obscure java.text.RuleBasedCollator: 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;TimeAnalysis Used as: Division One  Level Three:
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); } }Once you have the result in nanoseconds, you can hard code the different ranges as constants, or calculate them doing something like the following. 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"; 
