랭턴의 개미

1. 개요

• 개미가 흰색 칸에 위치: 현재 위치한 칸을 검은색으로 바꿈, 왼쪽으로 90도 회전, 한 칸 전진
• 개미가 검은색 칸에 위치: 현재 위치한 칸을 흰색으로 바꿈, 오른쪽으로 90도 회전, 한 칸 전진

2. Turmite

3. 목록

• 시작 상태는 개미 한 마리가 사각형 칸 (0, 0)에서 (0, 1)을 향하고 있을 때 기준
• 이동 규칙에서 L은 좌회전, R은 우회전, U는 U턴, N은 직진을 의미
• 이동 규칙에서 X는 L/R/U/N 중 아무거나 들어가도 결과가 바뀌지 않음을 의미
• 이동 규칙에서 모든 L과 R을 서로 바꾸면, 바꾸기 전과 좌우대칭인 같은 움직임을 보여준다. 표에서는 괄호가 아닌 쪽의 좌표만 기재
• 반복 간격에서 n은 n번째 구간을 의미

• 반복 구간 후에 좌표 변화가 있음: 7개 3종류

• 반복 구간 후에 좌표 변화가 없음: 7개 4종류
• 반복 간격 24: LU (RU), UL (UR)
• 반복 간격 8: LL (RR)
• 반복 간격 4: UU
• 반복 구간은 없지만 좌표 변화가 예측 가능함: 2개 1종류
• 2방향 확장: LN (RN)

• 반복 구간 후에 좌표 변화가 있음: 34개 11종류

• 반복 구간 후에 좌표 변화가 없음: 13개 7종류
• 반복 간격 276: LRU (RLU), ULR (URL)
• 반복 간격 36: LUU (RUU), ULU (URU), UUL (UUR)
• 반복 간격 12: LLL (RRR)
• 반복 간격 6: UUU
• 반복 구간은 없지만 좌표 변화가 예측 가능함: 7개 4종류
• 2방향 확장: LLN (RRN), LNL (RNR), LNN (RNN), UNN
• 반복 구간이 존재하는지 아직 밝혀내지 못함[9]: 10개 5종류
• LRL (RLR): 이동 횟수 약 616억
• LRR (RLL): 이동 횟수 약 1527억
• LNR (RNL): 이동 횟수 약 1255억
• ULN (URN): 이동 횟수 약 2815억
• UNL (UNR): 이동 횟수 약 2270억

• 반복 구간 후에 좌표 변화가 있음: 139개 39종류

• 반복 구간 후에 좌표 변화가 없음: 21개 11종류
• 반복 간격 1216: LRUU (RLUU), ULRU (URLU), UULR (UURL)
• 반복 간격 48: LULU (RURU), LUUU (RUUU), ULUL (URUR), ULUU (URUU), UULU (UURU), UUUL (UUUR)
• 반복 간격 16: LLLL (RRRR)
• 반복 간격 8: UUUU
• 반복 구간은 없지만 좌표 변화가 예측 가능함: 20개 11종류
• 2방향 확장: LLLN (RRRN), LLNL (RRNR), LLNN (RRNN), LUNU (RUNU), LNLL (RNRR), LNLN (RNRN), LNNL (RNNR), LNNN (RNNN), ULUN (URUN), UUNN, UNNU
• 반복 구간이 존재하는지 아직 밝혀내지 못함[10]: 76개 38종류

