태그 보관물: kolmogorov-complexity

kolmogorov-complexity

화난 오리 Qua U >

이 이모티콘 >:U이 무엇을 의미하는지는 확실 하지 않지만, 많은 학자들은 그것이 성난 오리 처럼 보인다고 생각합니다 . 그것이 사실이라고 가정 해 봅시다.

태스크

0에서 3 사이 의 정수 n이 주어지면 인쇄 또는 반환

quack

만약 N = 0,

>:U

만약 N = 1,

     U   U
>  : U   U
 >   U   U
>  : U   U
      UUU

만약 N = 2,

                  >:U         >:U
>:U               >:U         >:U
   >:U       >:U  >:U         >:U
      >:U         >:U         >:U
         >:U      >:U         >:U
      >:U         >:U         >:U
   >:U       >:U  >:U         >:U
>:U               >:U         >:U
                     >:U>:U>:U

n = 3 인 경우

입력이 항상 유효하다고 가정 할 수 있습니다. 출력에 선행 공간이 없어야하지만 후행 공간은 충분합니다. 오리 (@cobaltduck 제외)는 허점에 대한 내성을 갖지 않습니다. 바이트 단위의 최단 코드가 이깁니다.



답변

CJam, 108 90 85 바이트

"quack"">:U":D"scT¦{$ì"{269b22bSf*D}:F~[ZYB].*s.+s5/"ÿ3nÜïS{JÐø¦yûn"F*33/z]ri=zN*

일부 문자는 인쇄 할 수 없습니다. 온라인으로 사용해보십시오!

배경

CJam에서는 처음 두 개의 출력을 압축 할 수 없습니다.

마지막 출력을 압축하는 것은 간단합니다. 모든 줄 바꿈을 제거한 후 결과 문자열을에서 나누고 >:U각 결과 문자열 길이를 계산할 수 있습니다.

그 결과 배열

[18 9 0 15 9 3 7 2 9 6 9 9 9 6 9 6 9 9 3 7 2 9 0 15 9 21 0 0 0]

베이스 22에서베이스 269로 변환하여 효율적으로 저장할 수 있습니다.

[255 12 51 110 220 239 83 123 74 208 248 166 121 251 110 17]

각 자릿수가 256 보다 작으므로 단일 바이트로 저장할 수 있습니다.

마지막으로 행과 열을 바꾸면 세 번째 출력을 압축하는 것이 더 쉬워집니다.

 > >
  >

 : :

UUUU
    U
    U
    U
UUUU

공백이 아닌 문자 사이의 공백을 한 번 더 세면 배열을 얻습니다.

[1 1 3 8 1 6 0 0 0 5 4 4 0 0 0 0 0]

이것은

[115 159 99 84 166 123 36 236 6]

베이스 22에서베이스 269로 트랜스 코딩 될 때.

작동 원리

"quack"   e# Push the first output.

">:U":D   e# Push the second output, and save it in D.

e# Push [115 159 99 84 166 123 36 236 6] as bytes.

"scT¦{$ì"

{         e# Define a code block:
  269b22b e#   Transcode from base 269 to base 22.
  Sf*     e#   Replace each digit with a string of that many spaces.
  D       e#   Push D.
}         e#
:F~       e# Save the block in F. Execute it.
[ZYB]     e# Push [3 2 11].
.*        e# Vectorized repeat; push [">>>" "::" "UUUUUUUUUUU"].
s         e# Flatten the array of strings.
.+        e# Append the nth character to the nth string of spaces.
s5/       e# Flatten and split into chunks of length 5.

e# Push [255 12 51 110 220 239 83 123 74 208 248 166 121 251 110 17] as bytes.

"ÿ3nÜïS{JÐø¦yûn"

F         e# Execute F.
*         e# Join the resulting array of strings of spaces, separating by ">:U".
33/       e# Split into chunks of length 33.
z         e# Zip; transpose rows with columns.

]         e# Wrap the entire stack in an array.
ri        e# Read a token from STDIN and interpret it as an integer.
=         e# Retrieve the element at the corresponding index.
z         e# Zip; transpose rows with columns or map "string" to ["string"].
N*        e# Join, separating by linefeeds.


답변

자바, (303) 286 바이트

@VoteToClose 덕분에 17 바이트를 절약했습니다!

실제로 가장 짧은 것이 아니라 Java로 시도하는 것이 재미있을 것이라고 생각했습니다.

공통 문자열을 나타내는 문자열 변수 목록을 작성한 다음 모든 출력의 배열을 작성한 후 올바른 것을 출력합니다.

