TopCoder problem "QuiningTopCoder" used in SRM 152 (Division I Level Two)



Problem Statement

    

You're running a special TopCoder competition where all programs are written in a derivative of a restrictive language called Unefunge, and all programs must complete in under 80,000 cycles. Furthermore, all programs are required to be Quines. For the purpose of this problem, a Quine is a special type of program that prints out its own source code before it prints anything else. Thus, in order for the Unefunge program ":,:9#@_1+" to be a legal program it would first have to print the string ":,:9#@_1+".

The language Unefunge works like this: a program is just a single line of characters of length N, where N is between 1 and 50 inclusive. The program never changes. An instruction pointer starts with the value 0 (called the IP), a delta is given the value 1 (called D), and an empty stack is created. The stack will store integer values during program execution in a first-in-last-out manner; if a number is pushed, it is placed in the stack, and if a value is popped, the last number pushed is removed (or a 0 is popped if the stack is empty). During each cycle, the IPth character in the program is read, the instruction corresponding to that character is executed, and then IP is incremented to the new value (3*N+IP+D)%N. The instructions are as follows:

  • '0'-'9': pushes the number represented by that digit onto the stack.
  • '$' : pops a value off the stack, and discards it.
  • ':' : pops a value off the stack, then pushes that same value onto the stack twice.
  • 'W' : Pops a value A, then pops a value B, then pushes A, then pushes B.
  • ',' : pops a value X off of the stack, and prints the (absolute value of X)%Nth character in the source code.
  • '+' : pops two values, adds them, and pushes the result back onto the stack.
  • '-' : pops two values, subtracts the second popped value from the first, and pushes the result back onto the stack.
  • '#' : multiplies D by 2 for this cycle only.
  • 'R' : multiplies D by -1.
  • 'S' : pops a value, and if positive pushes a 1, else pushes a -1.
  • '_' : pops a value X, and sets D to that value X%N.
  • 'J' : pops a value X, and sets IP to the (absolute value of X)%N. (IP is not incremented after this step)
  • '@' : stops the program

You have to write a program that takes a String source and checks whether or not the program being submitted is valid. If the program doesn't end in 80,000 cycles or less, return "TIMEOUT". Otherwise you'll return a message with the ending condition replacing X with the cycle number in which this ending condition is reached.

  • If the program ends before printing out its source, return the string "BADEND X".
  • If a number less than -1000000000 or a number greater than 1000000000 is pushed onto the stack, return "OVERFLOW X".
  • If the result of an instruction makes it impossible for the output to match the source code, return "MISMATCH X".
  • If the result of an instruction makes the output match the source code, return "QUINES X".
 

Definition

    
Class:QuiningTopCoder
Method:testCode
Parameters:String
Returns:String
Method signature:String testCode(String source)
(be sure your method is public)
    
 

Notes

-Start counting cycles at cycle 0. This should be obvious from the first example.
-Note that digits are not grouped, but pushed on in order: the code "3004" pushes a 3, then a 0, then another 0, then finally a 4, so the stack would contain the four numbers [3,0,0,4] and not the single number [3004].
 

Constraints

-source will contain between 1 and 50 characters inclusive.
-source will only consist of characters contained in "0123456789:$W,+-#RS_J@" (quotes included for clarity).
 

Examples

0)
    
","
Returns: "QUINES 0"
The shortest quine.
1)
    
"_"
Returns: "TIMEOUT"
This pops a 0 from the stack and places it into delta, freezing the code where it stands.
2)
    
"1:+:1J"
Returns: "OVERFLOW 147"
This Unefunge code creates a stack of the powers of 2, until it overflows 1000000000.
3)
    
"0,1+:#@:$1J"
Returns: "QUINES 91"
Note the irrelevant commands in the center of this quine. If code starts with "0,1+:", ends with "1J", and the middle preserves the first two elements on the stack, then the code is a quine.
4)
    
"0,1+::9W-9W-S1W1W:+2_J_@_@"
Returns: "BADEND 437"
This code prints the first 18 characters of its code before halting.
5)
    
"#R,#:+1+:#,R#"
Returns: "QUINES 97"
This non-trivial code is both a quine and a palindrome. :)
6)
    
"R,#1+1:"
Returns: "MISMATCH 7"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1764

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4565&pm=1764

Writer:

leadhyena_inran

Testers:

lbackstrom , brett1479

Problem categories:

Simulation