중력의 악마

Java, C++, Pascal 같은 현대 프로그래밍 언어로 작성한 프로그램은 유난히 듬성듬성 보이지 않는가? 대부분의 편집기는 한 줄에 최소 80자 정도를 보여 줄 화면 공간을 갖추고 있지만, 한 줄에서 실제로 의미가 있는 문자의 평균 개수는 그중 일부에 불과하다. 요즘은 화면 공간을 효율적으로 쓰는 것보다 프로그램의 가독성을 더 중요하게 여긴다.

급진적인 컴퓨터 과학자 Faust 박사는 실제 프로그래머를 위한 편집기는 공간 효율이 더 높아야 한다고 믿는다. 그는 여러 해 동안 공간을 절약하는 연구를 하며 다양한 기법을 고안했지만, 자신의 아이디어로는 더 이상 본질적인 개선을 기대하기 어려운 지점에 이르렀다.

오래 고민한 끝에 그는 궁극적이지만 금기시된 방법을 택하기로 했다. 야망을 위해서라면 무엇이든 희생할 각오인 그는 영혼을 내주는 대신 초자연적인 지적 능력을 달라고 악마에게 청한다. 악마는 초월적인 지식과 능력을 바탕으로 편집기를 공간 효율적으로 구현하는 새로운 알고리즘과 자료 구조를 제공한다.

그 사악한 기법으로 구현된 편집기는 인간의 상상을 뛰어넘으며 이상하게 동작한다. Faust 박사가 부탁한 악마는 중력의 악마다. 그 지배를 받는 편집기는 자기력과 중력으로 공간을 절약한다.

당신의 임무는 악마의 도움 없이 이 이상한 편집기를 다시 구현해 Faust 박사를 무찌르는 것이다. 얼핏 보면 이 편집기는 평범한 텍스트 편집기처럼 보인다. 텍스트를 2차원 레이아웃으로 보여 주고, 커서 이동과 문자 삽입 및 삭제 같은 편집 명령을 받는다. 하지만 악마의 편집기가 다루는 텍스트는 공백이 없는 가로 방향 블록인 텍스트 조각으로 나뉜다. 아래 그림에는 "abcdef", "ghijkl", "mnop", "qrstuvw"의 네 텍스트 조각이 있으며, 앞의 두 조각은 같은 행에 놓여 있다.

abcdef ghijkl
     mnop
qrstuvw

이 편집기에는 다음과 같은 고유한 특징이 있다.

1. 바로 아래 행에 받쳐 주는 조각이 없는 텍스트 조각은 사악한 중력에 의해 떨어진다.
2. 같은 행에 있으면서 서로 맞닿은 텍스트 조각은 사악한 자기력에 의해 하나로 이어진다.

예를 들어 앞 그림에서 "mnop" 조각의 문자를 모두 지우면, 그 위에 있던 두 조각이 떨어져 다음과 같이 된다.

abcdef
qrstuvw ghijkl

그다음 "qrstuvw" 조각의 끝(즉, 가장 오른쪽 열의 바로 오른쪽)에 x를 추가하면 맨 아래 행의 두 조각이 이어진다.

abcdef
qrstuvwxghijkl

이제 이 그림에는 텍스트 조각이 두 개 남는다. 이처럼 편집기는 화면 공간을 아껴 주지만, 사용자에게 특별한 지적 능력을 요구한다.

일반적으로 명령을 실행한 뒤에는 다음 규칙이 적용된다. 여기서 S는 텍스트 조각이고, left(S)와 right(S)는 S의 가장 왼쪽 열과 가장 오른쪽 열, row(S)는 S의 행 번호다.

1. left(S)부터 right(S)까지의 열이 row(S)-1 행(S 바로 아래 행)에서 비어 있으면(어떤 텍스트 조각의 문자도 없으면) S는 열 위치를 유지한 채 row(S)-1 행으로 내려온다. row(S)-2, row(S)-3 등 같은 범위도 비어 있으면 S는 계속 내려간다. 편집기에는 행 번호 0인 궁극의 바닥이 있으므로 이 과정은 언젠가 끝난다.
2. 같은 행에 있는 두 텍스트 조각 S와 T에서 right(S)+1 = left(T), 즉 T가 S의 가장 오른쪽 문자 바로 오른쪽 열에서 시작하면 S와 T는 자동으로 이어져 left(S)에서 시작해 right(T)에서 끝나는 하나의 텍스트 조각이 된다. 새 조각은 원래 행에 그대로 남는다.

