5
\$\begingroup\$

Write a program to convert Polish prefix notation to infix notation, then change it to an RPN-to-infix converter in the shortest number of chars.

Your score is 100 minus the number of characters changed, added and deleted.

  • Don't write one PPN and one RPN function, then do something like:
    "I changed rpn(raw_input()) to ppn(raw_input())"
  • No ingenious variations of the above rule such as

    def f(s, rpn = False):
    if rpn:
        #rpn logic here
    else: 
        #ppn logic here
    
  • In short, your program must only implement one kind of logic, not both.

  • It must not be possible to only delete characters from the original program and so obtain a program which converts RPN to infix.
  • Try not to use inbuilt libraries.
  • Accept input from STDIN or from a file.
  • Note that program length itself does not matter.
  • Have fun.
\$\endgroup\$
  • \$\begingroup\$ Anyone who doesn't score 100 isn't really trying. The only way I can see to draw a clear line which prevents that is to say something along the lines of "It must not be possible to delete characters from the original program and so obtain a program which converts RPN to infix". \$\endgroup\$ – Peter Taylor May 3 '13 at 11:42
  • \$\begingroup\$ Could you explain why? Besides, deleted chars also count. \$\endgroup\$ – Soham Chowdhury May 3 '13 at 12:09
  • 6
    \$\begingroup\$ If the first token is a number, it's RPN: otherwise it's PPN. Dead easy to detect. \$\endgroup\$ – Peter Taylor May 3 '13 at 12:44
  • \$\begingroup\$ @PeterTaylor Even the "delete characters" version can be hacked. Simply encode your program using any non-basic scheme and add the decoding code - you can't remove any characters without breaking the program. \$\endgroup\$ – Howard May 4 '13 at 5:36
  • 1
    \$\begingroup\$ The last tip doesn't matter, as long as you use the same code in both it won't modify your score. \$\endgroup\$ – user8777 Aug 14 '13 at 4:55
12
\$\begingroup\$

Python - 100!

I'm pretty sure I've met all the criteria. I don't think its possible to make it more identical, without just having a big ol' if block, which would violate the criteria. Using cmp(), and what @PeterTaylor pointed out you can determine the direction you need to go. Rather than use an if/then which would violate the spirit of the challenge, this get the position of the first number and operator and compares those. While the list comprehensions use an if this is just to safely filter the indices and doesn't direct help determine if we are doing forward or reverse polish notation, but this does bend the rules a bit.

Rule-bending program: Both prefix and reverse Polish notation

s = raw_input().strip()                          # Get input
ops = "*-+/^"                                    # A string of operators
num="0123456789"                                 # A string of numbers
p_num= min([s.index(n) for n in num if n in s])  # Find the first number
p_op = min([s.index(o) for o in ops if o in s])  # Find the first operator
                                                 # We use the above 2 lines to determine what
                                                 #   direction we are going on line '2' below

                          #  Just like the original below
s=s.split()                  #  1. Split the input
d = cmp(p_op,p_num)          #  2. Set the direction... depending on what comes first!
                             #     If the first number is before the operator, go forwards
                             #     If the first number is after the operator, go backwards
def f(i):                    #  3. Define our recursive function
 if s[i] in operators:       #  4. If its an operator...
  a = f(i+d)                 #  5.  Recursively get the first argument
  b = f(i+d)                 #  6.  By the time the above is resolved the array is modified
                             #     So we can use the same offset
  c = [a,b,a]                #  7. Mash these in a padded array so the trick below works
  inf = c[d-1]+s.pop(i)+c[d] #  8. Lets put these in order... BASED ON d!!
                             #      And remove the operator from the array
  return "("+inf+")"         #  9. Return the infix version of this operator
 return s.pop(i)             # 10. Just a number?, pop and return.
print f([0,-1,42][d-1])      # 11. Call the recursive start case from the head of the array
                             #    i.e element 0, or just 0.
                             #    Print the final infix

If the above is too rule bendy, here is the code I had before that scored 99.

Original program: Polish prefix notation

s = raw_input().split(" ")   #  1. Get input
d = 1                         # 2. Set the direction to forwards
                             #     If the first number is before the operator, go forwards
                             #     If the first number is after the operator, go backwards
def f(i):                    #  3. Define our recursive function
 if s[i] in operators:       #  4. If its an operator...
  a = f(i+d)                 #  5.  Recursively get the first argument
  b = f(i+d)                 #  6.  By the time the above is resolved the array is modified
                             #     So we can use the same offset
  c = [a,b,a]                #  7. Mash these in a padded array so the trick below works
  inf = c[d-1]+s.pop(i)+c[d] #  8. Lets put these in order... BASED ON d!!
                             #      And remove the operator from the array
  return "("+inf+")"         #  9. Return the infix version of this operator
 return s.pop(i)             # 10. Just a number?, pop and return.
print f([0,-1,42][d-1])      # 11. Call the recursive start case from the head of the array
                             #    i.e element 0, or just 0.
                             #    Print the final infix

Modified to produce: Reverse polish notation

s = raw_input().split(" ")
d = -1                        # 2. Set the direction to backwards
def f(i):
 if s[i] in "*-+/^":
  a = f(i+d)
  b = f(i+d)
  c = [a,b,a]
  inf = c[d-1]+s.pop(i)+c[d]
  return "("+inf+")"
 return s.pop(i)
print f([0,-1,42][d-1])       #11. No change, but this pulls the second last (-2) element
                              #    Hence, why we bump it to 3 elements long.

Differences (not including the comments):

  • Line 2: 1 char, added - to change from +1 to -1

For a total of 1 character changed, which in Polish notation, gives

- 100 1 = 99
\$\endgroup\$
  • \$\begingroup\$ - 100 1 = 99 was the icing on the cake. Nice answer, and seeing how this is the best possible... \$\endgroup\$ – Soham Chowdhury Aug 17 '13 at 5:30

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.