Pragmatic Perl

Выпуск 9. Ноябрь 2013

Perl Golf

Perl Golf — это соревнование по поиску Perl-кода наименьшего размера (меньше всего символов), который решает заданную задачу. В этом выпуске будет сделан обзор решений предыдущего задания — «Цифры», торжественно будет оглашено имя победителя и предложена новая головоломка.

Цифры

То ли задание оказалось невообразимо сложным для читателей, то ли глупым и неинтересным (ни одной «звезды» не поставили репозиторию), то ли виной банальная лень, но было сделано лишь два(!) форка репозитория задачи на github golf-08. Pull-request’ы с решением были получены вообще только от одного человека — Сергея Можайского technix. Сергей грамотно подошёл к выполнению задания и регулярно отправлял улучшенные варианты своего решения. Помимо выполнения задания Сергей улучшил и тест для проверки решения, и сделал важные замечания по критериям проверки.

Например, пришлось явно изменить методику подсчёта длины скрипта. Первоначально в условии задачи говорилось, что в длину скрипта не входит первая строка с шебангом. Но от этого правила пришлось отказаться и учитывать также длину всех параметров, передаваемых в шебанге, таким образом, из подсчёта длины исключается только путь к интерпретатору и начальные символы #!. Основная причина — это наличие классного хака в Perl, позволяющего в параметрах передать часть кода скрипта. Сергей показал пример такого кода, я лишь приведу упрощённый для понимания пример:

#!/usr/bin/perl -i$x="yet\x20another\x20perl\x20hacker";print$x
eval$^I

Данный скрипт выведет фразу yet another perl hacker, при этом длина такого скрипта по методике, не учитывающей первую строку, всего 7 байт. Хитрость состоит в том, что у perl существует параметр -i, который позволяет редактировать файлы, имена которых переданы в командной строке, при этом значение после параметра задаёт расширение, которое будет добавляться для оригинальной копии редактируемого файла. Данная опция и поведение досталось perl в наследство от sed. Значение параметра можно получить внутри программы в специальной переменной $^I. Таким образом, если часть кода вынести в параметр для -i, то его затем можно выполнить в программе через обычный eval.

Решение

Единственное предложенное решение закономерно оказалось победителем турнира. Длина решения составила всего 90 байт! Для удобства восприятия будет продемонстрирован отформатированный вариант

#!perl -p0
while ($/) {
    $/ = s/ {9}\n//;
    for $a ( 1 .. 9 ) {
        $b = 10 - $a;
        $/ += s/$a((.{9} )*.{9}|\D*)[$a$b]/ $1 /s;
    }
}

Опция -p задаёт режим, в котором программа оборачивается в такой цикл:

while (<>) {
    ... # код скрипта
} continue {
    print or die;
}

Т.е. поток STDIN читается и сохраняется в переменной $_, а после того как весь STDIN будет прочитан, происходит печать на STDOUT содержимого $_.

Опция -0, после которой нет параметра, означает, что символом-разделителем строк $/ становится символ с кодом 0x00. Поскольку в нашем случае такого символа на входе точно нет, то это значит, что сразу будет прочитан весь STDIN в переменную $_.

Затем следует цикл while, который выполняется, пока значение $/ является истинным. Интересно, что первоначальное значение $/=chr(0) является истинным, поэтому цикл выполняется.

В строке 3 происходит удаление пустых строк (т.е. строк, где все цифры заменены пробелами). Если удаление произошло, то в $/ записывается 1, в противном случае — пустая строка.

В строке 4 начинается цикл по обходу всех возможных вариантов цифр от 0 до 9. Для каждой такой цифры вычисляется парное число (в сумме дают число 10). И вся суть алгоритма удаления пар заложена в регулярном выражении, которое ищет вхождения текущего числа, за которым следует ноль или несколько последовательностей из девяти произвольных символов и пробела (это проверка совпадения по вертикали), или за ним следует ноль или несколько нецифровых символов \D*, и затем идёт само число или его пара [$a$b]. Всё это заменяется строкой, в которой парные символы заменены пробелами. Модификатор s позволяет рассматривать в качестве любого символа . также символы переноса строки \n.

Если регулярное выражение выполнилось, то к переменной $/ добавляется 1, в противном случае добавляется 0. Таким образом цикл продолжает свою работу, пока все возможные пары цифр и пустые строки не будут удалены из переменной $_. Когда цикл завершится, переменная $_ будет выведена на экран.

Моё личное решение составило 126 байт. Используется схожий алгоритм, только я не догадался его так же здорово оптимизировать, как это сделал Сергей:

#!/usr/bin/perl -p
$d .= $_
}{
while ( $s ne $d ) {
    $s = $d;
    for ( 1 .. 9 ) {
        $j = 10 - $_;
        $d =~ s/$_(\s*|.{9}(\s.{9})*)($_|$j)/ $1 /sg;
    }
}
$_ = $d =~ s/(^\s{9}\n|\n\s{9})//rg

Используется переменная $d для считывания всего STDIN, затем символ эскимо }{, чтобы разорвать внешний цикл while, который формирует опция -p. Во внутреннем цикле я проверяю, есть ли отличия в строке копии, чтобы выяснить была ли произведена замена. Ну и совсем избыточно выглядит регулярное выражение удаления пустых строк, которое к тому же использует модификатор r, который доступен только в Perl 5.14+.

Победитель

Поздравляем Сергея Можайского с победой в турнире по Perl Golf восьмого выпуска журнала «Pragmatic Perl»! Желаем дальнейших успехов и удачи на этом нелёгком поприще.

Новое задание — «Морской бой»

В этом выпуске я хочу предложить вам поиграть в «Морской бой». Всем с детства известны правила этой игры. На карте из 10x10 клеток размещаются десять кораблей: один четырёхпалубный, два трёхпалубных, три двухпалубных и четыре однопалубных корабля. Корабли могут располагаться как вертикально, так и горизонтально, но при этом не должны соприкасаться углами. Ну и дальше игроки вслепую обмениваются ударами, сообщая координаты удара и получая информацию о результате: мимо, ранен, убит.

В ASCII-графике это может выглядеть примерно так:

 .-а-б-в-г-д-е-ж-з-и-к-.     .-а-б-в-г-д-е-ж-з-и-к-.
 1   0 0 0 0           |     1 *                   |
 2   *             0   |     2   *                 |
 3 0   0 0             |     3     *               |
 4 0                   |     4     * X X X         |
 5 0     *     0       |     5                     |
 6     *               |     6                     |
 7   X X *     *       |     7                     |
 8           0 0 0     |     8                     |
 9     0               |     9                     |
10     0       0       |    10                     |
 `---------------------'     `---------------------'

Попробуйте реализовать такой код, который получив на STDIN данные в виде ASCII-символьного поля 10x10, с изображёнными на нём результатом обстрела в виде * — промах, X — палуба поражённого корабля и пробел — неизвестная территория, попытается выполнить расчёт и поразить одну палубу ещё не обнаруженного четырёхпалубного корабля, выдав на STDOUT ту же самую карту, с проставленными символами @ в точках вероятного нахождения линкора. Гарантируется, что на входном поле нет недобитых кораблей.

Тестовый код будет проверять не только то, что вам удалось поразить линкор, но также просуммирует количество неуспешных попыток поражения (лишних @) в виде штрафных баллов, которые будут увеличивать длину вашего скрипта на 10 байт за каждый бал.

Репозиторий нового турнира доступен на github golf-09. Сделайте форк, создайте в директории script файл your_github_login.pl с вашим вариантом решения. Проверьте, что ваш вариант проходит тесты (с помощью команды prove) и сделайте pull request в основной репозиторий. Помните, что чем раньше вы опубликуете свой результат, тем больше шансов на победу.

Проверяться решения будут на последней стабильной версии Perl, т.е. 5.18.1. Приём решений закончится 30 ноября 2013 г. в 23:59:59.

Дерзайте, юнги! Победителя ждут слава и адмиральские погоны.

■ Владимир Леттиев