페블링 오도미터 4

Leonardo는 거리를 재는 수레인 최초의 오도미터를 만들었다. 수레바퀴가 돌 때 조약돌을 떨어뜨려 거리를 재는 방식이었다. 조약돌의 개수를 세면 바퀴가 돈 횟수를 알 수 있고, 이를 통해 오도미터가 이동한 거리를 계산할 수 있었다. 우리는 컴퓨터 과학자답게 오도미터에 소프트웨어 제어를 추가해 기능을 확장했다. 당신의 임무는 아래 규칙에 따라 오도미터를 프로그래밍하는 것이다.

동작 격자

오도미터는 256 × 256개의 단위 칸으로 이루어진 가상의 정사각 격자 위를 움직인다. 각 칸에는 조약돌이 최대 15개까지 들어갈 수 있고, 좌표 쌍 (행, 열)로 구분한다. 각 좌표는 0, …, 255 범위에 있다. 칸 (i, j)에 대해 인접한 칸은 (존재하는 경우) (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)이다. 첫 번째 행이나 마지막 행, 또는 첫 번째 열이나 마지막 열에 있는 칸을 경계라고 한다. 오도미터는 항상 칸 (0, 0)(북서쪽 모서리)에서 북쪽을 향한 상태로 시작한다.

기본 명령

오도미터는 다음 명령으로 프로그래밍할 수 있다.

• left — 왼쪽(반시계 방향)으로 90도 회전하고 현재 칸에 그대로 머문다. 예를 들어 이전에 남쪽을 향하고 있었다면 이 명령 뒤에는 동쪽을 향한다.
• right — 오른쪽(시계 방향)으로 90도 회전하고 현재 칸에 그대로 머문다. 예를 들어 이전에 서쪽을 향하고 있었다면 이 명령 뒤에는 북쪽을 향한다.
• move — 오도미터가 향한 방향으로 한 칸 앞의 인접한 칸으로 이동한다. 그 방향에 칸이 없으면(즉, 그 방향의 경계에 이미 도달했으면) 이 명령은 아무 효과도 없다.
• get — 현재 칸에서 조약돌을 하나 제거한다. 현재 칸에 조약돌이 없으면 이 명령은 아무 효과도 없다.
• put — 현재 칸에 조약돌을 하나 추가한다. 현재 칸에 이미 조약돌이 15개 있으면 이 명령은 아무 효과도 없다. 오도미터는 조약돌이 부족해지는 일이 없다.
• halt — 실행을 종료한다.

오도미터는 프로그램에 적힌 순서대로 명령을 실행한다. 프로그램에는 한 줄에 명령을 최대 하나까지 쓸 수 있다. 빈 줄은 무시한다. # 기호는 주석을 나타내며, 그 뒤부터 줄 끝까지의 모든 글자는 무시한다. 오도미터가 프로그램의 끝에 도달하면 실행이 종료된다.

예제 1

다음 프로그램을 생각하자. 오도미터를 칸 (0, 2)로 옮기고 동쪽을 향하게 한다. (오도미터가 북서쪽 모서리에서 북쪽을 향하고 있으므로 첫 번째 move는 무시된다.)

move # no effect
right
# now the odometer is facing east
move
move

레이블, 경계, 조약돌

현재 상태에 따라 프로그램의 흐름을 바꾸려면 레이블을 사용할 수 있다. 레이블은 a, …, z, A, …, Z, 0, …, 9 중에서 고른 기호로 이루어진 최대 128글자의 문자열이며 대소문자를 구분한다. 레이블과 관련된 새 명령은 다음과 같다. 아래 설명에서 L은 임의의 올바른 레이블을 나타낸다.

• L: (즉 L 뒤에 콜론 ‘:’) — 프로그램에서 레이블 L의 위치를 선언한다. 선언한 레이블은 모두 서로 달라야 한다. 레이블 선언은 오도미터에 아무 영향을 주지 않는다.
• jump L — 레이블 L이 붙은 줄로 무조건 점프하여 실행을 계속한다.
• border L — 오도미터가 격자의 가장자리를 향한 채 경계에 있으면(즉, move 명령이 아무 효과도 없으면) 레이블 L이 붙은 줄로 점프하여 실행을 계속한다. 그렇지 않으면 실행은 정상적으로 이어지고 이 명령은 아무 효과도 없다.
• pebble L — 현재 칸에 조약돌이 하나 이상 있으면 레이블 L이 붙은 줄로 점프하여 실행을 계속한다. 그렇지 않으면 실행은 정상적으로 이어지고 이 명령은 아무 효과도 없다.

예제 2

다음 프로그램은 0번 행에서 가장 서쪽에 있는 첫 번째 조약돌을 찾아 그 자리에서 멈춘다. 0번 행에 조약돌이 없으면 행의 끝 경계에서 멈춘다. 두 레이블 leonardo와 davinci를 사용한다.

right
leonardo:
pebble davinci # pebble found
border davinci # end of the row
move
jump leonardo
davinci:
halt

오도미터는 먼저 오른쪽으로 회전한다. 반복문은 레이블 선언 leonardo:로 시작해 jump leonardo 명령으로 끝난다. 반복문 안에서 오도미터는 조약돌이 있는지, 또는 행의 끝 경계인지 확인한다. 둘 다 아니면 현재 칸 (0, j)에서 인접한 칸 (0, j + 1)로 move한다. 후자가 존재하기 때문이다. (어차피 프로그램이 끝나므로 halt 명령은 여기서 꼭 필요하지는 않다.)

위에서 설명한 오도미터 언어로 프로그램을 제출해야 하며, 프로그램은 오도미터가 기대한 대로 동작하게 해야 한다. 각 부분 과제는 오도미터가 수행해야 하는 동작과 제출한 풀이가 만족해야 하는 제약을 명시한다. 제약은 다음 두 가지에 관한 것이다.

• 프로그램 크기 — 프로그램이 충분히 짧아야 한다. 프로그램의 크기는 프로그램에 있는 명령의 개수이다. 레이블 선언, 주석, 빈 줄은 크기에 포함하지 않는다.
• 실행 길이 — 프로그램이 충분히 빨리 끝나야 한다. 실행 길이는 수행한 단계의 수이다. 명령이 효과가 있었는지와 관계없이 명령을 한 번 실행할 때마다 한 단계로 센다. 레이블 선언, 주석, 빈 줄은 단계로 세지 않는다.

예제 1에서 프로그램 크기는 4이고 실행 길이는 4이다. 예제 2에서 프로그램 크기는 6이고, 칸 (0, 10)에 조약돌이 하나 있는 격자에서 실행하면 실행 길이는 43단계이다. right, 반복문 10회(각 회는 pebble davinci; border davinci; move; jump leonardo의 4단계), 마지막으로 pebble davinci와 halt가 수행된다.

격자에는 조약돌이 최대 15개 있고, 두 조약돌이 같은 칸에 있는 경우는 없다. 조약돌을 모두 북서쪽 모서리로 모으는 프로그램을 작성하라. 더 정확히는, 처음에 격자에 x개의 조약돌이 있었다면 끝날 때 칸 (0, 0)에 정확히 x개의 조약돌이 있고 다른 곳에는 조약돌이 없어야 한다.

• 프로그램 크기 ≤ 200