{{{#!folding [ 목록 펼치기 · 접기 ]
• LLRR (RRLL): 이동 횟수 약 4조 9438억[상하대칭]
• LLUN (RRUN): 이동 횟수 약 642억
• LLNR (RRNL): 이동 횟수 약 2273억
• LRLL (RLRR): 이동 횟수 약 1610억
• LRLU (RLRU): 이동 횟수 약 737억
• LRLN (RLRN): 이동 횟수 약 720억
• LRRL (RLLR): 이동 횟수 약 103억[상하대칭]
• LRRR (RLLL): 이동 횟수 약 2363억
• LRRU (RLLU): 이동 횟수 약 1206억
• LRRN (RLLN): 이동 횟수 약 1400억
• LRUL (RLUR): 이동 횟수 약 2436억
• LRNL (RLNR): 이동 횟수 약 630억
• LRNR (RLNL): 이동 횟수 약 1388억
• LRNU (RLNU): 이동 횟수 약 863억
• LRNN (RLNN): 이동 횟수 약 1239억
• LULR (RURL): 이동 횟수 약 2139억
• LURN (RULN): 이동 횟수 약 1478억
• LUUL (RUUR): 이동 횟수 약 3429억
• LUNR (RUNL): 이동 횟수 약 1921억
• LNLR (RNRL): 이동 횟수 약 993억
• LNLU (RNRU): 이동 횟수 약 1355억
• LNRL (RNLR): 이동 횟수 약 903억
• LNRR (RNLL): 이동 횟수 약 1430억
• LNRU (RNLU): 이동 횟수 약 1779억
• LNRN (RNLN): 이동 횟수 약 1284억
• LNUL (RNUR): 이동 횟수 약 183억
• LNUR (RNUL): 이동 횟수 약 1827억
• LNUU (RNUU): 이동 횟수 약 2023억
• LNUN (RNUN): 이동 횟수 약 1184억
• LNNR (RNNL): 이동 횟수 약 1207억
• ULLR (URRL): 이동 횟수 약 3376억
• ULLN (URRN): 이동 횟수 약 4232억
• ULNL (URNR): 이동 횟수 약 3473억
• ULNN (URNN): 이동 횟수 약 4788억
• UULN (UURN): 이동 횟수 약 7275억
• UNLL (UNRR): 이동 횟수 약 2780억
• UNLN (UNRN): 이동 횟수 약 829억
• UNNL (UNNR): 이동 횟수 약 4718억

}}}

• 반복 구간 후에 좌표 변화가 있음: 538개 132종류

