[Ruby, Занимательные задачки] Игра в Code Golf: сжатие кода и его сабмит на конкурс платформы AtCoder (перевод)
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Привет, Хабр! Представляю вашему вниманию перевод статьи "【コードゴルフ】コードを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
На этот раз он правильно уменьшается.
(Я не знаю, почему он увеличился, поэтому, пожалуйста, если есть люди знающие, расскажите).
Таким образом, через метод проб и ошибок, мы смогли сократить код.
Ссылка на оригинал данной статьи тут
Мы будем очень рады, если вы расскажете нам, понравилась ли вам данная статья, понятен ли перевод, была ли она вам полезна?
===========
Источник:
habr.com
===========
===========
Автор оригинала: Fish Maguro
===========Похожие новости:
- Результаты опроса разработчиков, использующих Ruby on Rails
- [Dart, Тестирование мобильных приложений, Flutter] Тестирование Flutter-приложений: инструменты, преимущества, проблемы
- [JavaScript, ReactJS, TypeScript] Пишем свой CLI генерации React компонент, а может быть не только компонент, а может не только React
- [Криптография, Занимательные задачки, Алгоритмы, Научно-популярное, Natural Language Processing] Ронго-ронго: нерасшифрованная письменность острова Пасхи
- [Занимательные задачки, Процессоры] Как заставить код выполняться за одинаковое время? Способы от Яндекс.Контеста
- [Системное администрирование, Занимательные задачки, Серверное администрирование] Любите ли вы IT-ребусы?
- [Системное администрирование, *nix, Оболочки, DevOps, Микросервисы] Blue-Green Deployment на минималках
- [Занимательные задачки, Математика] Теория игр и самоуправление
- [C#, Google Chrome, Тестирование веб-сервисов] Парсим любой сайт за считанные секунды. Как достать нужную информацию с сайта используя Selenium, XPath и Proxy Sever
- [Системное администрирование, Серверное администрирование, DevOps, Kubernetes] CRI-O как замена Docker в качестве исполняемой среды для Kubernetes: настройка на CentOS 8
Теги для поиска: #_ruby, #_zanimatelnye_zadachki (Занимательные задачки), #_ruby, #_bash, #_code_golf, #_devtools, #_ruby, #_zanimatelnye_zadachki (
Занимательные задачки
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 00:51
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Привет, Хабр! Представляю вашему вниманию перевод статьи "【コードゴルフ】コードを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 На этот раз он правильно уменьшается. (Я не знаю, почему он увеличился, поэтому, пожалуйста, если есть люди знающие, расскажите). Таким образом, через метод проб и ошибок, мы смогли сократить код. Ссылка на оригинал данной статьи тут Мы будем очень рады, если вы расскажете нам, понравилась ли вам данная статья, понятен ли перевод, была ли она вам полезна? =========== Источник: habr.com =========== =========== Автор оригинала: Fish Maguro ===========Похожие новости:
Занимательные задачки ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 00:51
Часовой пояс: UTC + 5