Core Wars

Core Wars is a game in which two opposing warrior programs try to destroy each other inside the memory of a virtual machine. They do this by overwriting each other's instructions, and the first program to execute an illegal instruction loses. Each program is written in an assembly-like language called Redcode, and the virtual machine that runs the two programs is the Memory Array Redcode Simulator (MARS). Your task is to write a MARS that reads two Redcode programs, simulates them, and prints which program wins.

MARS simulates an unusual environment compared with typical processors. The exact rules are:

1. Memory has 8000 locations, and each location stores exactly one Redcode instruction. A location cannot store raw data directly; however, every instruction carries two numeric operands, and those operands can be manipulated by other instructions to hold data. This also makes self-modifying code possible.
2. The locations form one continuous array: the first has address 0 and the last has address 7999. Every address computation is done modulo 8000, so addresses wrap around — 8000, 8001, and 8002 refer to the same locations as 0, 1, and 2. This works for negative numbers too: -7481, -15481, 519, and 8519 all refer to the same location.
3. All arithmetic and comparisons are done modulo 8000. An addition must normalize its final result into the range 0 to 7999 (inclusive) before writing it to memory. Consequently -124 is considered greater than 511, because after normalization -124 becomes 7876, and 7876 > 511.
4. The simulator keeps two separate instruction pointers (IPs) holding the address of each warrior's next instruction. After both programs are loaded, the IPs point at each program's first instruction. Each executed instruction increments its IP by one (modulo 8000). If a jump or skip is executed, the IP is instead set to the destination address and execution continues from there.
5. The simulator time-slices between warriors, running one instruction at a time and alternating after each instruction. For example, if the two programs are loaded at addresses 2492 and 6140, the first six instructions run in the order 2492, 6140, 2493, 6141, 2494, 6142 (assuming no jump or skip occurs).

Every MARS instruction has an opcode written as a three-letter mnemonic plus two operands, the A field and the B field. Each operand is a number in 0-7999 and uses one of three addressing modes:

• Immediate operands are prefixed with #, as in #1234. An immediate operand is a literal value. For example, the A field of an ADD (integer addition) may be immediate, in which case its literal value is one of the numbers being added.
• Direct operands are prefixed with \$, as in \$1234. A direct operand is an offset relative to the current IP address. For instance, if ADD #5 \$3 is stored at location 4357, it adds the literal 5 to the value in the B field of location 4360 (4357 + 3); if the same instruction were at location 132, it would use the B field of location 135 (132 + 3).
• Indirect operands are prefixed with @, as in @3, and work like pointers. The indirect operand is an offset relative to the current IP that identifies a first location; the value in the B field of that location is then used as a further offset from that same location to identify a second location. The B field of this second location is the one actually operated on. For example, if location 4357 holds ADD @1 @3, location 4358 holds 11 in its B field, and location 4360 holds 7996 in its B field, then the instruction adds the values in locations 4369 (4358 + 11) and 4356 (4360 + 7996 mod 8000).

Each opcode is defined below. Even instructions that do not use both operands must still specify them, because other instructions may use those operands as data storage. Some instructions update only the B field of another instruction; that changes the field's numeric value but not its addressing mode.

The first line contains a single integer n, the number of independent simulations to run. Each simulation provides a pair of programs, warrior number one and warrior number two, each given in this format:

• One line with an integer m (1 ≤ m ≤ 8000): the number of instructions to load for this warrior.
• One line with an integer a (0 ≤ a ≤ 7999): the address at which loading starts.
• Then m lines, each holding one instruction, loaded into consecutive locations. If loading reaches the end of memory, it wraps around and continues from the beginning.

The address ranges occupied by the two programs never overlap. Every location not loaded with warrior code is initialized to DAT #0 #0. Execution always starts with warrior number one (the warrior read first).

Each simulation runs until one warrior executes a DAT instruction, or until a total of 32000 instructions (counting both warriors) have been executed. If a warrior executes a DAT, the other warrior wins; print Program #x is the winner., where x is 1 or 2 for the winning warrior. If neither warrior executes a DAT before the instruction limit is reached, the warriors tie; print Programs are tied.