• 반복 구간 후에 좌표 변화가 없음: 23개 12종류
• 반복 간격 3940: LRUUU (RLUUU), ULRUU (URLUU), UULRU (UURLU), UUULR (UUURL)
• 반복 간격 60: LUUUU (RUUUU), ULUUU (URUUU), UULUU (UURUU), UUULU (UUURU), UUUUL (UUUUR)
• 반복 간격 20: LLLLL (RRRRR), ULULU (URURU)
• 반복 간격 10: UUUUU
• 반복 구간은 없지만 좌표 변화가 예측 가능함: 37개 21종류
• 2방향 확장: LLLLN (RRRRN), LLLNL (RRRNR), LLLNN (RRRNN), LLNLL (RRNRR), LLNLN (RRNRN), LLNNL (RRNNR), LLNNN (RRNNN), LNLLL (RNRRR), LNLLN (RNRRN), LNLNL (RNRNR), LNLNN (RNRNN), LNNLL (RNNRR), LNNLN (RNNRN), LNNNL (RNNNR), LNNNN (RNNNN), UNNNN, UNNUU, UUNNU, UUNUN, UUUNN
• 4방향 확장: LLULU (RRURU)
• 반복 구간이 존재하는지 아직 밝혀내지 못함: 426개 213종류
• 좌표의 확장 속도가 매우 느림: LLLRR (RRRLL), LLRRL (RRLLR), LLRRR (RRLLL), LRLRU (RLRLU), LRRLL (RLLRR), LRRRL (RLLLR), LRULR (RLURL), LURUU (RULUU), ULRLR (URLRL), ULURU (URULU), UULUR (UURUL)
• x좌표 또는 y좌표가 +-5000에 도달할 때까지 반복 구간이 등장하지 않음
  {{{#!folding [ 목록 펼치기 · 접기 ]
• LLLRU (RRRLU): 이동 횟수 약 1420억
• LLLRN (RRRLN): 이동 횟수 약 2606억
• LLLUU (RRRUU): 이동 횟수 약 1500억
• LLLUN (RRRUN): 이동 횟수 약 1587억
• LLRLR (RRLRL): 이동 횟수 약 1787억
• LLRLN (RRLRN): 이동 횟수 약 1130억
• LLRRU (RRLLU): 이동 횟수 약 2963억
• LLRRN (RRLLN): 이동 횟수 약 1989억
• LLRUR (RRLUL): 이동 횟수 약 1972억
• LLRUU (RRLUU): 이동 횟수 약 1451억
• LLRNR (RRLNL): 이동 횟수 약 2458억
• LLRNU (RRLNU): 이동 횟수 약 1050억
• LLRNN (RRLNN): 이동 횟수 약 1676억
• LLULR (RRURL): 이동 횟수 약 656억
• LLURN (RRULN): 이동 횟수 약 2142억
• LLUUL (RRUUR): 이동 횟수 약 536억
• LLUUN (RRUUN): 이동 횟수 약 1109억
• LLUNL (RRUNR): 이동 횟수 약 1255억
• LLUNU (RRUNU): 이동 횟수 약 1174억
• LLNLR (RRNRL): 이동 횟수 약 1440억
• LLNLU (RRNRU): 이동 횟수 약 1667억
• LLNRL (RRNLR): 이동 횟수 약 1652억
• LLNRR (RRNLL): 이동 횟수 약 2430억
• LLNRU (RRNLU): 이동 횟수 약 2574억
• LLNUL (RRNUR): 이동 횟수 약 330억
• LLNUR (RRNUL): 이동 횟수 약 1897억
• LLNUU (RRNUU): 이동 횟수 약 4376억
• LLNUN (RRNUN): 이동 횟수 약 1627억
• LLNNR (RRNNL): 이동 횟수 약 2195억
• LRLLL (RLRRR): 이동 횟수 약 2473억
• LRLLR (RLRRL): 이동 횟수 약 611억
• LRLLU (RLNNU): 이동 횟수 약 886억
• LRLLN (RLRRN): 이동 횟수 약 1120억
• LRLRL (RLRLR): 이동 횟수 약 1403억
• LRLRR (RLRLL): 이동 횟수 약 741억
• LRLUL (RLRUR): 이동 횟수 약 277억
• LRLNL (RLRNR): 이동 횟수 약 879억
• LRLNR (RLRNL): 이동 횟수 약 959억
• LRLNN (RLRNN): 이동 횟수 약 1072억
• LRRLR (RLLRL): 이동 횟수 약 1328억
• LRRLU (RLLRU): 이동 횟수 약 536억
• LRRLN (RLLRN): 이동 횟수 약 1112억
• LRRRR (RLLLL): 이동 횟수 약 2845억
• LRRRU (RLLLU): 이동 횟수 약 2255억
• LRRRN (RLLLN): 이동 횟수 약 2341억
• LRRUL (RLLUR): 이동 횟수 약 1178억
• LRRUU (RLLUU): 이동 횟수 약 1147억
• LRRUN (RLLUN): 이동 횟수 약 2212억
• LRRNL (RLLNR): 이동 횟수 약 1388억
• LRRNR (RLLNL): 이동 횟수 약 2086억
• LRRNU (RLLNU): 이동 횟수 약 1304억
• LRRNN (RLLNN): 이동 횟수 약 1867억
• LRULU (RLURU): 이동 횟수 약 922억
• LRULN (RLURN): 이동 횟수 약 1658억
• LRURL (RLULR): 이동 횟수 약 2072억
• LRURR (RLULL): 이동 횟수 약 815억
• LRURU (RLULU): 이동 횟수 약 3984억
• LRURN (RLULN): 이동 횟수 약 2114억
• LRUUL (RLUUR): 이동 횟수 약 2885억
• LRUNL (RLUNR): 이동 횟수 약 1384억
• LRUNR (RLUNL): 이동 횟수 약 2661억
• LRUNU (RLUNU): 이동 횟수 약 999억
• LRUNN (RLUNN): 이동 횟수 약 2974억
• LRNLU (RLNRU): 이동 횟수 약 602억
• LRNLN (RLNRN): 이동 횟수 약 906억
• LRNRL (RLNLR): 이동 횟수 약 1334억
• LRNRR (RLNLL): 이동 횟수 약 1666억
• LRNRU (RLNLU): 이동 횟수 약 1000억
• LRNUL (RLNUR): 이동 횟수 약 464억
• LRNUR (RLNUL): 이동 횟수 약 1945억
• LRNUU (RLNUU): 이동 횟수 약 842억
• LRNUN (RLNUN): 이동 횟수 약 1161억
• LRNNL (RLNNR): 이동 횟수 약 1177억
• LRNNR (RLNNL): 이동 횟수 약 1283억
• LRNNU (RLNNU): 이동 횟수 약 1088억
• LRNNN (RLNNN): 이동 횟수 약 1149억
• LULLR (RURRL): 이동 횟수 약 265억
• LULLN (RURRN): 이동 횟수 약 1313억
• LULUR (RURUL): 이동 횟수 약 1874억
• LULNL (RURNR): 이동 횟수 약 844억
• LULNR (RURNL): 이동 횟수 약 2912억
• LULNN (RURNN): 이동 횟수 약 3193억
• LURLN (RULRN): 이동 횟수 약 1628억
• LURRL (RULLR): 이동 횟수 약 1501억
• LURRR (RULLL): 이동 횟수 약 2548억
• LURRN (RULLN): 이동 횟수 약 2331억
• LURUL (RULUR): 이동 횟수 약 1919억
• LURUR (RULUL): 이동 횟수 약 1209억
• LURNL (RULNR): 이동 횟수 약 1043억
• LURNR (RULNL): 이동 횟수 약 1787억
• LURNU (RULNU): 이동 횟수 약 273억
• LURNN (RULNN): 이동 횟수 약 1315억
• LUULR (RUURL): 이동 횟수 약 4554억
• LUURN (RUULN): 이동 횟수 약 1737억
• LUUUL (RUUUR): 이동 횟수 약 3366억
• LUUNR (RUUNL): 이동 횟수 약 2418억
• LUUNN (RUUNN): 이동 횟수 약 512억
• LUNRR (RUNLL): 이동 횟수 약 2590억
• LUNRU (RUNLU): 이동 횟수 약 2274억
• LUNUL (RUNUR): 이동 횟수 약 1364억
• LUNUR (RUNUL): 이동 횟수 약 2598억
• LUNNL (RUNNR): 이동 횟수 약 1398억
• LUNNR (RUNNL): 이동 횟수 약 1202억
• LUNNU (RUNNU): 이동 횟수 약 1966억
• LUNNN (RUNNN): 이동 횟수 약 336억
• LNLLR (RNRRL): 이동 횟수 약 1439억
• LNLLU (RNRRU): 이동 횟수 약 1594억
• LNLRR (RNRLL): 이동 횟수 약 1591억
• LNLUL (RNRUR): 이동 횟수 약 1188억
• LNLUR (RNRUL): 이동 횟수 약 1611억
• LNLUU (RNRUU): 이동 횟수 약 1890억
• LNLUN (RNRUN): 이동 횟수 약 1219억
• LNLNU (RNRNU): 이동 횟수 약 1088억
• LNRLL (RNLRR): 이동 횟수 약 614억
• LNRLR (RNLRL): 이동 횟수 약 1340억
• LNRLU (RNLRU): 이동 횟수 약 748억
• LNRLN (RNLRN): 이동 횟수 약 1060억
• LNRRL (RNLLR): 이동 횟수 약 1512억
• LNRRR (RNLLL): 이동 횟수 약 1475억
• LNRRU (RNLLU): 이동 횟수 약 1759억
• LNRRN (RNLLN): 이동 횟수 약 1642억
• LNRUL (RNLUR): 이동 횟수 약 1227억
• LNRUR (RNLUL): 이동 횟수 약 1987억
• LNRUU (RNLUU): 이동 횟수 약 2121억
• LNRUN (RNLUN): 이동 횟수 약 1526억
• LNRNL (RNLNR): 이동 횟수 약 945억
• LNRNR (RNLNL): 이동 횟수 약 1448억
• LNRNU (RNLNU): 이동 횟수 약 1463억
• LNRNN (RNLNN): 이동 횟수 약 1338억
• LNULR (RNURL): 이동 횟수 약 2206억
• LNULU (RNURU): 이동 횟수 약 1540억
• LNURL (RNULR): 이동 횟수 약 1616억
• LNURR (RNULL): 이동 횟수 약 1924억
• LNURU (RNULU): 이동 횟수 약 1477억
• LNURN (RNULN): 이동 횟수 약 1307억
• LNUUL (RNUUR): 이동 횟수 약 3122억
• LNUUR (RNUUL): 이동 횟수 약 2691억
• LNUUU (RNUUU): 이동 횟수 약 3031억
• LNUUN (RNUUN): 이동 횟수 약 1572억
• LNUNR (RNUNL): 이동 횟수 약 1545억
• LNUNN (RNUNN): 이동 횟수 약 891억
• LNNLR (RNNRL): 이동 횟수 약 1107억
• LNNLU (RNNRU): 이동 횟수 약 700억
• LNNRL (RNNLR): 이동 횟수 약 943억
• LNNRR (RNNLL): 이동 횟수 약 1532억
• LNNRU (RNNLU): 이동 횟수 약 717억
• LNNRN (RNNLN): 이동 횟수 약 1289억
• LNNUR (RNNUL): 이동 횟수 약 618억
• LNNUN (RNNUN): 이동 횟수 약 577억
• LNNNR (RNNNL): 이동 횟수 약 1153억
• LNNNU (RNNNU): 이동 횟수 약 702억
• ULLLN (URRRN): 이동 횟수 약 2989억
• ULLNR (URRNL): 이동 횟수 약 1716억
• ULLNU (URRNU): 이동 횟수 약 7316억
• ULRLL (URLRR): 이동 횟수 약 556억
• ULRLU (URLRU): 이동 횟수 약 738억
• ULRLN (URLRN): 이동 횟수 약 1401억
• ULRRL (URLLR): 이동 횟수 약 7768억
• ULRRU (URLLU): 이동 횟수 약 6671억
• ULRUL (URLUR): 이동 횟수 약 3216억
• ULRNL (URLNR): 이동 횟수 약 2287억
• ULRNR (URLNL): 이동 횟수 약 5216억
• ULRNN (URLNN): 이동 횟수 약 8376억
• ULURL (URULR): 이동 횟수 약 2629억
• ULURR (URULL): 이동 횟수 약 2410억
• ULURN (URULN): 이동 횟수 약 5034억
• ULUNL (URUNR): 이동 횟수 약 2809억
• ULUNR (URUNL): 이동 횟수 약 4583억
• ULNLL (URNRR): 이동 횟수 약 4169억
• ULNLR (URNRL): 이동 횟수 약 3171억
• ULNLU (URNRU): 이동 횟수 약 4515억
• ULNLN (URNRN): 이동 횟수 약 2148억
• ULNRL (URNLR): 이동 횟수 약 1260억
• ULNRR (URNLL): 이동 횟수 약 2820억
• ULNUL (URNUR): 이동 횟수 약 2650억
• ULNUR (URNUL): 이동 횟수 약 3098억
• ULNUU (URNUU): 이동 횟수 약 2437억
• ULNUN (URNUN): 이동 횟수 약 2081억
• ULNNL (URNNR): 이동 횟수 약 4332억
• ULNNU (URNNU): 이동 횟수 약 4753억
• ULNNN (URNNN): 이동 횟수 약 2388억
• UULLL (UURRR): 이동 횟수 약 6600억
• UULLN (UURRN): 이동 횟수 약 1조 5192억
• UULRL (UURLR): 이동 횟수 약 1890억
• UULRR (UURLL): 이동 횟수 약 7151억
• UULUN (UURUN): 이동 횟수 약 5534억
• UULNL (UURNR): 이동 횟수 약 1조 2186억
• UUULN (UUURN): 이동 횟수 약 1조 4048억
• UUUNL (UUUNR): 이동 횟수 약 1조 429억
• UUNLL (UUNRR): 이동 횟수 약 1조 2983억
• UUNLU (UUNRU): 이동 횟수 약 7787억
• UUNUL (UUNUR): 이동 횟수 약 3698억
• UNLLU (UNRRU): 이동 횟수 약 5786억
• UNLUR (UNRUL): 이동 횟수 약 1982억
• UNLUU (UNRUU): 이동 횟수 약 3066억
• UNLUN (UNRUN): 이동 횟수 약 1743억
• UNLNR (UNRNL): 이동 횟수 약 1192억
• UNLNU (UNRNU): 이동 횟수 약 862억
• UNLNN (UNRNN): 이동 횟수 약 1667억
• UNNLR (UNNRL): 이동 횟수 약 9253억
• UNNUL (UNNUR): 이동 횟수 약 1조 1052억
• UNNNL (UNNNR): 이동 횟수 약 2250억

}}}

