Codegolf - Кто Хочет Стать Победителем На Сложности Колмогорова?

Ваша миссия сегодня — изобрести текстовый компрессор.

Задача

Вы напишете две функции:

• упаковщик — это функция, которая принимает строку символов ASCII (от U+0000 до U+007F) и выводит строку Unicode (от U+0000 до U+10FFFF), содержащую наименьшее возможное количество символов.

• распаковщик — это функция, которая принимает закодированную строку Unicode и выводит в точности исходную строку ASCII.

Вход

Единственными разрешенными входными данными являются строка ASCII (для упаковщика) и упакованная строка Unicode (для распаковщика). Никакого пользовательского ввода, никакого подключения к Интернету, никакого использования файловой системы.

Ваши функции могут иметь доступ к этот список английских слов. Вы можете использовать этот список как локальный текстовый файл или скопировать его содержимое в исходный код в виде строки или массив строк.

Вы не можете жестко запрограммировать приведенные ниже фрагменты в своих функциях.

Выход

Единственным разрешенным выводом для обеих функций является строка.

Выходные данные распаковщика должны содержать точно те же символы, что и входные данные упаковщика.

Ваши входные и выходные данные могут использовать любую кодировку символов, поддерживающую весь Unicode (UTF-8/16/32, GB18030, ...), поскольку ваш результат будет зависеть только от количества символов Unicode в выходных данных. Пожалуйста, уточните, какую кодировку вы используете.

Чтобы подсчитать количество символов Юникода в выводе, вы можете использовать этот инструмент: http://mothereff.in/byte-counter

Подсчет очков

Ваша запись должна быть в состоянии упаковать и распаковать 10 следующих фрагментов текста (которые я взял на этом форуме).

Ваша оценка будет равна сумме размеров ваших 10 упакованных строк (в символах Юникода) + размер двух ваших функций (также в символах Юникода).

Не считайте размер словаря, если вы им пользуетесь.

Пожалуйста, укажите в своих записях «оценку» каждого фрагмента и его упакованную версию.

Побеждает наименьший результат.

Данные

Вот фрагменты, которые нужно закодировать для расчета вашего балла:

1: Тексты песен Рика Ролла (1870b): Мы не новички в программировании гольфа, вы знаете правила, и я тоже.

Four score and seven years ago our fathers brought forth on this continent a new nation, conceived in liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation, or any nation so conceived and so dedicated, can long endure. We are met on a great battlefield of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this. But, in a larger sense, we can not dedicate, we can not consecrate, we can not hallow this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us-that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion-that we here highly resolve that these dead shall not have died in vain-that this nation, under God, shall have a new birth of freedom-and that government of the people, by the people, for the people, shall not perish from the earth.

2: Игрок в гольф (412b): Игра в гольф ASCII-арт

There was an old lady who swallowed a fly.  
I don't know why she swallowed that fly,  
Perhaps she'll die.

There was an old lady who swallowed a spider,  
That wriggled and iggled and jiggled inside her.  
She swallowed the spider to catch the fly,  
I don't know why she swallowed that fly,  
Perhaps she'll die.

There was an old lady who swallowed a bird,  
How absurd to swallow a bird.  
She swallowed the bird to catch the spider,  
She swallowed the spider to catch the fly,  
I don't know why she swallowed that fly,  
Perhaps she'll die.

There was an old lady who swallowed a cat,  
Imagine that to swallow a cat.  
She swallowed the cat to catch the bird,  
She swallowed the bird to catch the spider,  
She swallowed the spider to catch the fly,  
I don't know why she swallowed that fly,  
Perhaps she'll die.

There was an old lady who swallowed a dog,  
What a hog to swallow a dog.  
She swallowed the dog to catch the cat,  
She swallowed the cat to catch the bird,  
She swallowed the bird to catch the spider,  
She swallowed the spider to catch the fly,  
I don't know why she swallowed that fly,  
Perhaps she'll die.

There was an old lady who swallowed a horse,  
She died of course.

3: числовой ромб (233b): Распечатайте этот бриллиант

May the road rise up to meet you
May the wind be always at your back
May the sun shine warm upon your face
The rains fall soft upon your fields
And until we meet again
May God hold you in the hollow of His hand

4: алфавит четыре раза (107б): Распечатайте алфавит четыре раза.

