Comprimir uma sequência discrepância-2 máxima

18

Emita esta sequência binária de comprimento 1160:

-++-+--++-++-+--+--++-+--+--++-+--++-++-+-++--++-+---+-++-+--+--++++--+--++-+--++-++----++-++-+-++--++-+-+---++-+--++-++-+--++-+--+---+-++-+--++-++-+--+--++-++-+--++-+--+++-+-+----+++-+--+--+++---++-++-+--+--+++--+-+-+--+-+++-++-+--+--++-+--++-++-+--+--++--+++---+++-+---++-+--++--+-+--+-+++-+--++-++-+--++-+--+--++-+--++--+-++-+-+--+-+-++-+--++-+--+--++-+-+-++-+-+-++---+-+--++++--+---++-+-++-+--++-+--+--++-+--++++--+---+-++++--+--++-++-+--++-+--+--++-+--++-++-+--++-+--+--++-++-+----+++-+--++--+++---+-++-+--+-++---+-++-++-+--+--++--++++-+--+--+--++++--+--+++---++-++-+--++--+-+--+--++-++-+--+--+-+++-++-+--+--++--+-++-++-+--+--+--++-++-+--+++---++-+--++-++---+++---++-++----+++--+-++-+--+--++-+--++-++-+-++--++--++----+++-++--++----++-+++--++---+++----+-+-++-++-++-+-+----+++--++-+--++-++-+--+--+--++-+--++-++-+--++--+-+--+-+-+-++++---+-+-++--+--+-+-+-++-+-+++--+-+--+--+-+++--+-+++---++-+--+--++-++--++---++-+-++--++-+---+-++-+--+-++--++-+--++-+--+-+++-+--++--+-+-+++--+-+--++-++-+--+--+-++---+-++-+-++--++-+--+++-+----++--+-++-+-++--++-+--++-+-++--++-+---+-++-+--+++----+-+-++--++-+--++-++-++-+--+--+--++++---++---+-+-++-+-+++--+-++--+-+--+-+-++---+++-++

A sequência

Essa sequência finita é fortemente estruturada de uma maneira que, espero, leve a métodos únicos de compactação. Surge do problema da discrepância de Erdős, que foi apresentado em um desafio anterior .

Tratando os termos como +1 e -1, esta é uma sequência de discrepância de tamanho máximo 2, o que significa que:

Para cada tamanho de etapa positivo d, se você usar todos dos termos (começando com o dtermo), a soma da sequência resultante permanecerá entre -2 e 2, inclusive.

Se você pensa que cada +um significa um passo à direita e -um passo à esquerda, isso significa que a caminhada de cada dquinta instrução nunca se afasta mais de 2 passos da posição inicial.

Por exemplo, para d=3, pegar cada terceiro termo fornece a sequência +-++--+--+-..., cujas somas de execução são [1,0,1,2,1,0,1,0,-1,0,1,...], que nunca atingem -3 ou 3.

-++-+--++-++-+--+--++-+--+--++-+--+...
  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  ^
  +  -  +  +  -  -  +  -  -  +  -
   1  0  1  2  1  0  1  0 -1  0  -1  ...

Essa sequência foi encontrada em 2014 por meio de uma pesquisa no computador. Veja este artigo , onde a sequência é reproduzida no Apêndice B. A pesquisa prova que 1160 é o comprimento máximo de uma sequência de discrepância-2, embora exista mais de uma sequência desse comprimento. O problema da discrepância de Erdős, comprovado em 2015 , diz que qualquer sequência deve ter um comprimento finito para qualquer discrepância máxima cno lugar de 2.

Exigência de tempo

Seu código deve terminar em 5 segundos . Isso é para limitar a força bruta.

Formato de saída

Você pode usar dois caracteres ou valores distintos fixos para +e -em qualquer formato de lista ou de seqüência de caracteres. O formato deve ser aquele em que os valores de 1160 bits possam ser lidos diretamente, não por exemplo codificados como um número por meio de sua representação binária ou como uma string por valores de caracteres. Para saída de string, uma nova linha à direita é permitida.

Entre os melhores

Mostrar snippet de código

code-golf kolmogorov-complexity sequence combinatorics xnor
fonte
a maioria dos substrings comuns de comprimento 1-16 se alguém quer saber
ASCII-only
Eu sinto que será muito difícil de bater compressão ...
Esolanging Fruit

Respostas:

3

Geléia , 149 bytes

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

Existe algum padrão, por exemplo, apenas 81 das 256 seqüências binárias de 8 comprimentos estão presentes se alguém dividir a sequência em oito, mas eu (pelo menos ainda não notei) alguma maneira de utilizar alguma para reduzir a contagem de bytes dessa base direta Compressão 250 convertida em uma lista binária.

Experimente online! (o rodapé formata a lista binária em uma sequência para facilitar a comparação direta).

Jonathan Allan
fonte
3

Python 2 , 269 259 256 247 245 243 bytes

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

Experimente online!

Dennis
fonte
3

JavaScript (ES6), 263 253 252 bytes

Tentei usar o menor número possível de dados de carga útil. Infelizmente - mas não surpreendentemente - isso requer bastante código de descompressão.

Demolir:

  • dados de carga útil: 75 bytes, codificados como uma sequência Base64 de 100 caracteres
  • código: 163 153 152 bytes

Abaixo está uma versão formatada sem os dados. O código bruto está no snippet de demonstração.

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))
  :
    ''

Quão?

