Как стать автором
Обновить

Игра в Code Golf: сжатие кода и его сабмит на конкурс платформы AtCoder

Время на прочтение 4 мин
Количество просмотров 2.2K
Автор оригинала: Fish Maguro
Привет, Хабр! Представляю вашему вниманию перевод статьи "【コードゴルフ】コードをDeflate圧縮してAtCoderに提出する【圧縮ゴルフ】".

Вы когда-нибудь слышали о 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

На этот раз он правильно уменьшается.

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

Ссылка на оригинал данной статьи тут

Мы будем очень рады, если вы расскажете нам, понравилась ли вам данная статья, понятен ли перевод, была ли она вам полезна?
Теги:
Хабы:
+6
Комментарии 3
Комментарии Комментарии 3

Публикации

Истории

Работа

Ruby on Rails
17 вакансий
Программист Ruby
15 вакансий

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн