페블링 주행거리계 1

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, 각각 4단계(pebble davinci; border davinci; move; jump leonardo)를 수행하는 반복문 10회, 그리고 마지막으로 pebble davinci와 halt이다.

처음에 칸 (0, 0)에는 조약돌이 x개, 칸 (0, 1)에는 y개 있고 다른 모든 칸은 비어 있다. 어떤 칸에도 조약돌이 최대 15개까지만 들어갈 수 있음을 기억하라. x ≤ y이면 주행거리계가 칸 (0, 0)에서 종료되고, 그렇지 않으면 칸 (0, 1)에서 종료되는 프로그램을 작성하라. 종료 시 주행거리계가 향하는 방향은 상관없다. 종료 시 격자에 조약돌이 몇 개 있고 어디에 있는지도 상관없다.

• 프로그램 크기 ≤ 100
• 실행 길이 ≤ 1 000