Сжать максимальное расхождение-2 последовательности

18

Выведите эту двоичную последовательность длиной 1160:

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

Последовательность

Эта конечная последовательность тесно структурирована таким образом, что, я надеюсь, предоставляет уникальные методы сжатия. Это происходит из-за проблемы несоответствия Эрда, которая была показана в предыдущем испытании .

Рассматривая термины как +1 и -1, это последовательность максимальной длины несоответствия 2, что означает, что:

Для каждого положительного размера шага d, если вы возьмете каждый dдесятый член (начиная с dчетвертого), текущая сумма полученной последовательности останется между -2 и 2 включительно.

Если вы думаете, что каждый из них +означает шаг вправо и -шаг влево, это означает, что обход каждой dй инструкции никогда не проходит более 2 шагов от начальной позиции.

Например, для d=3, взяв каждый 3-й член, вы получите последовательность +-++--+--+-..., чьи промежуточные суммы [1,0,1,2,1,0,1,0,-1,0,1,...]никогда не достигают -3 или 3.

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

Эта последовательность была найдена в 2014 году с помощью компьютерного поиска. См. Этот документ , где последовательность воспроизведена в Приложении B. Поиск доказывает, что 1160 - это максимальная длина последовательности с расхождением-2, хотя существует более одной последовательности этой длины. Проблема расхождения Эрда, доказанная в 2015 году , говорит, что любая такая последовательность должна иметь конечную длину для любого максимального расхождения cвместо 2.

Время требования

Ваш код должен завершиться в течение 5 секунд . Это для ограничения грубой силы.

Выходной формат

Вы можете использовать любые два фиксированные отдельные символы или значения +и -в любом список, как и нитевидный формате. Формат должен быть таким, чтобы 1160 битовых значений можно было непосредственно считывать, например, не кодируя их как число через его двоичное представление или строку через символьные значения. Для вывода строки допускается завершающий перевод строки.

Leaderboard

Показать фрагмент кода

code-golf kolmogorov-complexity sequence combinatorics XNOR
источник
Наиболее распространенные подстроки длиной 1-16, если кто-то хочет знать
только ASCII
Я чувствую, что будет очень трудно победить компрессию ...
Esolanging Fruit

Ответы:

3

Желе , 149 байт

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

Существует некоторый шаблон, например, присутствует только 81 из 256 двоичных строк длиной 256, если кто-то разбивает последовательность на восемь, но я (по крайней мере, пока) не заметил какого-либо способа использовать любой из них для уменьшения количества байтов от этой прямой базы Сжатие 250 преобразуется в двоичный список.

Попробуйте онлайн! (нижний колонтитул форматирует двоичный список в строку для более простого прямого сравнения).

Джонатан Аллан
источник
3

Python 2 , 269 259 256 247 245 243 байта

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

Попробуйте онлайн!

Деннис
источник
3

JavaScript (ES6), 263 253 252 байта

Я старался использовать как можно меньше полезных данных. К сожалению - но не удивительно - для этого требуется довольно много декомпрессионного кода.

Сломать:

  • данные полезной нагрузки: 75 байтов, закодированные в виде 100-символьной строки Base64
  • код: 163 153 152 байта

Ниже приведена отформатированная версия без данных. Необработанный код находится в демонстрационном фрагменте.

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

Как?

Мы отслеживаем текущие суммы a [i] каждого i-го слагаемого. Каждый раз, когда одна из этих сумм достигает нижней границы -2 , мы знаем, что следующий член должен быть + . Та же логика применима к верхней границе. Это полезно до i = 264 и не сохраняет никаких дополнительных байтов.

Это оставляет нам 599 терминов, которые невозможно угадать. Мы храним их как ⌈599 / 8⌉ = 75 байт, закодированные в 100-символьную строку Base64.

демонстрация

Показать фрагмент кода

Arnauld
источник
3

Желе , 110 109 107 байт

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

На TIO это занимает слишком много времени, но на моем настольном компьютере это занимает менее 3 секунд.