Nós controlamos as somas em execução um [i] de cada i- ésimo termo. Cada vez que essas somas atingem o limite inferior -2 , sabemos que o próximo termo deve ser um + . A mesma lógica se aplica ao limite superior. Isso é útil até i = 264 e não salva nenhum byte extra além disso.

Isso nos deixa 599 termos que não podem ser adivinhados. Nós os armazenamos como 99599 / 8⌉ = 75 bytes, codificados em uma string Base64 de 100 caracteres.

Demo

Mostrar snippet de código

Arnauld
fonte
3

Geléia , 110 109 107 bytes

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

Isso demora muito no TIO, mas termina em menos de 3 segundos no meu computador desktop.

Experimente online!

Dennis
fonte
3

Gelatina , 135 133 130 129 105 104 bytes

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

Com base nos elementos anteriores da sequência, o algoritmo adivinhar qual seria o próximo elemento. Isso funciona para todos, exceto 99 elementos, cujos índices são codificados permanentemente para que os elementos correspondentes possam ser trocados.

Experimente online!

Dennis
fonte
2

MATL , 224 bytes

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"

A saída é da forma 1 0 0 1 0 ..., onde 1corresponde a '-'e 0corresponde a '+'.

Experimente online!

Explicação

A sequência foi codificada em toda a execução. Todas as 720 corridas têm comprimentos 1, 2, 3 ou 4, sendo 3 ou 4 menos comuns. Portanto, cada 3 foi substituído por 2, 0, 1 (uma execução de 2, depois uma execução de 0 do outro símbolo, depois uma execução de 1 novamente) e da mesma forma cada 4 foi substituído por 2, 0, 2. Isso fornece uma matriz ternária de comprimento 862.

Essa matriz é convertida na codificação base-94 e é a sequência longa mostrada no código ( '$Te...kG'). A codificação base 94 usa todos os 95 caracteres ASCII imprimíveis, exceto a aspas simples (que precisariam ser ignoradas).

O código converte essa cadeia de caracteres da base 94 para a base 3 e usa o resultado para decodificar em comprimento de execução os símbolos [1 0 1 0 ... 0](matriz de comprimento 862).

Luis Mendo
fonte
2

Geléia , 95 bytes

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

Um ponto intermediário entre minhas duas abordagens anteriores.

O código tenta adivinhar 842 elementos da sequência e codifica os 318 restantes. 19 dos palpites estão incorretos e precisam ser revertidos por meio de uma lista de índices codificados.

Experimente online!

Como funciona

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

380009100940380065412452185545474826295694594854898450166594167299196720639075810827320738450934©

BḤC©

BḤC1±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
fonte
Parece que a codificação aritmética seria mais simples do que alterar manualmente algumas entradas; você já tentou isso ou Jelly é inadequado?
lirtosiast
Existem apenas 19 entradas que precisam ser alteradas, codificadas em 23 bytes. Eu acho que um decodificador aritmético seria mais longo que isso, pelo menos com os dados associados.
Dennis
1

Carvão vegetal , 150 bytes

”a∧∨~℅¹÷Ｏμ6fＣC⁼∕⁵^;Ÿ‘«·T:∕Ｄ_=v§AＨŒ,—<Ｐr¢E!◨±Ｌ^|.τ"ＮO“šþŽ∧<n`bÞＥ÷β$+Ｚ⟦5⁶⁻.λ‹ζd⧴X>w,⊞?‹⟧⌈⪪-h÷³N“Ｋ⁺L¿>ρ@Ｐ⟲↘3νηKx÷?>™Ž¿•:8Ｖ¦£œεＧ↧x℅7¶	NＲü"m”⟦)&¶bＥ“Ｙv”

Experimente online!

Faz uso da compactação de cadeia incorporada do Charcoal. Usa .para -e !para +.

Somente ASCII
fonte
1

CJam, 153 bytes

"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

Usa 1para -e 0para +.

Contém imprimíveis. Experimente online!

Isso é bem simples. Converte uma sequência longa da base 256 para a base 2.

Esolanging Fruit
fonte
1

Python 3 , 236322 bytes

Agradecimentos ao Mego por salvar 4 bytes

#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:])

Experimente online!

Usa a codificação CP-437. Agradecemos a Dennis por apontar um erro.

Somente ASCII
fonte
437é um apelido para cp437, para que você possa economizar 4 bytes se livrando dos cpbits nas duas vezes em que ocorrem.
Mego 28/05
0

Python 2 , 364 250 bytes

Obrigado a Jonathan Allan por salvar 114 bytes.

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

Experimente online!

Somente ASCII
fonte
0

C # , 385 bytes

Dados

  • Entrada nenhuma
  • Saída String O resultado pretendido.

Golfe

()=>{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;};

Ungolfed

() => {
    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;
};

Código completo

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();
      }
   }
}

Lançamentos

  • v1.0 - 385 bytes- Solução inicial.

Notas

  • Nenhum
auhmaan
fonte
0

05AB1E , 149 bytes

•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 chato. Apenas um número compactado. Usa 1para -e 0para +.

Experimente online!

Okx
fonte
0

PHP, 276 bytes

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

Experimente online!

Jörg Hülsermann
fonte
0

Ruby , 245 bytes

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

Saída 0 para + e 1 para -.

Experimente online!

GB
fonte
0

Perl, 164 bytes

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

A solução óbvia e chata: basta colocar todos os bits em uma string binária, 8 bits por byte. Usa 0 para - e 1 para +. Vou tentar jogar isso um pouco mais.

Grimmy
fonte
0

Retina , 333 bytes


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

Experimente online!

ovs
fonte