Project EulerをD言語でワンライナーで解く。(Problem 1 to 5)

`Project Euler`をD言語でワンライナーという制約のもとで解いていきます。
これは、最近自分の中で破壊的代入が悪なのではないか、と考え、ラムダ計算(理解が十分ではないため、間違っていたらごめんなさい)を用いることで破壊的代入を極力減らそうとしてみたところ個人的に面白いコードが生まれたのでD言語の表現力の豊かさを示す例として提示しようと考えたからです。
それゆえに、一瞬`Lisp`っぽく見えるかもしれませんが、安心してください、D言語です。
自明な破壊的代入を避けるために再帰を多用しています。

ただし、流石に無名再帰が使えないと厳しいので`Z Combinator`を以下のテンプレートで定義してそれを用います。

```d
R delegate(Args) Z(R, Args...)(R delegate(R delegate(Args), Args) f){
  return (Args args) => f(Z(f), args);
}
```

ここではワンライナーとは`main`関数内部に一文しか書かかれていないものと定義します。(それゆえ、`import`や`main`関数の定義などは行数に含めません。)
また、基本的に自分で解いた時のコードを貼り付けますが、一部自分の解法ではどうにもワンライナーに落とし込んだのが面倒なときに限り、(当然ですが)自分が一度正解した後に他の方のコードを参考にしてコードを作成しています。(それでも途中で面倒くさくなって諦めてしまい一部複文になってしまっているコードも存在しますが、時間があればいずれ修正します。)
また、可読性を考慮し、適当にインデントしています。
それから、D言語の型推論を最大限に用いて変数(ラムダ式の引数)の型はできるだけ省略します。
ちなみに、コードは下から順に読んでいくことになります(引数として値を与えているので実引数が下の方に来て、仮引数が上の方に来ます)。

