로봇

두 대의 작은 로봇이 A와 B로 이루어진 문자열 위를 기어 다닌다. 이들의 목표는 그 문자열이 fine인지 coarse인지 판별하는 것이다.

두 로봇은 문자열의 가운데 3분의 1에 있는 A의 개수와 B의 개수가 같으면 그 문자열을 fine이라고 본다. 그 밖의 문자열은 모두 coarse라고 본다. 예를 들어 문자열 BBABAABBBABA는 가운데 3분의 1인 AABB에 A가 두 개, B가 두 개 있으므로 fine이다. 반대로 문자열 BAABABBBBAAB는 가운데 3분의 1인 ABBB에 A가 하나, B가 세 개 있으므로 coarse이다. 문자열 AABBAABB도 마찬가지로 coarse인데, 이 문자열에는 가운데 3분의 1이 없다.

매 순간 각 로봇은 문자열의 한 문자 위에 있고, 주변에 대해 다음과 같은 것을 인식한다. 자신이 문자열의 가장 왼쪽 문자, 내부 문자, 가장 오른쪽 문자 중 어디에 서 있는지 볼 수 있다. 다시 말해 왼쪽과 오른쪽에 문자가 더 있는지 볼 수 있다. 자신이 그 위치에 혼자인지, 아니면 다른 로봇도 같은 위치에 함께 있는지 볼 수 있다. 마지막으로 자신이 딛고 있는 문자가 A인지 B인지 볼 수 있다.

그 외에도 각 로봇은 자신의 이동에 대한 기억을 유지할 수 있다. 안타깝게도 각 로봇의 기억은 4비트밖에 되지 않는다.

모든 로봇의 머릿속에는 “명령 목록”이 있고, 두 목록은 크게 다를 수 있다.

각 명령은 세 부분으로 이루어진다.

왼쪽(조건)->(특수 문자)오른쪽(행동 명령)

왼쪽에는 다음이 들어간다.

• 로봇이 문자열의 끝 중 하나에 있는지 나타내는 문자 하나: L은 “Leftmost character(가장 왼쪽 문자)에 있으면”, I는 “Inner character(내부 문자)에 있으면”, R은 “Rightmost character(가장 오른쪽 문자)에 있으면”
• 로봇이 혼자인지 다른 로봇이 같은 위치에 함께 있는지를 나타내는 문자 하나: O는 “이 위치에 로봇이 One(하나) 있으면”, T는 “이 위치에 로봇이 Two(둘) 있으면”
• 로봇이 딛고 있는 문자: A는 “A 위에 있으면”, B는 “B 위에 있으면”
• 로봇의 기억 내용을 나타내는 0 또는 1 문자 4개. 예를 들어 0101은 “기억이 0101을 담고 있으면”

이렇게 왼쪽은 여러 단순 조건의 논리곱인 조건을 이루고, 로봇의 현재 위치와 4비트 기억에 저장된 이력에 따라 “참” 또는 “거짓” 값을 가진다.

오른쪽은 다음과 같이 나타난다.

• 로봇이 취할 행동을 나타내는 문자 하나: L은 “Left(왼쪽)으로 한 칸 이동”, R은 “Right(오른쪽)으로 한 칸 이동”, S는 “제자리에 Stay(머무름)”, Y는 “문자열이 fine이라고 Yes(예)를 보고”, N은 “문자열이 coarse이라고 No(아니오)를 보고”
• 작업이 끝나는 경우(행동 Y 또는 N)를 제외하고, 로봇의 기억의 수정된 내용을 나타내는 0 또는 1 문자 4개. 예를 들어 0110

명령 줄에서 두 특수 문자와 행동 문자를 제외한 모든 문자는 와일드카드 ?로 바꿀 수 있다.

명령의 왼쪽(조건)에 와일드카드 ?가 나오면 해당 단순 조건을 검사하지 않는다는 뜻이다.

명령 줄의 기억 덮어쓰기 부분(행동 문자 뒤)에 와일드카드 ?가 나오면 로봇 기억의 해당 비트를 그대로 둔다는 뜻이다.

예를 들어 명령 줄

LT???01->R??10

은 다음을 뜻한다. “로봇이 문자열의 가장 왼쪽 문자에 있고, 다른 로봇도 같은 위치에 함께 있고, 기억의 마지막 두 비트가 0과 1로 설정되어 있으면, (A 위에 있든 B 위에 있든 상관없이) 오른쪽으로 한 칸 이동하고 기억의 마지막 두 비트를 1과 0으로 바꾸며 앞의 두 비트는 바꾸지 않는다.”

두 로봇은 문자열의 가장 왼쪽 문자에서 여정을 시작한다. 처음에 각 로봇의 기억에 있는 모든 비트는 0으로 설정된다.

매 밀리초마다 각 로봇은 주변을 살피고, 기억을 뒤지고, 목록에서 지침을 찾아 왼쪽으로 한 칸 이동할지, 오른쪽으로 한 칸 이동할지, 제자리에 머무를지, 문자열에 대한 의견을 말할지 결정한다. 또한 로봇은 어떤 인상이나 의도를 기억에 기록할 수 있다. 어느 로봇이든 문자열에 대한 의견을 말하는 순간 작업이 끝나고 로봇은 꺼진다. 두 로봇이 동시에 의견을 말하면 먼저 말한 로봇의 의견이 유효하다.

자세히 말해, 각 로봇은 명령 목록을 차례로 확인하여 현재 상태가 어떤 명령의 왼쪽 부분과 정확히 일치하는지 본다. 처음 일치하는 명령을 만나면 그 명령을 실행한다. 그러한 명령이 없으면 로봇은 목록의 처음부터 다시 검색하여, 자신의 위치와 기억 내용에 해당하는 와일드카드가 포함된 첫 번째 명령을 실행한다. 이번에도 일치하는 것이 없으면 로봇은 문자열의 종류를 알아내지 못한 채 꺼진다(그리고 작업은 해결되지 않은 채 남는다).

여러분은 두 로봇 각각에 대한 명령 목록 두 개를 만들어, 길이가 최소 두 문자이고 A와 B로 이루어진 임의의 문자열이 fine인지 coarse인지 항상 올바르게 판별하도록 해야 한다.

이 문제는 출력 전용 문제다. 텍스트 파일 하나 robots.txt를 만들어 제출해야 하며, 그 내용은 다음 순서로 되어 있다.

• Robot 1이라고 적힌 한 줄
• 첫 번째 로봇의 명령 목록을 이루는 여러 명령 줄(한 줄에 명령 하나)
• Robot 2라고 적힌 한 줄
• 두 번째 로봇의 명령 목록을 이루는 여러 명령 줄(한 줄에 명령 하나).

robots.txt 파일에는 주석 줄이 들어갈 수 있고, 로봇은 이를 그냥 건너뛴다. 주석 줄은 %(퍼센트) 문자로 시작한다.

• 로봇이 문자열의 종류를 알리기 전까지 할 수 있는 공통 이동 횟수는 문자열 길이의 1000배를 넘지 않아야 한다.
• 각 테스트에는 길이가 12 이상 3600 이하인 문자열이 16개 또는 20개 들어 있고, 각 문자는 A 또는 B이다.
• 한 테스트에는 길이가 12인 문자열만 들어 있다.
• 두 테스트에는 길이가 36 이하인 문자열만 들어 있다.