경계가 있는 셀룰러 오토마타

스티븐 울프럼은 책 "새로운 종류의 과학"에서 1차원 셀룰러 오토마타를 설명한다. 칸이 한 줄로 늘어서 있고 각 칸은 검은색이거나 흰색이다. 새 줄은 바로 앞 줄만 보고 만든다. 어떤 칸의 다음 색은 앞 줄에서 그 칸과 양옆 칸, 모두 세 칸의 색으로 정해진다.

세 칸의 색 조합은 여덟 가지다. 검은색을 1, 흰색을 0으로 두고 왼쪽 칸에 4, 가운데 칸에 2, 오른쪽 칸에 1을 곱해 더한 값을 자리 번호로 쓴다. 규칙 번호를 이진수로 적었을 때 그 자리의 비트가 1이면 가운데 칸은 다음 단계에서 검은색이 되고, 0이면 흰색이 된다. 규칙 번호는 0부터 255까지다.

254를 이진수로 적으면 11111110이다. 그래서 규칙 254는 세 칸이 모두 흰색일 때만 흰색을 내놓고 나머지 일곱 경우에는 검은색을 내놓는다. 가운데 한 칸만 검은 줄에서 시작해 규칙 254를 되풀이 적용하면 검은 삼각형이 자란다.

경계가 있는 오토마타

이 문제의 오토마타는 "새로운 종류의 과학"에 나오는 것과 달리 유한한 공간에서 움직인다.

• 한 줄은 정확히 $n$개의 칸으로 이루어진다. 규칙이 무엇이든 첫 칸과 마지막 칸은 언제나 흰색이다. 오토마타는 두 번째 칸과 끝에서 두 번째 칸의 새 색을 정할 때 첫 칸과 마지막 칸을 살펴보지만, 첫 칸과 마지막 칸 자체는 바꾸지 못한다.
• 경계가 있는 오토마타는 언제나 칸 수가 홀수인 줄에서 시작한다. 1단계의 줄은 가운데 한 칸만 검은색이고 나머지 칸은 모두 흰색이다.
• $n$은 찾으려는 문자열의 길이, 곧 입력 줄의 둘째 항목의 길이로 정해진다.

프로그램

입력의 각 줄마다, 표준 시작 상태에서 출발한 256가지 규칙 가운데 그 줄을 주어진 최대 단계 번호 안에 만들어 내는 규칙을 모두 찾아라. 그런 규칙이 하나도 없으면 NONE을 출력한다. 여럿이면 아래 출력 형식에 맞춰 모두 출력한다.

• 입력의 각 줄은 공백 하나로 나뉜 두 항목으로 이루어진다.
• 첫 항목은 오토마타를 돌릴 최대 단계 번호 max_step이다. 이 값은 32비트까지 커진다. 주어진 입력 조건에서 시간 제한 안에 풀 수 있는 값만 주어진다.
• 둘째 항목은 한 줄의 칸을 나타내는 문자열이다. 길이는 256을 넘지 않으며 더 짧아도 된다. 이 항목의 길이가 곧 $n$이다.
• 문자 W는 흰 칸을, 문자 B는 검은 칸을 뜻한다.
• 문자열에 W와 B가 아닌 문자가 섞여 있거나 앞에서 설명한 경계 조건을 지키지 않으면, 곧 길이가 짝수이거나 첫 칸 또는 마지막 칸이 검은색이면 어떤 오토마타도 그 줄을 만들 수 없다. 이런 줄의 답은 NONE이다.
• 입력의 모든 줄은 줄바꿈 문자로 끝난다.
• 입력은 END OF INPUT이라고만 적힌 줄로 끝난다. 이 줄은 탐색 대상이 아니다.

• 입력 줄 하나마다 출력 줄 하나를 만든다.
• 출력 줄은 LINE, 공백 하나, 입력 줄 번호로 시작한다. 줄 번호는 1부터 세며 답이 NONE인 줄도 번호를 차지한다.
• 줄 번호 다음에 공백 하나를 두고, 그 줄을 만들어 낸 (규칙,단계) 쌍을 사이에 빈칸 없이 이어 붙인다. 규칙은 오토마타의 번호로 0 이상 255 이하이고, 단계는 그 오토마타가 그 줄을 처음 만들어 낸 단계 번호로 1 이상 max_step 이하다.
• 최대 단계 번호까지 돌렸을 때 그 줄을 만들어 내는 규칙이 여럿이면 규칙 번호가 작은 것부터 큰 것 순서로 모두 적는다.
• 어떤 규칙도 최대 단계 번호까지 그 줄을 만들어 내지 못하면 쌍 대신 NONE을 적는다.
• 출력 줄의 모양은 LINE 2 (15,8)(158,11)이나 LINE 4 NONE과 같다.