첫 번째 규칙은 두 번째 규칙보다 먼저 적용된다. 즉, 떨어지는 조각이 있는 동안에는 이어지는 일이 일어나지 않는다. 예를 들어 다음 경우를 보자.

   dddddddd
   cccccccc
bbbb
aaa

텍스트 조각 "bbbb"의 마지막 문자를 지우면, "cccccccc"와 "dddddddd" 두 조각이 떨어지기를 멈출 때까지 이어지는 규칙은 적용되지 않는다. 따라서 "bbb"와 "cccccccc"는 이어지지 않는다.

악마의 편집기에는 커서가 있으며, 커서는 항상 하나의 텍스트 조각, 즉 현재 조각 안에 있다. 커서는 현재 조각의 어떤 문자 위치 또는 그 끝에 놓인다. 커서는 받침이 될 수 없다. 예를 들어 앞의 예에서 커서가 "bbbb"의 마지막 문자에 있고 지운 뒤에도 같은 위치에 있더라도, 커서 혼자서는 "cccccccc"와 "dddddddd"를 더 이상 받칠 수 없어서 두 조각은 떨어진다. 마지막으로 커서는 가장 왼쪽의 "d"에 있다.

편집기는 다음 명령을 받으며, 각 명령은 문자 하나로 표시된다.

• F: 커서를 현재 조각 안에서 오른쪽으로 한 열 이동한다. 커서가 현재 조각의 끝에 있어 조각 안에서 더 이동할 수 없으면 오류가 발생한다.
• B: 커서를 현재 조각 안에서 왼쪽으로 한 열 이동한다. 커서가 현재 조각의 가장 왼쪽 위치에 있으면 오류가 발생한다.
• P: 커서를 위로 한 행 이동한다. 열 위치는 바뀌지 않는다. 새 위치가 기존 텍스트 조각 중 하나의 유효한 커서 범위를 벗어나면 오류가 발생한다.
• N: 커서를 아래로 한 행 이동한다. 열 위치는 바뀌지 않는다. 커서가 맨 아래 행에 있거나 새 위치가 기존 텍스트 조각 중 하나의 유효한 커서 범위를 벗어나면 오류가 발생한다.
• D: 커서 위치의 문자를 지운다. 커서가 현재 조각의 끝에 있어 그 자리에 문자가 없으면 오류가 발생한다. 문자가 있으면 그 문자를 지우고 현재 조각은 한 글자 짧아진다. 현재 조각의 가장 왼쪽 열과 커서의 열은 바뀌지 않는다. 다만 현재 조각이 비게 되면 그 조각은 제거되고 커서는 한 행 떨어진다. 새 위치가 기존 텍스트 조각 중 하나의 유효한 커서 범위를 벗어나면 오류가 발생한다. 이 명령 뒤에는 일부 텍스트 조각이 받침을 잃고 지옥을 향해 떨어질 수 있다. 현재 조각이 떨어지면 커서도 함께 떨어진다.
• C: 현재 커서 위치 바로 위에 길이가 1인 새 조각을 만든다. 내용은 커서 아래에 있는 문자의 복사본이다. 커서가 끝에 있으면 오류가 발생한다. 새 조각의 위치가 이미 다른 조각으로 차 있으면 오류가 발생한다. 명령을 실행하면 새 조각이 현재 조각이 되고, 커서는 오른쪽으로 한 열 진행한다.
• 소문자와 숫자(a부터 z, 0부터 9): 현재 커서 위치에 문자를 삽입한다. 현재 조각은 한 글자 길어지고, 커서는 앞으로 한 열 이동한다. 현재 조각의 시작 열은 바뀌지 않는다.

첫 줄에는 편집 세션의 개수를 나타내는 정수가 주어진다. 이어지는 각 줄에는 문자열 하나가 주어진다. 첫 문자는 초기 문자이고, 나머지는 그 세션에서 처리할 명령 순서다. 각 세션은 최하단 행에 초기 문자 하나로 이루어진 조각 하나에서 시작한다. 초기 커서 위치는 그 조각의 끝이다. 편집기는 위에서 설명한 방식에 따라 명령을 하나씩 처리한다.

각 명령 줄은 비어 있지 않으며 길이는 최대 100이다. 명령 순서는 줄바꿈으로 끝난다.

각 세션에 대해, 오류 없이 끝나면 세션이 끝난 시점의 현재 텍스트 조각을 한 줄에 출력한다. 세션 중 오류가 발생하면 대문자로 ERROR를 한 줄에 출력한다.