Battle of programs

 

Core War is a programming game, created by D. G. Jones and A. K. Dewdney (1984), in which two programs - the warriors - compete for the control of a MARS (Memory Array Redcode Simulator) computer. The warriors are written in a special assembly language named Redcode. The goal of the game is to cause the opposing program to terminate, leaving your program in possession of the machine.

 

The problem

Construct a MARS virtual machine to run a battle between two warriors.

The core or arena (the memory of the MARS computer) is a circular random access memory of instructions, empty except for the competing programs. The basic unit of memory is one instruction, instead of one byte as is usual.

Each Redcode instruction contains five parts:

  • the OpCode itself;

  • the type of the source value (TA);

  • the source field (A field);

  • the type of the target value (TB);

  • the target field (B field).

 

The assembly mnemonics and their informal semantics is explained below:

Mnemonic

A field

B field

#code

Meaning

DAT

 

value

0

Data variables. If executed, kills the running program. Fields TA, TB, and A are 0.

MOV

source

target

1

Copies data from source to target.

ADD

source

target

2

Adds source to target. Stores the result in target.

JMP

target

 

4

Continues the execution in target address. Fields TB and B are 0.

CMP

source

target

8

Compares source and target and skips the next instruction if they are equal.

 

Programs have no way of knowing where they reside in memory or where the memory ends, since there are no absolute addresses. Addresses are always computed relatively to the current address of execution. So address 0 means the current instruction, not the first instruction in the memory; the next instruction has address 1. All values are computed modulo the size of the memory (remember that the memory is circular).

Value types (TA and TB) define the meaning of the values in fields (A and B) and may be of three forms:

  • 0 means an immediate value, i.e. the value of the field is interpreted as an instruction or a number (it can not be used as an address);

  • 1 means a direct address, i.e. the value of the field is treated as an address relatively to the address of the current instruction;

  • 2 means an indirect address, i.e. the value of the field represents the address where there is a value to be treated as a direct address.

As an example, instruction 1 0 4 1 3 is interpreted as

1

OpCode: MOV (see table above)

0

TA: Field A is an immediate value

4

Field A: is number (DAT instruction) 4

1

TB: Field B is a direct address

3

Field B: address of the instruction three positions after the current instruction

 

If the address of the instruction is 421

 

 

The MARS virtual machine executes one instruction at a time, and then proceeds to the next one in the memory, unless the instruction explicitly tells it to jump to another address. On start up, MARS loads both warriors into memory and starts executing the first instruction of the first program loaded. Then it runs the first instruction of the second program and continues executing instructions alternately for both programs, one instruction at a time. If MARS tries to execute a DAT instruction of one program, the computation terminates and the other program wins the battle.

 

As an example consider the following program for warrior 1, loaded at absolute address 4 of a memory of size 20 (the program for warrior 2 is loaded, for example, at absolute address 13). In this example we consider absolute addresses between 0 and 19.

The first instruction adds (OpCode is 2) immediate number 4 (TA is 0) to the value in direct address 3 (TB is 1). This means that number 4 should be added to the value in address 7 (the address of the add instruction 4 plus 3). The value in address 7 becomes 0 0 0 0 3 (mind the modular addition (19 + 4) mod 20).

 

 

After executing the first instruction of warrior 2, the program proceeds by executing the second instruction of warrior 1 (in adress 5): move (OpCode is 1) immediate value 1 (TA is 0) to indirect address 2 (TB is 2).  To resolve an indirect address, first access memory address 7 (the address of the mov instruction 5 plus 2) and then use this number (3) as a direct address. Therefore, immediate value 1 will be written in memory address 8 (the address of the mov instruction 5 plus 3 � the value in memory address 7). After executing the second instruction of warrior 2, the next instruction of warrior 1 (in address 6) is executed: it tells MARS to proceed execution (jump) in instruction 4 (the address of the jump instruction (6 + 18) mod 20).

This program will write DAT instructions every four addresses of memory. Why? It hopes to hit its opponent and forces him to execute a DAT instruction, thus loosing the battle.

 

Input

The input file contains the information about the size of the arena, how many steps should be run in case no program dominates MARS, and the worriers themselves.

  • Line 1 indicates the size of the memory;

  • Line 2 specifies the maximum number of instructions to run for each program;

  • Line 3 contains the absolute address where program 1 must be loaded.

  • Line 4 and the following include the list of instructions for program 1. The list is terminated with a line containing 9 0 0 0 0.

  • The line after the list of instructions of program 1 contains the absolute address where program 2 must be loaded.

  • The following lines consist of the list of the instructions for program 2 (terminated also with 9 0 0 0 0).

Each instruction is in a line and is composed of 5 numbers (as described above) and an optional string containing a comment to facilitates the reading of the program and has no meaning for the virtual machine. For the sake of readability  (in comments) we prefix immediate values with symbol # and indirect addresses with symbol @. The line indicating the end of a program list (9 0 0 0 0) has no meaning in MARS (it is not an instruction) and must not be loaded into memory.

 

Output

The simulator should output:

  • In line 1 the number of steps executed;

  • In line 2 the winner of the battle

  • 0 - tie game;

  • 1 - player one won;

  • 2 - player two won;

  • In line 3 and the following the contents of the MARS memory, one instruction per line.

 

Sample input

20
7
4
2 0 4 1 3       ADD #4, 3
1 0 1 2 2       MOV #1, @2
4 1 18 0 0     JMP -2
0 0 0 0 19     DAT -1
9 0 0 0 0       END
13
1 1 0 1 1       MOV 0, 1
9 0 0 0 0       END

Sample output

7
0
1 1 0 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 0 4 1 3
1 0 1 2 2
4 1 18 0 0
0 0 0 0 11
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
1 1 0 1 1
1 1 0 1 1
1 1 0 1 1
1 1 0 1 1
1 1 0 1 1
1 1 0 1 1
1 1 0 1 1