Turmite Hunt 개미 규칙 9만 개 탐험기

격자 끝에 닿거나 200만 걸음이 되면 멈춥니다. 애매한 규칙은 2천만 걸음으로 한 번 더 돌렸습니다.

자세히 · C로 짠 시뮬레이터 tsim이 4096×4096 격자에서 초당 수천만 걸음을 돌립니다. 매 걸음 (읽은 색, 상태, 새 방향)을 1바이트로 적어 두고, 아래 ②의 반복 찾기는 그림 전체가 아니라 이 기록만으로 합니다.

묶음 하나를 돌 때마다 개미가 조금씩 앞으로 나가면 고속도로, 원래 자리로 돌아오면 덫입니다. 랭턴 개미는 9,977걸음 헤맨 뒤 104걸음 묶음을 되풀이합니다.

자세히 · 기록을 끝에서부터 거꾸로 읽고 KMP 알고리즘의 '접두사 함수'로 가장 짧은 반복 단위 p를 한 번에 구합니다. p가 6번 이상, 합쳐 2만 걸음 이상 반복될 때만 인정합니다. 그다음 기록[i] = 기록[i+p]인 동안 한 걸음씩 과거로 넓혀 정확한 시작 걸음을 찾습니다(RL은 9,977로 위키백과와 같음). 한 묶음 동안의 이동 거리가 0이 아니면 고속도로, 0이면 덫입니다. 보는 범위가 마지막 400만 걸음이라 묶음이 약 60만 걸음보다 길면 못 찾습니다.

무늬를 감싸는 상자 크기를 비교합니다. 안에서 무늬는 바뀌어도 상자가 그대로면 정체입니다.

자세히 · L과 R이 둘 다 들어간 개미는 결국 끝없이 커진다고 증명돼 있습니다. 그래서 L/R 개미의 '정체'는 멈춤이 아니라 아주 느린 성장입니다. 예: LLRRRR은 200만 걸음에 30×32칸, 2억 걸음에도 46×48칸입니다.

세 번 넘게 대칭으로 나오면 대칭입니다. Propp가 LLRR에서 처음 본 현상입니다.

자세히 · 무늬 상자의 중심을 기준으로 세로·가로·대각선 두 개, 모두 4개 축에 비춰 봅니다. 무늬가 지난 검사 때보다 30% 이상 커졌을 때만 다시 검사합니다.

반듯한 무늬는 왼쪽·위·왼쪽 위 칸만 알아도 가운데 칸 색이 거의 정해집니다. 어지러운 무늬는 이웃을 알아도 맞히기 어렵습니다.

자세히 · 점수 = H(칸 | 이웃 3칸) / H(칸), 즉 조건부 엔트로피의 비율입니다. 0.5보다 작으면 질서입니다. 위키백과 예시로 맞춘 값: 삼각형 RRLLLRLLLRRR 0.02, 정사각형 LRRRRRLLR 0.29, RLR 0.68, LLRR 0.73.