シェル芸 Project Euler - Problem 5

はじめに

@gin_135 さんの「Project Eulerをシェル芸で解いてみる」シリーズが大変面白いです.
大抵は @gin_135 さんの Qiita 投稿, @eban さんの別解 on ブログ, @MasWag さんの別解 on Twitter を楽しく読ませていただき, 読んだだけで分からないものは, 手元で再現などして楽しんでいますが, 方針として大きく異なる別解を思いついたものについて, 自分のエントリを立てようと思います.

「Project Euler」の解説, 問題文の引用などは省略します.

本エントリは Problem 5 (問題原文, 問題文日本語訳) の解答です.

環境は

$ /bin/sh --version
GNU bash, version 3.2.57(1)-release (x86_64-apple-darwin15)
Copyright (C) 2007 Free Software Foundation, Inc.

です.

方針

本題は, 数列に対する「二引数の最小公倍数演算」の「畳み込み」です.
(畳み込みって何? という方は「左畳み込み in シェル」をご覧ください)

最小公倍数スクリプトと左畳み込みスクリプトを用意して連結します.

最小公倍数

lcm

#!/bin/sh

ab=`expr $1 \* $2`
while [ 0 -lt $1 ]
do
  t=`expr $2 % $1`
  set $t $1
done
echo `expr $ab / $2`

を lcm としてカレントディレクトリに保存し, 実行パーミションを与えます.

while ... done の部分でユークリッドの互除法で最大公約数を計算し, expr $ab / $2 で最小公倍数を出力しています.
繰り返し中に明示的に名前を与えた二つの変数を使ってもよいのですが, set を使って $1 と $2 を使い回しています.
そのため, 後で使う $1 と $2 の積を最初に変数 ab に代入しています.

実行例です.

$ ./lcm 12 18
36
$ ./lcm 18 27
54

左畳み込み

reduce

#!/bin/sh

f=$1
i=$2
if [ "X$i" = "X" ]
then
  read i
fi
while read line
do
  set "$i" "$line"
  i=`eval $f`
done
echo $i

を reduce として保存し, PATH に含まれるディレクトリに保存 (または保存したディレクトリを PATH に追加), 実行パーミションを与えてあるとします.

解説は「左畳み込み in シェル」にあります.

例題解答

1 から 10 までの整数で割り切れる最小の正の整数は 2520 です.

% seq 10 | reduce './lcm $1 $2'
2520

本題解答

本題, 1 から 20 までの整数で割り切れる最小の正の整数は, 例題同様

% seq 20 | reduce './lcm $1 $2'

のようにします.

1 から 10 までの整数は 11 から 20 までの整数の約数ですので,

% seq 11 20 | reduce './lcm $1 $2'

としても同じ結果が得られます.

参考

@gin_135 さんの解答「Project Eulerをシェル芸で解いてみる(Problem 5)」
@MasWag さんの解答ツイート
@eban さんの解答「Project Euler Problem 5 #シェル芸 - jarp」
@eban さんの解答ツイート (抽象的な意味では私とまったく同じ方針)