Pragmatic Perl

Выпуск 11. Январь 2014

Perl Golf

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

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

Создать более или менее приличного робота на основе информации о четырёх соседних клетках оказалось нереально. Любым алгоритмам поиска пути, как например, A* требуется информация обо всех клетках до цели. Поэтому ни один робот не справлялся с задачей, если на пути встречалось препятствие хитрой формы.

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

Рассмотрим окончательные варианты решения. Решение, которое сделал Василий Король, имеет длину 90 байт. Отформатированный вариант:

#!perl -apl
for $j ( 0 .. 3 ) {
    $_ = $j % 2 ? "0 $x" : "$x 0"
      if $F[$j] ne '#'
      && $F[ 4 + $j % 2 ] * ( $x = $j % 3 > 0 || -1 ) > 0 | /#/;
}
$| = 1

Опция компилятора -p задаёт режим, в котором тело скрипта оборачивается в цикл while и происходит построчное считывание с STDIN и вывод значения переменной $_ на STDOUT. Опция -a совместно с -p выполняет команду split на каждую полученную строку и записывает результат в массив @F. Опция -l производит автоматическую обработку конца строк, выполняя chomp у входных строк и добавляя перенос строки при выводе $_.

Выражение $| = 1 в конце скрипта включает autoflush для STDOUT, заставляя perl делать вывод при каждой записи на вывод, отключая буферизацию.

Цикл for обходит четыре значения массива @F, в которых сохранены значения окружающих голову змеи клеток. На каждой итерации происходит попытка присвоения окончательного варианта смещения, при условии выполнения сложного условия. Если индекс массива чётный, то перемещение будет по вертикали, если нет — по горизонтали. Направление определяется из условия $x = $j % 3 > 0 || -1, то есть в сторону роста координат смещение положительное, а в сторону уменьшения координат отрицательное. Смещение будет зафиксировано при условии, что в текущей клетке нет препятствия, а также если смещение уменьшит расстояние до яблока.

Решение Сергея Можайского имеет длину 103 байта. Отформатированный вариант:

#!perl -alp
for $i ( 0 .. 3 ) {
    $| = @p = ( $i < 3 ? $i - 1 : 0, $i ? 2 - $i : 0 );
    $_ = $F[$i] eq '#' ? next : "@p";
    last if grep $_ * pop @p > 0, @F[ 5, 4 ];
}

Данный алгоритм схож с описанным выше. В строке 3 в массиве @p задаётся смещение в зависимости от направления текущей просматриваемой клетки. В следующей строке происходит присвоение $_ строчного значения массива, если в текущей клетке нет препятствия, иначе происходит следующая итерация. Затем следует проверка: если смещение уменьшит расстояние до яблока, то дальнейшие итерации не требуются.

Как обычно, за несколько минут до конца конкурса, то есть в тот момент, когда другие люди открывали шампанское, перед новогодним боем курантов, Иван Крылов aitap присылает своё решение длиной в 163 байта. Отформатированный вариант:

#!/usr/bin/perl -pal
$| = @_ = map $F[ 4 + $_ % 2 ] > 0 ? $_ : ( $_ + 2 ) % 4,
  ( abs $F[5] > abs $F[4] ) ? ( 1, 2 ) : ( 2, 1 );
@_[ 2, 3 ] = map { ( $_ + 2 ) % 4 } @_[ 1, 0 ];
($a) = grep $F[$_] ne '#', @_;
$_ = "-" x !( $a % 3 ) . 1;
$_ = $a % 2 ? "0 $_" : "$_ 0";

Если кто-то поймёт, как это работает, прошу в комментариях к статье рассказать — это будет отличной головоломкой. Особенность данной змейки в том, что она при перемещении к яблоку может двигаться по диагонали (точнее, по ломаной линии). За это как раз отвечает условное выражение ( abs $F[5] > abs $F[4] ) ?.

Итоги

Проведя тестирование, были получены следующие результаты:

example.pl: length=541, path= 60, fights= 86
  aitap.pl: length=163, path= 60, fights= 42
technix.pl: length=103, path= 60, fights= 76
vakorol.pl: length= 90, path= 60, fights= 78

And the oscar goes to vakorol.pl

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

Таким образом, в этом конкурсе у нас побеждает Василий Король, с решением всего в 90 байт. Поздравляем Василия с победой! Огромная благодарность Сергею и Ивану за участие. Хочется также особо отметить работу Ивана за запутанность алгоритма и внешне отличающееся от остальных поведение змейки.

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