Попробуйте онлайн!

Деннис
источник
3

Желе , 135 133 130 129 105 104 байта

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

Основываясь на предыдущих элементах последовательности, алгоритм делает обоснованное предположение, каким может быть следующий элемент. Это работает для всех элементов, кроме 99, индексы которых жестко закодированы, поэтому соответствующие элементы можно поменять местами.

Попробуйте онлайн!

Деннис
источник
2

MATL , 224 байта

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"

Выход имеет форму 1 0 0 1 0 ..., где 1соответствует '-'и 0соответствует '+'.

Попробуйте онлайн!

объяснение

Последовательность была закодирована по длине прогона. Все 720 трасс имеют длины 1, 2, 3 или 4, причем 3 или 4 менее распространены. Таким образом, каждая 3 была заменена на 2, 0, 1 (серия 2, затем серия 0 другого символа, затем серия 1 снова), и аналогично каждая 4 была заменена на 2, 0, 2. Это дает троичный массив длиной 862.

Этот массив преобразуется в кодировку base-94 и представляет собой длинную строку, показанную в коде ( '$Te...kG'). В кодировке Base 94 используются все 95 печатаемых символов ASCII, за исключением одинарных кавычек (которые должны быть экранированы).

Код преобразует эту строку из базы 94 в базу 3 и использует результат для декодирования символов по длине серии [1 0 1 0 ... 0](массив длиной 862).

Луис Мендо
источник
2

Желе , 95 байт

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

Средняя точка между моими двумя предыдущими подходами.

Код пытается угадать 842 элемента последовательности и жестко кодирует оставшиеся 318 элементов. 19 из догадок неверны и должны быть возвращены через список жестко закодированных индексов.

Попробуйте онлайн!

Как это устроено

“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Ḋ

Деннис
источник
Похоже, арифметическое кодирование будет проще, чем ручное изменение некоторых записей; Вы пробовали это или Jelly не подходит для этого?
lirtosiast
Необходимо изменить только 19 записей, которые закодированы в 23 байта. Я думаю, что арифметический декодер будет длиннее, по крайней мере, с соответствующими данными.
Деннис
1

Древесный уголь , 150 байт

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

Попробуйте онлайн!

Использует встроенную компрессию струн Charcoal. Использует .для -и !для +.

ASCII-только
источник
1

CJam, 153 байта

"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

Использует 1для -и 0для+ .

Содержит непечатные. Попробуйте онлайн!

Это довольно просто. Преобразует длинную последовательность из базы 256 в базу 2.

Esolanging Fruit
источник
1

Питон 3 , 236 232 байта

Спасибо Mego за сохранение 4 байта

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

Попробуйте онлайн!

Использует кодировку CP-437. Спасибо Деннису за указание на ошибку.

ASCII-только
источник
437это псевдоним для cp437, так что вы можете сбрить 4 байта, удаляя cpбиты оба раза, когда они происходят.
Мего
0

C # , 385 байт

Данные

  • вход нет
  • Выходные данные String Предполагаемый результат.

Golfed

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

Полный код

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

релизы

  • v1.0 - 385 bytes- Исходное решение.

Примечания

  • Никто
auhmaan
источник
0

05AB1E , 149 байтов

•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

Супер скучно Просто сжатый номер. Использует 1для -и 0для +.

Попробуйте онлайн!

Okx
источник
0

PHP, 276 байт

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

Попробуйте онлайн!

Йорг Хюльсерманн
источник
0

Рубин , 245 байт

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

Выведите 0 для + и 1 для -.

Попробуйте онлайн!

гигабайт
источник
0

Perl, 164 байта

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

Очевидное, скучное решение: просто поместите все биты в двоичную строку, 8 бит на байт. Использует 0 для - и 1 для +. Я попробую сыграть в гольф еще.

Grimmy
источник
0

Сетчатка , 333 байта


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

Попробуйте онлайн!

овс
источник