cho.shCore Wars
시간 제한1초메모리 제한128 MB문제
Core Wars는 두 개의 전사(warrior) 프로그램이 가상 머신의 메모리 안에서 서로를 파괴하려고 겨루는 게임입니다. 두 프로그램은 상대의 명령어를 덮어써서 공격하며, 잘못된(실행할 수 없는) 명령어를 먼저 실행한 프로그램이 패배합니다. 각 프로그램은 Redcode라는 어셈블리 유사 언어로 작성되고, 두 프로그램을 실행하는 가상 머신을 MARS(Memory Array Redcode Simulator)라고 부릅니다. 당신의 목표는 두 Redcode 프로그램을 읽어 시뮬레이션하고 어느 프로그램이 이겼는지 출력하는 MARS를 작성하는 것입니다.
MARS는 일반적인 프로세서와는 다른 독특한 환경을 시뮬레이션합니다. 규칙은 다음과 같습니다.
- 메모리에는 8000개의 위치가 있고, 각 위치에는 정확히 하나의 Redcode 명령어가 저장됩니다. 위치에 데이터를 직접 저장할 수는 없지만, 모든 명령어는 두 개의 숫자 피연산자를 가지며 다른 명령어가 이 피연산자를 조작해 데이터로 활용할 수 있습니다. 이 때문에 자기 수정(self-modifying) 코드도 가능합니다.
- 위치들은 하나의 연속된 배열을 이룹니다. 첫 위치의 주소는 0, 마지막 위치의 주소는 7999입니다. 모든 주소 계산은 8000으로 나눈 나머지(모듈로 8000)로 이루어져 주소가 순환합니다. 즉 8000, 8001, 8002는 각각 0, 1, 2와 같은 위치를 가리킵니다. 음수에도 적용되어 -7481, -15481, 519, 8519는 모두 같은 위치를 가리킵니다.
- 모든 산술과 비교는 모듈로 8000으로 수행됩니다. 덧셈은 결과를 메모리에 쓰기 전에 반드시 0 이상 7999 이하 범위로 정규화해야 합니다. 따라서 -124는 511보다 크다고 취급됩니다. 정규화하면 -124는 7876이 되고 7876 > 511이기 때문입니다.
- 시뮬레이터는 각 전사의 다음 실행 명령어 주소를 담는 두 개의 독립된 명령어 포인터(IP)를 유지합니다. 두 프로그램을 적재한 뒤 각 IP는 해당 프로그램의 첫 명령어를 가리킵니다. 명령어를 하나 실행할 때마다 IP는 1씩 증가합니다(모듈로 8000). 점프(jump)나 건너뛰기(skip)가 실행되면 IP는 증가하는 대신 목적지 주소로 설정되고 그곳부터 실행이 이어집니다.
- 시뮬레이터는 한 번에 한 명령어씩 실행하며 매 명령어마다 두 전사를 번갈아 처리하는 방식으로 시간을 분할합니다. 예를 들어 두 프로그램이 주소 2492와 6140에 적재되었다면, (점프나 건너뛰기가 없을 때) 처음 여섯 명령어는 2492, 6140, 2493, 6141, 2494, 6142 순서로 실행됩니다.
모든 MARS 명령어는 세 글자 니모닉으로 표기되는 연산 코드(opcode)와 두 피연산자 A 필드, B 필드로 구성됩니다. 각 피연산자는 0-7999 범위의 수이며 세 가지 주소 지정 방식 중 하나를 사용합니다.
- 즉시(immediate) 피연산자는 앞에
#를 붙여#1234처럼 씁니다. 즉시 피연산자는 리터럴 값 자체입니다. 예를 들어 정수 덧셈을 수행하는ADD의 A 필드가 즉시 피연산자이면 그 리터럴 값이 더해지는 수 중 하나가 됩니다. - 직접(direct) 피연산자는 앞에
\$를 붙여\$1234처럼 씁니다. 직접 피연산자는 현재 IP 주소에 대한 상대 오프셋입니다. 예를 들어ADD #5 \$3이 위치 4357에 저장되어 있으면 리터럴 5를 위치 4360(4357 + 3)의 B 필드 값에 더합니다. 같은 명령어가 위치 132에 있으면 위치 135(132 + 3)의 B 필드를 사용합니다. - 간접(indirect) 피연산자는 앞에
@를 붙여@3처럼 쓰며 포인터처럼 동작합니다. 간접 피연산자는 현재 IP에 대한 상대 오프셋으로 첫 번째 위치를 가리키고, 그 위치의 B 필드 값이 다시 그 위치로부터의 오프셋으로 사용되어 두 번째 위치를 가리킵니다. 실제로 연산되는 것은 이 두 번째 위치의 B 필드입니다. 예를 들어 위치 4357에ADD @1 @3이 있고 위치 4358의 B 필드가 11, 위치 4360의 B 필드가 7996이라면, 이 명령어는 위치 4369(4358 + 11)와 위치 4356(4360 + 7996 모듈로 8000)의 값을 더합니다.
각 opcode의 동작은 아래와 같습니다. 두 피연산자를 모두 사용하지 않는 명령어라도 다른 명령어가 그 피연산자를 데이터 저장에 쓸 수 있으므로 두 피연산자를 반드시 지정해야 합니다. 일부 명령어는 다른 명령어의 B 필드만 갱신하는데, 이는 필드의 수치 값만 바꾸고 주소 지정 방식은 바꾸지 않습니다.
| 명령어 | 동작 |
|---|---|
| DAT | 두 가지 용도가 있습니다. 임의 데이터를 담는 범용 자리표시자이며, 이 명령어를 실행하려 하면 시뮬레이션이 종료되고 실행한 프로그램이 패배합니다. 프로그램이 끝나는 유일한 방법이므로 각 전사는 상대를 DAT 명령어로 덮어쓰려 합니다. 두 피연산자 모두 즉시여야 합니다. |
| MOV | A 피연산자가 즉시이면 그 값이 MOV의 B 피연산자가 지정하는 명령어의 B 필드로 복사됩니다. 즉시가 아니면 위치 A의 명령어 전체(모든 필드 값과 주소 지정 방식 포함)가 위치 B로 복사됩니다. B 피연산자는 즉시일 수 없습니다. |
| ADD | A 피연산자가 즉시이면 그 값이 ADD의 B 피연산자가 지정하는 명령어의 B 필드에 더해져 그 B 필드에 다시 저장됩니다. 즉시가 아니면 두 피연산자 모두 명령어를 지정합니다. 위치 A 명령어의 A·B 필드가 위치 B 명령어의 A·B 필드에 각각 더해지고, 두 결과가 ADD의 B 피연산자가 지정하는 명령어의 A·B 필드에 각각 저장됩니다. B 피연산자는 즉시일 수 없습니다. |
| JMP | A 피연산자가 가리키는 주소로 점프합니다. IP가 증가하는 대신 그 주소로 설정됩니다. A 피연산자는 즉시일 수 없습니다. B 피연산자는 즉시여야 하지만 사용되지 않습니다. |
| JMZ | JMZ의 B 피연산자가 지정하는 명령어의 B 필드가 0이면 A 피연산자가 가리키는 주소로 점프합니다. 두 피연산자 모두 즉시일 수 없습니다. |
| SLT | A가 즉시이면 그 값을 SLT의 B 피연산자가 지정하는 명령어의 B 필드와 비교하고, 즉시가 아니면 두 피연산자가 지정하는 두 명령어의 B 필드를 비교합니다. 첫 번째 값(A가 지정한 값)이 두 번째 값보다 작으면 다음 명령어를 건너뜁니다. B 피연산자는 즉시일 수 없습니다. |
| CMP | A와 B가 지정하는 두 위치의 전체 내용을 비교합니다. 두 위치가 같으면(opcode가 같고 두 피연산자 필드의 값과 주소 지정 방식이 모두 같으면) 다음 명령어를 건너뜁니다. 두 피연산자 모두 즉시일 수 없습니다. |
입력
첫 줄에는 실행할 독립적인 시뮬레이션의 개수를 나타내는 정수 n이 주어집니다. 각 시뮬레이션마다 1번 전사와 2번 전사로 지정되는 두 프로그램이 다음 형식으로 주어집니다.
- 한 줄에 정수 m (1 ≤ m ≤ 8000): 이 전사가 적재할 명령어의 개수.
- 한 줄에 정수 a (0 ≤ a ≤ 7999): 코드 적재를 시작할 주소.
- 이어서 m개의 줄에 한 줄당 하나씩 전사의 명령어가 주어지며, 연속된 위치에 적재됩니다. 적재가 메모리 끝에 도달하면 순환하여 처음부터 이어서 적재됩니다.
두 프로그램이 차지하는 주소 범위는 겹치지 않습니다. 전사 코드가 적재되지 않은 모든 위치는 DAT #0 #0으로 초기화됩니다. 실행은 항상 1번 전사(입력에서 먼저 읽은 전사)부터 시작합니다.
출력
각 시뮬레이션은 한 전사가 DAT 명령어를 실행하거나, (두 전사를 합쳐) 총 32000개의 명령어가 실행될 때까지 진행됩니다. 한 전사가 DAT를 실행하면 다른 전사가 승리하며, 승리한 전사의 번호 x(1 또는 2)를 사용해 Program #x is the winner.를 출력합니다. 명령어 한계에 도달할 때까지 어느 전사도 DAT를 실행하지 않으면 비긴 것으로 보고 Programs are tied.를 출력합니다.