태그 보관물: code-challenge

code-challenge

밸런스드 제로원 인코딩 때문에, 대신의 비트 문자열을

직무

A-Z선호하는 체계를 사용하여 0과 1 만 사용하여 대문자 알파벳 ( )으로 완전히 구성된 문자열을 인코딩 하십시오. 그러나 규칙은 그렇게 간단하지 않습니다!

규칙

  1. 프로그램 / 기능은 길이가 8 인 유효한 입력 문자열을 올바르게 처리해야합니다 .
  2. 모든 입력에 대해 결과의 길이는 동일해야합니다.
  3. 개별 입력에 대해 결과가 고유해야합니다.
  4. 결과는 가능한 짧아야합니다.
  5. 결과는 0에서 1로 균형을 이루어야합니다 ( 0 과 유사한 수의 숫자가 있어야 함 ). 그들은 같을 필요는 없지만 (즉, 완벽하게 균형을 잡을 수는 있지만) 당신의 점수는 그에 대해 벌점을받습니다.

인코딩을 디코딩하는 프로그램 / 기능을 제공 할 필요는 없습니다.

입력과 출력

  • 대신 26 개의 고유 한 인쇄 가능한 ASCII 문자 세트를 허용하도록 결정할 수 있습니다 A-Z.
  • 및 대신 인쇄 가능한 고유 ASCII 문자 쌍을 출력하도록 결정할 수 있습니다 .01
  • 당신은되는 출력의 정수 허용되지 는 앞에 0을 가질 수 있기 때문에, 대신의 비트 문자열을 당신이 실제로 규칙이 만난 경우는 불분명하다.
  • 기본값 ( A-Z입력 및 01출력) 에서 벗어나기로 결정한 경우 제출에서 입력 / 출력 문자 세트를 지정해야합니다.

채점

  • 기본 점수 : 코드 크기 또는 프로그램이 비어있는 경우 1
  • 페널티
    • 길이에 대한 페널티 : 곱하기 1.5 ** (encoded length - 42)
    • 더 짧은 보너스는 없습니다; 42는 알파벳 크기가 26 인 8 길이 문자열의 완벽하게 균형 잡힌 인코딩의 최소 길이입니다.
    • 불평형 것에 대한 패널티 : 곱셈 2 ** max(abs(ones - zeros) for every valid input of length 8)여기서 ones그리고 zeros1과 0의 개수는 각각 각 출력한다.
    • 귀하의 제출물은 최악의 사례 (입력 / 출력) 또는 페널티 값에 대한 이론적 설명을 보여 주어야합니다.
  • 가장 낮은 점수가 이깁니다.

제출 예

가설 esolang, 0 바이트, 점수 74733.8906

비어있는 프로그램이 입력 문자의 모든 ASCII 코드를 이진으로 인쇄하는 가상의 esolang이 있습니다.

 

예를 들어, AAAAAAAA입력으로 입력하면 프로그램이 1000001연속으로 8 회 인쇄됩니다 ( 예 🙂 10000011000001100000110000011000001100000110000011000001.

입력 알파벳이로 선택되었습니다 CEFGIJKLMNQRSTUVXYZabcdefh. 이런 식으로 모든 문자는 이진수로 7 자리로 변환되며 0-1 카운트는 문자 당 1 씩만 다릅니다 (이진수로 변환 될 때 모두 1과 4가 0이거나 그 반대).

출력 길이는 항상 56이고, 최악의 경우 불균형은과 같은 입력에서 발생하며, CCCCCCCC0은 1보다 8 배 더 많이 나타납니다.

따라서이 제출 점수는 1.5 ** (56 - 42) * 2 ** 8 == 74733.8906입니다.



답변

Stax , 11 바이트, 0 페널티, 점수 11

이 프로그램은 [0-9A-P]입력 및 [01]출력에 사용합니다.

ö■▄←·ï↨≡⌐╠H

온라인으로 실행 및 디버깅 -실행 버튼을 클릭하여 시작하십시오. 처음 네 가지 테스트 사례는 밀리 초 단위로 실행됩니다. 초의 다섯 번째입니다. 밀레니아에서 여섯 번째.

이 프로그램의 해당 ASCII 표현은 이렇습니다.

A$21*,26|bD|N

|N배열에 대한 순열을 얻는 명령 에 크게 의존합니다 .

A$21*           "10" repeated 21 times
     ,26|b      get input and decode it as a base 26 number
          D|N    ... that many times get the next lexicographic permutation

모든 출력은 초기 문자열의 순열입니다. 21 개의 0과 21 개의 0이 있습니다. 따라서 모든 출력은 42 자이며 완벽하게 균형을 이룹니다.


답변

젤리 , 19 바이트

O_65ḅ26ị2Ḷ¤x21¤Œ!Q¤

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

설명

O_65ḅ26ị2Ḷ¤x21¤Œ!Q¤  Main Link
O                    Take the character code of each character
 _65                 Subtract 65 (the code of "A")
    ḅ26              Convert to base 26
       ị             Get the <left-arg>th element of:
        2Ḷ¤x21¤Œ!Q¤  All balanced strings of length 42:
        2Ḷ           range(2) == [0, 1]
           x21       stretch 21 ([0, 0, ..., 0, 1, 1, ..., 1])
               Œ!    all permutations
                 Q   deduplicate

답변

Pyth, 20 19 14 바이트, 최대 거리 : 0, 길이 : 64, 점수 : 149636.5528 142154.7251 104745.5869

sm@S.{.p*`T4xG

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

[a-z]대문자 대신 소문자 알파벳 ( )을 사용합니다 . 2 바이트의 비용 으로을 대체 G하여 대문자를 사용할 수 있습니다 rG1.

더 나은 점수를 얻기 위해 HyperNeutrino 의 Python 3 답변 을 번역 할 수는 있지만 솔직히 실제로 작동하는 답변을 원합니다.


답변

파이썬 (2) , 779 (645) 바이트의 맥스 (DIFF) = 0, 길이 = 48, 점수 = 7346.95

def f(s):
 a,b=0,""
 for i in s:a=a*26+ord(i)-65
 a+=56*252**4
 for i in range(5):b=bin((int("4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33",36)>>a%252*10)&1023)[2:].rjust(10,"0")+b;a/=252
 return b[2:]

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

매직 넘버
4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33(기수 36) 또는 그와 동등한 10 진수 382136276621246556626597379364678993894472503063952720559883124988542417847157286833446006767955087631166943136913765901237281892296575754126024183763829277879554548743231384272055945084065681774297483130020386641869860456147616177702938121538230311395513497506285733567467605871232294046704309941152721616618474501854355102646152223338484615876165254236449912858255665248186687952137487016925761633237335983620006273901509768720506129789443353730706676483647298576692613113269388239830925662977837917272690235355742330377154505179476767457756888107428475384947712227312747517748632498691058764154580934614231152483398774630508576533263098942260213967880819240793990219283490212843120923539516962682466148372296338428497778127570401190309339992457562121354271는 5 0와 5 1의 252 개의 순열을 모두 인코딩합니다 .

알고리즘은 먼저 그것을 기본 26 숫자로 변환 A-Z하여 0-25처리 한 다음를 더 56*252**4합니다.

그런 다음 숫자는 5 자리 기본 252 숫자로 변환되고 해당 순열 5 0초와 5 1초로 대체됩니다 .

그 후에는 처음 2 비트를 삭제하십시오 01. 그런 다음 문자열을 정확히 24 0초와 24 1초로 구성된 48 비트 문자열로 인코딩했습니다 .


답변

자바 스크립트 (ES8), 22186.623779296875

f=
s=>s.replace(/./g,(c,i)=>(i%2*127^c.charCodeAt()).toString(2).padStart(7,0))
<input oninput=o.textContent=f(this.value)><pre id=o>

짝수 길이 입력의 경우 항상 3.5 *의 0과 1을 출력하므로 1.5 ** 14의 페널티 만 지불합니다. 지원되는 문자 : '+-.3569:<GKMNSUVYZ\cefijlqrtx.


답변

젤리 , 16 바이트

42ɠO%ḅ26ịœcH$ạ‘Ṭ

+,-./0123456789:;<=>?@ABCD입력에 사용 하고 1과 0의 목록을 리턴합니다.

이것은 메모리에 538,257,874,440 조합의 목록을 작성하려고 시도하므로 그대로 실행하려면 많은 양의 RAM이 필요합니다.

온라인으로 사용해보십시오! (테스트 가능; 입력 길이 3, 출력 길이 18)

작동 원리

42ɠO%ḅ26ịœcH$ạ‘Ṭ  Main link. No arguments.

42                Set the argument and the return value to 42.
  ɠ               Read one line from STDIN.
   O              Ordinal; map ['+', ..., 'D'] to [43, ..., 69].
    %             Take the code points modulo 42, mapping [43, ..., 69] to
                  [1, ..., 26].
     ḅ26          Convert the result from base 26 to integer.
            $     Combine the two links to the left into a monadic chain.
           H          Halve; yield 21.
         œc           Generate all 21-combinations of [1, ..., 42].
                  There are 538,257,874,440 of these combinations. The first
                  269,128,937,220 begin with a 1.
        ị         Retrieve the combination at the index to the left.
                  [26, 26, 26, 26, 26, 26, 26, 26] in bijective base 26 equals
                  217,180,147,158 in decimal, so the retrieved combination will
                  begin with a 1.
              ‘   Increment; yield 43.
             ạ    Absolute difference; map [1, ..., 42] to [42, ..., 1].
                  The combination now begins with a 42.
               Ṭ  Untruth; turn the combination into a Boolean list, with 1's
                  at the specified indices and 0's elsewhere.
                  Since the maximum of the combination is 42, this list will have
                  exactly 42 items, 21 of which will be 1's.

답변

Python 3 , 985135 바이트, Max Diff 0, 길이 42, 점수 135

lambda s:C(int(s,26),21,20)
B=lambda x,y:y<1or-~x*B(x+1,y-1)//y
def C(n,o,z):p=B(o,z);x=n>=p;return z+1and[x]+C(n-p*x,o-x,z-1+x)or[1]*o

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

버블 러 제공

Ungolfed 코드 :

import math

def binomial(x, y):
    return math.factorial(x) // math.factorial(y) // math.factorial(x - y)

def string_to_int(input_str):
    result = 0
    for i in range(0,8):
        result += (ord(input_str[i])-65)%26 * pow(26,i)
    return result

def counting_function(target, ones, zeros):
    if zeros > 0:
        position = binomial(ones+zeros-1,zeros-1)
    else:
        position = 1
    if target > position:
        if ones > 0:
            print("1", end='')
            ones -= 1
            counting_function(target-position,ones,zeros)
    else:
        if zeros > 0:
            print("0", end='')
            zeros -= 1
            counting_function(target,ones,zeros)
        elif ones > 0:
            print("1", end='')
            ones -= 1
            counting_function(target,ones,zeros)

input_str = input("Input string (A-Z): ")
input_int = string_to_int(input_str)+1
target = input_int
ones = 21
zeros = 21
counting_function(target, ones, zeros)
print("")

다른 접근 방식은 매우 비효율적이므로 시간 최적화 방법을 시도했습니다. N 비트의 인코딩에서 clealy O (N)이며 이는 큰 O 최적입니다.

힌트 : 이것에 대한 파스칼의 삼각형을 생각해보십시오 ( 이 도표 는 그것을 보여줍니다)

샘플 출력 :

Input:  AAAAAAAA
Output: 000000000000000000000111111111111111111111

 

Input:  ZZZZZZZZ
Output: 011001000000011010011000111010110110111110

실행 시간 : <0.013s (모든 입력에 대해 거의 일정)