Score 199503, Java solution
import java.util.HashMap;
import java.util.HashSet;
public class RPN {
public static void main(String[] args) {
// Loop to calculate total over all 10001 numbers as defined in puzzle
int total = 0;
System.out.println("n\tscore\trpn");
for (int k = 0; k <= 10000; k++) {
final String rpn = findRPN(k);
final int scr = calcScore(rpn);
System.out.println(k + "\t" + scr + "\t" + rpn);
total += scr;
}
System.out.println("TOTAL: " + total);
}
// simple scoring calculator for a given rpn representation (ignores 10% bonus)
private static int calcScore(String rpn) {
int score = 0;
for (char ch : rpn.toCharArray()) {
if (Character.isDigit(ch)) {
score += ch - '0';
} else {
score++;
}
}
return score;
}
// hashmap caching intermediate results and all results for 0<=n<=10000
final static int max = 6000000;
final static HashMap<Integer, String> rpns = new HashMap<Integer, String>();
// maximum score expected for numbers 0<=n<=10000
final static int maxScore = 26;
private static void preCalculate() {
// hashmap which contains all numbers with a given score
final HashMap<Integer, HashSet<Integer>> perScore = new HashMap<Integer, HashSet<Integer>>();
// numbers are build by combining those with lower score
for (int sc = 1; sc <= maxScore; sc++) {
final HashSet<Integer> currentScore = new HashSet<Integer>();
perScore.put(sc, currentScore);
// 1-9 can be reached directly by pushing
if (sc < 10 && !rpns.containsKey(sc)) {
rpns.put(sc, Integer.toString(sc));
currentScore.add(sc);
}
if (sc > 2) {
// score is increased by 2 if appending "d+" or "d*" to an existing rpn
for (int n : perScore.get(sc - 2)) {
String rpn_n = rpns.get(n);
consider(n * 2, currentScore, rpn_n, "d+");
consider(n * (long)n, currentScore, rpn_n, "d*");
}
}
// another possibility to get score sc is to take two operands
// with scores sc1 and sc2 and add another operator
// with the requirement that sc1 + sc2 + 1 = sc
for (int sc2 = 1; sc2 <= sc - 2; sc2++) {
int sc1 = sc - sc2 - 1;
HashSet<Integer> l1 = perScore.get(sc1);
HashSet<Integer> l2 = perScore.get(sc2);
// try all combinations of operators from list 1 and list 2
// with each operator + - * / and %
for (int n : l1) {
String rpn_n = rpns.get(n);
for (int m : l2) {
String prefix = rpn_n + rpns.get(m);
// Commutative operators - only need to consider them once
if (n < m) {
consider(n + m, currentScore, prefix, "+");
consider(n * (long)m, currentScore, prefix, "*");
}
// Non-commutative operators.
consider(n - m, currentScore, prefix, "-");
// div and mod only possible if m!=0
if (m != 0) {
consider(n / m, currentScore, prefix, "/");
consider(n % m, currentScore, prefix, "%");
}
}
}
}
}
}
private static void consider(long value, HashSet<Integer> currentScore, String prefix, String suffix) {
if (value < -max || value > max) return;
Integer r = Integer.valueOf((int)value);
if (!rpns.containsKey(r)) {
rpns.put(r, prefix + suffix);
currentScore.add(r);
}
}
private static String findRPN(int number) {
if (rpns.isEmpty()) {
preCalculate();
}
// if number is negative try 1(-n+1)-
if (number < 0) {
return "1" + findRPN(-number + 1) + "-";
}
// if number not in precalculated list try number/2
if (!rpns.containsKey(number)) {
if (number % 2 == 0) {
return findRPN(number / 2) + "d+";
} else {
return findRPN(number / 2) + "d+1+";
}
}
// otherwise use cached result
return rpns.get(number);
}
}
The solution is pretty much optimized to get a good score within the defined range of numbers (i.e. 0 to 10000). It sacrifices non-optimal solutions outside the range for (hopefully) optimal representations within. Nevertheless it will still work for other numbers too.
I think the score given by that solution is very close to optimal although I'm not able to prove it.
Output:
n score rpn
0 3 11-
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 5 3d+
7 7 7
8 6 4d+
9 5 3d*
10 7 5d+
11 8 3d*2+
12 7 3d+d+
...
9990 19 5d+d*d*3d*-1-
9991 17 5d+d*d*3d*-
9992 18 5d*d+d*2-d+d+
9993 19 5d+d*d*3d+-1-
9994 17 5d+d*d*3d+-
9995 17 5d+d*d*5-
9996 16 5d+d*d*4-
9997 15 5d+d*d*3-
9998 14 5d+d*d*2-
9999 13 5d+d*d*1-
10000 11 5d+d*d*
TOTAL: 199503
3Is
Nalways integer? Are intermediate non-integer results allowed? – Howard – 2012-03-26T05:00:56.9932The time limit is irrelevant if we're allowed to hard-code a lookup table... – Peter Taylor – 2012-03-26T09:16:58.887
@Howard, Lets assume integer division so all intermediate values will be integers as well. – captncraig – 2012-03-26T16:25:35.247
@Peter I can't really disallow that, but it is not particularly useful if it can't calculate values outside of the given range on the fly. – captncraig – 2012-03-26T16:38:34.920