Pragmatic Perl

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

Perl Golf

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

«Морской бой»

Решить это задание было не очень сложно, поскольку даже элементарное заполнение карты символами @ выполняло задачу. Интереснее было бы найти решение, которое бы выполняло эту задачу более оптимально, учитывая границы подбитых кораблей и исключая места, в которых линкор поместиться не мог. Именно для этих целей и была создана система штрафных балов, которая бы отсеяла решения в лоб.

На конкурс были представлены два решения, причём последнее подоспело за несколько минут до окончания срока приёма.

Автором первого решения является Сергей Можайский technix. Его первоначальный вариант предусматривал некоторый интеллектуальный анализ карты, но всё-таки в окончательном решении был выбран шаблонный обстрел полей, потому что, несмотря на пенальти, размер скрипта был небольшим и давал за счёт этого суммарный выигрыш.

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

Скрипт обходит карту по четыре символа, и если третий символ совпадает с пробелом, замещает его символом @, таким образом в худшем случае на карте будут находиться 24 обстрелянные точки.

Иван Крылов aitap, автор второго решения, предложил следующий вариант (отформатированная версия):

#!perl -p0
sub z : lvalue {
    substr $_, $a + pos() - 1, 1
}
while (/X/g) {
    for $a ( -12 .. -10, -1, 1, 10 .. 12 ) {
        z && z =~ s/ /*/
    }
}
s/(   ) /$1@/g;
{
    s/(( .{10}){3}) /$1@/sgc
      && redo
}

Цикл while обходит карту в поиске полей с подбитой палубой. Как только такое поле найдено, запускается цикл, который обходит поля, находящиеся вокруг данного поля, функция z возвращает символ в данной позиции и если позиция существует, то производится замена пробела на символ *, таким образом на карте маскируются позиции, где линкор располагаться не может.

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

К сожалению, в реализации содержится ошибка, связанная с тем, что pos() возвращает undef, каждый раз после того, как происходит успешное замещение пробела в s/ /*/. В итоге оказываются замещены позиции по углам карты, что выявляется при тестирование на большом количестве тестовых карт.

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

Финальное тестирование было проведено на 500 случайных тестовых картах, для которых выполнялся случайный обстрел в 60%, 50%, 40% и 30% картах (т.е. в общей сложности 2000 проверок для решения), что давало небольшую статистическую погрешность результата.

example.pl: length= 17, penalty=509
technix.pl: length= 40, penalty=121

По итогам тестирования решение Сергея получало наименьшее значение — 161. Таким образом Сергей вновь становится победителем. Поздравляем Сергея с победой и выражаем благодарность Ивану за участие.

Как обычно, покажу и мой собственный вариант решения. Его размер составил 119 байт. Отформатированный вариант выглядит так

#!/usr/bin/perl -p0
while ($/) {
    $/  = s/ (.{9,11})?X/o$1X/s;
    $/ += s/X(.{9,11})?\K /o/s
}
s/ {3}\K /@/g;
while ($") {
    $" = s/( .{10}){3}\K /@/s
}
s/o/ /g

Алгоритм таков. Изначально карта сохраняется в переменной $_. Первый цикл while выполняет два регулярных выражения с заменой. Чтобы понять их смысл, обратимся к иллюстрации:

[1] [1] [1]
[1] [X] [2]
[2] [2] [2]

В центре квадрата из девяти полей находится палуба поражённого корабля. По правилам игры это значит, что поля вокруг этого квадрата не могут содержать палубы другого корабля. Первое регулярное выражение заменяет все поля, помеченные цифрой 1, символом о, если там находился символ пробела. Второе регулярное выражение замещает, соответственно, поля, помеченные цифрой 2. Т.о. мы закрыли все поля, где не может быть линкора в принципе.

Следующим шагом, регулярное выражение ищет четыре пробельных поля подряд и замещает в последнем поле пробел на @.

Дальнейший цикл while проводит такую же операцию, но для всех вертикальных полей.

Ну и чтобы вернуть карту в тот вид, в котором оно было изначально — удаляем символы o, которые были расставлены на первом шаге.

По результатам тестирования такой алгоритм давал очень низкое пенальти ~ 34, т.е. в среднем всего 3-4 лишних символа на карте.

«Искусственный интеллект»

В то время как Google тестирует автомобили, которые управляются роботом, предлагаю не отставать и реализовать искусственный интеллект, который бы управлял Змейкой.

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

В репозитории golf-10 реализован простейший вариант консольной игры с использованием библиотеки Curses. В простейшем варианте змейкой можно поуправлять вручную (snake.pl), а можно поиграть и против роботов (snake-fight.pl), но в этом случае надо реализовать хотя бы одного такого робота.

Как сделать своего робота? Для этого необходимо создать файл скрипта в каталоге script с именем your_github_login.pl. Ваш робот будет запущен в отдельном процессе и на STDIN получит строку с шестью полями, разделёнными пробелом, со следующими данными:

1. содержимое поля над головой змеи ( 0 — пусто, # — препятствие, @ — яблоко(пища) )
2. содержимое поля справа от головы змеи
3. содержимое поля снизу от головы змеи
4. содержимое поля слева от змеи
5. смещение по оси Y до яблока
6. смещение по оси X до яблока

Например:

0 0 # 0 -10 2

На STDOUT должны будут быть переданы значения смещения по координатам Y и X, относительно текущего положения головы, например:

-1 0

Смещение по оси Y на 1 вниз, нет смещения по оси X. Необходимо учитывать, что змейка не может двигаться по диагонали, поэтому только одна координата может иметь ненулевое смещение. В нашем случае координаты точки 0,0 находятся в левом верхнем углу, ось Y растёт вниз, в ось X вправо.

Цель игры — написать не просто самый короткий вариант реализации управления, но и самый результативный в плане количества поглощённых яблок. И, как обычно, победителя определит make test.

Проверяться решения будут на последней стабильной версии Perl, т.е. 5.18.1 (или 5.18.2, если она выйдет в декабре). Приём решений закончится как только куранты начнут бить 12 ударов и начнётся Новый 2014 год. Поднимая бокал шампанского, можете загадать, чтобы ваш вариант выиграл в конкурсе, ведь вдруг потом вашим роботом заинтересуются в Google.

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