Wyjście tej sekwencji binarnej o długości 1160:
-++-+--++-++-+--+--++-+--+--++-+--++-++-+-++--++-+---+-++-+--+--++++--+--++-+--++-++----++-++-+-++--++-+-+---++-+--++-++-+--++-+--+---+-++-+--++-++-+--+--++-++-+--++-+--+++-+-+----+++-+--+--+++---++-++-+--+--+++--+-+-+--+-+++-++-+--+--++-+--++-++-+--+--++--+++---+++-+---++-+--++--+-+--+-+++-+--++-++-+--++-+--+--++-+--++--+-++-+-+--+-+-++-+--++-+--+--++-+-+-++-+-+-++---+-+--++++--+---++-+-++-+--++-+--+--++-+--++++--+---+-++++--+--++-++-+--++-+--+--++-+--++-++-+--++-+--+--++-++-+----+++-+--++--+++---+-++-+--+-++---+-++-++-+--+--++--++++-+--+--+--++++--+--+++---++-++-+--++--+-+--+--++-++-+--+--+-+++-++-+--+--++--+-++-++-+--+--+--++-++-+--+++---++-+--++-++---+++---++-++----+++--+-++-+--+--++-+--++-++-+-++--++--++----+++-++--++----++-+++--++---+++----+-+-++-++-++-+-+----+++--++-+--++-++-+--+--+--++-+--++-++-+--++--+-+--+-+-+-++++---+-+-++--+--+-+-+-++-+-+++--+-+--+--+-+++--+-+++---++-+--+--++-++--++---++-+-++--++-+---+-++-+--+-++--++-+--++-+--+-+++-+--++--+-+-+++--+-+--++-++-+--+--+-++---+-++-+-++--++-+--+++-+----++--+-++-+-++--++-+--++-+-++--++-+---+-++-+--+++----+-+-++--++-+--++-++-++-+--+--+--++++---++---+-+-++-+-+++--+-++--+-+--+-+-++---+++-++
Sekwencja
Ta skończona sekwencja jest ściśle skonstruowana w sposób, który, mam nadzieję, nadaje unikalne metody kompresji. Wynika to z problemu rozbieżności Erdősa, który został opisany w poprzednim wyzwaniu .
Traktując terminy jako +1 i -1, jest to sekwencja rozbieżności 2 o maksymalnej długości, co oznacza, że:
Dla każdego pozytywnego rozmiaru kroku
d
, jeśli weźmiesz każdy cod
trzeci (poczynając odd
tego), bieżąca suma wynikowej sekwencji pozostaje między -2 a 2 włącznie.
Jeśli uważasz, że każdy z nich +
oznacza krok w prawo i -
krok w lewo, oznacza to, że spacer każdej d
instrukcji nigdy nie przebiega o więcej niż 2 kroki od pozycji początkowej.
Na przykład, d=3
przyjmowanie co 3 kadencję daje sekwencję +-++--+--+-...
, której sumy bieżące są [1,0,1,2,1,0,1,0,-1,0,1,...]
, które nigdy nie trafiają -3 lub 3.
-++-+--++-++-+--+--++-+--+--++-+--+...
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
+ - + + - - + - - + -
1 0 1 2 1 0 1 0 -1 0 -1 ...
Sekwencję tę znaleziono w 2014 r. Za pomocą wyszukiwania komputerowego. Zobacz ten artykuł , w którym sekwencja została odtworzona w załączniku B. Wyszukiwanie dowodzi, że 1160 jest maksymalną długością sekwencji rozbieżności-2, chociaż istnieje więcej niż jedna sekwencja o tej długości. Problem rozbieżności Erdősa, udowodniony w 2015 r. , Mówi, że każda taka sekwencja musi mieć skończoną długość dla każdej maksymalnej rozbieżności c
zamiast 2.
Wymagany czas
Twój kod powinien zakończyć się w ciągu 5 sekund . Ma to na celu ograniczenie brutalnego wymuszania.
Format wyjściowy
Można użyć dowolnych dwóch stałych odrębne znaki lub wartości +
, a -
w każdym lista podobnego lub ciąg podobnego formatu. Format powinien być taki, w którym można bezpośrednio odczytać wartości 1160 bitów, a nie na przykład zakodować jako liczbę poprzez binarną reprezentację lub ciąg znaków poprzez wartości znakowe. W przypadku ciągów znaków dozwolony jest końcowy znak nowej linii.
Tabela liderów
Odpowiedzi:
Galaretka , 149 bajtów
Istnieje pewien wzorzec, na przykład, tylko 81 z 256 ciągów binarnych o długości 256 jest obecnych, jeśli ktoś pokroi sekwencję na ósemki, ale nie zauważyłem (przynajmniej jeszcze) żadnego sposobu wykorzystania dowolnego w celu zmniejszenia liczby bajtów z tej prostej bazy Kompresja 250 przekonwertowana na listę binarną.
Wypróbuj online! (stopka formatuje listę binarną na ciąg znaków, aby ułatwić bezpośrednie porównanie).
źródło
Python 2 ,
269259256247245243 bajtówWypróbuj online!
źródło
JavaScript (ES6),
263253252 bajtówPróbowałem użyć jak najmniejszej ilości danych. Niestety - ale nie jest to zaskakujące - wymaga to sporo kodu dekompresyjnego.
Awaria:
163153152 bajtówPoniżej znajduje się sformatowana wersja bez danych. Surowy kod znajduje się we fragmencie wersji demonstracyjnej.
W jaki sposób?
Śledzimy bieżące sumy [i] każdego i-tego terminu. Za każdym razem, gdy sumy te przekroczą dolną granicę -2 , wiemy, że następny termin musi być znakiem + . Ta sama logika dotyczy górnej granicy. Jest to pomocne do i = 264 i nie oszczędza żadnego dodatkowego bajtu poza tym.
Pozostaje nam 599 terminów, których nie można zgadnąć. Przechowujemy je jako 99599 / 8⌉ = 75 bajtów, zakodowane w 100-znakowym ciągu Base64.
Próbny
Pokaż fragment kodu
źródło
Galaretka ,
110109107 bajtówTo trwa zbyt długo w TIO, ale kończy się w niecałe 3 sekundy na moim komputerze stacjonarnym.
Wypróbuj online!
źródło
Galaretka ,
135133130129105104 bajtówW oparciu o poprzednie elementy sekwencji algorytm w wyrafinowany sposób zgaduje, jaki mógłby być następny element. Działa to dla wszystkich elementów oprócz 99, których indeksy są zakodowane na stałe, aby można było zamienić odpowiednie elementy.
Wypróbuj online!
źródło
MATL , 224 bajty
Wyjście ma postać
1 0 0 1 0 ...
, w której1
odpowiada'-'
i0
odpowiada'+'
.Wypróbuj online!
Wyjaśnienie
Sekwencja została zakodowana na całej długości. Wszystkie 720 przebiegów mają długości 1, 2, 3 lub 4, przy czym 3 lub 4 są mniej powszechne. Tak więc każda 3 została zastąpiona przez 2, 0, 1 (seria 2, następnie seria 0 drugiego symbolu, następnie seria 1 ponownie) i podobnie każda 4 została zastąpiona 2, 0, 2. To daje tablicę trójskładnikową o długości 862.
Tablica ta jest konwertowana na kodowanie base-94 i jest długim łańcuchem pokazanym w code (
'$Te...kG'
). Kodowanie Base 94 wykorzystuje wszystkie 95 znaków drukowalnych ASCII, z wyjątkiem pojedynczego cudzysłowu (który musiałby być poprzedzony znakiem ucieczki).Kod konwertuje ten ciąg z podstawy 94 na podstawę 3 i wykorzystuje wynik do dekodowania symboli w czasie przebiegu
[1 0 1 0 ... 0]
(tablica o długości 862).źródło
Galaretka , 95 bajtów
Środkowy punkt między moimi dwoma poprzednimi podejściami.
Kod próbuje odgadnąć 842 elementy sekwencji i koduje pozostałe 318 elementów. 19 domysłów jest niepoprawnych i należy je cofnąć za pomocą listy zakodowanych wskaźników.
Wypróbuj online!
Jak to działa
©
B
Ḥ
C
⁽¡ɠ
Ḋ
źródło
Węgiel drzewny , 150 bajtów
Wypróbuj online!
Wykorzystuje wbudowaną kompresję sznurka Charcoal. Zastosowania
.
dla-
i!
dla+
.źródło
CJam, 153 bajty
Zastosowań
1
dla-
i0
dla+
.Zawiera materiały niedrukowalne. Wypróbuj online!
To jest całkiem proste. Konwertuje długą sekwencję z zasady 256 na zasadę 2.
źródło
Python 3 ,
236232 bajtyDzięki Mego za uratowanie 4 bajtów
Wypróbuj online!
Wykorzystuje kodowanie CP-437. Dzięki Dennis za wskazanie błędu.
źródło
437
jest aliasem dlacp437
, więc możesz ogolić 4 bajty, pozbywając sięcp
bitów za każdym razem, gdy się pojawią.Python 2 ,
364250 bajtówPodziękowania dla Jonathana Allana za uratowanie 114 bajtów.
Wypróbuj online!
źródło
C # , 385 bajtów
Dane
String
Udany wynik.Grał w golfa
Bez golfa
Pełny kod
Prasowe
385 bytes
- Wstępne rozwiązanie.Notatki
źródło
05AB1E , 149 bajtów
Super nudno. Tylko skompresowana liczba. Zastosowania
1
dla-
i0
dla+
.Wypróbuj online!
źródło
PHP, 276 bajtów
Wypróbuj online!
źródło
Rubinowy , 245 bajtów
Wyjście 0 dla + i 1 dla -.
Wypróbuj online!
źródło
Perl, 164 bajty
Hexdump:
Oczywiste, nudne rozwiązanie: wystarczy umieścić wszystkie bity w ciągu dwójkowym, 8 bitów na bajt. Używa 0 dla - i 1 dla +. Spróbuję jeszcze trochę zagrać w golfa.
źródło
Retina , 333 bajty
Wypróbuj online!
źródło