5
\$\begingroup\$

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Peter Taylor Mar 26 '12 at 21:22
  • \$\begingroup\$ @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. \$\endgroup\$ – Howard Mar 27 '12 at 3:55
  • \$\begingroup\$ I applied this algorithm to only push 1s for the bonus and I got a score of 238157 - 10% = 214341.3 \$\endgroup\$ – captncraig Mar 27 '12 at 4:50
  • \$\begingroup\$ 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. \$\endgroup\$ – captncraig Mar 27 '12 at 5:08
  • \$\begingroup\$ @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). \$\endgroup\$ – Peter Taylor Mar 27 '12 at 8:35
2
\$\begingroup\$

JavaScript, 217597

var minNum = new Uint32Array(10001), minMA = ['11-','1','2'];
minNum[0] = 3;
minNum[1] = 1;
minNum[2] = 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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Irrelevant for scoring, but for negative numbers you can do better with "1" + Make(-n) + "1+-"; (and maybe better still as Howard's solution). \$\endgroup\$ – Peter Taylor Mar 26 '12 at 17:55
  • \$\begingroup\$ 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. \$\endgroup\$ – captncraig Mar 26 '12 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.