Compressez une séquence d'écart maximal-2

18

Sortez cette séquence binaire de longueur 1160:

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

La séquence

Cette séquence finie est étroitement structurée d'une manière qui, je l'espère, se prête à des méthodes de compression uniques. Il découle du problème de divergence d'Erdős, qui a été présenté dans un défi précédent .

En traitant les termes comme +1 et -1, il s'agit d'une séquence de longueur maximale de divergence 2, ce qui signifie que:

Pour chaque taille de pas positive d, si vous prenez chaque d'ème terme (en commençant par le de terme), la somme cumulée de la séquence résultante reste comprise entre -2 et 2 inclus.

Si vous pensez que chacun +signifie un pas à droite et -un pas à gauche, cela signifie que la marche de chaque dinstruction ne se déplace jamais à plus de 2 pas de la position de départ.

Par exemple, pour d=3, prendre tous les 3 trimestres donne la séquence +-++--+--+-..., dont les sommes cumulées sont [1,0,1,2,1,0,1,0,-1,0,1,...], qui ne frappent jamais -3 ou 3.

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

Cette séquence a été trouvée en 2014 via une recherche informatique. Voir cet article , où la séquence est reproduite à l'annexe B. La recherche prouve que 1160 est la longueur maximale d'une séquence de divergence-2, bien qu'il existe plusieurs séquences de cette longueur. Le problème de divergence d'Erdős, prouvé en 2015 , dit qu'une telle séquence doit avoir une longueur finie pour toute divergence maximale cau lieu de 2.

Exigence de temps

Votre code devrait se terminer dans les 5 secondes . C'est pour limiter le forçage brutal.

Format de sortie

Vous pouvez utiliser deux valeurs ou caractères distincts fixes pour +et -dans n'importe quel format de type liste ou chaîne. Le format doit être un format dans lequel les 1160 bits peuvent être directement lus, et non par exemple codés sous forme de nombre via sa représentation binaire ou de chaîne via des valeurs de caractères. Pour la sortie de chaîne, une nouvelle ligne de fin est autorisée.

Classement

Afficher l'extrait de code

code-golf kolmogorov-complexity sequence combinatorics xnor
la source
les sous - chaînes les plus courantes de longueur 1-16 si quelqu'un veut savoir
ASCII uniquement
J'ai l'impression qu'il sera très difficile de battre la compression ...
Esolanging Fruit

Réponses:

3

Gelée , 149 octets

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

Il y a un modèle, par exemple, seulement 81 des 256 chaînes binaires de longueur 8 sont présentes si l'on coupe la séquence en huit, mais je n'ai (au moins encore) remarqué aucun moyen d'en utiliser pour réduire le nombre d'octets à partir de cette base directe. 250 compression convertie en liste binaire.

Essayez-le en ligne! (le pied de page formate la liste binaire en une chaîne pour une comparaison directe plus facile).

Jonathan Allan
la source
3

Python 2 , 269 259 256 247 245 243 octets

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

Essayez-le en ligne!

Dennis
la source
3

JavaScript (ES6), 263 253 252 octets

J'ai essayé d'utiliser le moins de données de charge utile possible. Malheureusement - mais sans surprise - cela nécessite beaucoup de code de décompression.

Panne:

  • données utiles: 75 octets, codés sous forme de chaîne Base64 de 100 caractères
  • Code: 163 153 152 octets

Voici une version formatée sans les données. Le code brut se trouve dans l'extrait de démonstration.

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

Comment?

Nous gardons une trace des sommes cumulées un [i] de chaque i- ème terme. Chaque fois que l'une de ces sommes atteint la borne inférieure -2 , nous savons que le terme suivant doit être un + . La même logique s'applique à la limite supérieure. Ceci est utile jusqu'à i = 264 et n'économise aucun octet supplémentaire au-delà de cela.

Cela nous laisse avec 599 termes qui ne peuvent être devinés. Nous les stockons sous la forme ⌈599 / 8⌉ = 75 octets, codés dans une chaîne Base64 de 100 caractères.

Démo

Afficher l'extrait de code

Arnauld
la source
3

Jelly , 110 109 107 octets

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

Cela prend trop de temps sur TIO, mais il se termine en moins de 3 secondes sur mon ordinateur de bureau.

Essayez-le en ligne!

Dennis
la source
3

Gelée , 135 133 130 129 105 104 octets

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

Sur la base des éléments précédents de la séquence, l'algorithme fait une supposition éclairée de ce que pourrait être l'élément suivant. Cela fonctionne pour tous les éléments sauf 99, dont les indices sont codés en dur afin que les éléments correspondants puissent être échangés.

