Skompresuj maksymalną sekwencję rozbieżności-2

18

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 co dtrzeci (poczynając od dtego), 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 dinstrukcji nigdy nie przebiega o więcej niż 2 kroki od pozycji początkowej.

Na przykład, d=3przyjmowanie 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 czamiast 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

xnor
źródło
najczęstsze podciągi o długości 1-16, jeśli ktoś chce wiedzieć
tylko ASCII
Wydaje

Odpowiedzi:

3

Galaretka , 149 bajtów

“×GOẈ*m¬¿3d{ẋạ⁻@Ɓ]ZĊỵINBƬḊṿẊ*N¹Ẹ÷ƲẋɼoṬḳ£®⁾ƙŒọ¡[P1&ạ€ẊʠNỌXḢṖėÐß⁹Ụṗ¬⁹E#ụḷḌṁżżR=Ɗѳıɲ-ṭỌṾɲẎĿỴ⁶€ḋtɦÐ\ỵƒ⁾ƒụṫṡĊKpƭẏkaṪ,Ẋȧ⁻ḅMɓ%YḷsƲƭl¤æĊbṬ9D6ẎƘẓ^Œ⁷Ɲḷḷ€ḟ1g’B

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).

Jonathan Allan
źródło
3

Python 2 , 269 259 256 247 245 243 bajtów

r=[1]
c=int('bmqnh8j8rdo4mirjos6uxbfthu8t39pjy6up43axryzwbwcu5d528nsakitjwqbo6dnnozy0oybhk6jduaoc53lqkzdb04opj5t50a24w9he5y7qbgd2',36)
while c:t=sum(sum(r[::-k])/3for k in range(1,264)if len(r)%k<1);r[-1:]=cmp(0,t)or c%2*2-1,1;c>>=t==0
print r

Wypróbuj online!

Dennis
źródło
3

JavaScript (ES6), 263 253 252 bajtów

Próbowałem użyć jak najmniejszej ilości danych. Niestety - ale nie jest to zaskakujące - wymaga to sporo kodu dekompresyjnego.

Awaria:

  • dane ładunku: 75 bajtów, zakodowane jako 100-znakowy ciąg Base64
  • kod: 163 153 152 bajtów

Poniżej znajduje się sformatowana wersja bez danych. Surowy kod znajduje się we fragmencie wersji demonstracyjnej.

f = (a = Array(264).fill(n = p = 0)) =>
  n++ < 1160 ?
    '+/-'[
      p += !a.some((v, i) =>
        n % i | v * v - 4 ?
          0
        :
          r = v / 2,
        r = atob`...`.charCodeAt(p / 8) >> p % 8 & 1 || -1
      ),
      r + 1
    ] +
    f(a.map((v, i) => n % i ? v : v - r))
  :
    ''

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

Arnauld
źródło
3

Galaretka , 110 109 107 bajtów

;1mS€:3o/Nȯ®Ṫṭḷ
“ĖṄẋ{Xṛ-İIṗ®6⁼Ḟ2a⁻!Ċẉȥ+¡Ƒ¥mvrẓsṘ×⁴ç&$nỴỤ)M7?ẊẎḅ=ṠƈTṙḌȥụẋXḌ⁵Ḣ⁺ḲL÷æTƥĿv€%ḟ¢®!Ė’BḤ’©ṛ⁽¡ɠÆD€Nç/

To trwa zbyt długo w TIO, ale kończy się w niecałe 3 sekundy na moim komputerze stacjonarnym.

Wypróbuj online!

Dennis
źródło
3

Galaretka , 135 133 130 129 105 104 bajtów

42“I=İėZP*ðEḄẈṆ'mBƝėŻƝ6®Ṇɼḥ[bȦėṡV£(6ṘɱX)Ṅẹ6~K7°ȤÄỴ¥ƝÇ5prḳġŻ£ƭṗṄFṾḃ{©@ɼ’ḃÄċL
L+Ø.ÆDm@NÇ¡§§No¥/Ṡo-ṭ
Ç⁽¡ɠ¡Ḋ

W 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!

Dennis
źródło
2

MATL , 224 bajty

862:o'$Te]BQHoHxkw!-CEjv(j=zGp.8_C{\?wkH{t&%W.:ja#7=+>"/,=0wDJ+"2BREtgh9_2I%1>+99T3kPrknzlJ}&8kUR(S!pX]C]05u{"6MHA7"gg(M6\5Vp.k.18Y(c~m&wroTrN)sf" |>\,Lg80C:nUez|l;<h~m(%]4xx6?`=qGtZ):d"*"@~1M.T}jJ)Bl7>Ns >9$8R1MlkG'F3:qZaY"

