태그 보관물: kolmogorov-complexity

kolmogorov-complexity

어떻게 만들 수 있습니까? 수있는 공예 만을 사용하여 나무 나무에서 만들어진

21 개 항목이 있습니다 마인 크래프트 당신이 할 수있는 공예 만을 사용하여 나무 나무에서 만들어진 및 항목 :

도끼
보트
그릇
버튼
가슴
공예 테이블

울타리
게이트
괭이
사다리
곡괭이
판자
압력 플레이트

기호
슬래브
계단
스틱

트랩 도어

이 목록은 6 가지 유형 의 나무 판자 / 슬라브 / 문 / 등을 가정합니다. 모두 같은 항목으로 계산됩니다. 그것을 생각하는 또 다른 방법은 한 가지 유형의 나무에만 접근 할 수 있다고 가정하는 것입니다.

이 21 개의 아이템은 각각 다른 제작법을 가지고 있습니다. 이러한 레시피를 각각 2 × 2 또는 3 × 3 격자로 표현합니다 .WPS. 는 ., 빈 공예 슬롯입니다 W입니다 나무 , P위한 나무 널빤지S입니다 스틱 . 이 특정 항목에는 다른 문자가 필요하지 않습니다.

예를 들어, 이것은 가슴 의 요리법입니다 .

PPP
P.P
PPP

도전

위에 표시된대로 정확하게 21 개의 항목 중 하나의 이름을 사용하고 해당 항목에 대한 유효한 제작법을 인쇄하는 프로그램을 작성하십시오.

제작 레시피는 변하지 않는 번역이므로 입력이 인 fence경우 둘 다 유효합니다.

PSP
PSP
...
...
PSP
PSP

레시피가 2 × 2 그리드에 맞는 경우 2 × 2 또는 3 × 3 그리드로 출력 할 수 있습니다. 예 stick:

.P
.P
...
.P.
.P.

레시피는 수평 대칭 (수직 대칭 선 주위)으로도 미러링 할 수 있지만 이것은 도끼, 괭이 및 계단에만 차이가 있습니다. 예 hoe:

.PP
.S.
.S.
PP.
.S.
.S.

따라서 그리드에 맞는 레시피를 출력하고 올바른 모양 (번역 및 미러링 무시)이 프로그램에서 수행해야합니다. 이것들은 공식 게임이 인식 할 수있는 모든 레시피입니다. (레시피는 수직으로 회전하거나 미러링 할 수 없습니다.)