Essayez-le en ligne!

Dennis
la source
2

MATL , 224 octets

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"

La sortie est de la forme 1 0 0 1 0 ..., où 1correspond à '-'et 0correspond à '+'.

Essayez-le en ligne!

Explication

La séquence a été codée en longueur. Les 720 pistes ont toutes des longueurs 1, 2, 3 ou 4, 3 ou 4 étant moins courantes. Ainsi, chaque 3 a été remplacé par 2, 0, 1 (une série de 2, puis une série de 0 de l'autre symbole, puis une série de 1 à nouveau) et, de même, chaque 4 a été remplacé par 2, 0, 2. Cette donne un tableau ternaire de longueur 862.

Ce tableau est converti en encodage base 94 et est la longue chaîne affichée dans le code ( '$Te...kG'). L'encodage en Base 94 utilise tous les 95 caractères ASCII imprimables à l'exception du guillemet simple (qui devrait être échappé).

Le code convertit cette chaîne de la base 94 en base 3 et utilise le résultat pour décoder en longueur les symboles [1 0 1 0 ... 0](tableau de longueur 862).

Luis Mendo
la source
2

Gelée , 95 octets

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

Un point milieu entre mes deux approches précédentes.

Le code tente de deviner 842 éléments de la séquence et code en dur les 318 autres. 19 des suppositions sont incorrectes et doivent être inversées via une liste d'indices codés en dur.

Essayez-le en ligne!

Comment ça fonctionne

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

Il s'agit d'une base bijective 250 littérale qui utilise la page de codes de Jelly pour les chiffres et code l'entier 380009100940380065412452185545474826295694594854898450166594167299196720639075810827320738450934©

BḤC©

BḤC1±1

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

Cette chaîne monadique prend un préfixe de la sortie souhaitée (avec un préfixé0 au début) et ajoute l'élément suivant de la sortie. La chaîne fonctionne comme suit:

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

Dennis
la source
Il semble que le codage arithmétique serait plus simple que de modifier manuellement certaines entrées; avez-vous essayé ou est-ce que Jelly ne convient pas?
lirtosiast
Il n'y a que 19 entrées qui doivent être modifiées, qui sont codées en 23 octets. Je pense qu'un décodeur arithmétique serait plus long que cela, au moins avec les données associées.
Dennis
1

Charbon de bois , 150 octets

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

Essayez-le en ligne!

Utilise la compression de cordes intégrée de Charcoal. Utilise .pour -et !pour +.

ASCII uniquement
la source
1

CJam, 153 octets

"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

Utilise 1pour -et 0pour +.

Contient non imprimable. Essayez-le en ligne!

C'est assez simple. Convertit une longue séquence de la base 256 en base 2.

Esolanging Fruit
la source
1

Python 3 , 236 232 octets

Merci à Mego pour avoir économisé 4 octets

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

Essayez-le en ligne!

Utilise l'encodage CP-437. Merci à Dennis d' avoir signalé une erreur.

ASCII uniquement
la source
437est un alias pour cp437, vous pouvez donc raser 4 octets en vous débarrassant des cpbits chaque fois qu'ils se produisent.
Mego
0

Python 2 , 364 250 octets

Merci à Jonathan Allan d' avoir enregistré 114 octets.

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

Essayez-le en ligne!

ASCII uniquement
la source
0

C # , 385 octets

Les données

  • ContributionAucune
  • Sortie String Le résultat prétendu.

Golfé

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

Non golfé

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

Code complet

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

Communiqués

  • v1.0 - 385 bytes- Solution initiale.

Remarques

  • Aucun
auhmaan
la source
0

05AB1E , 149 octets

•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 ennuyeux. Juste un nombre compressé. Utilise 1pour -et 0pour +.

Essayez-le en ligne!

Okx
la source
0

PHP, 276 octets

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

Essayez-le en ligne!

Jörg Hülsermann
la source
0

Rubis , 245 octets

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

Sortie 0 pour + et 1 pour -.

Essayez-le en ligne!

GB
la source
0

Perl, 164 octets

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

La solution évidente et ennuyeuse: il suffit de mettre tous les bits dans une chaîne binaire, 8 bits par octet. Utilise 0 pour - et 1 pour +. Je vais essayer de jouer au golf un peu plus.

Grimmy
la source
0

Rétine , 333 octets


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

Essayez-le en ligne!

ovs
la source