Wyjście ma postać 1 0 0 1 0 ..., w której 1odpowiada '-'i 0odpowiada'+' .

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).

Luis Mendo
źródło
2

Galaretka , 95 bajtów

“qạʂṅs⁽fØʋZ%BÞġı½.m0&u⁺TsƝȧAuỴż⁶3uÞ$+ȷ@4Ṣ’BḤC©µmLÆD$§SṠȯ®ṪNLḟ“⁶ .£µ+£gÐ9Ц.ñ×µ¥¤®‘ÄḤ¤ɗ}¡ṭø⁽¡ɠ¡Ḋ

Ś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

“qạʂṅs⁽fØʋZ%BÞġı½.m0&u⁺TsƝȧAuỴż⁶3uÞ$+ȷ@4Ṣ’

380009100940380065412452185545474826295694594854898450166594167299196720639075810827320738450934©

BḤC©

BC1±1

µmLÆD$§SṠȯ®ṪNLḟ“⁶ .£µ+£gÐ9Ц.ñ×µ¥¤®‘ÄḤ¤ɗ}¡ṭ

0

mLÆD$§SṠȯ®ṪNLḟ“⁶ .£µ+£gÐ9Ц.ñ×µ¥¤®‘ÄḤ¤ɗ}¡ṭ  Monadic chain. Arument: A (array)

 LÆÐ$                                       Compute all divisors of the length of A.
m                                           For each divisor d, generate the subarray
                                            of each d-th element.
     §                                      Take the sum of each subarray.
      S                                     Take the sum of the sums.
       Ṡ                                    Take the sign of the sum.
        ȯ®                                  If the result is 0, replace it with the
                                            array in the register.
          Ṫ                                 Tail; pop and yield the last element,
                                            modifying the register for a zero sum.
                                            This is a no-op for a non-zero sum.
              “⁶ .£µ+£gÐ9Ц.ñ×µ¥¤®‘ÄḤ¤      Yield all indices of incorrect guesses.
           NLḟ                        ɗ¡    If the length of A doesn't appear among
                                            the indices, negate the result.
                                        ṭ   Append the result to A.
ø⁽¡ɠ¡Ḋ

0⁽¡ɠ11600

Dennis
źródło
Wydaje się, że kodowanie arytmetyczne byłoby prostsze niż ręczna zmiana niektórych wpisów; próbowałeś tego, czy też Jelly nie nadaje się do tego?
lirtosiast
Jest tylko 19 wpisów, które należy zmienić, które są zakodowane w 23 bajtach. Myślę, że dekoder arytmetyczny byłby dłuższy, przynajmniej z powiązanymi danymi.
Dennis
1

Węgiel drzewny , 150 bajtów

”a∧∨~℅¹÷Oμ6fCC⁼∕⁵^;Ÿ‘«·T:∕D_=v§AHŒ,—<Pr¢E!◨±L^|.τ"NO“šþŽ∧<n`bÞE÷β$+Z⟦5⁶⁻.λ‹ζd⧴X>w,⊞?‹⟧⌈⪪-h÷³N“K⁺L¿>ρ@P⟲↘3νηKx÷?>™Ž¿•:8V¦£œεG↧x℅7¶	NRü"m”⟦)&¶bE“Yv”

Wypróbuj online!

Wykorzystuje wbudowaną kompresję sznurka Charcoal. Zastosowania .dla -i !dla +.

Tylko ASCII
źródło
1

CJam, 153 bajty

