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


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

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


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!


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


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!


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!


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


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


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


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.


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.


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!


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

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!


0

PHP, 276 bajtów

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

Wypróbuj online!


0

Rubinowy , 245 bajtów

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

Wyjście 0 dla + i 1 dla -.

Wypróbuj online!


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.


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!

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.