String a(int y){String n="\n",d=">:U",A=" ",B=A+A,C=B+B,D=C+C,a="U"+B+" U"+n,G=D+A,H=C+B,c=d+G+d+n,E=B+A,F=C+E;String[]z={"quack",d,C+A+a+">"+B+": "+a+" >"+E+a+">"+B+": "+a+C+B+"UUU",D+D+B+c+d+D+F+c+B+A+d+F+d+B+c+H+d+G+c+G+d+H+c+H+d+G+c+E+d+F+d+B+c+d+D+F+c+D+D+C+A+d+d+d};return z[y];}

언 골프 드 :

String a(int y) {
    String n = "\n", d = ">:U", A = " ", B = A + A, C = B + B, D = C + C,
            a = "U" + B + " U" + n, G = D + A, H = C + B, c = d + G + d + n,
            E = B + A, F = C + E;
    String[] z = { "quack", d, C + A + a + ">" + B + ": " + a + " >" + E + a + ">" + B + ": " + a + C + B + "UUU", D + D + B + c + d + D + F + c + B + A + d + F + d + B + c + H + d + G + c + G + d + H + c + H + d + G + c + E + d + F + d + B + c + d + D + F + c + D + D + C + A + d + d + d };
    return z[y];
}

이것이이 사이트의 첫 번째 답변이므로 내가 잘못한 점이 있으면 알려주십시오.


답변

05AB1E , 162 (159) 157 바이트

암호

젠장, 너무 길지만 적어도 뭔가 :

">:U"VI3Qið16×7166b1ð:0Y:DUJ,Yð13×JD?X,3838b1ð:0Y:D?X,16255b1ð:0Y:D?X,16367b1ð:0Y:4F?X,}ð21×Y3×J,}¹2Qið4×" U   U"©J,">  :"®JD," >  "?®,,ð6×'U3×J,}¹iY,}"quack

온라인으로 사용해보십시오!


설명

코드의 첫 번째 부분은의 문자열로 ">:U"V설정 Y됩니다. 그런 다음 입력이 3과 같은지 확인하면됩니다 I3Qi. 같으면 거대한 까치를 인쇄합니다.

N = 3

먼저 ð16×16 개의 공백 문자를 입력합니다. 그 후에는 숫자가 7166b있습니다. 이것은 ">:U "Retina의 약간의 도움으로 부분을 다룹니다 :). 이 스크립트 를 사용 하여 문자열을 이진수로 변환했습니다. 그 후, 우리는에 도착 1ð:0Y:모든 대체 부분, 1공백 문자와 각과 0Y설정되었습니다 >:U. 그 후, 우리는 D이 문자열을 uplicate에 저장 X사용 UJ스택 OIN. 우리는 이것을 사용 ,하여 전체 문자열을 줄 바꿈으로 인쇄합니다. 그 이후의 다른 모든 항목은 모두 동일한 프린시 페를 기반으로합니다. if 문은 두 번째로 끝납니다 }.

전체 변환은 여기 에서 찾을 수 있습니다 .

N = 2

이제 입력이 2인지 확인합니다. 이것은 ¹2Qi부분 에서 수행됩니다 . 그 후, 같으면를 사용하여 공백 문자를 4 번 누릅니다 ð4×. 그 후, 우리는 " U U"문자열 을 밀어 넣고 ©(Jelly : p에서 도난당한 아이디어를 사용하여) 저장합니다 . 우리는 다시 J스택에 손을 대고 개행으로 이것을 인쇄합니다. 그 후, 우리는 밀어 "> :"문자열의 검색 " U U"사용을 ®, J스택 OIN과 D이 문자열을 uplicate과 같은 줄에 두 가지를 인쇄 할 수 있습니다.

간단한 퀴즈,이 작업은 무엇 " > "?®,입니까?

위의 문자열을 인쇄 한 후, 얼굴의 두 번째 줄의 복제본을 가져 와서 인쇄합니다 (두 번째 줄과 동일하기 때문에).

이 사례에서 다루는 마지막 부분은 다음과 같습니다.

ð6×'U3×J,

ð6×        # Push the space character × 6
   'U3×    # Push the "U" character three times
       J,  # Join and print pop with a newline

N = 1

이것은 설명하기가 더 쉽습니다.

¹1QiY

¹1Qi   # Check if the input is equal to 1
    Y  # Push the magpie face
       # This is then implicitly printed

N = 0

¹0Qi"quack

¹0Qi        # Check if the input is equal to 0
    "quack  # Weird sound what magpies make
            # Implicitly printed


답변

Vitsy , 172 (171) 159 바이트

오 이런 방법의 힘을 과시하기를 원한다면 나는 그것을 얻었습니다.

' 'V1+m
'kcauq'Z
'U:>'Z
58m5m6m'   > 'Z5m6m'UUU'68m
f3+bm9mamcm98m2m6bmcmam9mf6+8m3\[2m]
a'U   U'Z
' :  >'Z5m
Z2m98ma2m
\VZ
2mfbm
VVVZ2m78m2mVV7m
8m7m
68m2m9bm

온라인으로 사용해보십시오!

