Привет, Хабр! Представляю вашему вниманию перевод статьи "【コードゴルフ】コードをDeflate圧縮してAtCoderに提出する【圧縮ゴルフ】".
Вы когда-нибудь слышали о Code Golf? Это что-то вроде игры, где все стараются написать определенный код максимально маленьким количеством символов.
Одно из решений (171-байтный код), засабмиченных в контест на AtCoder*, подвергается широкой критике, поэтому я решил разобраться, в чем же там проблема.
(Прим. переводчика: AtCoder — платформа, где проводятся различные соревнования среди разработчиков. Судя по домену .jp, платформа — японская, но пользователи там со всего мира. Например, на момент перевода этой статьи в топе сайта есть 3 пользователя из России.)
Как я понимаю, сжатие кода (=уменьшение его размера-веса) сокращает его символьно. Участники Code Golf, можно сказать, душу вкладывают в сокращение каждого символа, каждого байта. А так как цель такого соревнования — написать максимально короткий код, нет причин его не сжимать.
Сначала взгляните на следующий код.
Я с трудом могу это прочитать. Но по первой строчке я понимаю, что код написан на Ruby.
Это шебанг, и в качестве опции командной строки указано -Kn и -rzlib.
-Kn указывает, что написанный код нужно рассматривать в качестве двоичного, не содержащего символы код. Например, #coding: binary выполняет те же функции.
-rzlib — требование библиотеки zlib. Сокращение от require «zlib».
Следующая строка.
Zlib.inflate — это метод распаковки сжатого кода. Так как видно, что после символа ' еще есть строка, мы понимаем, что эта часть кода распаковывает сжатый код и применяет к нему eval.
Я подумал, что было бы неплохо создать шаблон по сжатию кода.
Для этого необходимо выполнить три шага: 1) написать код, 2) сжать код и 3) выдать конечный код. В свою очередь, чтобы уменьшить степень сжатия, нужно повторять шаги 1 и 2.
Сначала напишем код. (Ну, этот шаг особых проблем не сулит)
Длина этого кода составляет 216 байт.
Теперь попробуем сжать.
С использованием этого скрипта мне удалось уменьшить его до 194 байтов!
Код я сжал и хотел уже отправить его, но возникла одна проблема.
К сожалению, я не могу просто скопировать и вставить этот код и отправить его как есть. Код, сгенерированный сжатием, является двоичным. Однако экран отправки AtCoder — UTF-8. В большинстве случаев сжатый код содержит байтовые строки, которые недопустимы в UTF-8, поэтому, если вы скопируете и вставите его как есть, он будет искажен.
Поэтому я отправлю код в кодировке URI напрямую с помощью DevTools.
Откроем экран отправки и запустим DevTools. Страницу для отправки решения на контест держим открытой.
Когда все подготовили, как указано на скриншоте выше, нажимаем кнопку отправки нашего решения на сайте. В DevTools отобразиться отправленный нами запрос.
Выбираем запрос под названием “submit” и кликаем по нему правой кнопкой мыши, нажимаем Copy, затем Copy as fetch.
Открываем консоль и вставьте только что скопированный код.
Вставляем после sourceCode= наш код в кодировке URI (не показано на скриншоте). Для энкодинга в URI используем этот скрипт. (Сохраняем как deflate-uriencode.rb)
Преобразовываем agc047_e.rb в deflate-uriencode.rb.
Из второй строчки вывода копируем все, что находится после %23, и вставлем после вышеупомянутого sourceCode=.
Теперь можем отправлять наше решение.
Сократим код. Есть два способа сократить код после сжатия.
Попробую использовать оба метода. Сокращение исходного кода — это любимый способ участников Code Golf.
Как я могу увеличить степень сжатия? Теперь мы используем сжатие Deflate, которое представляет собой комбинацию сжатия длин серий и кодирования Хаффмана. Обратите внимание на этот код Хаффмана. Код Хаффмана отличается тем, что степень сжатия увеличивается по мере уменьшения ��нтропии до сжатия. Энтропия уменьшается по мере смещения вероятностей появления кода. Следовательно, если вероятность появления кодов смещена, степень сжатия будет увеличиваться по мере смещения.
Эффективный способ уменьшить вероятность появления кода — уменьшить тип символа. Для этого можно переименовать переменную.
В первом коде давайте переименуем переменные x и v в t и p. Затем, поскольку он помещается с именем функции puts или map, тип символа можно уменьшить.
Хм, он увеличился.
Уберем p и заменим его на s.
На этот раз он правильно уменьшается.
(Я не знаю, почему он увеличился, поэтому, пожалуйста, если есть люди знающие, расскажите).
Таким образом, через метод проб и ошибок, мы смогли сократить код.
Ссылка на оригинал данной статьи тут
Мы будем очень рады, если вы расскажете нам, понравилась ли вам данная статья, понятен ли перевод, была ли она вам полезна?
Вы когда-нибудь слышали о Code Golf? Это что-то вроде игры, где все стараются написать определенный код максимально маленьким количеством символов.
Одно из решений (171-байтный код), засабмиченных в контест на AtCoder*, подвергается широкой критике, поэтому я решил разобраться, в чем же там проблема.
(Прим. переводчика: AtCoder — платформа, где проводятся различные соревнования среди разработчиков. Судя по домену .jp, платформа — японская, но пользователи там со всего мира. Например, на момент перевода этой статьи в топе сайта есть 3 пользователя из России.)
Сжатие кода
Как я понимаю, сжатие кода (=уменьшение его размера-веса) сокращает его символьно. Участники Code Golf, можно сказать, душу вкладывают в сокращение каждого символа, каждого байта. А так как цель такого соревнования — написать максимально короткий код, нет причин его не сжимать.
Сначала взгляните на следующий код.
#!ruby -Knrzlib
eval Zlib.inflate'x�=�Q
� D��OS�c
]r� �����ݳ�By�
����O{4�.��i�aQ(`}cB���I2e�ߣ��IeT�јL>������)u,�p�S�W��H~.�,�:
z:Ӊ��g�O7ʲ��vQ�1h�^<����=&�\u7'Я с трудом могу это прочитать. Но по первой строчке я понимаю, что код написан на Ruby.
#!ruby -KnrzlibЭто шебанг, и в качестве опции командной строки указано -Kn и -rzlib.
-Kn указывает, что написанный код нужно рассматривать в качестве двоичного, не содержащего символы код. Например, #coding: binary выполняет те же функции.
-rzlib — требование библиотеки zlib. Сокращение от require «zlib».
eval Zlib.inflate'…Следующая строка.
Zlib.inflate — это метод распаковки сжатого кода. Так как видно, что после символа ' еще есть строка, мы понимаем, что эта часть кода распаковывает сжатый код и применяет к нему eval.
Попробую сам
Я подумал, что было бы неплохо создать шаблон по сжатию кода.
Для этого необходимо выполнить три шага: 1) написать код, 2) сжать код и 3) выдать конечный код. В свою очередь, чтобы уменьшить степень сжатия, нужно повторять шаги 1 и 2.
Пишем код
Сначала напишем код. (Ну, этот шаг особых проблем не сулит)
puts [6484,a=?+,0,1,3,?<,2,3,3]+[0,1].map{|x|[a,x,3,x]+(0..29).map{v=x+4;u=x*60+9+_1;[a,v,v,v,a,v,3,6,*[a,6,6,6]*(29-_1),?<,6,x,u,a,v,u,v]}}+(0..59).map{|t|[a,2,2,2]+(0...t).map{[a,8+t-_1,69+_1,5,?<,3,5,6,a,2,6,2]}}Длина этого кода составляет 216 байт.
Теперь попробуем сжать.
Сжимаем
С использованием этого скрипта мне удалось уменьшить его до 194 байтов!
$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
194 BСабмитим на AtCoder
Код я сжал и хотел уже отправить его, но возникла одна проблема.
К сожалению, я не могу просто скопировать и вставить этот код и отправить его как есть. Код, сгенерированный сжатием, является двоичным. Однако экран отправки AtCoder — UTF-8. В большинстве случаев сжатый код содержит байтовые строки, которые недопустимы в UTF-8, поэтому, если вы скопируете и вставите его как есть, он будет искажен.
Поэтому я отправлю код в кодировке URI напрямую с помощью DevTools.
Откроем экран отправки и запустим DevTools. Страницу для отправки решения на контест держим открытой.
Когда все подготовили, как указано на скриншоте выше, нажимаем кнопку отправки нашего решения на сайте. В DevTools отобразиться отправленный нами запрос.
Выбираем запрос под названием “submit” и кликаем по нему правой кнопкой мыши, нажимаем Copy, затем Copy as fetch.
Открываем консоль и вставьте только что скопированный код.
Вставляем после sourceCode= наш код в кодировке URI (не показано на скриншоте). Для энкодинга в URI используем этот скрипт. (Сохраняем как deflate-uriencode.rb)
$ ruby deflate-uriencode.rb agc047_e.rb
194 B
%23%21ruby+-Knrzlib%0Aeval+Zlib.inflate%27x%DA-%8DQ%0A%830%10D%AF%D2Ou%B7A%13%5D%14%2B%1E%24%04%C9%01%0AB%13%094%B9%7Bwc%99%8F%81%99%E1%CD%19%C3%E7ai%9CG%F4%DB%0E%D8%E3%80%06%F7%17j6%E3%C0r%E0%D4%DB%9F%DF%9C%B2%F5%988N%0E%9A%5E%29%BD%B4%B5%B8%B6%04%E3%1A%B7%D4Q%0F%0B%1C%C3%CA%BB%ABJ%DC+a%C7%09%89%5C%D7%E8%E5y%0C%AD%5C%10%D3b%DDD%BC%5C%29%95%3A%FD%A99%C8%9D%16%DDw*%DC%05%A73%04f+%C9%19N%822l%84%B2%DE%97%F2%03%93%919%B0%DE%97%F2%03%93%919%B0%27Преобразовываем agc047_e.rb в deflate-uriencode.rb.
Из второй строчки вывода копируем все, что находится после %23, и вставлем после вышеупомянутого sourceCode=.
Теперь можем отправлять наше решение.
Изменяем код (делаем его еще короче)
Сократим код. Есть два способа сократить код после сжатия.
- Сократить исходный код
- Увеличить степень сжатия
Попробую использовать оба метода. Сокращение исходного кода — это любимый способ участников Code Golf.
Увеличиваем степень сжатия
Как я могу увеличить степень сжатия? Теперь мы используем сжатие Deflate, которое представляет собой комбинацию сжатия длин серий и кодирования Хаффмана. Обратите внимание на этот код Хаффмана. Код Хаффмана отличается тем, что степень сжатия увеличивается по мере уменьшения ��нтропии до сжатия. Энтропия уменьшается по мере смещения вероятностей появления кода. Следовательно, если вероятность появления кодов смещена, степень сжатия будет увеличиваться по мере смещения.
Эффективный способ уменьшить вероятность появления кода — уменьшить тип символа. Для этого можно переименовать переменную.
В первом коде давайте переименуем переменные x и v в t и p. Затем, поскольку он помещается с именем функции puts или map, тип символа можно уменьшить.
puts [6484,a=?+,0,1,3,?<,2,3,3]+[0,1].map{|t|[a,t,3,t]+(0..29).map{p=t+4;u=t*60+9+_1;[a,p,p,p,a,p,3,6,*[a,6,6,6]*(29-_1),?<,6,t,u,a,p,u,p]}}+(0..59).map{|t|[a,2,2,2]+(0...t).map{[a,8+t-_1,69+_1,5,?<,3,5,6,a,2,6,2]}}$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
275 BХм, он увеличился.
Уберем p и заменим его на s.
puts [6484,a=?+,0,1,3,?<,2,3,3]+[0,1].map{|t|[a,t,3,t]+(0..29).map{s=t+4;u=t*60+9+_1;[a,s,s,s,a,s,3,6,*[a,6,6,6]*(29-_1),?<,6,t,u,a,s,u,s]}}+(0..59).map{|t|[a,2,2,2]+(0...t).map{[a,8+t-_1,69+_1,5,?<,3,5,6,a,2,6,2]}}$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
184 BНа этот раз он правильно уменьшается.
(Я не знаю, почему он увеличился, поэтому, пожалуйста, если есть люди знающие, расскажите).
Таким образом, через метод проб и ошибок, мы смогли сократить код.
Ссылка на оригинал данной статьи тут
Мы будем очень рады, если вы расскажете нам, понравилась ли вам данная статья, понятен ли перевод, была ли она вам полезна?
