TopCoder Problem Statement - QuiningTopCoder |
Single Round Match 152 Round 1 - Division I, Level Two |
Implement a small programming language, and determine if a program written in this language outputs itself.
001: import java.util.Stack; 002: 003: public class QuiningTopCoder { 004: 005: private static final int MAX_CYCLES = 80000; 006: private static final int MIN_STACK_VAL = -1000000000; 007: private static final int MAX_STACK_VAL = 1000000000; 008: 009: /* 010: * A custom version of the standard Stack. This will return 0 if the user 011: * attempts to pop a an empty stack (default behavior is to throw an 012: * EmptyStackException). Also checks the value being pushed to ensure 013: * it is between MIN_STACK_VAL and MAX_STACK_VAL. If not, it throws 014: * an illegalArgumentException. 015: */ 016: private class MyStack extends Stack{ 017: 018: public Integer pop() { 019: return (isEmpty()) ? 0 : super.pop(); 020: } 021: 022: public Integer push(Integer i) throws IllegalArgumentException { 023: 024: if ((i < MIN_STACK_VAL) || (i > MAX_STACK_VAL)) { 025: throw new IllegalArgumentException(); 026: } 027: return super.push(i); 028: } 029: } 030: 031: 032: // The function for updating the instruction pointer. 033: private static int incIp(int n, int ip, int d) { 034: return ((3 * n) + ip + d) % n; 035: } 036: 037: // Method called by TopCoder. 038: public String testCode(String source) { 039: 040: int ip = 0; 041: int d = 1; 042: int cycles = 0; 043: int n = source.length(); 044: 045: Stack stack = new MyStack(); 046: 047: StringBuilder output = new StringBuilder(); 048: 049: try { 050: 051: while (cycles <= MAX_CYCLES) { 052: 053: char instruction = source.charAt(ip); 054: 055: /* 056: * '0'-'9': pushes the number represented by that digit onto 057: * the stack. 058: */ 059: if ((instruction >= '0') && (instruction <= '9')) { 060: stack.push(instruction - '0'); 061: ip = incIp(n, ip, d); 062: 063: } else { 064: 065: int x, y; 066: 067: switch (instruction) { 068: 069: // '$' : pops a value off the stack, and discards it. 070: case '$': 071: stack.pop(); 072: ip = incIp(n, ip, d); 073: break; 074: 075: /* 076: * ':' : pops a value off the stack, then pushes that 077: * same value onto the stack twice. 078: */ 079: case ':': 080: x = stack.pop(); 081: stack.push(x); 082: stack.push(x); 083: ip = incIp(n, ip, d); 084: break; 085: 086: /* 087: * 'W' : Pops a value A, then pops a value B, then 088: * pushes A, then pushes B. 089: */ 090: case 'W': 091: x = stack.pop(); 092: y = stack.pop(); 093: stack.push(x); 094: stack.push(y); 095: ip = incIp(n, ip, d); 096: break; 097: 098: /* 099: * ',' : pops a value X off of the stack, and prints the 100: * (absolute value of X)%Nth character in the source 101: * code. 102: */ 103: case ',': 104: x = stack.pop(); 105: x = Math.abs(x) % n; 106: output.append(source.charAt(x)); 107: 108: /* 109: * Whenever the output changes, check to see 110: * if we're done, or at least still on track. 111: * */ 112: if (output.toString().equals(source)) { 113: return "QUINES " + cycles; 114: } 115: if (!source.startsWith(output.toString())) { 116: return "MISMATCH " + cycles; 117: } 118: 119: ip = incIp(n, ip, d); 120: break; 121: 122: /* 123: * '+' : pops two values, adds them, and pushes the 124: * result back onto the stack. 125: */ 126: case '+': 127: x = stack.pop(); 128: y = stack.pop(); 129: stack.push(x + y); 130: ip = incIp(n, ip, d); 131: break; 132: 133: /* 134: * '-' : pops two values, subtracts the second popped 135: * value from the first, and pushes the result back onto 136: * the stack. 137: */ 138: case '-': 139: x = stack.pop(); 140: y = stack.pop(); 141: stack.push(x - y); 142: ip = incIp(n, ip, d); 143: break; 144: 145: // '#' : multiplies D by 2 for this cycle only. 146: case '#': 147: ip = incIp(n, ip, (2 * d)); 148: break; 149: 150: // 'R' : multiplies D by -1. 151: case 'R': 152: d *= -1; 153: ip = incIp(n, ip, d); 154: break; 155: 156: /* 157: * 'S' : pops a value, and if positive pushes a 1, else 158: * pushes a -1. 159: */ 160: case 'S': 161: x = stack.pop(); 162: 163: // 0 is treated at not positive. 164: if (x > 0) { 165: stack.push(1); 166: } else { 167: stack.push(-1); 168: } 169: 170: ip = incIp(n, ip, d); 171: break; 172: 173: // '_' : pops a value X, and sets D to that value X%N. 174: case '_': 175: x = stack.pop(); 176: d = x % n; 177: ip = incIp(n, ip, d); 178: break; 179: 180: /* 181: * 'J' : pops a value X, and sets IP to the (absolute 182: * value of X)%N. (IP is not incremented after this step) 183: */ 184: case 'J': 185: x = stack.pop(); 186: ip = Math.abs(x) % n; 187: break; 188: 189: /* 190: * '@' : stops the program 191: * It must be a BADEND here, because if the output 192: * had matched the source, then we would have caught it 193: * in the ',' command. 194: */ 195: case '@': 196: return "BADEND " + cycles; 197: 198: // Should not reach this so long as the input is valid. 199: default: 200: return "ERROR bad command: " + instruction; 201: 202: } 203: } 204: cycles++; 205: } 206: 207: // Exceeded MAX_CYCLES 208: return "TIMEOUT"; 209: 210: } catch (IllegalArgumentException e) { 211: 212: // A value outside of MIN_STACK_VAL | MAX_STACK_VAL was pushed. 213: return "OVERFLOW " + cycles; 214: } 215: } 216: }
This is a pretty straight forward problem. Just follow the instructions carefully, and you shouldn't run into any problems.
To implement the stack, I chose to extend java.util.Stack and override the pop() and push() methods. Although the problem doesn't explicitly state it, you can see from the first example that if pop() is called on an empty stack, it should return 0. The default behavior of java.util.Stack is to throw an EmptyStackException. I also modified push() to check that the value is between MIN_STACK_VAL (-1000000000) and MAX_STACK_VAL (1000000000) before pushing it. If the value is outside these bounds, it will throw an IllegalArgumentException.
When the ',' command is encountered, a value is popped from the stack and appended to output. This is the only time that output is modified. Whenever output changes, we check to see if it now equals source, or failing that, ensure source continues to begin with output.
Since output is only changed by the ',' command, if '@' is ever encountered, we return BADEND. At that point output cannot match the program since we would have caught it when processing the ',' command.
The while loop watches the value of cycles (which gets incremented after each command is processed), and terminates when it reaches MAX_CYCLES.
The only other exit point is when we catch an IllegalArgumentException from pushing a value outside the legal range onto the stack. This exception is caught and returns an OVERFLOW message.
The rest of the program simply implements the logic given in the problem statement. Again, be careful and you won't have any problems.
No comments:
Post a Comment