BashでProject Euler 1の解答例をいろいろ考える

Project Euler の1問目をプログラムで解いた場合、言語によっていろんな書き方が思い浮かびますが、
特にBashなどのシェルスクリプトは結構ユニークに書けたりするので、今回はちょっとそれで遊んでみました。

全体のソースコードは gist からどうぞ。

Project Euler の1問目ってどういう問題だったっけ？

日本語版のサイトから引用
Problem 1 「3と5の倍数」

Problem 1 「3と5の倍数」
10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.
同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.

解答例

forコマンドを使用

まずは、オーソドックスな書き方から。

以下の記事がなければ、ずっと算術式嫌いなままだったはず。
Bash $((算術式)) のすべて - Qiita

※ 関数の引数に指定する値が問題文にある1000ではなく、999になっているのは、
　自身としてもとても気持ち悪いが、そこは無視でお願いしたい。

euler_001::func01() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  local _sum=0
  local i
  for i in $(seq $_limit); do
    if ((i % _num_a == 0 || i % _num_b == 0)); then
      ((_sum += i))
    fi
  done
  echo $_sum
}

euler_001::func01 999 3 5

whileコマンドを使用

今度はwhileコマンドで書きました。
readコマンドの-rオプションはなくても動作します。
-rオプションはバッグスラッシュ(\)のエスケープを無効にするためのオプションで
よくこれ付けていないためにハマったりするので、癖で付けるようにしています。

euler_001::func02() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  local _sum=0
  local i
  while read -r i; do
    if ((i % _num_a == 0 || i % _num_b == 0)); then
      ((_sum += i))
    fi
  done < <(seq $_limit)
  echo $_sum
}

euler_001::func02 999 3 5

awkを使用

これはBashではないですが、Bashスクリプト内でawkを使うこともよくある？と思いますので、
掲載してみました。

このサイトにはお世話になりました。
AWK リファレンス - UNIX & Linux コマンド・シェルスクリプト リファレンス

euler_001::func03() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  seq $_limit | awk -v num_a=$_num_a -v num_b=$_num_b '
    BEGIN {
      sum = 0
    }
    ($1 % num_a == 0 || $1 % num_b == 0) {
      sum += $1
    }
    END {
      print sum
    }
  '
}

euler_001::func03 999 3 5

bcを使用

これもBashではないですが、Bashスクリプト内でbcを使うことも(ry

euler_001::func04() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  echo $(bc << __EOM__
    sum = 0
    for (i = 0; i <= $_limit; i++) {
      if (i % $_num_a == 0 || i % $_num_b == 0) {
        sum += i
      }
    }
    print sum
__EOM__
  )
}

euler_001::func04 999 3 5

パイプを使用（Part1）

パイプは楽しい。

euler_001::func05() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  (seq $_num_a $_num_a $_limit; seq $_num_b $_num_b $_limit) \
    | sort -n \
    | uniq \
    | tr '\n' '+' \
    | sed -e 's/+$/\n/' \
    | bc
}

euler_001::func05 999 3 5

パイプを使用（Part2）

factorコマンドなんて初めて知りました。

euler_001::func06() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  seq $_limit \
    | factor \
    | awk '{print $0" "}' \
    | grep " [${_num_a}${_num_b}] " \
    | awk -F: '{a += $1} END {print a}'
}

euler_001::func06 999 3 5

パイプを使用（Part3）

これはいい感じでキモイ。

euler_001::func07() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  seq $_limit \
    | sed "0~${_num_a}b; 0~${_num_b}!d" \
    | paste -sd+ \
    | bc
}

euler_001::func07 999 3 5

ファイルを使用

これもキモイ。そして、echo * 辺りがいい味効かせている。

euler_001::func08() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  temp_dir=$(mktemp -d)
  pushd $temp_dir >/dev/null 2>&1
  touch $(seq $_num_a $_num_a $_limit | paste -sd' ') \
    $(seq $_num_b $_num_b $_limit | paste -sd' ')
  echo * \
    | tr ' ' '+' \
    | bc
  popd >/dev/null 2>&1
  rm -r $temp_dir
}

euler_001::func08 999 3 5

let × ブレース展開技を使用

1番目の解答例で紹介した記事で算術式を使ってループや条件分岐が書けることを知りました。

3.2 let × ブレース展開技

euler_001::func09() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  local _sum=0
  local i
  eval let "i={1..$_limit},'((i % $_num_a == 0 || i % $_num_b == 0)) && ((_sum += i))'"
  echo $_sum
}

euler_001::func09 999 3 5

↑ こういう書き方の場合、再帰の深さに仕様限界があるようで、1022回までが上限だそうです。
　ただ、なぜか上の書き方ではそれが引っ掛からないようで、ちゃんと計算できました。
　カンマ(,)移行を再帰ではなく、$_limitの回数分呼び出すようにしているから再帰がループ回数分深くならないためなのか。
　この辺はまだよくわかっていません。。

引用させてもらって記事投稿者の @akinomyoga さんから回答いただけました。
上記の書き方だとその記事で意味している再帰にはならないとのことです。
詳しくはコメントをご確認ください。

チューリング完全な算術式を使用

上で紹介した記事には、チューリング完全な演算ができるようにするための書き方も紹介されていたので、
そちらの解法でも試してみました。

※ 関数の引数がこれ以降999ではなく、1000になるのですが、これはただの体力切れです。

euler_001::func10() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  local -r __while='__depth = 0, __break = 0, __loop ,__break '
  local -r __loop='__depth++ ,__break || (__break = !__cond) || ((__body), __depth < 64 && (__loop, __loop)), __depth--'
  local -r __cond="i < $_limit"
  local -r __body="((i % $_num_a == 0 || i % $_num_b == 0) && (_sum += i)), i++"

  local _sum=0
  local i=0
  local __depth __break
  echo $((__while, _sum))
}

euler_001::func10 1000 3 5

数学Bで解く

これまでは掲載した解き方は比較的ネットでも見る解き方でしたが、
もっと計算方法を見直すことによって、無駄な演算をなくし、処理を速くすることができます。

※ 元々は誰かの記事を読んでこの方法を知ったのですが、
　 今検索してみるとヒットしなかったのでもしかしたら消えちゃったのかも。

以下、簡単な説明。

3 あるいは 5 の倍数の総和は， 3 の倍数の総和と 5 の倍数の総和の合計から， 15 の倍数の総和を引いた値である．
したがって， 与えられた数 p の倍数の総和さえ求められれば良い．
これは m=⌊(1000-1)/p⌋ と置けば， 以下の式で求められる．
Σ i=1からmまでのpi = p*m(m+1)/2

よって，
p=3 の時の m は 333， p=5 の時の m は 199，p=15 の時の m は 66 であることから， 
Σ i=1 から 333 までの i*3  は 166,833
Σ i=1 から 199 までの i*5  は  99,500
Σ i=1 から 333 までの i*15 は  33,165
とそれぞれ求められる．

したがって， 166,833 + 99,500 - 33,165 = 233,168 となる．

上記で書いた通り手でも解けてしまいましたが、あえてBashで実装していきます。

# $limitまでの$factorの倍数の総和を算出する。
msum() {
  local -r _factor="$1"
  local -r _limit="$2"
  # Σ i=1からmまでのpiを算出 -> p*m(m+1)/2
  local -r _m=$(( (_limit - 1) / _factor ))
  echo $(( _factor * _m * (_m + 1) / 2 ))
}

# 最大公約数（The greatest common divisor）を算出
gcd() {
  local _num_a="$1"
  local _num_b="$2"

  local _tmp
  if (($_num_a < $_num_b)); then
    ((_tmp = _num_a, _num_a = _num_b, _num_b = _tmp))
  fi

  local _r=$((_num_a % _num_b))
  until ((_r == 0)); do
    ((_num_a = _num_b, _num_b = _r, _r = _num_a % _num_b))
  done
  echo $_num_b
}

# 最小公倍数（The least common multiple）を算出
lcm() {
  local _num_a="$1"
  local _num_b="$2"

  echo $((
    _num_a * _num_b / $(gcd $_num_a $_num_b)
  ))
}

# Σ i=1からmまでのpiを算出
euler_001::func11() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  echo $((
    $(msum $_num_a $_limit) + $(msum $_num_b $_limit) - $(msum $(lcm $_num_a $_num_b) $_limit)
  ))
}

euler_001::func11 1000 3 5

数学Bで解く（awkの場合）

今度はawkで上の解き方で書いていきます。
ここまでくると、Bash書いている感じが全くしません。

euler_001::func12() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  echo "" | awk -v num_a=$_num_a -v num_b=$_num_b -v limit=$_limit '
    function gcd(num_a, num_b,    tmp, r) {
      if (num_a < num_b) {
        tmp = num_a
        num_a = num_b
        num_b = tmp
      }

      r = num_a % num_b
      while (r != 0) {
        num_a = num_b
        num_b = r
        r = num_a % num_b
      }
      return num_b
    }

    function lcm(num_a, num_b) {
      return num_a * num_b / gcd(num_a, num_b)
    }

    function msum(factor, limit,    m) {
      m = int((limit - 1) / factor)
      return factor * m * (m + 1) / 2
    }

    END {
      lcm_result=lcm(num_a, num_b)
      print msum(num_a, limit) + msum(num_b, limit) - msum(lcm_result, limit)
    }
  '
}

euler_001::func12 1000 3 5

数学Bで解く（bcの場合）

bcも関数機能あったんですね。

@akinomyoga さんからコメントいただき、 bc の関数では auto でローカル変数を宣言できるようです。
（以下の実装例は auto 未使用版）

euler_001::func13() {
  local -r _limit="$1"
  local -r _num_a="$2"
  local -r _num_b="$3"

  echo $(bc << __EOM__
    define gcd(num_a, num_b) {
      if (num_a < num_b) {
        tmp = num_a
        num_a = num_b
        num_b = tmp
      }

      r = num_a % num_b
      while (r != 0) {
        num_a = num_b
        num_b = r
        r = num_a % num_b
      }
      return num_b
    }

    define lcm(num_a, num_b) {
      return num_a * num_b / gcd(num_a, num_b)
    }

    define msum(factor, limit) {
      m = (limit - 1) / factor
      return factor * m * (m + 1) / 2
    }

    lcm_result=lcm($_num_a, $_num_b)
    print msum($_num_a, $_limit) + msum($_num_b, $_limit) - msum(lcm_result, $_limit)
__EOM__
  )
}

euler_001::func13 1000 3 5

まとめ

行数が短ければ、Bashは書いてて面白い。