素因数分解ワンライナーの作り方 その１ - すぎゃーんメモの、続き。
前回はワンライナーの中でサブルーチンを定義し、それを再帰的に呼び出すことによって素因数分解を行っていた。
これを、サブルーチンの再帰呼び出しを使わずに表現することはできないか？
つまり、while文を用いて因数分解ができる限り繰り返す、という方法になる。
単純に考えると、
処理 while (条件); 処理：素因数を取り出し、対象の数を最小の素因数で割る 条件：対象の数が素因数を持つ
という構造になる。
ところで前回は素因数を調べるのにfor文を使って2から順番に割り切れる数を探していた。
これまた前回も書いた通り、forやwhileの後置はいずれか１つしかできない。今回while文をメインで使う以上は、for文を使わずに素因数を見つけ出さなくてはならない。
ここで、for文を使わずにリストの各要素に操作をする方法として"grep", "map"という関数がある。これを上手く使えば素因数を見つけ出せる。
例えば、15の素因数を探し出してみよう。まずは1から15までを順番に入れたリストを作る。
$ perl -le 'print (1..pop)' 15 123456789101112131415
う、見にくい。スペースを挟もう
$ perl -le '$,=" "; print (1..pop)' 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
さて、ここでgrepをかけてみる。これはリスト内からデフォルト変数$_を持ってきて、条件に合うものを探してくれる。
$ perl -le '$,=" "; print grep { $_ > 7 } (1..pop)' 15
8 9 10 11 12 13 14 15
$ perl -le '$,=" "; print grep { $_ % 3 == 0 } (1..pop)' 15
3 6 9 12 15というように、条件に合うものだけを返すことになる。
ということは、「popで取り出してきた値をそれぞれの値で割った余り」を条件に使うことができる。
popから変数に代入し、試してみよう
$ perl -le '$,=" "; print grep { $a % $_ == 0 } (1..($a = pop))' 15
1 3 5 15ktkr!! これはつまり、1から15(popして$aに代入された値)までの数値のうち、15($aに代入されたリストの最大値)を割り切ることの出来るものだけを取り出したものになる。すなわち、約数を列挙するワンライナー、ということになる。
$ perl -le '$,=" "; print grep { $a % $_ == 0 } (1..($a = pop))' 120
1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120これはこれで十分に面白い。
が、今回ここで欲しいのは最小の素因数なので、どうせ1は必ず含まれるということで2番目の要素を取り出せれば良い。
$ perl -le 'print $b = (grep { $a % $_ == 0 } (1..($a = pop)))[1]' 15
3grepした結果を配列として扱い、indexが1番の要素を取り出すことで、最小の素因数を得られた。
ちなみにこのgrepやmapで得た結果に対してshiftやpopといった操作はできないらしい。内部での実装が関係してるのかな？
さて、素因数を得る方法ができたので、次は繰り返し処理の部分だ。とりあえず$aが対象の数、$bが素因数なのだから、$bを表示させて$aを$bで割ってやればいいだけじゃないだろうか。
前回と同様、２つの処理は論理積で繋げることにする。でもこの場合"&&"じゃなくて"and"を使わないといけないらしい。演算子の優先順位の関係かな？
$ perl -le 'print $b and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a = pop)))[1]' 15
3ん？3だけ出力されて5が出てこない。何故だろう？
これは、１度目のwhile文が終わった後に再び条件を評価する際に($a = pop)が呼び出されてしまうから。
コマンドの引数は１つだけなのだから、２回目以降はpopの返り値はundefになってしまう。
繰り返されたあとはpopじゃなくて$aを使いたいのだから、最初だけpopを呼ぶようにしたい。とりあえずこうしておく。
$ perl -le 'print $b and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a = pop)))[1]' 15
3↓ ($a = pop) を ($a or $a = pop) に
$ perl -le 'print $b and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a or $a = pop)))[1]' 15
3
5こうすることで、最初に呼ばれるときだけはまだ$aが定義されていないのでpopが$aに代入され、それ以降は$aの値がそのまま使われる。
ついに素因数分解っぽくなったぞ！他の数でも試してみよう。
$ perl -le 'print $b and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a or $a = pop)))[1]' 18
2
3
3
$ perl -le 'print $b and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a or $a = pop)))[1]' 60
2
2
3
5うん、大丈夫そうだ。あとは出力の方法を工夫してやればいいだけだ。改行をやめて"*"を追加するようにしよう。
$ perl -le 'print $b and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a or $a = pop)))[1]' 60
2
2
3
5↓ perlオプション"-l"をなくし、出力を"$b"から"$b*"に
$ perl -e 'print "$b*" and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a or $a = pop)))[1]' 60
2*2*3*5*うん、かっこわるいね。どうにかして繰り返しの最後の部分を見つけ出してやりたい。
実は、繰り返しの最後の部分では$aと$bは同じ値になっている。その条件を使ってやれば良い。三項演算子の登場だ。
$ perl -e 'print $b, $a == $b ? "\n" : "*" and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a or $a = pop)))[1]' 60
2*2*3*5ここから短くまとめていってみよう。
まずは$aへのpopからの代入。$aが定義されていない場合のみpopの値を代入、という操作は"||="という演算子が使える。これは便利だ。
あとはリストをくくる括弧も省略できる。
$ perl -e 'print $b, $a == $b ? "\n" : "*" and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a or $a = pop)))[1]' 60↓ ($a or $a = pop) を ($a ||= pop) に
$ perl -e 'print $b, $a == $b ? "\n" : "*" and $a = $a / $b while $b = (grep { $a % $_ == 0 } (1..($a ||= pop)))[1]' 60↓ (1..($a ||= pop)) は括弧でくくる必要ない
$ perl -e 'print $b, $a == $b ? "\n" : "*" and $a = $a / $b while $b = (grep { $a % $_ == 0 } 1..($a ||= pop))[1]' 60
次はgrepの条件式。0と比較するならダイレクトに左辺値を評価してやれば良い。0に等しくなる、ということは偽(false)になっていれば良いのだから、notで反転させてやる。
$ perl -e 'print $b, $a == $b ? "\n" : "*" and $a = $a / $b while $b = (grep { $a % $_ == 0 } 1..($a ||= pop))[1]' 60↓ { $a % $_ == 0 } を { not $a % $_ } に
$ perl -e 'print $b, $a == $b ? "\n" : "*" and $a = $a / $b while $b = (grep { not $a % $_ } 1..($a ||= pop))[1]' 60"!"で反転させてもいいけど、優先順位が変わるのでその場合は { !($a % $_) } と括弧でくくってから反転する必要がある。
whileの条件式はこんなもので、次に左側の処理の方を縮めていこう。まず目につくのは$aへの除算。$a = $a / $b なんてまどろっこしいことはやってられない。普通に"/="演算子を使おう。
ついでにこの除算処理そのものを$aの値として扱うことができるので、出力時に登場する$aにまとめることができる。
$ perl -e 'print $b, $a == $b ? "\n" : "*" and $a = $a / $b while $b = (grep { not $a % $_ } 1..($a ||= pop))[1]' 60↓ $a = $a / $b を $a /= $b に
$ perl -e 'print $b, $a == $b ? "\n" : "*" and $a /= $b while $b = (grep { not $a % $_ } 1..($a ||= pop))[1]' 60↓ $a == $b の両辺を$bで割るイメージで ($a /= $b) == 1 と変換できる
$ perl -e 'print $b, ($a /= $b) == 1 ? "\n" : "*" while $b = (grep { not $a % $_ } 1..($a ||= pop))[1]' 60この ($a /= $b) を1と比較するのもかっこわるい。0との比較なら真偽値で評価できるので1を引くことで評価する。条件は逆になるので三項演算子も入れ替える。
$ perl -e 'print $b, ($a /= $b) == 1 ? "\n" : "*" while $b = (grep { not $a % $_ } 1..($a ||= pop))[1]' 60↓ ($a /= $b) - 1 をダイレクトに評価、"\n" と "*" を交換
$ perl -e 'print $b, ($a /= $b) - 1 ? "*" : "\n" while $b = (grep { not $a % $_ } 1..($a ||= pop))[1]' 60
あと縮められるところと言えば改行文字くらい。特殊変数$/とかがデフォルトで改行文字なので拝借してしまおう。
$ perl -e 'print $b, ($a /= $b) - 1 ? "*" : "\n" while $b = (grep { not $a % $_ } 1..($a ||= pop))[1]' 60↓ "\n" を $/ に
$ perl -e 'print $b, ($a /= $b) - 1 ? "*" : $/ while $b = (grep { not $a % $_ } 1..($a ||= pop))[1]' 60
かなり削ったぞ！最後の仕上げとしてスペースを詰めよう！実はこれ、全部詰めても大丈夫。
$ perl -e 'print $b, ($a /= $b) - 1 ? "*" : $/ while $b = (grep { not $a % $_ } 1..($a ||= pop))[1]' 60↓ スペースを詰める
$ perl -e'print$b,($a/=$b)-1?"*":$/while$b=(grep{not$a%$_}1..($a||=pop))[1]' 60一目見ただけでは素因数分解やっているようには見えないキモいワンライナーの出来上がり！
コマンド部分の長さは75文字と、前回の最短よりもさらに4文字少なくできた。
