# 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.

• Is N always integer? Are intermediate non-integer results allowed? – Howard Mar 26 '12 at 5:00
• The time limit is irrelevant if we're allowed to hard-code a lookup table... – Peter Taylor Mar 26 '12 at 9:16
• @Howard, Lets assume integer division so all intermediate values will be integers as well. – captncraig Mar 26 '12 at 16:25
• @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 Mar 26 '12 at 16:38

### 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));
}

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);
}
}

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

• There's a lot of shared code which could be factored out to improve readability. (If you don't want to do it yourself but you don't mind me doing it, I'll edit, but I don't want to edit without prior permission). – Peter Taylor Mar 26 '12 at 21:22
• @PeterTaylor Please feel free to edit the solution. I also thought about the refactoring but didn't find a nice way which lazily evaluates the string concatenations. – Howard Mar 27 '12 at 3:55
• I applied this algorithm to only push 1s for the bonus and I got a score of 238157 - 10% = 214341.3 – captncraig Mar 27 '12 at 4:50
• I tend to agree with you that this is optimal, but I also can't quite prove it. Perhaps increasing the max for intermediate values could improve scores in very few cases, but also opens up to overflow issues. I think your logic is pretty sound. d- d/ d% are all useless, but I wonder if there is any reason to do something like 1d+d1+*, where the result of the d is not used immediately. – captncraig Mar 27 '12 at 5:08
• @CMP, I increased the max for intermediate values from 6m to 15m and saw no improvement, so the only real possibility for improvement would be if one or two can shave off a character with % (currently necessary for 1 point). – Peter Taylor Mar 27 '12 at 8:35

## JavaScript, 217597

var minNum = new Uint32Array(10001), minMA = ['11-','1','2'];
minNum = 3;
minNum = 1;
minNum = 2;
for(var tr=2,i=2,sum=0;i<=1e4;i++){
var minVal=i<10?i:9e9,j,minMethod=i<10?''+i:'';
if(tr*tr*tr==i){
if(minNum[tr]+4<minVal) minVal=minNum[tr]+4,minMethod=minMA[tr]+"dd**";
tr++;
}
for(j=1;j<10&&j<i;j++) if(minVal>minNum[i-j]+minNum[j]+1) minVal=minNum[i-j]+minNum[j]+1,minMethod=minMA[i-j]+minMA[j]+'+';
if(i>2) for(j=2;j<10&&i>j;j++) if(i%j==0){
if(minVal>minNum[i/j]+minNum[j]+1) minVal=minNum[i/j]+minNum[j]+1,minMethod=minMA[i/j]+minMA[j]+'*';
if(minVal>minNum[i/j]+2*(j-1)){
minVal=minNum[i/j]+2*(j-1);
for(minMethod=minMA[i/j],dd='',pp='',k=j-1;k-->0;dd+='d',pp+='+'); minMethod+=dd+pp;
}
}
for(j=10;j<Math.sqrt(i);j++) if(i%j==0){
if(minVal>minNum[i/j]+minNum[j]+1) minVal=minNum[i/j]+minNum[j]+1,minMethod=minMA[i/j]+minMA[j]+'*';
if(minVal>minNum[i/j]+2*(j-1)){
minVal=minNum[i/j]+2*(j-1);
for(minMethod=minMA[i/j],dd='',pp='',k=j-1;k-->0;dd+='d',pp+='+'); minMethod+=dd+pp;
}
}
if(Math.sqrt(i)==~~Math.sqrt(i)) if(minVal>minNum[Math.sqrt(i)]+2) minVal=minNum[Math.sqrt(i)]+2,minMethod=minMA[Math.sqrt(i)]+'d*';
minNum[i] = minVal; minMA[i] = minMethod;
console.log(i,minVal,minMethod);
}
for(i=0;i<=10000;i++){
sum+=minNum[i];
}
console.log("Score : "+sum);


Quite trivial solution... does not use -, /, and % at all.. :P

I can add the case for n^5, n^7, ..., but that doesn't reduce the score quite well (only ~400).

This problem reminds me of some PE problems... (not saying that this is a part of a PE problem)

2 2 "2"
3 3 "3"
4 4 "4"
5 5 "5"
6 5 "3d+"
7 7 "7"
8 6 "2dd**"
9 5 "3d*"
10 7 "3d*1+"
11 8 "3d*2+"
12 7 "3d+d+"
13 9 "3d+d+1+"
...
9990 25 "3d+d*1+3dd***5*d+"
9991 27 "3d+d*1+3dd***5*d+1+"
9992 27 "4d*d*3d+d*3+*2dd**+"
9993 26 "4d*d*3d+d*3+*3d*+"
9994 27 "4d*d*3d++1+3d+d*2+*"
9995 27 "3d+d*1+3dd***d+1+5*"
9996 23 "7d+d*5d*d+1+*"
9997 24 "4d*d*3*1+3d+d+1+*"
9998 26 "4d*d*3*1+3d+d+1+*1+"
9999 25 "3d*1+d*1+7d*d+1+*"
10000 11 "3d*1+d*d*"
Score : 217597


Here's my baseline solution in C#:

string Make(int n)
{
if(n < 0) return "1" + Make(-n) + "1+-";
if(n == 0) return "11-";
if(n == 1) return "1";
if(n % 2 == 0) return Make(n / 2) + "d+";
return Make(n / 2) + "d+1+";
}

public void CalcTotal()
{
var total = Enumerable.Range(0, 10001).Sum(x => Make(x).Length);
Console.WriteLine(total);
}


Gets a score of 346491 - 10% = 311841.9

• Irrelevant for scoring, but for negative numbers you can do better with "1" + Make(-n) + "1+-"; (and maybe better still as Howard's solution). – Peter Taylor Mar 26 '12 at 17:55
• true. Howard definitely blew this out of the water already, but that is a good optimization. I just threw this together as an intuitive direct solution. – captncraig Mar 26 '12 at 19:05