_   _      _ _                             _     _ _
| | | | ___| | | ___    __      _____  _ __| | __| | |
| |_| |/ _ \ | |/ _ \   \ \ /\ / / _ \| '__| |/ _` | |
|  _  |  __/ | | (_) |   \ V  V / (_) | |  | | (_| |_|
|_| |_|\___|_|_|\___( )   \_/\_/ \___/|_|  |_|\__,_(_)

|/

5: Тексты песен Old McDonald's (203b): Старая функция Макдональда

1, 2, 3 o'clock, 4 o'clock rock,
5, 6, 7 o'clock, 8 o'clock rock,
9, 10, 11 o'clock, 12 o'clock rock,
We're gonna rock around the clock tonight.

6: Текст песни «Рок круглосуточно» (144b): Рок круглосуточно

Old MacDonald had a farm, E-I-E-I-O,
And on that farm he had a cow, E-I-E-I-O,
With a moo moo here and a moo moo there,
Here a moo, there a moo, everywhere a moo moo,
Old MacDonald had a farm, E-I-E-I-O!

7: Привет, мир (296b): Скажите «Привет» миру в ASCII-изображении

abcdefghijklmnopqrstuvwxyz
qwertyuiopasdfghjklzxcvbnm
pyfgcrlaoeuidhtnsqjkxbmwvz
zyxwvutsrqponmlkjihgfedcba

8: Ирландское благословение (210b): Старое ирландское благословение

1

121

12321

1234321

123454321

12345654321

1234567654321

123456787654321
12345678987654321

123456787654321

1234567654321

12345654321

123454321

1234321

12321

121

1

9: Был текст песни старушки (1208b): Жила-была старушка

'\                   .  .                        |>18>>

\              .         ' .                   |

O>>         .                 'o                |

\       .                                      |

/\    .                                        |

/ /  .'                                         |

jgs^^^^^^^`^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

10: Геттисбергский адрес (1452b): Насколько случайен Геттисбергский адрес

We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guy
I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

We've known each other for so long
Your heart's been aching but
You're too shy to say it
Inside we both know what's been going on
We know the game and we're gonna play it
And if you ask me how I'm feeling
Don't tell me you're too blind to see

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

(Ooh, give you up)
(Ooh, give you up)
(Ooh)
Never gonna give, never gonna give
(Give you up)
(Ooh)
Never gonna give, never gonna give
(Give you up)

We've know each other for so long
Your heart's been aching but
You're too shy to say it
Inside we both know what's been going on
We know the game and we're gonna play it

I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Всего (без сжатия): 6135 символов/байт.

Веселиться!

#код-гольф #колмогоров-сложность See More

Хаскелл — 5322 балла

Байты кода:

 
 
 
 
 
 
 
 
 
 
 ValueError 
 
 
 
 
 
 
 
 
 
 

Оригинальный размер: 0xFFFF 1

Закодированный размер: 19 860

Счет : 6135

Сжатие количества символов: 281

Код

Помимо оптимизации, это сохраняет значения между from zlib import *;v=256 def e(b): x=0 for c in compress(b,9):x=(x*v)+ord(c) b=bin(x)[2:] return "".join(unichr(int("1"+b[a:a+19],2))for a in range(0,len(b),19)) def d(s): y=int("".join(bin(ord(a))[3:]for a in s),2);x="" while y:y,d=(y/v,chr(y%v));x=d+x return decompress(x) and 607 out/1.bin 128 out/2.bin 101 out/3.bin 143 out/4.bin 177 out/5.bin 145 out/6.bin 186 out/7.bin 222 out/8.bin 389 out/9.bin 1103 out/10.bin 3201 total в символах Юникода в качестве их основных факторов.

Он не уменьшает количество байтов закодированного вывода, а только уменьшает количество символов Юникода. Например, тест №4 содержит if __name__ == '__main__': import os total = 0 for i in range(1,10+1): out = p(open('data/%d.txt'%i,'rb').read()) total += len(out) open('out/%d.bin'%i,'w',encoding='utf8').write(out) print(total) for i in range(1,10+1): out = u(open('out/%d.bin'%i,'r',encoding='utf8').read()) open('data2/%d.txt'%i,'wb').write(out) characters and the encoded output, x<U+AC0DC><U+BB701><U+D0200><U+D00B0><U+AD2F4><U+EEFC5>???<U+F4F34>멍<U+3C63A><U+2F62C><U+BA5B6><U+4E70A><U+F7D88><U+FF138><U+40CAE> <U+CB43E><U+C30F5><U+6FFEF>???<U+698BE><U+9D73A><U+95199><U+BD941><U+10B55E><U+88889><U+75A1F><U+4C4BB><U+5C67A><U+1089A3><U+C75A7> <U+38AC1><U+4B6BB><U+592F0>ᚋ<U+F2C9B> . Однако их соответствующие размеры less and import zlib as Z def p(s): z=int.from_bytes(Z.compress(s),'big');o='' while z: z,d=divmod(z,1<<20) if d>0xd000:d+=1<<16 o+=chr(d) return o[::-1] def u(s): i=0 for c in s: d=ord(c) if d>0xe000:d-=1<<16 i=(i<<20)+d return Z.decompress(i.to_bytes(i.bit_length()//8+1,'big')) байты.

Как это работает

• Кодирование

  1. Каждый символ преобразуется в его числовой эквивалент, давайте назовем это число 쏏э?? .
  2. <U+4E1C5><U+8F265><U+CD9F4><U+69D5A><U+F66DD><U+DBF87><U+1E5CF><U+A75ED> <U+DFC79><U+F42B8><U+F7CBC><U+BA79E><U+BA77F>쏏э??<U+A356B><U+D9EBC><U+63ED8> <U+B76D1><U+5C3CE><U+6CF8F><U+96CC3><U+BF2F5><U+D3934><U+74DDC><U+F8EAD> <U+7E316><U+DEFDB><U+D0AF5><U+E7C77><U+EDD7A><U+73E5C><U+786FD><U+DB766> <U+BD5A7><U+467CD><U+97263><U+C5840> is then converted into a list of its prime factors, less .
     • Удобно, что числа от 0 до 127 имеют 32 общих простых делителя, не считая U+FFFFF . This mean they, the factors, can be stored as indexes on as little as 5 bits.
     • U+10FFFF is a special case and is represented by an empty list.
  3. С U+0000 the encoding can now start.
     1. Каждое число #include <cstdio> #include <iostream> #include <locale> #include <string> using namespace std; long b, n, i, l; // Compress void c() { string d; char x; // Read from STDIN until EOF while((x = cin.get()) != EOF) d += x; // Calculate the number of bits used from the last unicode character // (maximum 19) and store it into the first 5 bits b = (d.size() * 7) % 20; n = 5; // Set the output locale to allow unicode wcout.imbue(locale()); // For each character in the input... for (char y : d) { // Add its bit representation (7 bits) to the right of the buffer // by shifting the buffer left and ORing with the character code b = (b << 7) | (y & 127); // Add 7 to the bit counter n += 7; // If enough data is present (20 bits per output character), // calculate the output character by shifting the buffer right, // so that the last 20 bits are the left 20 bits of the buffer. // Also decrement the bit counter by 20, as 20 bits are removed. if (n >= 20) wcout.put((b >> (n -= 20)) & 0xFFFFF); } // If there are still bits in the buffer, write them to the front of // another unicode character if (n) wcout.put((b << (20 - n)) & 0xFFFFF); } // Decompress void d() { wstring d; wchar_t w; // Set STDIN to UNICODE wcin.imbue(locale()); // Read wide characters from STDIN (std::wcin) until EOF while ((w = wcin.get()) != EOF) d += w; // `l' represents the number of bits used in the last unicode character. // It will be set later l = -1; // For each input character... for (wchar_t y : d) { // Add it to the buffer and add 20 to the bit counter b = (b << 20) | y; n += 20; // If the number of bits in the last unicode character has not been // set yet, read the first 5 buffer bits into `l'. This is // necessary because the last character may contain more than 7 // (one entire uncompressed character) unused bits which may // otherwise be interpreted as garbage. if (l < 0) { l = (b >> 15) & 31; n -= 5; } // As long as there is data to turn into output characters // (at least 7 bits in the buffer and either not the last // unicode character or before the unused bits) while (n >= 7 && ((i < d.size() - 1) || (n > (20 - l))) cout.put((b >> (n -= 7)) & 127); // Output the left 7 bits in the buffer as an ASCII character ++i; // Increment the character index, so that we know when we reach the last input character } } int main(int t, char**a) { // Set the default locale to en_US.utf8 (with unicode) locale::global(locale("en_US.utf8")); // Decide whether to compress or decompress. // This is just fancy pointer stuff for a[1][0] < 'd' ? c() : d() (**(++a) < 'd') ? c() : d(); } is converted into its index in the list of 32 unique factors (In the above code this list is identified as stdout ).
     2. (Имейте в виду, что на этом этапе мы имеем дело со списком индексов простых факторов). Чтобы перейти к следующему шагу, stdin needs to be flattened. To preserve the integrity of the data, each list is converted into another list of two parts
        1. Первый элемент хранит свою длину и, если он состоит из одного и того же фактора.
           • В каждом списке содержится не более 6 простых множителей, эта информация хранится в трех крайних правых битах. Пятый бит используется как флаг, указывающий, состоит ли список из одного фактора.
        2. Остальные элементы — это сами индексы или один индекс, если в списке меньше двух разных факторов.
     3. Затем эти списки объединяются в один плоский список. d .
  4. Элементы D can then be packed into unicode characters using bit shifting.

• Декодирование

  • Выполните шаги кодирования в обратном порядке.
  • Если вам интересно, как ./compress d fits into this, I would like to remind you that ./compress c .

Тесты

Использование этого интерфейса для тестирования было бы болезненным, поэтому я использовал эту функцию, чтобы предоставить результаты ниже.

Образец

Вывод функции кодирования ((b << 20) - n) & 0xFFFFF for test #4 is this
b<<20-n&0xFFFFF
или если вы любитель тарабарщины, это
g++ -std=c++11

Дополнительные примечания

• С использованием http://mothereff.in/byte-counter, списки каталогов и clang++ the size of the tests are all consistent but still differs from the indicated size in the question.
• Тест №10 содержит пару EM DASH ( stdin ) that I replaced with wc -c поскольку они находятся за пределами wc -c - wc -m диапазон.
• Дальнейшее сжатие может быть достигнуто с использованием оставшегося четвертого бита при выравнивании, например: #include <cstdio> #include <iostream> #include <locale> #include <string> #define L locale using namespace std;long b,n,i,l;void c(){string d;char x;while((x=cin.get())!=EOF)d+=x;b=(d.size()*7)%20;n=5;wcout.imbue(L());for(char y:d){b=b<<7|y&127;n+=7;if(n>=20)wcout.put(b>>(n-=20)&0xFFFFF);}if(n)wcout.put(b<<20-n&0xFFFFF);}void d(){wstring d;wchar_t w;wcin.imbue(L());while((w=wcin.get())!=EOF)d+=w;l=-1;for(wchar_t y:d){b=b<<20|y;n+=20;if(l<0)l=b>>15&31,n-=5;while(n>=7&(i<d.size()-1|n>20-l))cout.put(b>>(n-=7)&127);++i;}}int main(int t,char**a){L::global(L("en_US.utf8"));**++a<'d'?c():d();} base case, 11 повторить все, 10 repeat except last, 01 повторить, кроме последних двух.
• Тестовые файлы и код доступны здесь. https://github.com/gxtaillon/codegolf/tree/master/Kolmogorov

С++ (С++11), 2741 балл

В этом ответе в качестве кодировки сжатого текста используется UTF-32.

Подсчет символов и подсчет очков

Код: 593 символа (конечная новая строка удаляется)

Сжатые тексты (символы Юникода): 654 + 145 + 82 + 38 + 51 + 104 + 73 + 423 + 506 = 2148 (считается с 7f for the number of unicode characters rather than bytes, the byte counts are, as as with @gxtaillon's answer, higher than the originals, 8413 bytes in total, as counted with 0 ).

Коэффициент сжатия (ASCII в Unicode): 35,01% (используя 6135 байт из вопроса (так же, как - ))

Остерегаться:

Многие оболочки не могут обрабатывать символы Юникода, которые создает эта программа. Таким образом, распаковка может привести к тому, что текст будет обрезан где-то, когда оболочка не сможет обработать символ, поскольку ввод осуществляется через — from the shell.

Компиляция

Он должен скомпилироваться с edTest and ????????????豱э???????????숼э?????????????????????????????????????????踾э??????????????????????????????????????숼э????????衣???쑡???????????????????????????衂???????????????????????????숼э???????????쑁???豁?????????쑢???ꡃ????????????貱э?????????????????裱э??????????? , но будет отображаться несколько предупреждений о приоритете операторов, например, выражение типа "\99429\582753\135266\70785\35953\855074\247652\1082563\68738\49724\164898\68157\99429\67973\1082404\587873\73795\298017\330818\198705\69861\1082435\595009\607426\36414\69873\855074\265249\346275\67779\68738\77985\1082513\821353\132131\101410\247652\1082562\49724\164898\67649\594977\34915\67746\50273\135265\103997\563265\103457\1086021\99399\584802\70753\73889\34882\582722\411459\67779\68740\1084516\1082563\1091681\103491\313282\49724\164897\68705\135741\69858\50241\607426\35905\608421\1082435\69858\50274\71777\43075\298018\280517\1082404\67971\36017\955425\67665\919600\100452\132129\214883\35057\856097\101474\70753\135737" will not be treated as g , как и следовало ожидать, а скорее как λ> edTest "1" 1871,1396,1871,True λ> edTest "2" 412,233,412,True λ> edTest "3" 234,163,234,True λ> edTest "4" 108,92,108,True λ> edTest "5" 204,153,204,True λ> edTest "6" 145,115,145,True λ> edTest "7" 297,197,297,True λ> edTest "8" 211,164,211,True λ> edTest "9" 1209,979,1209,True λ> edTest "10" 1453,1144,1453,True .

Использование

• Скомпилируйте программу в исполняемый файл, например. edTest f = do t <- readFile f let txt = T.pack t enc = g txt dec = h enc tst = txt == dec putStrLn $ (show $ T.length txt) ++ "," ++ (show $ T.length enc) ++ "," ++ (show $ T.length dec)++","++(show tst) putStrLn $ if not tst then T.unpack txt ++ "\n---NEXT---\n" ++ T.unpack dec else "" .
• Запустите программу как product [] == 1 to compress or 1 для декомпрессии. (Осторожно, если оставить эту опцию, то СЕГФАУЛТ (проверка ошибок настолько дорога...) и другие варианты (например, использование fs instead of fs ) может дать неожиданные результаты
• Ввод считывается из ps and output written to a

Как это работает

Негольфед

Объяснение

Поскольку все символы Юникода из ps to 1 разрешены, мы можем использовать 20 бит на символ Юникода: 1 uses 20 bits and is still included in the allowed range. Thus, we just try to cram all the individual ASCII char bits into the unicode characters to store multiple ASCII characters in one unicode character. However, we also need to store the number of bits used in the last unicode character, because unused garbage bits may otherwise be interpreted as proper compressed ASCII characters. As the maximum number of used bits in the last unicode character is 20, we will need 5 bits for that, which are placed in the beginning of the compressed data.

Пример вывода

Это результат примера № 4 (как указано в ps ):

( n give import Data.Bits import Data.List import Data.Numbers.Primes import qualified Data.Text as T a=nub$concat$map(primeFactors)[0..127] d(a:r)c=let s=shift c 5in if s<=0x10ffffthen d r(s+a)else c:d r a d[]c=[c] f(a:r)=let o=a.&.0x1fin(if o/=a then f((shiftR a 5):r)else f r)++[o] f[]=[] g=T.pack.map(toEnum).(\(a:r)->d r a).concatMap j.map(map(\x->head$elemIndices x a)).map(primeFactors.fromEnum).T.unpack h=T.pack.map(toEnum.product.map((!!)a)).i.f.reverse.map(fromEnum).T.unpack i(a:r)=let z=a`clearBit`4;x=if a`testBit`4then(take z$repeat$head r,tail r)else splitAt z r in[fst x]++i(snd x) i[]=[] j x@(a:_)=let l=length x in if(take l(repeat a))==x then[l`setBit`4,a]else[l]++x j[]=[0] в виде кодов символов, но возможно я ошибся)

Python 3, 289+818=1107 баллов

Только слегка играл в гольф.

Общий размер кода составляет 289 байт, и данные 6135 байт кодируются в 818 символов Юникода. Общее количество выходных байтов составляет 3201 байт, что значительно меньше, чем исходные входные данные.

Кодирует с использованием zlib, а затем с использованием кодировки Unicode. Некоторая дополнительная логика была необходима, чтобы избежать суррогатов (которые Python действительно ненавидит).

Пример вывода из #4, как видно 108 (37 Unicode chars):

Программа-драйвер для тестирования:

Количество выходных байтов:

Питон 2 — 1141 балл

Размер кода ~25% bytes and it encodes the 686+ 4636 байты в = 1396+233+163+92+153+115+197+164+979+1144 unicode characters.

Как это работает:

Чтобы закодировать:

1. Сжать строку, которую нужно закодировать.
2. Интерпретируйте сжатую строку как число по основанию 256.
3. Преобразуйте число в двоичное.
4. Разделите двоичный файл на группы 4636 bits, add a = 1871+415+234+108+204+145+297+211+1209+1453 бит в начало каждого из них, а затем преобразовать в символы Юникода.

Декодирование происходит в обратном порядке.

Обратите внимание, что некоторые версии Python могут обрабатывать только символы Юникода до 6147 , and thus this code will raise a 686 .