이것이 작동하는 방법은 다양한 방법을 자체적으로 호출하는 것입니다. 설명은 다음과 같습니다.

' 'V1+m
' 'V      Save character literal ' ' as a permanent variable.
    1+    Add one to the top item of the stack (input + 1)
      m   Go to that index of code.

'kcauq'Z
'kcauq'   Push 'quack' to the stack.
       Z  Output everything in the stack as a char.

'U:>'Z
'U:>'Z    Ouput ">:U" with the same method as the previous line.

Now on to some more... interesting lines.

58m5m6m'   > 'Z5m6m'UUU'68m
5              Push space, push 4
 8m            Call the 8th line index.
               As we will soon see, the 8th line index duplicates the space
               the number of times specified by the number just before the call
               (4 in this case)
   5m          Call the 5th line index.
               The 5th line index outputs the 'U   U' and a newline.
     6m        Call the 6th line index.
               The 6th line index outputs '>  : U   U' and a newline.
'   > 'Z       Output ' >   '.
        5m6m   Same method calls as before.
'UUU'          Push 'UUU'.
     68m       Push 6, then call the 8th line index. This gives us the correct padding.

f3+bm9mamcm98m2m6bmcmam9mf6+8m3\[2m]
f3+              Push 18.
   bm            Call the 11th line index.
                 The 11th line index calls the 8th line index (which we've already seen
                 in action) and then the 7th line index, which you can find and explanation
                 for below (it does a lot)
     9m          Call the 9th line index.
                 The 9th line index outputs '>:U               >:U         >:U' (explanation lower)
       am        Call the 10th line index.
                 ...I'm gonna stop explaining these and just tell you to go to the lines now. :P
         cm      Call the 12th line index.
9                Push space, push 9.
 8m              Call the 8th line index (explained below and before).
   2m            Call the 2nd line index.
     6           Push 6.
      bm         Call the 11th line index. We've finished up to '>:U      >:U         >:U' now.
cm               You guessed it! Call the 12th line index. (explanation below)
  am             Call the 10th line index. (explanation below)
    9m           Call the 9th line index. (explanation below)
f6+              Push space, push 19 21.
   8m            Call the 8th line index. (explanation below)
     3\[2m]      Call the 2nd line index thrice.

All of the rest of these methods are supporting methods now.

a'U   U'Z       Output 'U   U' followed by a newline.

' :  >'Z5m      Output '>  : U   U' followed by a newline.

Z2m98ma2m
Z               Output everything currently in the stack.
 2m             Call the 2nd line index.
   9            Push space, push 8.
    8m          Call the 8th line index. (explained below)
      a         Push a newline to the stack.
       2m       Call the 2nd line index.
                This handles the biggest angry duck face's faces showing the eyebrows and eyes.

\VZ
\V    Push space as many times as the top item specifies.
  Z   Output everything in the stack.

2mfbm
2m      Call the 2nd line index.
  f     Push space, push 14.
   bm   Go to the 11th line index.
        This handles the mouth and some parts of the eyebrows of the biggest duck face.

VVVZ2m78m2mVV7m
VVVZ              Output 3 spaces (and whatever was pushed before it)
    2m            Call the 2nd line index.
      7           Push space, push 6.
       8m         Call the 8th line index. (explained... above)
         2m       Call the 2nd line index.
           VV     Push 2 spaces.
             7m   Call the 7th line index.

8m7m     This is pretty damn self-explanatory if you've read this far.

68m2m9bm
6            Push space, push 5.
 8m          Call the 8th line index.
   2m        Call the 2nd line index.
     9       Push space, push 9.
      bm     Call the 11th line index.

이 코드는 말도 안됩니다. 자세한 형태는 다음과 같습니다.

toggle single quote;
 ;
toggle single quote;
save top as permanent variable;
push 1;
add top two;
goto top method;
:toggle single quote;
k;
push 12;
push 10;
flatten top two stacks;
q;
toggle single quote;
output stack as chars;
:toggle single quote;
U;
clone current stack;
go forward;
toggle single quote;
output stack as chars;
:push 5;
push 8;
goto top method;
push 5;
goto top method;
push 6;
goto top method;
toggle single quote;
 ;
 ;
 ;
go forward;
 ;
toggle single quote;
output stack as chars;
push 5;
goto top method;
push 6;
goto top method;
toggle single quote;
U;
U;
U;
toggle single quote;
push 6;
push 8;
goto top method;
:push 15;
push 3;
add top two;
push 11;
goto top method;
push 9;
goto top method;
push 10;
goto top method;
push 12;
goto top method;
push 9;
push 8;
goto top method;
push 2;
goto top method;
push 6;
push 11;
goto top method;
push 12;
goto top method;
push 10;
goto top method;
push 9;
goto top method;
push 15;
push 6;
add top two;
push 8;
goto top method;
push 3;
repeat next instruction set top times;
begin recursive area;
push 2;
goto top method;
end recursive area;
:push 10;
toggle single quote;
U;
 ;
 ;
 ;