問題はProject Eulerの公式サイトで、Creative Commons 2.0 表示-非営利-継承 のもとで公開されている原文を、Puki WikiのProject Eulerの日本語訳のページから引用しています(こちらも同様に Creative Commons 2.0 表示-非営利-継承 の元で公開されています)。
公式サイト : [projecteuler.net](https://projecteuler.net)
日本語訳Wiki : [odz.sakura.ne.jp/projecteuler/](http://odz.sakura.ne.jp/projecteuler/)


では、さっそくはじめましょう。

#Problem 1
>If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
>
>Find the sum of all the multiples of 3 or 5 below 1000.

日本語訳

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

これはまぁ、単純にNを0から999まで1つずつ増やしていき、そのNに対して順に

* 単純に3と5の最小公倍数である15の倍数であるかどうか
* そうでなければ5の倍数であるかどうか
* そうでなければ3の倍数であるか

というのを調べていけば良さそうですね。
それをコードに落とし込んだのが以下

```d
import std.stdio,
       std.range,
       std.algorithm;

void main() {
  (1000.iota.filter!(x =>
    (x % 15 == 0 ? true
    : x % 5 == 0 ? true
    : x % 3 == 0)).sum).writeln;
}
```

このようにして解くことが出来ます。

次に参りましょう。


#Problem 2
>Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
>
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
>
>By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

日本語訳

>フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
>
>1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
>数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

なるほど〜、ここではフィボナッチ数列を扱わなければなりません。
手続きっぽく順当に現実的な時間で解を得ようと思うと思うとメモ化を用いて条件を満たすまでループさせてその時に総和を計算する解法が簡単に浮かびます。
しかし、今回はその手法が使えないので再帰で解くことを考えます。

その結果が以下

```d
import std.algorithm,
       std.range,
       std.stdio;

R delegate(Args) Z(R, Args...)(R delegate(R delegate(Args), Args) f){
  return (Args args) => f(Z(f), args);
}

void main() {
  (max => 
    (solver =>
      solver(1, 0, 0)
    )(Z((ulong delegate(ulong, ulong, ulong)solver, ulong n1, ulong n2, ulong sum) =>
        n2 < max ? solver(n1 + n2, n1, n2 % 2 == 0 ? sum + n2 : sum) : sum
      ))
  )(4000000).writeln;
}
```

コードの解説としては、`solver`の中で無名再帰を行い、フィボナッチ数列を計算しています。ここで、`n`回目の呼び出しのときに`n2`はフィボナッチ数列の第`n`項となっています。
そして、`n2`が偶数であるならばそれをsumに加えて再び再帰を繰り返します。
同様に再帰を繰り返し、ある`N`回目に`n2`が400万を超えた時、再帰を終了し`sum`を返します。
ここでポイントはコードを少しでも短くしようと思えば`solver`の中身を以下のように書き換えることも出来ます。(先ほどのコードは問題文に対して素直に書いたものです)

```d
n2 < max ? solver(n1 + n2, n1, sum + n2) : sum / 2
```

こうすることでとりあえず`n2`が400万になるまでの全部のフィボナッチ数の総和を計算し、`n2`が400万以上になった時にその総和を2で割って解を得ています。


では、次に参りましょう


#Problem 3
>The prime factors of 13195 are 5, 7, 13 and 29.
>
>What is the largest prime factor of the number 600851475143 ?

日本語訳

>13195 の素因数は 5, 7, 13, 29 である.
>
>600851475143 の素因数のうち最大のものを求めよ.

今回(Problem 1 to 5)のなかで一番苦労したのがこの問題であり、唯一複文になってしまいました(`while`や`foreach`を無名関数の再帰に置き換えることで解消できると思いますが、コードが長くて面倒くさくなってしまったので妥協しました)。
また、僕の解法ではワンライナーに落とし込んだのが大変だったので以下のリンク先を参考にさせていただきました。
[CodeIQ のアルゴリズム問題「チョコの量を減らせ！」by @hyuki に解答しました](http://antimon2.hatenablog.jp/entry/2013/02/15/214029)

ここでは、`600851475143`という巨大な数の素因数を考えなければなりません。したがって、素因数分解する必要があります。そこで、先ほどの方が実装されいたアルゴリズムを参考にして素因数分解を実装します。

素因数分解の実装も含めて解答に用いたコードが以下

```d
import std.algorithm,
       std.random,
       std.range,
       std.stdio;

R delegate(Args) Z(R, Args...)(R delegate(R delegate(Args), Args) f){
  return (Args args) => f(Z(f), args);
}

void main() {
  (N => 
    (getRand =>
      (mr_prime => 
        (rho_find_pd =>
          (rho_prime_division =>
            rho_prime_division(N, false).join.sort!"a>b".uniq.array[0]
          )(Z((ulong[][] delegate(ulong, bool) rho_prime_division, ulong n, bool suppress_sort) =>
            mr_prime(n) ?
              [[n, 1]]
            : (d =>
                (ulong[][] res) {
                  foreach (arr; rho_prime_division(d, true)) {
                    (cnt => 
                      (q, k) {
                        while (n % q == 0) {
                          n /= q;
                          cnt++;
                        }
                        res ~= [q, cnt];
                      }(arr[0], arr[1])
                    )(0);
                  }

                  res ~= rho_prime_division(n, true);
                  return suppress_sort ? res : res.sort.array;
                }([[]])
              )(rho_find_pd(n))
          ))
        )((ulong n) => 
          (gcd =>
            (f_gen =>
              (k) {
                  foreach (_; k.iota) {
                    return ((ulong delegate(ulong) f) => 
                      ((ulong d, ulong x, ulong y) {
                        while (d == 1) {
                          x = f(x);
                          y = f(f(y));
                          d = gcd(n, (z => z < 0 ? z * -1 : z)(x - y));
                        }

                        return d < n ? d : n;
                      })(1, 2, 2)
                    )(f_gen());
                  }
                  return true;
              }(3)
            )(() => 
              (c) {
                while(!(c != 0 && c != n - 2)) {
                  c = getRand() % n;   
                }
                return ((ulong x) => (x * x + c) % n);
              }(getRand() % n)
            )
          )(Z((ulong delegate(ulong, ulong) gcd, ulong a, ulong b) => b ? gcd(b, a%b) : a < 0 ? a * -1 : a))
        )
      )((ulong n) =>
        (mod_pow =>
          (_d => 
            (d => 
              (k) {
                foreach(_; k.iota) {
                  if (!
                      (a =>
                        (t =>
                          (y) {
                            while (t != n-1 && y != 1 && y != n-1) {
                              y = (y * y) % n;
                              t <<= 1;
                            }

                            if (y != n - 1 && (t & 1) == 0) {
                              return false;
                            } else {
                              return true;
                            }
                          }(mod_pow(a, t, n))
                        )(d)
                      )(getRand() % (n - 1) + 1)) {
                        return false;
                      }
                }

                return true;

              }(20)
            )((d) {
              while((d & 1) == 0) {
                d >>= 1;
              }
              return d;
            }(_d))
          )(n - 1)
        )((ulong base, ulong pwr, ulong mod) =>
          (ulong r) {
            while (pwr > 0) {
              if((pwr & 1) == 1) {
                r = (r * base) % mod;
              }
              base = (base * base) % mod;
              pwr >>= 1;
            }
            return r;
          }(1)
        )
      )
    )(() =>
      ((Mt19937 gen) =>
        (gen.seed(unpredictableSeed), gen.front)
      )(Mt19937.init)
    )
  )(600851475143).writeln;
}
```

一部、破壊的代入や複文を含むため、個人的にはすごく再帰で書き直したいと思いますが時間がないのでいずれ時間があれば書き直します。

解法はまぁ単純に、素因数分解して、`sort`して素因数の最大を取り出しているだけです。

次に参りましょう


#Problem 4
>A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
>
>Find the largest palindrome made from the product of two 3-digit numbers.

日本語訳

>左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
>
>では, 3桁の数の積で表される回文数の最大値を求めよ.

なるほど〜、これはひとけたずつ取り出して逆順にしていったものが元の数字と一致するかで判定ができそうですのでその方針で実装します。
それが以下

```d
import std.algorithm,
       std.random,
       std.range,
       std.stdio;

R delegate(Args) Z(R, Args...)(R delegate(R delegate(Args), Args) f){
  return (Args args) => f(Z(f), args);
}

void main() {
  (M =>
    (N =>
     (cond => 
        M.map!(m => N.map!(n => m * n)).join.filter!(x => cond(x)).array.sort!"a>b".array[0]
      )((ulong number) => 
        (condSub =>
          condSub(number, 0, 0, number)
        )(Z((bool delegate(ulong, ulong, ulong, ulong) condSub, ulong number, ulong remaind, ulong reverse, ulong tmp) =>
            (remaind =>
              (reverse =>
                (tmp =>
                  tmp != 0 ? condSub(number, remaind, reverse, tmp) : reverse == number
                )(tmp / 10)
              )(reverse * 10 + remaind)
            )(tmp % 10)
          ))
      )
    )(100.iota(1000))
  )(100.iota(1000)).writeln;
}
```

まー、こうなります。ポイントは`mod 10`で桁をとりだす、ぐらいですかね。

それでは今回の最後に参りましょう


#Problem 5
>2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
>
>What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

日本語訳

>2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
>
>では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

なるほど、最小公倍数を求めればいいっぽいですね。
`lcm`を実装すればあとはそれを用いて`foldl1(D言語ではreduce)`に渡せば解が得られそうですね。
`lcm`を実装するために、`gcd`も実装します。

すべてを実装し、解答に用いたコードが以下

```d
import std.algorithm,
       std.random,
       std.range,
       std.stdio;

R delegate(Args) Z(R, Args...)(R delegate(R delegate(Args), Args) f){
  return (Args args) => f(Z(f), args);
}

void main() {
  (N =>
    (gcd => 
      (lcm =>
        1.iota(N).reduce!((a, b) => lcm(b, a))
      )((int a, int b) => a * b / gcd(a, b))
    )(Z((int delegate(int, int) gcd, int a, int b) => b ? gcd(b, a%b) : a < 0 ? a * -1 : a))
  )(20).writeln;
}
```

コンパクトですね〜
これは単純に1~20の最小公倍数を求めるだけです。というのも、
1 から 20 までの整数全てで割り切れる数字の中で最小の正の数 ⇔ 1から20までの各数の最小公倍数
となるからです。



#まとめ
以上でD言語でワンライナーという制約のもとで`Project Euler`の`Problem 1`から`Problem 5`を解いてみました。
D言語は`C/C++`に代表される手続き形のようにも書くことも出来ますし、上に示したようにも書くことが出来ます。
D言語の表現力の豊かさを示せたでしょうか?

とりあえず、今回はここまで。
時間(と需要)があればいずれ`Problem 6`以降についても記事を書きます