"Ke²ÉLº[
O%2¹d²Ý,Éeñlr[´KeÙ.Y­K-iZ[*Të
ÊYl°Ý
ËeËd¼Y%³l69,ÖÉmÙ¤¶ÉcN9<il²S3ÄÏ#8õ$¯d¶Ë%Õ¦Õ(Öѣɦ]-2ËEd¶)/4¦YLºXõ2É-°çR5©Ä"256b2b

Zastosowań 1dla -i 0dla +.

Zawiera materiały niedrukowalne. Wypróbuj online!

To jest całkiem proste. Konwertuje długą sekwencję z zasady 256 na zasadę 2.

Esolanging Fruit
źródło
1

Python 3 , 236 232 bajty

Dzięki Mego za uratowanie 4 bajtów

#coding:437
print(bin(int.from_bytes('ûKe▓╔L║[\rûO%2╣d▓▌,û╔eè±lr[\x1a┤KeÆ┘Ä.Y¡\x16K-ûiZû[*Tδ\r╩Yl░▌\rÆ╦eÆ╦d╝YÄû¥%│\x0bl69,╓╔m\x12┘ñ╢╔cûN9<il▓S3─╧#8⌡$»\x19d╢╦%Ü╒\x0eª╒(╓╤úû╔£ª]-2╦EÜìd╢¥)û/4ªYL║X⌡2╔-░τRì5⌐─'.encode('437'),'big'))[2:])

Wypróbuj online!

Wykorzystuje kodowanie CP-437. Dzięki Dennis za wskazanie błędu.

Tylko ASCII
źródło
437jest aliasem dla cp437, więc możesz ogolić 4 bajty, pozbywając się cpbitów za każdym razem, gdy się pojawią.
Mego
0

Python 2 , 364 250 bajtów

Podziękowania dla Jonathana Allana za uratowanie 114 bajtów.

print bin(int('28x0lphxjx8ze4uuhtdzo0oebr25amtmuxm62cbit0ibdwjm2sf50clh2ejq0a73ndseo5tove8uqca6nf66bo4abbkg867woh2b435at0o3pddvqmsqp29b6as5bd4eo28xgwkkj607gp66icba1q4n9fc13dltp45j340mpzbc56wsrbb3oejnczsbzfgh82xdi8aku8m4wlmwuxkgy4yaew7pu4p1g',36))[2:]

Wypróbuj online!

Tylko ASCII
źródło
0

C # , 385 bajtów


Dane

  • WejścieBrak
  • Wyjście String Udany wynik.

Grał w golfa

()=>{var s="i´\u009aM6³E¤òi°ÚÍF\u009bM\"Ói6\u009au\u000e\u0093\u008d¤åK´\u009am&qѦRé´Òi\u0096¥i¤Õ«\u0014ò5¦\u0093O\"òm4\u009am4\u009bC¦qibÚLô\u0093ÉÆÓ)6\u0092í&[I6\u009ci±ÆÃ\u0096\u0093M¬Ì;0ÜÇ\nÛPæ\u009bI4Úe*ñY*×).\\i6cY¢ÒÍ4ºer\u009bIbÖiÐËY¦³E§\nÍ6ÒO\u0018­rÊV;";var o="";foreach(var c in s)foreach(var b in Convert.ToString(c,2).PadLeft(8,'0'))o+=(char)(43+(49-(int)b)*2);return o;};

Bez golfa

() => {
    var s = "i´\u009aM6³E¤òi°ÚÍF\u009bM\"Ói6\u009au\u000e\u0093\u008d¤åK´\u009am&qѦRé´Òi\u0096¥i¤Õ«\u0014ò5¦\u0093O\"òm4\u009am4\u009bC¦qibÚLô\u0093ÉÆÓ)6\u0092í&[I6\u009ci±ÆÃ\u0096\u0093M¬Ì;0ÜÇ\nÛPæ\u009bI4Úe*ñY*×).\\i6cY¢ÒÍ4ºer\u009bIbÖiÐËY¦³E§\nÍ6ÒO\u0018­rÊV;";
    var o = "";

    foreach( var c in s )
        foreach( var b in Convert.ToString( c, 2 ).PadLeft( 8, '0' ) )
            o += (char) ( 43 + ( 49 - (int) b ) * 2 );

    return o;
};

Pełny kod

using System;

namespace Namespace {
   class Program {
      static void Main( String[] args ) {
        Func<String> f = () => {
            var s = "i´\u009aM6³E¤òi°ÚÍF\u009bM\"Ói6\u009au\u000e\u0093\u008d¤åK´\u009am&qѦRé´Òi\u0096¥i¤Õ«\u0014ò5¦\u0093O\"òm4\u009am4\u009bC¦qibÚLô\u0093ÉÆÓ)6\u0092í&[I6\u009ci±ÆÃ\u0096\u0093M¬Ì;0ÜÇ\nÛPæ\u009bI4Úe*ñY*×).\\i6cY¢ÒÍ4ºer\u009bIbÖiÐËY¦³E§\nÍ6ÒO\u0018­rÊV;";
            var o = "";

            foreach( var c in s )
                foreach( var b in Convert.ToString( c, 2 ).PadLeft( 8, '0' ) )
                    o += (char) ( 43 + ( 49 - (int) b ) * 2 );

            return o;
        };

        Console.WriteLine( $" Input: <none>\nOutput: {f()}\n" );

        Console.ReadLine();
      }
   }
}

Prasowe

  • v1.0 - 385 bytes- Wstępne rozwiązanie.

Notatki

  • Żaden
auhmaan
źródło
0

05AB1E , 149 bajtów

•19GÈRÕŸ
pт6½÷Ü;вVåΔĀÈ₄¤Ü³Aʒм5[¦PŠÅøœ^‚₆賦ìóV“LÛ'ßq;αÎΩªî»(2∍©däf×5 V5Ú”gÜ/\^(Ã∊Ƶ!3šÍ3°(§A΄ǝ₂È₅ç£6óàÖCsa*zƒÚ¥Î\ªD¹,n∊ðˆ.ëçPαǝƒ.É∍¯ü₂³Λ‘g∍Θþ“‚œΔи‹•b

Super nudno. Tylko skompresowana liczba. Zastosowania 1dla -i 0dla +.

Wypróbuj online!

Okx
źródło
0

PHP, 276 bajtów

<?=gzinflate(base64_decode("dVJRFgMgCDoQj/tfb2+boqj9VJohQgQI8rv+D1yHuIIytGLsYh6vwAlYIMS62mVCiWMm56vfHiGOuTwjiMHQEC7OVlkNzzK0LZFTN8l0gavGdX4wOfJDsZpXZS0csig0l13wEsoRlvKzhYHMv+F9MnxaCXHWrC2Kx4UqQ8o4qmgNcsjbzA5lZG7LE6LdNMlt2sRKFpNhk/sL59N6DSMKp4No7vP2QcP0c2XWb6nPblqYfJBfHw=="));

Wypróbuj online!

Jörg Hülsermann
źródło
0

Rubinowy , 245 bajtów

puts"%b"%"28x0lphxjx8ze4uuhtdzo0oebr25amtmuxm62cbit0ibdwjm2sf50clh2ejq0a73ndseo5tove8uqca6nf66bo4abbkg867woh2b435at0o3pddvqmsqp29b6as5bd4eo28xgwkkj607gp66icba1q4n9fc13dltp45j340mpzbc56wsrbb3oejnczsbzfgh82xdi8aku8m4wlmwuxkgy4yaew7pu4p1g".to_i(36)

Wyjście 0 dla + i 1 dla -.

Wypróbuj online!

GB
źródło
0

Perl, 164 bajty

print unpack'b*','-Y²lÍ¢%O
[³bÙ²DËlY®pɱ%§Ò-Y¶deJ-Ki¥%«Õ(O¬eÉòDO¶,Y¶,ÙÂeF[2/ÉcËlI·dÚl9cÃiɲ53Ü;ãPÛ
gÙ,[¦TTët:lÆEK³,]¦NÙFkÓeÍ¢åP³lKòµNSjÜ'

Hexdump:

00000000: 7072 696e 7420 756e 7061 636b 2762 2a27  print unpack'b*'
00000010: 2c27 962d 59b2 6ccd a225 4f96 0d5b b362  ,'.-Y.l..%O..[.b
00000020: d9b2 44cb 966c 59ae 70c9 b125 a7d2 2d59  ..D..lY.p..%..-Y
00000030: b664 8e8b 654a 972d 4b96 69a5 9625 abd5  .d..eJ.-K.i..%..
00000040: 284f ac65 c9f2 444f b62c 59b6 2cd9 c265  (O.e..DO.,Y.,..e
00000050: 8e96 465b 322f c993 63cb 946c 49b7 64da  ..F[2/..c..lI.d.
00000060: 926c 3996 8d63 c369 c9b2 3533 dc0c 3be3  .l9..c.i..53..;.
00000070: 50db 0a67 d992 2c5b a654 8f9a 54eb 9474  P..g..,[.T..T..t
00000080: 3a96 6cc6 9a45 4bb3 2c5d a64e d992 466b  :.l..EK.,].N..Fk
00000090: 960b d39a 65cd a2e5 50b3 6c4b f218 b54e  ....e...P.lK...N
000000a0: 536a dc27                                Sj.'

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.

Ponury
źródło
0

Retina , 333 bajty


ADG-RMCGHQFDLEM+-FAG-CADGPAKBBLHBCH-EGHJBORGEH-HB-FJOBPRCA+JAG-A+A+NJHQLIB-R+Q-OQPRAGP-HBEH-CGNCDGEH+BCCHQH-PDJCEGOGECDGCPK-FNH-EDLHCRIEELHDELEKE-HLJDDA+LHFGCFADJJBK+-JDCJBI+JCOOLGEDELMCGNAGKBEJKJEGCNCIF+BLECMMCAKLJDFDGCH+-E-JIQDJJNHD¶
R
GF
Q
+C
P
EA
O
CK
N
D-
M
I-A
L
--
K
D+
J
CB
I
A++
H
E+
G
AB
F
-AD
E
C+
D
B+
C
-B
B
-+
A
-++-+-

Wypróbuj online!

ovs
źródło