모양 번호

컴퓨터 비전에서 체인 코드(chain code) 는 물체의 윤곽선을 따라가며 이동한 방향들을 숫자로 나열한 수열이다. 예를 들어 아래 그림은 체인 코드 22234446466001207560 으로 표현된 윤곽선을 나타낸다(왼쪽 위 모서리에서 시작).

같은 모양이라도 회전되어 있거나 윤곽선의 시작점을 다르게 잡으면 서로 다른 체인 코드로 표현될 수 있다. 회전에 대해 정규화하기 위해 체인 코드의 1차 차분(first difference) 을 계산한다. 이웃한 두 원소 사이에서 반시계 방향으로 방향이 바뀐 횟수, 즉 (다음 값 - 현재 값) mod 8 을 세면 된다(마지막 원소는 첫 번째 원소와 이웃한 것으로 본다). 위 코드의 1차 차분은 다음과 같다.

00110026202011676122

마지막으로 시작점에 대해 정규화하기 위해, 1차 차분의 모든 순환 회전(cyclic rotation) 중에서 사전순으로 가장 작은 것을 고른다. 이렇게 얻은 코드를 모양 번호(shape number) 라고 한다.

00110026202011676122
01100262020116761220
11002620201167612200
...
20011002620201167612

이 경우 00110026202011676122 가 위 모양의 모양 번호이다.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 케이스는 한 줄에 하나씩 주어지고 입력의 끝까지 읽는다. 각 줄은 한 모양의 체인 코드이다. 체인 코드의 길이는 최대 $300{,}000$ 이며, 모든 숫자는 $0$ 이상 $7$ 이하이다. 윤곽선은 스스로 교차할 수 있고, 반드시 시작점으로 되돌아올 필요는 없다.

각 케이스마다 정규화를 거친 모양 번호를 한 줄에 하나씩 출력한다.