Русский
Русский
English
Статистика
Реклама

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

Привет, Хабр! Представляю вашему вниманию перевод статьи "DeflateAtCoder".

Вы когда-нибудь слышали о Code Golf? Это что-то вроде игры, где все стараются написать определенный код максимально маленьким количеством символов.

Одно из решений (171-байтный код), засабмиченных в контест на AtCoder*, подвергается широкой критике, поэтому я решил разобраться, в чем же там проблема.

(Прим. переводчика: AtCoder платформа, где проводятся различные соревнования среди разработчиков. Судя по домену .jp, платформа японская, но пользователи там со всего мира. Например, на момент перевода этой статьи в топе сайта есть 3 пользователя из России.)

Сжатие кода


Как я понимаю, сжатие кода (=уменьшение его размера-веса) сокращает его символьно. Участники Code Golf, можно сказать, душу вкладывают в сокращение каждого символа, каждого байта. А так как цель такого соревнования написать максимально короткий код, нет причин его не сжимать.

Сначала взгляните на следующий код.

#!ruby -Knrzlibeval Zlib.inflate'x=Q DOSc]r By              O{4.iaQ(`}cBI2eIeTL>)u,pSWH~.,:z:gO7vQ1h^<=&\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.rb194 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.rb194 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.rb275 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.rb184 B

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

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

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

Мы будем очень рады, если вы расскажете нам, понравилась ли вам данная статья, понятен ли перевод, была ли она вам полезна?
Источник: habr.com
К списку статей
Опубликовано: 08.09.2020 20:05:54
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Ruby

Занимательные задачки

Bash

Code golf

Devtools

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru