2 Refactoring
source | link
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)) {
                    int r;

                   String rrpn_n = 2 * n;
                    if (r >= -max && r <= max && !rpns.containsKey(r)) {
                        rpns.put(r, rpns.get(n) + "d+");
                        currentScore.add(r);
                    }

                    if consider(n * (long)2, ncurrentScore, <=rpn_n, max"d+") {;
                        r = consider(n * n;
                        if (r >= -max && r <= max && !rpns.containsKey(r)long) {
                            rpns.put(rn, rpns.get(n)currentScore, +rpn_n, "d*");
                            currentScore.add(r);
                        }
                    }
                }
            }

            // 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) {
                        int r;

                        r = n + m;
                        if (r >= -max && r <= max && !rpns.containsKey(r)) {
                            rpns.put(r, rpns.get(n) + rpns.get(m) + "+");
                            currentScore.add(r);
                        }

                       String rprefix = n - m;
                        if (r >= -max && r <= max && !rpns.containsKey(r)) {
                            rpns.put(r, rpns.get(n)rpn_n + rpns.get(m) + "-");
                            currentScore.add(r);
                        }

                        if (n * (long) m <= max) {
                       // Commutative operators - only rneed =to nconsider *them m;once
                            if (r >= -max && r <= maxn &&< !rpns.containsKey(r)m) {
                                rpns.put(r, rpns.getconsider(n) + rpns.get(m), +currentScore, "*"prefix, "+");
                              consider(n * currentScore.add(rlong);
                         m, currentScore, prefix, }"*");
                        }

                        // Non-commutative operators.
                        consider(n - m, currentScore, prefix, "-");
                        // div and mod only possible if m!=0
                        if (m != 0) {
                            r = consider(n / m;
                            if (r >= -max && r <= max && !rpns.containsKey(r)) {
                                rpns.put(rm, rpns.get(n) + rpns.get(m)currentScore, +prefix, "/");
                                currentScore.addconsider(r);
                            }

                            r = n % m;
                            if (r >= -max && r <= max && !rpns.containsKey(r)) {
                                rpns.put(rm, rpns.get(n) + rpns.get(m)currentScore, +prefix, "%");
                                currentScore.add(r);
                            }
                        }
                    }
                }
            }
        }
    }

    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);
    }
}
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)) {
                    int r;

                    r = 2 * n;
                    if (r >= -max && r <= max && !rpns.containsKey(r)) {
                        rpns.put(r, rpns.get(n) + "d+");
                        currentScore.add(r);
                    }

                    if (n * (long) n <= max) {
                        r = n * n;
                        if (r >= -max && r <= max && !rpns.containsKey(r)) {
                            rpns.put(r, rpns.get(n) + "d*");
                            currentScore.add(r);
                        }
                    }
                }
            }

            // 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) {
                    for (int m : l2) {
                        int r;

                        r = n + m;
                        if (r >= -max && r <= max && !rpns.containsKey(r)) {
                            rpns.put(r, rpns.get(n) + rpns.get(m) + "+");
                            currentScore.add(r);
                        }

                        r = n - m;
                        if (r >= -max && r <= max && !rpns.containsKey(r)) {
                            rpns.put(r, rpns.get(n) + rpns.get(m) + "-");
                            currentScore.add(r);
                        }

                        if (n * (long) m <= max) {
                            r = n * m;
                            if (r >= -max && r <= max && !rpns.containsKey(r)) {
                                rpns.put(r, rpns.get(n) + rpns.get(m) + "*");
                                currentScore.add(r);
                            }
                        }

                        // div and mod only possible if m!=0
                        if (m != 0) {
                            r = n / m;
                            if (r >= -max && r <= max && !rpns.containsKey(r)) {
                                rpns.put(r, rpns.get(n) + rpns.get(m) + "/");
                                currentScore.add(r);
                            }

                            r = n % m;
                            if (r >= -max && r <= max && !rpns.containsKey(r)) {
                                rpns.put(r, rpns.get(n) + rpns.get(m) + "%");
                                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);
    }
}
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);
    }
}
1
source | link

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)) {
                    int r;

                    r = 2 * n;
                    if (r >= -max && r <= max && !rpns.containsKey(r)) {
                        rpns.put(r, rpns.get(n) + "d+");
                        currentScore.add(r);
                    }

                    if (n * (long) n <= max) {
                        r = n * n;
                        if (r >= -max && r <= max && !rpns.containsKey(r)) {
                            rpns.put(r, rpns.get(n) + "d*");
                            currentScore.add(r);
                        }
                    }
                }
            }

            // 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) {
                    for (int m : l2) {
                        int r;

                        r = n + m;
                        if (r >= -max && r <= max && !rpns.containsKey(r)) {
                            rpns.put(r, rpns.get(n) + rpns.get(m) + "+");
                            currentScore.add(r);
                        }

                        r = n - m;
                        if (r >= -max && r <= max && !rpns.containsKey(r)) {
                            rpns.put(r, rpns.get(n) + rpns.get(m) + "-");
                            currentScore.add(r);
                        }

                        if (n * (long) m <= max) {
                            r = n * m;
                            if (r >= -max && r <= max && !rpns.containsKey(r)) {
                                rpns.put(r, rpns.get(n) + rpns.get(m) + "*");
                                currentScore.add(r);
                            }
                        }

                        // div and mod only possible if m!=0
                        if (m != 0) {
                            r = n / m;
                            if (r >= -max && r <= max && !rpns.containsKey(r)) {
                                rpns.put(r, rpns.get(n) + rpns.get(m) + "/");
                                currentScore.add(r);
                            }

                            r = n % m;
                            if (r >= -max && r <= max && !rpns.containsKey(r)) {
                                rpns.put(r, rpns.get(n) + rpns.get(m) + "%");
                                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