Pragmatic Perl

Выпуск 10. Декабрь 2013

Морской бой на Perl — решение Perl Golf 09

Задача Perl Golf из 9 номера оказалась одновременно и проще, и сложнее предыдущей. Проще — потому что алгоритм был прост и понятен (ведь все играли в Морской бой хоть раз), а сложнее — потому что одной только оптимизации по размеру было недостаточно.

Итак, цель — поразить хотя бы одну палубу линкора (4-клеточного корабля) на заданном поле. Забегая вперед, скажу, что если бы условием задачи было бы поразить все палубы линкора, эта история сложилась бы совсем по-другому.

За каждое лишнее попадание в каждом тесткейсе дается пенальти в 10 символов, затем по итогам всех тестов оно усредняется и прибавляется к длине скрипта. Тестовый скрипт генерирует несколько случайных полей с разной плотностью имеющихся попаданий, поэтому пенальти между запусками может отличаться в пределах 10-20 баллов — именно поэтому я дальше в статье указываю его приблизительное значение.

В качестве примера к заданию прилагался скрипт, который просто заменял все пробелы символами попадания — при длине 17 символов он дает пенальти 510, итого 527 баллов. Нужно написать что-то получше :)

Первый вариант решения я написал сравнительно быстро, взяв код для поворота поля из своего решения предыдущего гольфа. Пришлось, конечно, повозиться с регулярным выражением — использовать выражение [^X] для отсеивания стоящих рядом кораблей я догадался далеко не сразу.

#!perl -n0
sub r {
    # поворот поля на 90 градусов
    my @e;
    $e["@-" % 11] .= $& while /[^E]/gs; # оставляем в повернутом поле
                                        # только нужные символы
    @e
}
sub x {
    s/
                         # возле корабля не должно быть попаданий:
    (?<=[^X]{6}.{5}[^X]) # ни перед ним,
    [ @]{4,}
    (?=[^X].{5}[^X]{6})  # ни после него
    /
    '@'x length $&       # заменяем найденный "корабль" из 4 и более
                         # символов на соответствующее количество попаданий
    /egsx
}
$_ = "E"x11 . $_ . "E"x20; # прицепляем лишние символы, чтобы в начале и конце
                           # поля срабатывал prematch и postmatch
s/\n/E/g;
x;                         # делаем проход в поисках горизонтальных кораблей
$_ = "E"x11 . join ("E", r) . "E"x20; # поворачиваем поле на 90 градусов
x;                                    # и ищем вертикальные корабли
$_ = join "E", r;          # поворачиваем поле "как было"
s/E/\n/g;
print "$_\n";              # выводим результат

Длина 274 символа, пенальти порядка 170 — итог 444 балла.

Конечно, можно обойтись без замены переносов строки буквой “Е”, что я сразу же и сделал. Процедуру r можно научить сразу “собирать” поле обратно, все равно нам нужно это делать каждый раз после поворота поля. Ну и ключ -p вместо print $_ — замечательный хак, позволяющий сэкономить несколько символов.

Немного подчистим код, и вот у нас уже 173 символа с тем же пенальти. Итого 343 балла:

#!perl -p0
sub r {
    my @e;
    $e["@-"%11] .= $& while /[^\n]/gs;
    join "\n", @e
}
sub x {
    s/(?<=[^X]{6}.{5}[^X])[ @]{4,}(?=[^X].{5}[^X]{6})/'@' x length $&/egs
}
$z = "\n" x 11;
$_ = $z . $_ . $z;
x;
$_ = $z . r . $z;
x;
$_ = r

Нетрудно заметить, что в конце скрипта у нас снова есть повторяющиеся операции. Логично будет действия процедур r и x объединить в одну, тогда размер скрипта станет еще меньше. Кроме того, чтобы уменьшить величину пенальти, мы будем стрелять только в первый из четырех квадратов возможного расположения линкора.

Получился код длиной 136 символов с пенальти около 65 — в сумме 201 балл:

#!perl -p0
sub r {
    $_ = $z . $_ . $z;
    s/(?<=[^X]{6}.{5}[^X]) (?=   [^X].{5}[^X]{6})/@/gs;
    my @e;
    $e["@-"%11] .= $& while /[^\n]/g;
    $_ = join "\n", @e
}
$z = "\n" x 22;
r;
r

Достаточно неплохой результат, и на нем вполне можно было бы остановиться.

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

Есть несколько способов это сделать:

 +-а-б-в-г-д-е-ж-з-и-к-+        +-а-б-в-г-д-е-ж-з-и-к-+
 1 * * * @ * * * @ * * |        1 * * @ * * * @ * * * |
 2 @ * * * @ * * * @ * |        2 * * * @ * * * @ * * |
 3 * @ * * * @ * * * @ |        3 @ * * * @ * * * @ * |
 4 * * @ * * * @ * * * |        4 * @ * * * @ * * * @ |
 5 * * * @ * * * @ * * |        5 * * @ * * * @ * * * |
 6 @ * * * @ * * * @ * |        6 * * * @ * * * @ * * |
 7 * @ * * * @ * * * @ |        7 @ * * * @ * * * @ * |
 8 * * @ * * * @ * * * |        8 * @ * * * @ * * * @ |
 9 * * * @ * * * @ * * |        9 * * @ * * * @ * * * |
10 @ * * * @ * * * @ * |       10 * * * @ * * * @ * * |
 +---------------------+        +---------------------+
      25 выстрелов                     24 выстрела

Таким образом, достаточно поместить значки выстрела в заданные позиции при условии, что в них находится пробел.

В качестве эксперимента я попробовал считерить и просто сгенерировать пустое поле с попаданиями в нужных местах с помощью коротенького кода:

#!perl -p
$_='   @'x25

Но как и следовало ожидать, этот трюк не прокатил — скрипт получает пенальти более 2300, поскольку в тестах проверяется разница между оригинальным полем и тем, которое выдал проверяемый скрипт.

Ладно, попробуем первый вариант, он попроще:

#!perl -0p
s/(...)(.)/$2eq' '?"$1@":$&/egs

Всего 35 (!) символов с пенальти порядка 130. И по сумме баллов (165) эта версия выигрывает у “интеллектуального” варианта выше.

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

Для сравнения я реализовал второй вариант простреливания поля — код получился на 5 символов длиннее:

#!perl -0p
s/(..)(.)(.)/$2eq' '?"$1\@$3":$&/egs

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

Вот такая история о победе грубой силы над интеллектом. Спасибо за внимание!

■ Сергей Можайский