Блог пользователя caustique

Автор caustique, 11 лет назад, По-русски

Всем привет!

В мире спортивного программирования существует одна разновидность необычных контестов — соревнование на самый короткий код. Я встречал такой официальный конкурс на сборах в Харькове и неофициальные на форумах ТопКодера или например в этой задаче.

Поскольку на 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.

Для чего это делается? Во-первых, чтобы скрыть логику работы — для проприетарных программ это важно. Во-вторых, для некомпилируемых языков программирования скорость работы зависит от длины кода, поэтому чем короче код — тем быстрее загружается страница.

Итак, подводя итог, писать обфусцированный и короткий код иногда не только интересно, но и полезно.

Давайте сделаем из этого соревнование?

  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

Так руками для продакшна так никто не делает же. Пишется парсер с кучей логики на кручение-верчение кодом, который потом применяется на весь репозиторий :).

И это не всегда хорошо. В динамических языках, как JS, можно увидеть код, который не позволит вам просто так менять имена переменных или переструктуировать код под более короткий минифаером, один из экземпляров — Prototype.js.

Казалось бы, одна из самых тупых фичей JS, такая как трансформация функции в исходный код этой функции в ран-тайме используется Prototype.js, что не может не печалить, так как надеяться на названия аргументов функции, наличие каких-то специальных строк и тому-подобное напоминает быдло-кодинг.

Пример:

У вас есть функция типа:

function myPrettyFunction (specialArg, awesomeObject) {
    return specialArg;
}

Дельный минифаер это сожмет до:

function f(a){return a}

Но тут сюрприз — в некоторых случаях кто-то может сделать myPrettyFunction.toString() и попытаться сделать какое-то решение только из исходного кода, который уже подвергся сильным изменениям.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Ну я понимаю, что этот код писали не руками. Да и задачи олимпиадные на JavaScript никто вроде не сдает. А возможность написать такую крутилку-вертелку кода для C++ например — как раз интересный аспект соревнования.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -21 Проголосовать: не нравится

      Напиши хотя бы компилятор C++, готов поспорить — года не хватит :).

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Ну все-таки написать хотя бы простейший обфускатор кода (например — поменять имена всех переменных и функций на однобуквенные) намного проще, чем компилятор.

        Про создание своего компилятора почитай в этом моем посте http://mirror.codeforces.com/blog/entry/6910 — там уже находились такие энтузиасты и я даже сначала им поверил, а потом решил, что все это разводка:)

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          При наличии готового парсера — да, намного проще. Иначе — все упирается как раз в этот самый парсер.

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится

            Всегда можно испльзовать CLang++. Там пять строк на питоне/С++ дадут тебе готовое дерево разбора, можно делать любые рефакторинги, что угодно. Так сейчас почти все плагины для текстовых редакторов для автодополнения и навигации пишутся.

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

      Ну, если понимаете, что в реале так не делают, зачем писать пол поста про пользу в реальной жизни, говнокоды и Гугл? Я как бы на это отвечал, против контестов на обфускацию ничего не имею.

      Если контест на КодФорсес ждете, а его все нет — посмотрите на http://www.ioccc.org/.

»
11 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

И в роли задачи — Сокобан с Тимуса, чтобы интересней было.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Мне кажется, это слишком простая задача для такого серьёзного соревнования.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -40 Проголосовать: не нравится

      Эту задачу сдало 3 человека без всяких ограничений на размер кода.

      Какая же она после этого простая?:)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -28 Проголосовать: не нравится

    Забавно, что этой задаче 6 лет, а по ней всего 3 AC.

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +55 Проголосовать: не нравится

      ИМХО, честно сдать какой-нибудь зачет куда проще, чем получить АС по сокобану

»
11 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Мне вспомнилось название HugiCompo или как-то так

http://www.hugi.scene.org/compo/

Кажется это оно. Впервые я слышал о такой штуке лет 13 назад, ещё в фидо. Языком решения задач был вроде бы ассемблер x86-ой, задачи сами были в духе:

  • распечатать содержимое всех восьми регистров в заданном формате;
  • распечатать содержимое каталога.

Ну и т.п. Размер программы измерялся непосредственно в байтах, поэтому требовалось хорошее представление об ассемблерных инструкциях и АПИ доса (например, использование INT 29 для печати символа экономило целый байт!)

Мне кажется возродить такую штуку действительно было бы интересно.

Однако ассемблер для x86-ых хотя и можно запускать в эмуляторе, по-моему тем не менее не будет слишком удобен.

Вместо этого можно:

  • либо написать собственный какой-нить полуэзотерический язык оперирующий скажем на стеке и имеющий все команды состоящие из 1 символа;
  • либо выбрать один из уже имеющихся;
  • либо взять например байт-код JVM который кстати очень близко подходит к указанным требованиям.
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я не знаток местной проверяющей системы, но разве при подсчёте размера программы не игнорируются пробелы и переводы строк?

btw, кто короче? :D

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Ошибочка, похоже, тут символы пробела и перевода строки тоже учитываются Оо

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

По идее, основная метрика для сложных в реализации задач — скорость написания кода и простота его отладки. Краткость в данном случае ИМХО уместна лишь в тех рамках, в которых она помогает по отношению к первому пункту.

А вообще, опять же ИМХО, оптимизация размера кода имеет смысл только при жестком ограничении на его размер. Кроме жабаскрипта из веб-страниц на ум приходят разве что микроконтроллеры и все, что им подобно.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну моя идея — сделать что-то типа Unknown Language Round, только когда язык известен и нужно как можно лучше им воспользоваться, чтобы сократить исходный код.

    Формат существующих контестов, которые именно на решение задач, я менять не предлагаю:)

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      В качестве языка можно malbolge использовать, например =)

»
11 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Насколько я понимаю, такие соревнования называются code golf. Мне было бы очень интересно в таком поучаствовать на CF.

Особенно большой потенциал для сжимающего коверкания кода у C без плюсов: http://iitbhu.ac.in/codefest/blog/?p=321 . В контесте по ссылке еще в некоторых задачах запрещали использовать в программе определенные символы или последовательности символов.

»
11 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Интересно мнение одного человека по этому поводу. См. лучшие попытки. А я — не осилил бы такого соревнования, посему — хотел бы посмотреть, как это сделают другие)

PS

int s(int a){return-a>a?-1:1;}
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Минификация кода в продакшене не уместна относительно этого поста — другие подходы, другие цели. я бы выбросил это из текста.

А вот само по себе соревнование code golf считаю интересным и уместным, принял бы участие.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Такие соревнования есть на https://www.hackerrank.com/ . Правда задач там пока не много.

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
»
11 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Обычно подобные соревнования жёстко привязаны к языку, чаще всего я слышу о perl golf'е, хотя не обязательно он самый популярный. Perl достаточно податлив в плане минимизации. :) ioccc достаточно популярное соревнование по C. А недовольствие — дело относительное... Язык можно менять в конце концов от соревнования к соревнованию, если полетит.