Zadanie

Zakoduj ciąg, który w całości składa się z wielkich liter ( A-Z), używając tylko zer i jedynek, używając własnego ulubionego schematu. Ale zasada nie jest taka prosta!

Zasady

1. Twój program / funkcja musi poprawnie obsługiwać dowolny prawidłowy ciąg wejściowy o długości 8 .
2. Wyniki muszą mieć tę samą długość dla wszystkich danych wejściowych.
3. Wyniki muszą być odrębne dla różnych danych wejściowych.
4. Wyniki muszą być jak najkrótsze.
5. Wyniki muszą być zrównoważone od zera jeden (mieć liczbę takich samych jak zera). Nie muszą być równe (tj. Idealnie wyważone), ale twój wynik zostanie za to ukarany.

Nie musisz zapewniać programu / funkcji, która dekoduje twoje kodowanie.

Wejście i wyjście

• Można zdecydować się przyjąć dowolny zestaw 26 różnych znaków ASCII zamiast A-Z.
• Możesz zdecydować o wypuszczeniu dowolnej pary wyraźnych drukowalnych znaków ASCII zamiast 0i 1.
• Nie wolno wypisywać liczb całkowitych zamiast ciągów bitowych, ponieważ mogą one mieć zera na początku i nie jest jasne, czy rzeczywiście spełniasz regułę 2.
• Jeśli zdecydujesz się odejść od wartości domyślnej ( A-Zwejściowej i 01wyjściowej), musisz określić zestawy znaków wejściowych / wyjściowych w przesyłanym pliku.

Punktacja

• Wynik podstawowy: rozmiar kodu lub 1, jeśli Twój program jest pusty.
• Kary
  • Kara za długość: pomnóż 1.5 ** (encoded length - 42)
  • Nie ma premii za bycie krótszym; 42 to minimalna długość dla idealnie zbalansowanego kodowania 8-łańcuchowych ciągów o rozmiarze 26 alfabetu.
  • Kara za brak równowagi: pomnóż 2 ** max(abs(ones - zeros) for every valid input of length 8), gdzie onesi zerossą liczbami odpowiednio 1 i 0 na każdym wyjściu.
  • Twoje zgłoszenie musi zawierać albo najgorszy przykład (wejście / wyjście), albo teoretyczne wyjaśnienie wartości kary.
• Najniższy wynik wygrywa.

Przykładowe przesłanie

Hipotetyczny esolang, 0 bajtów, wynik 74733,8906

Oto hipotetyczny esolang, w którym pusty program drukuje binarnie wszystkie kody ASCII znaków wejściowych.

Na przykład, jeśli podasz AAAAAAAAjako dane wejściowe, program wydrukuje 10000018 razy z rzędu, tj 10000011000001100000110000011000001100000110000011000001.

Wybrany alfabet wejściowy to CEFGIJKLMNQRSTUVXYZabcdefh. W ten sposób wszystkie znaki są konwertowane na siedem cyfr w postaci binarnej, a liczby zero-jedynkowe różnią się tylko o jeden na znak (wszystkie mają trzy zera i cztery zera lub odwrotnie, gdy są konwertowane na binarne).

Długość wyjściowa wynosi zawsze 56, a najgorszy przypadek niezrównoważenia występuje na wejściach takich jak CCCCCCCC, gdzie zera pojawiają się 8 razy więcej niż jedynki.

W związku z tym wynik tego przedłożenia wynosi 1.5 ** (56 - 42) * 2 ** 8 == 74733.8906.

Stax , 11 bajtów, 0 kar, wynik 11

Ten program wykorzystuje [0-9A-P]dane wejściowe i [01]wyjściowe.

ö■▄←·ï↨≡⌐╠H

Uruchom i debuguj online - kliknij przycisk Uruchom, aby rozpocząć. Pierwsze cztery przypadki testowe działają w milisekundach. Piąta za sekundy. Szósty od tysiącleci.

Odpowiednia reprezentacja ascii tego programu jest następująca.

A$21*,26|bD|N

W dużym stopniu opiera się na |Ninstrukcji, która uzyskuje późniejszą permutację tablicy.

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

Wszystkie dane wyjściowe są permutacjami początkowego ciągu. Ma 21 zer i 21 zer. Dlatego wszystkie wyjścia mają 42 znaki i są idealnie zbalansowane.

Galaretka , 19 bajtów

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

Wypróbuj online!

Wyjaśnienie

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 bajtów, Max Diff: 0, Length: 64, Score: 149636.5528 142154.7251 104745.5869

