以前に自分が書いたワンライナーについて聞かれたのに答えられなかったので反省して、どうやって考えたのかを整理しつつもう一度作り直してみる。
まず素因数分解のプログラムの流れ。
- 対象の数の素因数を探す
- 具体的には、2から初めて小さい順に割り切れる数を探せば良い。
- 割り切れる数が見つかれば、それが最小の素因数となる。
- 対象の数をその素因数で割った商に対して、また素因数を探す
- 素因数が見つからなかった場合(素数であった場合)、終了
という繰り返し、もしくは再帰的な処理になるはず。簡単なスクリプトを書くと以下のようになると思う。
#!/usr/bin/perl use strict; use warnings; # 引数を得る my $n = $ARGV[0]; # 素因数の配列を得る my @factors = &factorization($n); # 答えとして表示するために素因数の配列を"*"で繋げる print join("*", @factors), "\n"; # 与えられた数の素因数配列を返すサブルーチン sub factorization { # サブルーチンに与えられた引数 my $arg = shift; # 2から始めて割り切れる数を探索する for my $i (2 .. $arg - 1) { # 引数を割り切ることが出来た場合 if ($arg % $i == 0) { # 変数$iは素因数として確定、引数を$iで割った値の素因数を再び探す return ($i, &factorization($arg / $i)); } } # 割り切れる数が見つからなかったらそれは素数だったということでそのままその値を返す return $arg; }
これで素因数分解の結果を表示するプログラムが出来上がっているはず。
$ chmod +x factorization.pl $ ./factorization.pl 100 2*2*5*5
ということで、このスクリプトを使ってワンライナーを作って行くことにする。
まずはコメントを削除。
#!/usr/bin/perl use strict; use warnings; my $n = $ARGV[0]; my @factors = &factorization($n); print join("*", @factors), "\n"; sub factorization { my $arg = shift; for my $i (2 .. $arg - 1) { if ($arg % $i == 0) { return ($i, &factorization($arg / $i)); } } return $arg; }
分かりやすくするために操作の返り値をわざわざ変数に代入しているけど、どうせ1回しか使われないなら変数に代入などせずにそのまま次の操作の引数にぶち込んでしまえば良い。
my $n = $ARGV[0]; my @factors = &factorization($n); print join("*", @factors), "\n";
↓ $nへの代入不要
my @factors = &factorization($ARGV[0]); print join("*", @factors), "\n";
↓ @factorsへの代入不要
print join("*", &factorization($ARGV[0])), "\n";
これでサブルーチンの呼び出しを行うメインの部分は1行に収まる。
#!/usr/bin/perl use strict; use warnings; print join("*", &factorization($ARGV[0])), "\n"; sub factorization { my $arg = shift; for my $i (2 .. $arg - 1) { if ($arg % $i == 0) { return ($i, &factorization($arg / $i)); } } return $arg; }
次はサブルーチンの部分。まずは余計な変数を削ろう。for文のループ変数$iは定義しなければデフォルト変数$_に代入されるので、それを使う。
for my $i (2 .. $arg - 1) { if ($arg % $i == 0) { return ($i, &factorization($arg / $i)); } }
↓ $iを使わない
for (2 .. $arg - 1) { if ($arg % $_ == 0) { return ($_, &factorization($arg / $_)); } }
ここからさらなる簡潔化を考える。
Perlのfor文, if文などの制御構文は
for (リスト) { 処理; } if (条件) { 処理; }
というものを
処理 for (リスト); 処理 if (条件);
という書き方にすることができるので、中身の処理が簡単なものであれば1行に簡潔にすることができる。
ただし、この後置の構文は２つ重ねることは出来ないらしい。言語仕様的に。(何でだろう？使いすぎると混乱するから？)
残念ながら
for (リスト) { if (条件) { 処理; } }
を
処理 if (条件) for (リスト);
という形に書き換えることはできない。syntax errorになってしまうのです。
ではどうすれば良いか。if文を使わずに条件分岐させれば良い。
ここで使えるのが条件演算子(三項演算子)の"?:"、もしくは論理和、論理積演算子の"&&", "||", "and", "or"など。
上のようなfor文の中のif文などは、これらの演算子を使えば
(条件) ? 処理 : next for (リスト);
(条件) && 処理 for (リスト);
と表現することができる。
論理積演算子は「左被演算子が偽であれば、右被演算子は評価さえ行なわれない」ので、まさにif文的な動きをしてくれる。if-else構文を書き換えるならば条件演算子を使うべきだろうけど、単純なif文ならこの論理積演算子を使うのが良いと思う。
参考資料：perlop - Perl の演算子と優先順位 - perldoc.jp
ということで、サブルーチン内のfor文の部分は
for (2 .. $arg - 1) { if ($arg % $_ == 0) { return ($_, &factorization($arg / $_)); } }
↓ if文を論理積"&&"で書き換え
for (2 .. $arg - 1) { ($arg % $_ == 0) && return ($_, &factorization($arg / $_)); }
↓ for文を後置させる
($arg % $_ == 0) && return ($_, &factorization($arg / $_)) for (2 .. $arg - 1);
というわけでかなり短くなってきた。
#!/usr/bin/perl use strict; use warnings; print join("*", &factorization($ARGV[0])), "\n"; sub factorization { my $arg = shift; ($arg % $_ == 0) && return ($_, &factorization($arg / $_)) for (2 .. $arg - 1); return $arg; }
ここまでくれば、もうワンライナーにすることが十分可能。頭の３行は無視して、サブルーチンの３行は全部セミコロンで繋げてしまえばいい。
$ perl -e 'print join("*", &factorization($ARGV[0])), "\n"; sub factorization { my $arg = shift; ($arg % $_ == 0) && return ($_, &factorization($arg / $_)) for (2 .. $arg - 1); return $arg; }' 100
2*2*5*5とりあえずワンライナーが完成だ！
でもちょっと長いよね。ここから文字数を削るために工夫していこう。
まず何が長いってサブルーチンの名前。ワンライナーに長いサブルーチン名なんて必要ない。識別できればいいんだから1文字でいい。fにしよう。ついでに言うと呼び出しの部分も他の関数と衝突しないのであれば"&"もつける必要ないらしい。
$ perl -e 'print join("*", &factorization($ARGV[0])), "\n"; sub factorization { my $arg = shift; ($arg % $_ == 0) && return ($_, &factorization($arg / $_)) for (2 .. $arg - 1); return $arg; }' 100↓ s/factorization/f/g;
$ perl -e 'print join("*", &f($ARGV[0])), "\n"; sub f { my $arg = shift; ($arg % $_ == 0) && return ($_, &f($arg / $_)) for (2 .. $arg - 1); return $arg; }' 100↓ s/&f/f/g;
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { my $arg = shift; ($arg % $_ == 0) && return ($_, f($arg / $_)) for (2 .. $arg - 1); return $arg; }' 100
さて、次はどこか。サブルーチンの中だな。まずスコープがはっきりしているならmy宣言は削れる。そして$argへのshift代入が無駄。代入式を括弧でくくってしまえば代入した値で評価されるので、次のfor文の中で最初に$argが使われる部分を代入式に置き換えてしまえば良い。それはforのリスト内の"(2 .. $arg - 1)"の部分。さらに言えば、名前も$argなんかじゃなくて$aで良い。
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { my $arg = shift; ($arg % $_ == 0) && return ($_, f($arg / $_)) for (2 .. $arg - 1); return $arg; }' 100↓ s/my//g;
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { $arg = shift; ($arg % $_ == 0) && return ($_, f($arg / $_)) for (2 .. $arg - 1); return $arg; }' 100↓ for文の中でshiftからの代入を行う
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { ($arg % $_ == 0) && return ($_, f($arg / $_)) for (2 .. ($arg = shift) - 1); return $arg; }' 100↓ s/arg/a/g;
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { ($a % $_ == 0) && return ($_, f($a / $_)) for (2 .. ($a = shift) - 1); return $a; }' 100
次は条件文。"$a % $_"の値が0になる、というのは"$a % $_"が偽(false)である、ということなので、0と比較せずにそのまま使ってしまえば良い。ただし次のreturnに進むための条件が逆になるので、論理積を論理和に変更する。あと括弧いらない。
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { ($a % $_ == 0) && return ($_, f($a / $_)) for (2 .. ($a = shift) - 1); return $a; }' 100↓ 0と比較せずに論理和へ
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { ($a % $_) || return ($_, f($a / $_)) for (2 .. ($a = shift) - 1); return $a; }' 100↓ 括弧も取り除く
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = shift) - 1); return $a; }' 100
次は最後のreturn。サブルーチンの返り値は最後に評価された値になるので、明示的にreturnと書かなくても$aとだけ書いておけばそれで$aが返る。ついでに言えば最後のセミコロンも省略可能ｗ
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = shift) - 1); return $a; }' 100↓ 最後のreturnを削除
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = shift) - 1); $a; }' 100↓ 最後のセミコロンも削除
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = shift) - 1); $a }' 100
引数をもってくるのに"$ARGV[0]"は長い。shiftで代用できる。ついでに言えば引数が１つならpopでも同じ。名前の短いpopの方にしよう
$ perl -e 'print join("*", f($ARGV[0])), "\n"; sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = shift) - 1); $a }' 100↓ $ARGV[0] を pop に。これでスクリプトの引数を取ってくる
$ perl -e 'print join("*", f(pop)), "\n"; sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = shift) - 1); $a }' 100↓ サブルーチン内のshiftもpopに変更。引数が１つならどちらも変わらない
$ perl -e 'print join("*", f(pop)), "\n"; sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = pop) - 1); $a }' 100
あとはなんだろう。出力時の改行コードか。これはperlのコマンドラインオプション"-l"を使えば勝手に改行して出力してくれるようになるはずなので、それを使おう。
$ perl -e 'print join("*", f(pop)), "\n"; sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = pop) - 1); $a }' 100↓ 改行コードの出力を削除、コマンドラインオプションに"-l"を追加
$ perl -le 'print join("*", f(pop)); sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = pop) - 1); $a }' 100これで相当短くなったね！この時点でコマンド本体は111文字。Twitterにだって投稿できちゃうよ！
さぁ、あとは読みやすさを捨てて不要なスペースを詰めてしまおう。join関数の括弧も削れる。for文のリストも括弧なくても大丈夫。さらにサブルーチンの定義を先に持ってくればその後に続けてメインの文が書けるからセミコロンが１つ削れる！
$ perl -le 'print join("*", f(pop)); sub f { $a % $_ || return ($_, f($a / $_)) for (2 .. ($a = pop) - 1); $a }' 100↓ 詰めても問題ないスペースは詰める
perl -le'print join("*",f(pop));sub f{$a%$_||return($_,f($a/$_))for(2..($a=pop)-1);$a}' 100↓ join関数の括弧を削る
perl -le'print join"*",f(pop);sub f{$a%$_||return($_,f($a/$_))for(2..($a=pop)-1);$a}' 100↓ for文の括弧を削る
perl -le'print join"*",f(pop);sub f{$a%$_||return($_,f($a/$_))for 2..($a=pop)-1;$a}' 100↓ サブルーチン定義を先頭に持ってくる
perl -le'sub f{$a%$_||return($_,f($a/$_))for 2..($a=pop)-1;$a}print join"*",f(pop)' 10084文字まで減った！！これで完成だ！！
さらに短くするために
ここまで来たところでロジックの変更を考えてみる。
forループに使うリストの最後を"($a=pop)-1"から"($a=pop)"に変更するとどうなるか。
$ perl -le'sub f{$a%$_||return($_,f($a/$_))for 2..($a=pop);$a}print join"*",f(pop)' 100
2*2*5*5*1最後に"1"が出てくる。
なぜならforループのデフォルト変数が最後には$aの値になるので、サブルーチンfに素数が渡っても最後には$_で割り切れてしまうから。
そして$aが素数でも$aがその素因数として数えられ、fに($a/$a)、すなわち1が渡される。fの引数が1のときはfor文が回らず、そのまま$a(=1)を返す。
と、いうことは、この場合最後に1が渡されるまでサブルーチンfはfor文の最後まで行くことがないので、この最後に$a(=1)を返すところを削除してしまえば、同じような素因数分解ロジックになるはず。
$ perl -le'sub f{$a%$_||return($_,f($a/$_))for 2..($a=pop)}print join"*",f(pop)' 100
2*2*5*5これで上記の素因数分解ワンライナーよりさらに短いものができあがる！79文字！！
ただしこの場合、コマンド引数に1が入ると空文字列が出力されてしまうので、ちょっと残念なカンジ。
オマケ
サブルーチンを定義すると同時に使う、というやり方も。
$ perl -le'print join"*",&{$f=sub{$a%$_||return($_,&$f($a/$_))for 2..($a=pop)}}(pop)' 100無名サブルーチンを$fに代入すると同時にメイン文として使うという荒技。
何となくスッキリするような気もするけど、文字数は上のものより長くなるしキモいだけかも。
