Generate number in reverse polish notation Your task is to write a function which accepts a number N and creates a string of Reverse Polish Notation which will generate that number. Valid operations are:

1-9: Push number onto stack. Only 1-9 are allowed.
+-*/%: take two numbers from top of stack and apply arithmetic operation,
    pushing the result.
d: duplicate - push a copy of the top of the stack


That's all. For - / and % which are order dependent, the operand which was pushed first goes first. ie 63/ = 2 63- = 3 and 64% = 2

Entries are judged not by brevity of code, but by the size of the generated strings. The smaller the better. I also want to encourage pushing smaller numbers rather than bigger ones. The score for a number is calculated like so:

For any number pushed, add that number to the score.
For every operand (+-*/%d) add 1.


Your final score is the sum of your score for all numbers 0 to 10,000 inclusive. Lets go ahead and limit total running time to two minutes for all 10k, on a reasonable machine, to avoid too much brute forcing.

If you can do it only pushing 1s, go ahead and subtract 10% from your score.
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 &lt;= 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&lt;=n&lt;=10000
    final static int max = 6000000;
    final static HashMap&lt;Integer, String&gt; rpns = new HashMap&lt;Integer, String&gt;();

    // maximum score expected for numbers 0&lt;=n&lt;=10000
    final static int maxScore = 26;

    private static void preCalculate() {
        // hashmap which contains all numbers with a given score
        final HashMap&lt;Integer, HashSet&lt;Integer&gt;&gt; perScore = new HashMap&lt;Integer, HashSet&lt;Integer&gt;&gt;();

        // numbers are build by combining those with lower score
        for (int sc = 1; sc &lt;= maxScore; sc++) {
            final HashSet&lt;Integer&gt; currentScore = new HashSet&lt;Integer&gt;();
            perScore.put(sc, currentScore);

            // 1-9 can be reached directly by pushing
            if (sc &lt; 10 &amp;&amp; !rpns.containsKey(sc)) {
                rpns.put(sc, Integer.toString(sc));
                currentScore.add(sc);
            }

            if (sc &gt; 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 &lt;= sc - 2; sc2++) {
                int sc1 = sc - sc2 - 1;
                HashSet&lt;Integer&gt; l1 = perScore.get(sc1);
                HashSet&lt;Integer&gt; 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 &lt; 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&lt;Integer&gt; currentScore, String prefix, String suffix) {
        if (value &lt; -max || value &gt; 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 &lt; 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