놀랍게도 이 문제는 숏코딩이 가능하다. 제출하라는 512×256×512 크기의 Anvil 파일은 사실 16×256×16 크기의 Chunk 1024개로 이루어져 있다. 구조가 알려져 있으므로 직접 Anvil 파일을 최적화하는 방법도 있겠지만, 다행히 Anvil 파일에서 필요없는 Chunk를 날려버리는 mcaselector라는 툴이 있다. 이를 이용해서 1개의 Chunk 안에 코드를 구현하고 필요없는 1023개의 Chunk를 지워버리면 굉장히 작은 파일으로 제출할 수 있다.
먼저 에디토리얼을 읽고 오면 A and not B를 계산하는 A ? B만을 이용해서 4 bit adder를 구현해야 한다는 사실을 알 수 있다. 이때 중계기의 특성상 B가 A보다 먼저 도착해야 하지만, 괜히 시간을 다르게 해놓으면 헷갈리므로 모든 A ? B는 A와 B가 같은 시간에 도착하도록 구현하는게 좋다.
A or B는 마인크래프트 특성상 레드스톤을 이어주면 된다.
A xor B는 (A ? B) or (B ? A)로 구현할 수 있다.
A and B는 A ? (A ? B)로 구현할 수 있다.
이제 Ripple-carry adder를 구현하면 문제를 풀 수 있다.
우선 문제를 A[3:0] + B[3:0] = S[4:0]라고 표현하자. 최하위 비트부터 세서 A[0]은 LSB, A[3]은 MSB가 된다.
먼저 최하위 비트는 half adder 한 개로 구현할 수 있다.
S[0] = A[0] xor B[0]
C[1] = A[0] and B[0]나머지 비트들은 full adder를 구현하면 되는데, half adder 두 개로 구현할 수 있다.
H1 = A[i] xor B[i]
H2 = A[i] and B[i]
H3 = C[i] xor H1
H4 = C[i] and H1
S[i] = H3
C[i + 1] = H2 or H4이때 S[4] = C[4]다.
half adder를 구현할 때 A xor B와 A and B는 A ? B가 겹치는 것을 이용해 공간을 절약할 수 있지만, 모든 half adder를 저런 식으로 구현하면 A and B를 4틱에 구현하게 되어 S[4]를 계산하는데 16틱이 걸리게 된다. A ? (A ? B)도 X ? (Y ? Z) 꼴이므로 A and B를 한번은 3틱으로 구현해야 한다.
이제 위 내용을 마인크래프트로 구현하면 된다. 혹시 마인크래프트를 어떻게 하는지 모른다면 아래 내용들을 읽어보자.
- 먼저 Minecraft Launcher에서 설치 설정으로 들어간 다음 신규를 눌러 1.15.2 버전의 마인크래프트를 만든다. 옛날에 만든 문제라서 최신 버전을 사용하면 안 된다.
- 게임 모드를 크리에이티브로 설정한 후 고급 세계 설정을 클릭한다. 이후 구조물 생성을 꺼짐으로, 치트 허용을 켜짐으로 설정하고 세계 유형을 완전한 평지로 설정한 다음 사용자 지정을 클릭한다. 잔디랑 흙을 지워버리고 기반암만 남긴 다음 완료를 누른다. (기반암이
bedrock이다.) - /를 누르면 명령어를 입력할 수 있다. 아래 명령어들을 입력한다.
/gamerule doMobSpawning false
/gamerule doPatrolSpawning false
/gamerule doTileDrops false
/gamerule doTraderSpawning false
/tp 0 ~ 0
/fill -1 ~ -1 -1 255 16 minecraft:torch keep
/fill -1 ~ 16 16 255 16 minecraft:torch keep
/fill 16 ~ 16 16 255 -1 minecraft:torch keep
/fill 16 ~ -1 -1 255 -1 minecraft:torch keep
- E를 눌러서 인벤토리에 아이템을 추가할 수 있다. 오른쪽 위의 나침반을 클릭하면 아이템을 검색할 수 있다. 허용되는 아이템은 기반암, 돌, 사암, 레드스톤 가루(이걸 깔면
redstone_wire가 된다), 레드스톤 중계기(repeater), 레버, 레드스톤 조명, ~색 콘크리트다. (콘크리트 가루는 안 된다.) 인벤토리에 추가한 아이템은 숫자키 1~9나 마우스 휠로 선택할 수 있다. - 이제 WASD로 움직이면서 우클릭으로 블록을 깔고 좌클릭으로 블록을 부순다. 안 움직이면 한영키를 누르자. 스페이스 바는 점프지만 스페이스 바를 두번 눌러서 날아다니는게 편하다. 스페이스 바를 누르면 올라갈 수 있고 왼쪽 쉬프트를 누르면 내려갈 수 있다. 왼쪽 컨트롤 키로 달릴 수 있지만 우리는 좁은 공간에만 있기 때문에 필요없다.
- 마지막으로 F3을 누르면 현재 위치, 그리고 현재 가리키고 있는 블록의 상태를 볼 수 있다. 레드스톤의 신호는 레버나 중계기 이후 15로 시작해서 한 칸씩 이동할 수록 신호가 1 감소하는데, 신호가 도달하고 있는지 확인할 때 좋다.
명령어 덕분에 위 사진처럼 Chunk 테두리가 횃불로 표시되어 있다. (만지면 부셔져서 매우 불편하게 될테니 만지지 말자.) 이 안쪽에서만 만들어야 1개의 Chunk 안에 코드를 구현할 수 있다.
위에서 말한대로 half adder를 A ? B를 동시에 쓰게 만들면 좁은 공간에 만들 수 있다. 이를 이용해 최하위 비트를 더한다. A ? B 꼴을 만들때 A와 B가 같은 틱에 들어오도록 중계기의 틱 수를 오른쪽 마우스로 조절하자.
나머지 비트들은 언급한대로 half adder 두 개를 이용하여 더할 수 있다. 같은 half adder를 계속 구현하는 것은 귀찮으니 마인크래프트의 clone 명령어를 쓰자.
이 작업을 반복해주면 된다. 앞서 말했던대로 마지막에는 중계기를 이어붙여서 1틱을 줄여야 15틱 이내로 A+B를 계산할 수 있다. (만약 모든 A and B를 중계기를 이어붙여 3틱에 계산했다면 12틱만에 A+B를 계산할 수 있다.)
여기까지 하면 만점을 받을 수 있지만, 숏코딩을 하려면 마인크래프트를 끄고 mcaselector를 다운받으면 된다. 설명대로 따라해 mcaselector를 실행한 다음 File -> Open에서 만들었던 마인크래프트 월드의 region 폴더를 연다.
성공했다면 위 사진처럼 뜰 것이다. 마우스 휠로 줌, 마우스 휠로 드래그를 해서 이동, 마우스 좌클릭 & 드래그로 선택, 마우스 우클릭 & 드래그로 선택 취소한 다음 Selection -> Delete selected chunks를 누른다. 이제 필요없는 chunk들이 사라져서 용량이 매우 줄어들었을 것이다.