Всем привет!
В мире спортивного программирования существует одна разновидность необычных контестов — соревнование на самый короткий код. Я встречал такой официальный конкурс на сборах в Харькове и неофициальные на форумах ТопКодера или например в этой задаче.
Поскольку на Codeforces уже проводились Unknown Language Round, соревнование марафонского типа (как во время VK CUP Round 1, 2) и даже что-то похожее на промышленное программирование (конкурс с парсингом файлов в директории, который использовался при создании визарда для Тренировок), а также был популярен Russian AI Cup, думаю, что новое необычное соревнование будет интересно многим.
Давайте устроим соревнование на короткий код и посмотрим, кто сможет написать решение какой-нибудь длинной в реализации задачи лучше всех!
Кстати говоря, такое соревнование вполне себе имеет отношение к реальной жизни.
Сразу приведу пример — http://pastebin.com/hrSGFbPp Вы думаете, я взял этот кусок с сайта http://govnokod.ru/?
Ничего подобного — такое написал Google. Чтобы самим найти такой кусок кода на JavaScript, приведу пример для Google Chrome: откройте ваш любимый сайт, кликните в любом месте страницы правой кнопкой мыши, выберите "Просмотр кода элемента", в появившемся окне вкладку "Sources", дальше Ctrl+O и выберите файл с каким-нибудь непонятным названием. Там будет такой вот обфусцированный JavaScript.
Для чего это делается? Во-первых, чтобы скрыть логику работы — для проприетарных программ это важно. Во-вторых, для некомпилируемых языков программирования скорость работы зависит от длины кода, поэтому чем короче код — тем быстрее загружается страница.
Итак, подводя итог, писать обфусцированный и короткий код иногда не только интересно, но и полезно.
Давайте сделаем из этого соревнование?
Так руками для продакшна так никто не делает же. Пишется парсер с кучей логики на кручение-верчение кодом, который потом применяется на весь репозиторий :).
И это не всегда хорошо. В динамических языках, как JS, можно увидеть код, который не позволит вам просто так менять имена переменных или переструктуировать код под более короткий минифаером, один из экземпляров — Prototype.js.
Казалось бы, одна из самых тупых фичей JS, такая как трансформация функции в исходный код этой функции в ран-тайме используется Prototype.js, что не может не печалить, так как надеяться на названия аргументов функции, наличие каких-то специальных строк и тому-подобное напоминает быдло-кодинг.
Пример:
У вас есть функция типа:
Дельный минифаер это сожмет до:
Но тут сюрприз — в некоторых случаях кто-то может сделать
myPrettyFunction.toString()
и попытаться сделать какое-то решение только из исходного кода, который уже подвергся сильным изменениям.Ну я понимаю, что этот код писали не руками. Да и задачи олимпиадные на JavaScript никто вроде не сдает. А возможность написать такую крутилку-вертелку кода для C++ например — как раз интересный аспект соревнования.
Напиши хотя бы компилятор C++, готов поспорить — года не хватит :).
Ну все-таки написать хотя бы простейший обфускатор кода (например — поменять имена всех переменных и функций на однобуквенные) намного проще, чем компилятор.
Про создание своего компилятора почитай в этом моем посте http://mirror.codeforces.com/blog/entry/6910 — там уже находились такие энтузиасты и я даже сначала им поверил, а потом решил, что все это разводка:)
При наличии готового парсера — да, намного проще. Иначе — все упирается как раз в этот самый парсер.
Всегда можно испльзовать CLang++. Там пять строк на питоне/С++ дадут тебе готовое дерево разбора, можно делать любые рефакторинги, что угодно. Так сейчас почти все плагины для текстовых редакторов для автодополнения и навигации пишутся.
Ну, если понимаете, что в реале так не делают, зачем писать пол поста про пользу в реальной жизни, говнокоды и Гугл? Я как бы на это отвечал, против контестов на обфускацию ничего не имею.
Если контест на КодФорсес ждете, а его все нет — посмотрите на http://www.ioccc.org/.
И в роли задачи — Сокобан с Тимуса, чтобы интересней было.
Мне кажется, это слишком простая задача для такого серьёзного соревнования.
Эту задачу сдало 3 человека без всяких ограничений на размер кода.
Какая же она после этого простая?:)
Забавно, что этой задаче 6 лет, а по ней всего 3 AC.
Вот если бы преподаватели программирования обещали первокурснику, который получил AC с самым маленьким временем среди своих одногруппников (чтобы избежать списывания), зачет автоматом, то я уверен, что эту задачу сразу бы посдавали гораздо больше народу.
ИМХО, честно сдать какой-нибудь зачет куда проще, чем получить АС по сокобану
Мне вспомнилось название HugiCompo или как-то так
http://www.hugi.scene.org/compo/
Кажется это оно. Впервые я слышал о такой штуке лет 13 назад, ещё в фидо. Языком решения задач был вроде бы ассемблер x86-ой, задачи сами были в духе:
Ну и т.п. Размер программы измерялся непосредственно в байтах, поэтому требовалось хорошее представление об ассемблерных инструкциях и АПИ доса (например, использование INT 29 для печати символа экономило целый байт!)
Мне кажется возродить такую штуку действительно было бы интересно.
Однако ассемблер для x86-ых хотя и можно запускать в эмуляторе, по-моему тем не менее не будет слишком удобен.
Вместо этого можно:
Я не знаток местной проверяющей системы, но разве при подсчёте размера программы не игнорируются пробелы и переводы строк?
btw, кто короче? :D
Ошибочка, похоже, тут символы пробела и перевода строки тоже учитываются Оо
По идее, основная метрика для сложных в реализации задач — скорость написания кода и простота его отладки. Краткость в данном случае ИМХО уместна лишь в тех рамках, в которых она помогает по отношению к первому пункту.
А вообще, опять же ИМХО, оптимизация размера кода имеет смысл только при жестком ограничении на его размер. Кроме жабаскрипта из веб-страниц на ум приходят разве что микроконтроллеры и все, что им подобно.
Ну моя идея — сделать что-то типа Unknown Language Round, только когда язык известен и нужно как можно лучше им воспользоваться, чтобы сократить исходный код.
Формат существующих контестов, которые именно на решение задач, я менять не предлагаю:)
В качестве языка можно malbolge использовать, например =)
Насколько я понимаю, такие соревнования называются code golf. Мне было бы очень интересно в таком поучаствовать на CF.
Особенно большой потенциал для сжимающего коверкания кода у C без плюсов: http://iitbhu.ac.in/codefest/blog/?p=321 . В контесте по ссылке еще в некоторых задачах запрещали использовать в программе определенные символы или последовательности символов.
Интересно мнение одного человека по этому поводу. См. лучшие попытки. А я — не осилил бы такого соревнования, посему — хотел бы посмотреть, как это сделают другие)
PS
Он как-то писал, что задачи на сайте несложные и просто решать их — неинтересно, поэтому он решал на шорткод. Из той же оперы феерического шорткода — задача на 121 символ. И еще несложная геометрия на 131 символ. Зачетно выглядят первые места на С++ в задачах на длинную арифметику.
Для любителей
Минификация кода в продакшене не уместна относительно этого поста — другие подходы, другие цели. я бы выбросил это из текста.
А вот само по себе соревнование code golf считаю интересным и уместным, принял бы участие.
Такие соревнования есть на https://www.hackerrank.com/ . Правда задач там пока не много.
Вот еще зачетный шортик http://fabiensanglard.net/rayTracing_back_of_business_card/index.php
Я за, но появляется другая проблема: у одних языков может быть преимущество над другими. Поэтому придется разрешать только один язык, что вызовет недовольство среди пользователей других языков.
Обычно подобные соревнования жёстко привязаны к языку, чаще всего я слышу о perl golf'е, хотя не обязательно он самый популярный. Perl достаточно податлив в плане минимизации. :) ioccc достаточно популярное соревнование по C. А недовольствие — дело относительное... Язык можно менять в конце концов от соревнования к соревнованию, если полетит.