sm@S.{.p*`T4xG

Wypróbuj online!

Używa małych liter ( [a-z]) zamiast wielkich liter. Można używać wielkich liter, zastępując Gje rG1, kosztem 2 bajtów.

Mógłbym przetłumaczyć odpowiedź HyperNeutrino na Python 3, aby uzyskać lepszy wynik, ale szczerze mówiąc, chcę odpowiedź, która faktycznie działa.

Python 2 , 779 645 bajtów, Max (Różnica) = 0, Długość = 48, Wynik = 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:]

Wypróbuj online!

Liczba magiczna 4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33(w bazie 36) lub jej ekwiwalent dziesiętny 382136276621246556626597379364678993894472503063952720559883124988542417847157286833446006767955087631166943136913765901237281892296575754126024183763829277879554548743231384272055945084065681774297483130020386641869860456147616177702938121538230311395513497506285733567467605871232294046704309941152721616618474501854355102646152223338484615876165254236449912858255665248186687952137487016925761633237335983620006273901509768720506129789443353730706676483647298576692613113269388239830925662977837917272690235355742330377154505179476767457756888107428475384947712227312747517748632498691058764154580934614231152483398774630508576533263098942260213967880819240793990219283490212843120923539516962682466148372296338428497778127570401190309339992457562121354271koduje wszystkie 252 permutacje z 5 0si 5 1s.

Pierwszy algorytm przekształca A-Zjęzyk 0-25i traktuje go jako liczbę zasadową-26, a następnie dodać 56*252**4.

Następnie liczba jest konwertowana na 5-cyfrową liczbę podstawową-252 i zastępuje ją odpowiednią permutacją 5 0si 5 1s.

Następnie usuń pierwsze 2 bity, co jest gwarantowane 01. Następnie zakodowaliśmy ciąg do 48-bitowego ciągu, który składa się dokładnie z 24 0s i 24 1s.

JavaScript (ES8), wynik 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>

W przypadku parzystej długości zawsze wypisuje 3,5 * zer i jedynek, więc płaci tylko 1,5 ** 14 karę. Obsługiwane znaki: '+-.3569:<GKMNSUVYZ\cefijlqrtx.

Galaretka , 16 bajtów

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

Wykorzystuje +,-./0123456789:;<=>?@ABCDdane wejściowe i zwraca listę zer i jedynek.

Podjęto próbę zbudowania listy 538,257,874,440 kombinacji w pamięci, więc będziesz potrzebować dużej ilości pamięci RAM, aby ją uruchomić tak, jak jest ...

Wypróbuj online! (testowalny; długość wejściowa 3, długość wyjściowa 18)

Jak to działa

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 , 985 135 bajtów, maksymalna różnica 0, długość 42, wynik 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

Wypróbuj online!

Dzięki uprzejmości Bubbler

Nieskluczony kod:

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("")

Ponieważ inne podejścia wydają się dość nieefektywne, próbowałem stworzyć optymalne czasowo. Jest to wyraźnie O (N) w N bitach kodowania, co jest optymalne dla dużych O.

Wskazówka: spróbuj pomyśleć o trójkącie Pascala dla tego ( ten schemat to pokazuje)

Przykładowe wyniki:

Input:  AAAAAAAA
Output: 000000000000000000000111111111111111111111

Input:  ZZZZZZZZ
Output: 011001000000011010011000111010110110111110

Czas wykonania: <0,013 s (w przybliżeniu stały dla wszystkich wejść)

Perl 5 , 55 bajtów, maks. Różnica 0, długość 42, wynik 56 55

To działa, ale zajmie to dużo czasu, ale wykonalne ( ZZZZZZZZzajęło mi 2,5 dnia na moim komputerze). Pamięć nie stanowi problemu.

Wykorzystuje A-Zjako znaki wejściowe 1i Ajako znaki kodujące. Zawsze są idealnie wyważone. Pomija pierwsze 26^7 = 8031810176zrównoważone kombinacje reprezentujące ciąg krótszy niż 8 znaków, ale to jest OK, ponieważ są 538257874440dostępne, a ja używam 208827064575i 208827064575 + 8031810176 < 538257874440.

Jednak tak naprawdę „liczy się” aż do kombinacji docelowej, co potrwa bardzo długo. Dlatego w łączu TIO użyłem tylko zbyt krótkiego ciągu wejściowego (które są również obsługiwane), aby pokazać, że dane wyjściowe są prawidłowe. Będzie działać do nieco więcej niż AAAAAAprzed upływem limitu czasu TIO. ZZZZZZZZpowinno być około 26^3 = 17576razy wolniejsze.

#!/usr/bin/perl -ap
$_=1x21 .($i=A)x21;s/(A*)(1*)1A/$2$1A1/ until"@F"eq$i++

Wypróbuj online!

Dekoder jest prawie taki sam:

#!/usr/bin/perl -ap
$_=1x21 .($\=A)x21;s/(A*)(1*)1A/$2$1A1/,$\++until"@F"eq$_}{

Wypróbuj online!

> <> , 75 bajtów, maksymalna różnica 0, długość 42, wynik 75

0i:0(?v'A'-$dd+*+!
.")1+.\1+:0$:2%:}:@-2,@+$bl"
[ab+-?\$:?vv~3
~~]>n<v$-1<>

Wypróbuj online!

Fair Warning, to będzie trwać bardzo bardzo bardzo dużo czasu, aby zakończyć nawet na trywialne AAAAAAAAsprawy. Przebiega przez każdą reprezentację binarną licznika, aż do osiągnięcia (podstawowa reprezentacja 26 danych wejściowych) liczby binarnej z 21 1s. Jeśli chcesz nieco przetestować program, możesz zastąpić ab+trzecią linię, 1która zwróci n-tą liczbę binarną tylko jednym 1, Wypróbuj online!

Python 3 , 75 bajtów, maksymalna różnica 0, długość 42, wynik 112

lambda s:sorted({*permutations("01"*21)})[int(s,26)]
from itertools import*

Wypróbuj online!

Działa to tylko teoretycznie z powodu ograniczeń pamięci. Istnieją 538257874440wyraźne zbalansowane ciągi zerowe o długości 42 i 208827064575możliwe dane wejściowe, więc niektóre z możliwych danych wyjściowych nie zostaną wykorzystane.

-37 bajtów dzięki @recursive

C ++, 146 bajtów, 42 maksymalna długość, 0 asymetrii, wynik 146

#include<algorithm>
long long i,s;int f(char*I,char*O){for(O[i=42]=s=0;i--;i<8?s=s*26+I[i]:0)O[i]=i%2|48;for(;s--;)std::next_permutation(O,O+42);}

Działa dla każdego ciągłego 26 znaków, ale ostrzeżenie, że działa w niedopuszczalnym czasie