Выпуск 28. Июнь 2015
← Анонс «Perl Mama» — 2015 | Содержание | Рефакторинг Legacy →Perl Golf на YAPC::Russia 2015
Рассказ про соревнование Perl Golf, проходившее в течение двух дней на майской YAPC::Russia в Москве
Perl Golf — это конкурс на написание самой короткой программы на перле (подробнее об этом можно прочитать в ранних выпусках журнала Pragmatic Perl). Задание для гольфа YR2015 озвучил Вадим Пуштаев в начале первого дня конференции.
Решения, присланные участниками, размещены в репозитории YAPC_Russia_2015_perl_golf на гитхабе.
Задача. Скрипт принимает два параметра — длину и ширину матрицы — и по порядку печатает в заданном поле числа, закручивая их по спирали внутрь:
$ perl script.pl 7 6
1 2 3 4 5 6 7
22 23 24 25 26 27 8
21 36 37 38 39 28 9
20 35 42 41 40 29 10
19 34 33 32 31 30 11
18 17 16 15 14 13 12Колонки должны быть выровнены влево и отделены друг от друга ровно одним пробелом.
Минимальное решение bronton.pl, которое шло в комплекте с заданием, содержало 338 символов, и сабмитить более длинное не было смысла. А за длиной остальных было интересно наблюдать, обновляя страницу новостей на сайте, где публиковались промежуточные результаты, но, конечно, без самих решений. В какой-то момент было три решения в 244, 245 и 246 символов, и казалось, что эти кандидаты могут побороться еще за один-два символа, чтобы обогнать друг друга. Но почти перед дедлайном конкурса Денис Ибаев запостил решение в 205 символов, которое уже само по себе никому не оставило шанса, и потом улучшил свой рекорд до 202 символов. Для меня самое удивительное, что Денис написал свой код на айпаде.
202 dionys.pl
208 agrishaev.pl
213 andrey_shitov.pl
229 nikolas_shulyakovskiy_s.pl
243 kyusev.pl
246 andrey_fedorov.pl
258 khripunov.pl
294 bor_vas.pl
303 orlenko_aleksandr.pl
326 evgeniy_kim.pl
338 bronton.plЯ расскажу о своем решении (и предлагаю читателям самостоятельно разобраться в коде других участников :-).
Первым делом надо было понять, как оптимальнее закручивать матрицу. Я хотел придумать или найти формулу, вычисляющую значение клетки по ее координатам. В интернетах описана спираль Улама — она такая же, как в задании, но раскручивается из центра, — и даже находится не очень внятная формула, которая позволяет вычислить значение по координатам, но я не пошел этим путем, потому что было неясно, как же рассчитывать число пробелов между колонками. Имея формулу, мне хотелось сразу печатать значения, не создавая два цикла — один для генерации данных, а второй для их печати.
Но в итоге пришлось делать два этапа: генерацию и печать. ОК, чтобы закрутить спираль, надо понять, как поворачивать на углах и как не испортить уже заполненные клетки. Я порисовал матрицы на бумажке (здесь очень пригодились блокноты со страницами «в точечку», выдаваемые организаторами конференции) и заметил, что каждый поворот спирали уменьшает длину следующего прямолинейного отрезка на единицу. То есть для матрицы размером 7×5 первые два поворота будут через 7 и 4 шага, следующие два через 6 и 3, затем через 5 и 2 и так далее.
Этот алгоритм отражен в первом варианте решения.
#!/usr/bin/perl
($w,$h)=@ARGV; # ширина и высота
exit if !($w*$h);
#$n=0; # величина, записываемая в клетку
#$x=0; # начальное положение по горизонтали
$y=1; # начальное положение по вертикали
$v=1; # вектор движения по горизонтали
$u=1; # и по вертикали
# основной цикл - по ширине
while ($wi=$w--) { # здесь упомянутое выше уменьшение длины
while ($wi--) { # прямолинейного отрезка
$x+=$v; # перемещение на одну клетку вправо или влево
$a[$x][$y]=++$n; # фиксирование результата
$L[$x]=$n; # @L -- одномерный массив по числу строк,
# по мере генерации в него записывается
# текущее число, поэтому к моменту печати
# в каждом элементе будет максимальное число,
# которое возможно в соответствующей колонке,
# а значит известна и нужная ширина колонки.
};
$v=-$v; # подготовка для следующего горизонтального участка,
# где смещение будет -1, то есть справа налево.
$hi=$h--;
while(--$hi) { # а теперь идем по вертикали
$y+=$u; # вверх (-1) или вниз (+1)
$a[$x][$y]=++$n;
$L[$x]=$n;
}
$u=-$u;
last if !$h;
}
($w,$h)=@ARGV; # исходные переменные уже испорчены, читаем заново
# нехитрые циклы для печати @a
for $y (1..$h) {
for $x (1..$w) {
# хитрость только в выводе через
# форматную строку типа "%-5i" с длиной из @L
$s = $x != $w ? 1+length $L[$x] : '';
printf "%-${s}i", $a[$x][$y];
}
print "\n";
}Кстати, решение dionys.pl не содержит двумерной матрицы, а данные читаются из одного массива.
По ходу решения выяснилось, что просто посчитать ширину колонки как 1 + length $w*$h нельзя, потому что может оказаться так, что даже если самое длинное число будет только одно, оно сразу сделает одну из колонок шире всех остальных.
$ perl script.pl 10 10
1 2 3 4 5 6 7 8 9 10
36 37 38 39 40 41 42 43 44 11
35 64 65 66 67 68 69 70 45 12
34 63 84 85 86 87 88 71 46 13
33 62 83 96 97 98 89 72 47 14
32 61 82 95 100 99 90 73 48 15
31 60 81 94 93 92 91 74 49 16
30 59 80 79 78 77 76 75 50 17
29 58 57 56 55 54 53 52 51 18
28 27 26 25 24 23 22 21 20 19 Прежде всего можно немного сэкономить на повторном извлечении размеров таблицы:
($p,$q)=($w,$h)=@ARGV;Проверка на правильность введенных данных тоже не нужна, потому что таких входных параметров нет в тесте, проверяющем правильность решения :-) При нулевых и отрицительных значениях программа может уйти в бесконечный цикл, но это неважно.
exit if !($w*$h);Ширина колонки определяется по длине числа в соответствующем элементе массива @L. Чтобы избавиться от пробелов в конце строк, нужно сделать длину последнего элемента нулевой:
$L[$p]='';Это дает возможность исключить исходную проверку при вычислении ширины колонки:
$s = $x != $w ? 1+length $L[$x] : '';Теперь хочется избавиться от проверки условий для завершения. Цикл для генерации спирали выглядит примерно так:
while ($wi=$w--) {
. . .
last if !$h;
}Вместо этого можно написать так:
while ($h * ($wi=$w--)) {
. . .
}Инициализацию переменных (тех, которые не получилось начать с нуля) можно сделать в одну строку:
$y=$v=$u=1;То же самое можно сделать для следующих двух строк, и вместо
$a[$x][$y]=++$n;
$L[$x]=$n; записать
$L[$x]=$a[$x][$y]=++$n;Теперь небольшая, но полезная оптимизация цикла печати с использованием постфиксной записи for:
for $y (1..$q) {
printf "%-".(1+length$L[$_])."i", $a[$_][$y] for 1..$p;
print "\n";
}Потом наступило понимание, что изменение переменных $u и $v всегда происходит друг за другом, и они никогда не используются вместе, то есть к тому моменту, когда они нужны для вычислений, они всегда содержат одинаковое значение. Поэтому обе я заменил одной переменной $d, и ее знак меняется в конце тела внешнего цикла:
$d=1;
while ($h * ($i=$w--)) {
. . .
$d=-$d;
}Вложенные циклы while тоже следует заменить постфиксной записью, но сначала можно попровать вынести повторяющийся код в функцию, и это действительно помогло заметно сэкономить:
sub p {
$L[$x]=$a[$x][$y]=++$n
}Вместо
while($wi--) {
$x+=$v;
$L[$x]=$a[$x][$y]=++$n;
}и
while(--$hi) {
$y+=$u;
$L[$x]=$a[$x][$y]=++$n;
}теперь так:
$x+=$d, p while $i--;
. . .
$y+=$d, p while --$i;Было сильное желание разобраться с тем, как привести декременты $i-- и --$i к одному виду, чтобы убрать повторяющийся код, но быстро это сделать не получилось. Вместо этого я потратил время на неудачную попытку создать еще одну функцию, которая будет менять либо переменную $x, либо $y:
#sub e {
# eval "\$$_[0]+=$d, p while $_[1]"
#}
. . .
#e 'x','$i--';
. . .
#e 'y','--$i';Но при таком подходе код оказался длиннее исходного.
Зато получилось избавиться от инициализации $y = 1. Исходное значение теперь 0, а запись $y = 0 для гольфа не нужна.
Итоговый цикл вычисления спирали теперь такой:
$d=1;
while ($h * ($i=$w--)) {
$x+=$d, p while $i--;
$i=$h--;
$y+=$d, p while --$i;
$d=-$d;
}Еще один подход к этапу печати. Сначала экономлю один символ, заменяя \n настоящим переводом строки в коде:
print "
"Но потом, почитав perldoc perlop и Perl Golf 101, понимаю, что гольфисты уже все давно придумали и вместо "\n" пишут $/.
И небольшой, но удачный эксперимент по замене конкатенации строк
printf "%-".(1+length$L[$_])."i"интерполяцией с выполнением кода в строке "@{[]}":
printf "%-@{[1+length$L[$_]]}i"Готово. 213 символов:
sub p{$L[$x]=$a[$x][$y]=++$n}($p,$q)=($w,$h)=@ARGV;$d=1;while($h*($i=$w--))
{$x+=$d,p while$i--;$i=$h--;$y+=$d,p while--$i;$d=-$d}$L[$p]='';
for$y(0..$q-1){printf"%-@{[1+length$L[$_]]}i",$a[$_][$y]for 1..$p;print$/}И еще о нескольких интересных приемах, которыми воспользовались другие участники.
Александр Орленко сразу продублировал входные параметры:
($w,$h,$y,$z)=(@ARGV)x2;Хотя эта запись на два символа менее выгодна аналогичной:
($p,$q)=($w,$h)=@ARGV;В авторском примере bronton.pl есть еще один интересный подход к начальному присваиванию:
($c,$m,$n)=(1,@ARGV);Хотя он длиннее, чем если делать все по-отдельности:
$c=1;($m,$n)=@ARGV;Николай Шуляковский применил редкий оператор-«качель» ...:
do{$r[$j][$v+($i+=$v)]+1}...do{$r[$v+($j+=$v)][$i]+1and$v*=-1}Андрей Федоров меняет направление, используя умножение на -1 или на 0, хитро вычисляя его из текущей позиции:
$X*=!!$Y--;$k*=-1;Кстати, вариант с умножением ничем не отличается от явной смены знака:
$k*=-1;
$k=-$k;Сергей Хрипунов использовал полезный прием для экономии на слове length:
$l=y///c;В решении Евгения Кима места поворотов спирали вычисляются с помощью матрицы (предвычесленные значения всегда хорошо):
@r=([1,0],[0,1],[-1,0],[0,-1]);
. . .
($x,$y)=@{$r[++$d%4]}Анатолий Гришаев сразу создает матрицу-заготовку и затем заполняет ее числами:
($a,$b)=@ARGV;$_=('1 'x$a++."0\n")x$b;@s=split;s/\d/$z++/ge;← Анонс «Perl Mama» — 2015 | Содержание | Рефакторинг Legacy →