4. 프로세싱 코드

[ 코드 펼치기 · 접기 ]

// The following are adjustable parameters
String rule = "LR"; // Rule that the ant follows (L: turn left, R: turn right, U: turn 180, N: no change)
int initialDir = 0; // Initial direction of the ant (0: up, 1: left, 2: down, 3: right)
float cellSize = 1; // Size of cells in pixels
int numSteps = 100000000; // Number of steps done per frame
long stepLimit = 10000L*numSteps; // Maximum number of steps
int stepDisplayPeriod = 100000000; // How often showing the progress in console (Don't make it too low)

// The following are non-adjustable
Ant a; // The ant that moves around the field
int[][] field; // Array of values for cells in the field
int numColors = rule.length(); // Number of cell states
int w, h; // Width and height of screen in cells (rather than pixels)
long stepCounts = 0; // Total number of steps done

void setup() {

frameRate(1); // Frame rate per second
size(1000, 1000); // Size of screen in pixels (Adjust memory limit in settings for large size)
background(255);
noStroke();
w = int(width/cellSize);
h = int(height/cellSize);
a = new Ant(w/2, h/2, initialDir);
field = new int[w][h];

}

void draw() {

for (int c = 0; c < numSteps; c++)

if (stepCounts == stepLimit || a.xPos == 0 || a.xPos == w-1 || a.yPos == 0 || a.yPos == h-1) {

for (int m = 0; m < w; m++)

for (int n = 0; n < h; n++)

if (field[m][n] != 0) {

fill(255*((field[m][n]+numColors-1)%numColors)/(numColors-1));
rect(m*cellSize, n*cellSize, cellSize, cellSize);

}

if (stepCounts == stepLimit)

println("Total steps done:", stepCounts);

else {

fill(0);
rect(a.xPos*cellSize, a.yPos*cellSize, cellSize, cellSize);
println("Total steps done:", stepCounts+1);

}
save("ant_" + rule + ".png");
noLoop();
break;

}
else a.update();

}
class Ant {

int xPos, yPos, dir;
Ant(int tXPos, int tYPos, int tDir) {

xPos = tXPos;
yPos = tYPos;
dir = tDir;

}
void update() {

stepCounts++;
if (stepCounts % stepDisplayPeriod == 0)

println("current steps:", stepCounts, "(", xPos-w/2, "," , h/2-yPos, ")");

char rotation = rule.charAt(field[xPos][yPos]);
switch (rotation) {
case 'L':

dir++;
if (dir == 4) dir = 0;
break;

case 'R':

dir--;
if (dir == -1) dir = 3;
break;

case 'U':

dir = (dir+2)%4;
break;

}
field[xPos][yPos] = (field[xPos][yPos]+1)%numColors;
switch (dir) {
case 0:

yPos--;
break;

case 1:

xPos--;
break;

case 2:

yPos++;
break;

case 3:

xPos++;
break;

}

}

}