この記事は，東京大学航空宇宙工学科／専攻 Advent Calendar 2017向けの記事です．
今回はPerlのワンライナーの解読をしてみようと思います．
これを読めば，「高橋くんの宿題最適化して！」と言われて「<>=~$";$;=$';$s>$;and$s+=$_,++$%for sort{$a-$b}map{/ /,$s+=$`,$'-$`}<>;print$s>$;?-1:$%,$/」，「旅館の部屋割り最適化して！」と言われて「<>;$_='@b=sort{$b<=>$a}<>=~/\d+/g;'x2;s/b/a/;eval;$_>$a[$i++]&&($x=NO)for@b;print$x||YES,$/」と答えられるようになりますよ！
トップ画像の出典はこちら．
Microsoft Windows 10 Home (64bit)
perl 5, version 24, subversion 2
Perlにはワンライナーという，処理を１行で済ませてしまおう，という文化がある．
また，
$ perl -e program # one line of program (several -e's allowed, omit programfile)
というように，ワンライナーをコマンドラインから実行するためのオプションまで用意されている．
今回はそのPerlのワンライナーを競技プログラミングの問題を例に解読していきたいと思う．
Perlに馴染みのない方は，「」を先に一読するのがいいかもしれません．
１つ目の例として，CODE FESTIVAL 2015 予選A C問題 を例にする．
（※ブラウザの画面幅を広くしたほうがみやすい．）
この世界，宿題が最大10000個出るのか...．
日本に生まれてよかった...．
僕がこのコンテスト当時に提出したコードを比較として載せておく．
まあ，普通．
標準入力から与えられるデータを受け取って，宿題を写すことによる利得が多いものから順に高橋くんのキャパに収まるように選択していくだけ．
これでも変数一括初期化や，後置ifでの短絡演算子の使用など，ショートコーディングとなっている．
use strict;
use warnings;
use utf8;
# 2015/09/26
my $in;
$in = <STDIN>; # 標準入力一行目
$in =~ s/\r\n$|\r$|\n$//; # 改行コード除去
my ($n, $t) = split(/ /, $in); # スペースでsplitし，N,Tを取得
my (@A, @B, @C);
my ($sumA, $sumB) = (0, 0);
for (my $i=0; $i<$n; $i++) {
my $temp = <STDIN>; # 一行ずつ標準入力を取得
$temp =~ s/\r\n$|\r$|\n$//; # 改行コード除去
my ($t1, $t2) = split(/ /, $temp); # A_i,B_iの配列をつくる
push(@A, $t1);
push(@B, $t2);
push(@C, $t1 - $t2); # A_iとB_iの差C_iの配列をつくる
$sumA += $t1; # sum
$sumB += $t2; # sum
}
&p(-1) and exit if $sumB > $t; # 特殊ケースはここで解答
&p(0) and exit if $sumA <= $t; # 特殊ケースはここで解答
my @Cs = sort { $b <=> $a } @C; # 降順にソート
my $i = 0;
while ($sumA > $t) { # 高橋くんのキャパに収まるまで写す分を増加させる
&p(-1) and exit if $i == $n;
$sumA -= $Cs[$i];
$i++;
}
&p($i); # 解答出力
sub p{
print $_[0], "\n";
}
すげぇ...．
<>=~$";$;=$';$s>$;and$s+=$_,++$%for sort{$a-$b}map{/ /,$s+=$`,$'-$`}<>;print$s>$;?-1:$%,$/
さあ，ワンライナーを解読していこう．
正しく処理される状態のまま，コードを変形していく．
まず初期状態
<>=~$";$;=$';$s>$;and$s+=$_,++$%for sort{$a-$b}map{/ /,$s+=$`,$'-$`}<>;print$s>$;?-1:$%,$/
とりあえず適当に改行とスペースを挿入し，略記も復元．
最後に;を加え，一応文を閉じておく．
はあ，ようやく色分けがちゃんと機能するようになった．
<STDIN>=~$";
$;=$';
$s>$; and $s+=$_, ++$% for sort{$a-$b} map{/ /,$s+=$`,$'-$`} <STDIN>;
print $s>$; ? -1 : $%, $/;
$"は文字列を配列展開するときの区切り文字を表す特殊変数．
ここではスペースなので，置換する．
$;は，一般的には多次元配列のエミュレート時の添字セパレータを表す特殊変数だが，ここでは一般変数として用いている模様．
なお，$'は最後にパターンマッチした部分より後ろの部分の文字列である．
$%は，一般的にはセレクト中の出力ファイルハンドラのページ数を表す特殊変数だが，ここではこれも一般変数として用いている模様．
さらに$/は入力レコードのセパレータ表す特殊変数であるので，"\n"に置換しておく．
にしても，元のコードの<>=~$";$;=$';$s>$;部分，人間に読ませまいとする強い意思を感じる...．
;って普通，文区切りだと思うじゃん...．
<STDIN>=~/\s/;
$t=$';
$s>$t and $s+=$_, ++$i for sort{$a-$b} map{/ /,$s+=$`,$'-$`} <STDIN>;
print $s>$t ? -1 : $i, "\n";
ほぼ複文のようなものに対して後置forが使われているので，これをforeach化．
さらに，これはPerlではよくある書き方だが，短絡演算子である論理演算子（優先順位低いVer.）andによって，$s+=$_, ++$iの実行を切り替えているので，これはif化．
なお，$s+=$_, ++$iとカンマ演算子,を馴染みのない使い方をしているが，カンマ演算子の仕様は，「（左辺がスカラーコンテキストの場合）左辺を評価後その値を捨て，右辺を評価しその値を返す．」であるので，ここでは複文と同等である．
（後述（）するコードゴルフ的観点から見ると，文字数を減らすために用いられていると推測される．）
<STDIN>=~/\s/;
$t=$';
foreach (sort{$a-$b} map{/ /,$s+=$`,$'-$`} <STDIN>) {
if ($s>$t) {
$s+=$_;
++$i;
}
}
print $s>$t ? -1 : $i, "\n";
さらにsortをPerlらしく符号付き比較演算子<=>で書き直す．
<STDIN>=~/\s/;
$t =$';
$s = 0;
@C = ();
while (<STDIN>) {
$_=~/\s/;
$s += $`;
push(@C, $'-$`);
}
@Cs = sort {$a <=> $b} @C;
foreach (@Cs) {
if ($s > $t) {
$s += $_;
++$i;
}
}
print $s>$t ? -1 : $i, "\n";
これで，自明なコードとなり，解読終了．
これでも十分短いが...．
念のため補足しておくと，$'は最後に成功したパターンマッチでマッチした部分に続く文字列であり，$`最後に成功したパターンマッチでマッチした前の文字列である．
つまり8行目ではスペースでsplitして，その差分を配列@Cにpushしている．
$t, $iなどと一般変数と自明にわかる文字を使わず，$;, $%という特殊変数を代用しているのは，コードゴルフのためだと思われる．
（もちろん，例にあげたCODE FESTIVAL 2015はコードゴルフではないが．）
Perlにはトークンが区別できれば空白は不要なので，$t, $iを使うよりも$;, $%を使ったほうが文字数を少なくすることができる．
具体例をあげると，
$s>$;and$s+=$_,++$%for sort{$a-$b}map{/ /,$s+=$`,$'-$`}<>;
は
$s>$t and$s+=$_,++$i for sort{$a-$b}map{/ /,$s+=$`,$'-$`}<>;
とは書けるが，
$s>$tand$s+=$_,++$ifor sort{$a-$b}map{/ /,$s+=$`,$'-$`}<>;
とは書けない．
なぜなら，and, forがトークンとして認識されなくなってしまうためだ．
コードゴルフの観点から見ると，これで2 byte節約しているわけだ．
さらに符号付き比較演算子<=>を二項演算子-で代用しているあたりも，発想がすごい．
２つ目の例として，CODE FESTIVAL 2015 予選B C問題 を例にする．
（※例によって例のごとく，ブラウザの画面幅を広くしたほうがみやすい．）
この旅館，部屋数が最大で10000部屋とか...．
さらに最大の部屋の収容人数，最大10000人とか...．
めちゃめちゃでかい旅館だ...．
僕がこのコンテスト当時に提出したコードを比較として載せておく．
予めソートしておくことで，計算量を減らし，あとは人数の多い順に部屋を割り当てていくだけ．
計算量を減らさずに愚直にやると，実行時間が間に合わずに部分点解法となる．
use strict;
use warnings;
use utf8;
# 2015/10/25
my $in;
$in = <STDIN>;
$in =~ s/\r\n$|\r$|\n$//;
my ($n, $m) = split(/ /, $in);
$in = <STDIN>;
$in =~ s/\r\n$|\r$|\n$//;
my @A = split(/ /, $in);
$in = <STDIN>;
$in =~ s/\r\n$|\r$|\n$//;
my @B = split(/ /, $in);
# ここでソートすることによって，
# 計算量がO((N+M)M) → O(N logN + M logM)
# となり，満点解答となる．
my @As = sort { $b <=> $a } @A;
my @Bs = sort { $b <=> $a } @B;
# 人数の多い順に大きい部屋を割り当てていく
my $nowN = 0;
foreach my $b (@Bs) {
goto NG if $nowN >= $n;
while ($b > $As[$nowN]) {
$nowN++;
goto NG if $nowN >= $n;
}
$nowN++;
}
&p("YES");
exit;
NG:
&p("NO");
exit;
sub p{
print $_[0], "\n";
}
相変わらずやべぇ...．
<>;$_='@b=sort{$b<=>$a}<>=~/\d+/g;'x2;s/b/a/;eval;$_>$a[$i++]&&($x=NO)for@b;print$x||YES,$/
解読していきますか．
ただ，パット見た感じ，例１のようにミスリードなものはないし，頭から見ていけばよさそうですね．
初期状態．
<>;$_='@b=sort{$b<=>$a}<>=~/\d+/g;'x2;s/b/a/;eval;$_>$a[$i++]&&($x=NO)for@b;print$x||YES,$/
改行，スペースなどを挿入．
というか，一行目の標準入力，捨ててますね...．使わずに解けるんですね...．
<>;
$_ = '@b=sort{$b<=>$a}<>=~/\d+/g;' x 2;
s/b/a/;
eval;
$_ > $a[$i++] && ($x=NO) for @b;
print $x || YES, $/;
省略されているものを補う．
デフォルト対象特殊変数$_を，こう積極的に使って文字数を減らしていたのか．
<STDIN>;
$_ = '@b = sort {$b<=>$a} <STDIN> =~ /\d+/g;' x 2;
$_ =~ s/b/a/;
eval $_;
$_ > $a[$i++] && ($x=NO) for @b;
print $x || YES, $/;
ほぼおなじコードを，x2と置換，evalで実装している...．
コードを短くするために，evalまで持ち出すとは...．
<STDIN>;
$_ = '@a = sort {$b<=>$a} <STDIN> =~ /\d+/g; @b = sort {$b<=>$a} <STDIN> =~ /\d+/g;';
eval $_;
$_ > $a[$i++] && ($x=NO) for @b;
print $x || YES, $/;
use strict;をしていないことをいいことに，NO, YESを無修飾で使うの，わけわからなくなるww
後置forに関しては，このくらいならまあわかりやすい．
<STDIN>;
@a = sort {$b<=>$a} <STDIN> =~ /\d+/g;
@b = sort {$b<=>$a} <STDIN> =~ /\d+/g;
$i = 0;
foreach (@b) {
$_ > $a[$i++] && ($x="NO");
}
print $x || "YES", "\n";
短絡演算子である論理演算子（優先順位高いVer.）&&なども，わかりやすくif化しておく．
さらには，$iの変数宣言・初期化も追加．
<STDIN>;
@a = sort {$b<=>$a} <STDIN> =~ /\d+/g;
@b = sort {$b<=>$a} <STDIN> =~ /\d+/g;
$i = 0;
foreach (@b) {
if ($_ > $a[$i]) {
$x = "NO";
}
$i++;
}
print $x || "YES", "\n";
最後に，短絡演算子である論理演算子（優先順位高いVer.）||で$xがundefかどうかで出力をスイッチしている．
わかりやすく書くと以下．
<STDIN>;
@a = sort {$b<=>$a} <STDIN> =~ /\d+/g;
@b = sort {$b<=>$a} <STDIN> =~ /\d+/g;
$i = 0;
foreach (@b) {
if ($_ > $a[$i]) {
$x = "NO";
}
$i++;
}
if (defined($x)) {
print "NO", "\n";
} else {
print "YES", "\n";
}
こちらもこれで，自明なコードとなり，解読終了．
補足しておくと，<STDIN> =~ /\d+/gは標準入力に対する（みんな大好き！）正規表現によるパターンマッチで，gオプションが付いているため，ここのような配列コンテキスト上ではマッチしたもののリストを返す．
慣れれば，splitよりわかりやすく簡潔にかけていいかもしれないな...．
ワンライナーの解読，謎解き感があって面白いですね（特に例１）．
gnuplotでのデータ整形など，実用的なワンライナーもあるので，興味のある人は調べてみてください．
Perlはいいぞ！
P.S.
Perl使ったことがない人でもわかるように書いたつもりですが，何かあればコメントください．追記します．
名前
Email (※公開されることはありません)
コメント