세부

  • stdin 또는 명령 행에서 입력을 가져 오십시오. 입력이 항상 유효하다고 가정 할 수 있습니다. 입력 주위에 따옴표가 필요합니다 (예 🙂 "chest".
  • 선택적인 후행 줄 바꿈을 사용하여 stdout (또는 가장 가까운 대안)으로 출력하십시오.
  • 바이트 단위 의 최단 제출 이깁니다.

다음은 모든 입력 및 샘플 출력 목록입니다.

axe
PP.
SP.
S..

boat
P.P
PPP
...

bowl
P.P
.P.
...

button
P.
..

chest
PPP
P.P
PPP

crafting table
PP
PP

door
PP.
PP.
PP.

fence
PSP
PSP
...

gate
SPS
SPS
...

hoe
PP.
S..
S..

ladder
S.S
SSS
S.S

pickaxe
PPP
.S.
.S.

planks
W.
..

pressure plate
PP
..

shovel
P..
S..
S..

sign
PPP
PPP
.S.

slab
PPP
...
...

stairs
P..
PP.
PPP

stick
P.
P.

sword
P..
P..
S..

trapdoor
PPP
PPP
...


답변

CJam, 100 96 94 91 바이트

"+WcbKF AQH;_{GM8Lyf=_tmTn"141bDb3/l72b970%={Z"O>HVa=4a"98bZb+"P.SW"f=3/=}%N*

StackExchange는 인쇄 할 수없는 항목을 처리하므로 여기에 복사하여 붙여 넣는 대신 permalink가 있습니다. 또한 여기에 테스트 프로그램이 있습니다.

( fJamam의 모듈로 색인에 대해 알려 주신 @Optimizer와 @ MartinBüttner 에게 감사드립니다 .)

Cygwin ‘s hexdump:

0000000 0122 2b1e 571a 6308 621f 4b05 2046 5141
0000010 1608 1848 5f3b 1115 1d7b 4d47 4c38 6679
0000020 5f3d 6d74 0c54 226e 3431 6231 6244 2f33
0000030 376c 6232 3739 2530 7b3d 225a 1b4f 483e
0000040 6156 343d 2261 3839 5a62 2b62 5022 532e
0000050 2257 3d66 2f33 7d3d 4e25 002a
000005b

설명

레시피를 구성하기 위해 13 개의 다른 행을 사용합니다 (이것이 왜 최소인지 설명도 나와 있습니다).

0    W..    (required by planks)
1    ...    (required by many)
2    .PP    (required by many)
3    PPP    (required by chest)
4    .P.    (required by bowl)
5    ..P    (required by stairs)
6    S.S    (required by ladder)
7    SSS    (required by ladder)
8    .S.    (required by sign)
9    .SP    (required by axe)
10   P.P    (required by bowl)
11   PSP    (required by fence)
12   SPS    (required by gate)

를 통해 우리는 행을 인코딩 Z"O>HVa=4a"98bZb+"P.SW"f=3/, 제공하는

["W.." "..." ".PP" "PPP" ".P." "..P" "S.S" "SSS" ".S." ".SP" "P.P" "PSP" "SPS"]

첫 번째 비트 "+WcbKF AQH;_{GM8Lyf=_tmTn"141bDb3/, 조리법을 인코딩 제공

[[3 3 8] [1 0 0] [1 0 0] [3 8 8] [1 3 3] [2 8 8] [6 7 6] [1 0 0] [1 10 3] [1 1 2] [2 2 2] [1 11 11] [1 1 4] [1 0 1] [1 10 4] [2 9 8] [3 10 3] [1 2 2] [4 8 8] [1 4 4] [1 1 3] [1 12 12] [4 4 8] [5 2 3]]

첫 번째 항목이 얼마나 주 [3 3 8]에 대한 제조법 인 sign.

l72b970%=입력을 읽은 다음 목록에서 가져올 레시피를 해결하기 위해 몇 가지 마술을 적용합니다. 21 개의 레시피 만 있지만리스트에는 24 개의 레시피가 있습니다. 여분의 스팟은 [1 0 0]s에 해당합니다 .

입력을 읽은 후 레시피를 선택하고 레시피를 행으로 변환 한 후 줄 바꿈 N*과 자동 인쇄를 수행했습니다.


CJam, 89 86 83 바이트

'W"9=!%)S@*m:@DQzk?V$%qyR55AmVEpPNW}"132b3b"P.S"f=+3/3/l57b5342%24%(=N*

… CJam에서는 모든 출력을 하드 코딩하는 것이 약간 더 좋습니다. 나는 매우 실망했다.

다시 한번 우리는 인쇄 할 수없는 것들이 있으므로 여기에 permalink and test program이 있습니다.

Cygwin ‘s hexdump:

0000000 5727 0222 3d39 1021 2925 531e 2a40 6d0b
0000010 403a 1844 7a51 3f6b 2456 7125 5279 3506
0000020 4135 046d 1a56 7045 1550 164e 1057 7d01
0000030 3122 3233 3362 2262 2e50 2253 3d66 332b
0000040 332f 6c2f 3735 3562 3433 2532 3432 2825
0000050 4e3d 002a
0000053

설명

출력은베이스 3을 사용하여 인코딩되며 W, 문자열이 3으로 분할되어 행이 제공되기 전에 고독 이 앞쪽에 고정되고 행이 3의 그룹으로 분할되어 레시피가 제공됩니다.

위와 같이,베이스 변환과 모듈로 매직이 레시피를 선택하는 데 사용됩니다. 22 가지 레시피 (하나는 사용하지 않음)가 있지만 모듈로 24를 사용해야하므로 실제로 24%모듈로 색인에 의존하기보다는이 시간 을 명시 적으로 지정해야 합니다.


답변

자바 스크립트 (ES6), 235 (241) (262)

편집 입력이 항상 유효하다는 규칙을 더 많이 사용하지 않으면 W가 필요한 항목이 하나 뿐이며 특별한 경우가 있습니다. 따라서 출력 그리드는 9 자리 기본 3 자리 숫자로 인코딩됩니다.

팝업을 통한 I / O가있는 235 바이트

w=prompt();
"926a722boa182bo2b19520ch224c6056d644f448g764h7651l2294pi8pr758sh2915si26sl19172sta56st785s728t"
.replace(/(\d+)(\D+)/g,(c,p,m)=>w.search(m+z)||[for(c of'11\n11\n111')z+='.SP'[~~p%3]+(p/=3,-c?'':c)],z='');
alert(&&z||'W.\n..')

테스트 가능한 함수로 221 바이트

F=w=>"926a722boa182bo2b19520ch224c6056d644f448g764h7651l2294pi8pr758sh2915si26sl19172sta56st785s728t"
.replace(/(\d+)(\D+)/g,(c,p,m)=>w.search(m+z)||[for(c of'11\n11\n111')z+='.SP'[~~p%3]+(p/=3,-c?'':c)],z='')&&z||'W.\n..'

항상 3×3 그리드로 출력합니다. 4 개의 사용 가능한 출력 심볼로 그리드는 3x3x2 (18) 비트 번호로 인코딩됩니다. 입력이 항상 유효해야하므로 문자열은 최소한으로 잘립니다.

Firefox / FireBug 콘솔에서 테스트

;["axe", "boat", "bowl", "button", "chest", "crafting table", "door",
 "fence", "gate", "hoe", "ladder", "pickaxe", "planks", "pressure plate",
 "shovel", "sign", "slab", "stairs", "stick", "sword", "trapdoor"]
.forEach(v=>console.log(v+'\n'+F(v)))

산출

axe
PP.
SP.
S..

boat
P.P
PPP
...

bowl
P.P
.P.
...

button
P..
...
...

chest
PPP
P.P
PPP

crafting table
PP.
PP.
...

door
PP.
PP.
PP.

fence
PSP
PSP
...

gate
SPS
SPS
...

hoe
PP.
S..
S..

ladder
S.S
SSS
S.S

pickaxe
PPP
.S.
.S.

planks
W.
..

pressure plate
PP.
...
...

shovel
P..
S..
S..

sign
PPP
PPP
.S.

slab
PPP
...
...

stairs
P..
PP.
PPP

stick
P..
P..
...

sword
P..
P..
S..

trapdoor
PPP
PPP
...

답변

파이썬, 305 바이트

n=2**(23-hash(raw_input())/535366%24);print "W..\n...\n..." if n==1024 else "\n".join(["".join(['P' if [16706041,9740732,7635081,7399784,5267501,7372808,57344,57344,49152][j+i*3]&n==n else 'S' if [6,2097152,6,131078,10748162,6,131138,9699584,2][j+i*3]&n==n else '.' for j in range(3)]) for i in range(3)])

설명

# Compute a unique number for each item.
# 535366 and 24 are precalculated values that were bruteforced.
n = 23 - hash(raw_input()) / 535366 % 24

# Use precalculated tables that represent which ingredient in this recipe of
# an item. The nth bit of p[0] will be set if the first ingredient of the item
# associated with the unique number n is some planks. It works the same for s.
p = [16706041,9740732,7635081,7399784,5267501,7372808,57344,57344,49152]
s = [6,2097152,6,131078,10748162,6,131138,9699584,2]

# Handle planks differently, as it is the only one using wood.
if n == 10:
    print "W..\n...\n..."
else:
    for i in xrange(3):
        line = ""
        for j in xrange(3):
            # Now we can check if the ingredient is some planks...
            if p[j + i * 3] & 1 << n == 1 << n:
                line += 'P'
            # ...or if it is some sticks...
            elif s[j + i * 3] & 1 << n == 1 << n:
                line += 'S'
            # ...or if it is simply empty.
            else:
                line += '.'
        print line

논평

이 코드는 확실히 가장 작지는 않지만 잘 작동합니다. 나는 만족했다. 🙂

파이썬, 282 바이트

n=hash(raw_input())/808789215%21;print "\n".join(["P.PPPP...P..S..S..PP.......PP.PP....P........SPSSPS...PPPPPP.S.PP.PS..S.W........PPPPPP...PP..S..S.P..PP.PPPS.SSSSS.SPPP.S..S.PPP......P..P..S..PPPP.PPPPPSPPSP...PP.PP.PP.P..P.....P.P.P...."[9*n+i*3:9*n+(i+1)*3] for i in range(3)])

동일한 기술을 사용하여 고유 식별자를 생성하지만 배열에서 레시피를 직접 검색합니다. 첫 번째 코드보다 훨씬 간단하고 작습니다.


답변