U;
toggle single quote;
output stack as chars;
:toggle single quote;
 ;
clone current stack;
 ;
 ;
go forward;
toggle single quote;
output stack as chars;
push 5;
goto top method;
:output stack as chars;
push 2;
goto top method;
push 9;
push 8;
goto top method;
push 10;
push 2;
goto top method;
:repeat next instruction set top times;
save top as permanent variable;
output stack as chars;
:push 2;
goto top method;
push 15;
push 11;
goto top method;
:save top as permanent variable;
save top as permanent variable;
save top as permanent variable;
output stack as chars;
push 2;
goto top method;
push 7;
push 8;
goto top method;
push 2;
goto top method;
save top as permanent variable;
save top as permanent variable;
push 7;
goto top method;
:push 8;
goto top method;
push 7;
goto top method;
:push 6;
push 8;
goto top method;
push 2;
goto top method;
push 9;
push 11;
goto top method;


답변

자바 스크립트 (ES6), 163 바이트

var solution =

n=>["quack",d=">:U",`5U3U
>2:1U3U
1>3U3U
>2:1U3U
6UUU`,`99090
096090
30702090
609090
906090
609090
30702090
096090
993000`][n].replace(/\d/g,c=>+c?" ".repeat(c):d)
<input type="number" oninput="R.textContent=solution(+this.value)"><pre id="R"></pre>

설명

JavaScript로 실행 압축을 사용합니다 : 실행 길이 인코딩. 숫자가 1하는 9많은 공간에 매핑, 0성난 오리 얼굴에 매핑하고, 다른 문자는 동일하게 유지됩니다.


답변

JAPT, 116 (105) 102 99 96 바이트

["quack""c)`+«öÂ[@=^Gñ`1]o2"mc r'4#¿+R "4z>2:z >2z>2:z6UUU"rz" U3U
" '1]®r'1">:U" r"%d"_SpZ}ÃgU

인쇄 할 수 없습니다. 온라인으로 테스트하십시오!

작동 원리

처음 두 문자열은 전혀 압축되지 않습니다. 세 번째는 각 실행 간격을 길이로 바꾼 다음 간단히로 압축하여 압축 " U3U"됩니다 "z". 마지막 것은 더 복잡합니다.

  1. 2-9 공백의 각 런을 길이로 바꿉니다.
  2. 교체 >:U와 함께 1.
  3. 교체 191\n와 함께 4. ( 4문자열의 다른 곳에서는 사용되지 않습니다.)
  4. 유효한 각 바이트 코드 ( 10255또는 0AFF)를 해당 문자 코드가있는 문자에 매핑하십시오 .

결과 문자열의 길이는 21 19 바이트이지만 압축 해제는 다른 31 29를 차지합니다 .

문자열을 압축 해제 한 후 U입력 항목의 위치를 ​​간단히 가져옵니다 . (배열은 처음이 아닌 배열 [0,3,2,1] 에서부터 계산되는 버그가 있기 때문에 배열됩니다.)

[                      // Create an array of the following:
  "quack"              //  "quack".

  "c)`+«öÂ[@=^Gñ`1]o2" //  Take this string (contains an unprintable).
                       //  Map each char to its char code.
                       //  This produces "994196431712461949164619431712419649931112".
  r'4#¿+R              //  Replace each "4" with the char code of "¿" (191) + a newline.

  "4z>2:z >2z>2:z6UUU" //  Take this string.
  rz" U3U\n"           //  Replace each "z" with " U3U\n".

  '1                   //  "1".
]
®              Ã       // Map each item by this function:
r'1">:U"               //  Replace each "1" with ">:U".
r"%d"_SpZ}             //  Replace each remaining digit Z with Z spaces.

gU                     // Get the item at index -U, wrapping.
                       // (This should just be U, but there's a bug which negates it.)


답변

MATL , 283 182 바이트

@Adnan 덕분에 101 바이트가 절약되었습니다!

이것은 소수를 사용하여 인덱스를 인코딩합니다 03사례 2와 3의 경우 4 개의 문자로. 십진수는 base-64 인코딩을 사용하여 압축 될 수 있지만 ck!

경우 3 @Adnan 제안 아주 좋은 트릭이 사용된다 : 각 행을 인코딩 곳 바이너리 시퀀스를 정의 0하고 1공간 및 해당 >:U각각.

~?'quack'}G1=?'>:U'}G2=?' :>U'12336 8466480h2109488h8466480h4032h4YA47-)}268697600 67174401h16795656h67174464h67174912h67174464h16795656h67174401h14680064h"@BP48+]Xh49'>:U'YX48 32YXc

온라인으로 사용해보십시오!