ループ変数をクロージャで包む

Gauche で確認コードを書いてみました。

(use srfi-42) ; list-ec

(define (f)
  (list-ec (: i 0 3)
           (lambda () i)))

(define (g)
  (rlet1 lis ()
    (do ((i 0 (+ i 1)))
        ((= i 3))
      (push! lis (lambda () i)))))

実行結果です。

gosh> (map (lambda (f) (f)) (f))
(0 1 2)
gosh> (map (lambda (f) (f)) (g))
(2 1 0)

ハミング数

Gauchedata.heap モジュール を使ってハミング数を求めてみます。(効率は悪いです)

(use data.heap)
(use gauche.generator)

(define (hamming n)

  (define (gen)
    (generate
     (^[yield]
       (let1 heap (make-binary-heap)
         (binary-heap-push! heap 1)
         (let loop ()
           (let1 v (binary-heap-pop-min! heap)
             (yield v)
             (dolist (x '(2 3 5))
               (binary-heap-push! heap (* v x)))
             (loop)))))))

  ;; 連続する重複値は流さないジェネレータ
  (define (distinct g)
    (let1 head (g)
      (generate
       (^[yield]
         (yield head)
         (let loop ((prev head))
           (let1 curr (g)
             (unless (eqv? prev curr)
               (yield curr))
             (loop curr)))))))

  (generator->list (distinct (gen)) n))

実行結果です。

gosh> (hamming 30)
(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80)

参考:

ソート後の移動先インデックスを求める

配列をソートしたときの移動先インデックスを知りたい場合があります。
D 言語だと topNIndex 関数で知ることが出来ます。

import std;

void main() {
    auto a = [99, 1, 100, 2, 150];
    auto id = new int[a.length];
    a.topNIndex(id, Yes.sortOutput);
    foreach (i; 0..a.length) {
        writefln("a[%d] = %d", id[i], a[id[i]]);
    }
}

実行結果です。

a[1] = 1
a[3] = 2
a[0] = 99
a[2] = 100
a[4] = 150

競プロ(AtCoder)の問題を D 言語で解くための Tips

これは Competitive Programming (2) Advent Calendar 2018 の 12 日目の記事です。

競プロの問題を D 言語で解くための Tips を集めました。
オンラインジャッジサイトによって、D 言語のコンパイラのバージョンは異なりますので、この記事では、 AtCoder での現時点(2018/12/12)のコンパイラバージョン(DMD64 v2.070.1)を想定しています。

配列の要素を一気に書き換える

a[] = 100 と書くと、配列 a の要素を全て 100 に書き換えることができます。

import std.stdio;

void main() {
    int[3] a;   // 要素は 0 で初期化されます
    writeln(a); // [0, 0, 0]
    a[] = 100;  // 全ての全てを 100 で書き換える
    writeln(a); // [100, 100, 100]
}

2 次元配列の使い方

import std.stdio;

void main() {
    auto a = new int[][](2, 3);
    writeln(a);           // [[0, 0, 0], [0, 0, 0]]
    writeln(a.length);    // 2
    writeln(a[0].length); // 3

    a[0][1] = 100;
    writeln(a); // [[0, 100, 0], [0, 0, 0]]
}

配列の最大値、最小値を求める

reduce を使います。

import std.algorithm;
import std.stdio;

void main() {
    int[] a = [3, 1, 4, 1, 5];
    writeln(a.reduce!((a, b) => min(a, b))); // 1
    writeln(a.reduce!((a, b) => max(a, b))); // 5

    // こう書くこともできます
    writeln(a.reduce!min); // 1
    writeln(a.reduce!max); // 5
}

minElement, maxElement2.072.0 から追加されましたが、AtCoderコンパイラは 2.070.0 なので残念ながら使うことは出来ません。

Set を使う

C++set クラスに相当するクラスは D 言語の標準ライブラリにはありません。代わりに連想配列を使います。

import std.stdio;

void main() {
    bool[int] set;

    foreach (x; [3, 1, 4, 1, 5, 9, 2]) {
        set[x] = true;
    }

    writeln(set.length); // 6
    writeln(1 in set ? "yes" : "no"); // yes
    writeln(set.keys); // [5, 4, 3, 2, 1, 9]
}

スタック、キューを使う

D 言語の標準ライブラリには、スタック、キューは用意されていませんが、 DList クラスがスタック、キューの代わりになります。

スタックとしての使い方:

import std.container;
import std.stdio;

void main() {
    auto stack = DList!int();
    writeln(stack.empty); // true

    // スタックにプッシュ
    stack.insertBack(10);
    // スタックの要素をピーク
    writeln(stack.back); // 10
    stack.insertBack(20);
    writeln(stack.back); // 20

    // スタックからポップ
    stack.removeBack();
    writeln(stack.back); // 10
}

キューとしての使い方:

import std.container;
import std.stdio;

void main() {
    auto queue = DList!int();
    writeln(queue.empty); // true

    // キューに値を格納する
    queue.insertBack(10);
    queue.insertBack(20);

    // キューから値を取り出す
    int x = queue.front;
    writeln(x); // 10
    queue.removeFront();
}

タプルに名前が付けられる

import std.stdio;
import std.typecons;

alias Point = Tuple!(int, "x", int, "y");

void main() {
    auto p = Point(10, 20);
    writeln(p);   // Tuple!(int, "x", int, "y")(10, 20)
    writeln(p.x); // 10
    writeln(p.y); // 20
}

べき乗演算子

べき乗演算子が定義されている言語について調べてみました。

D

int x = 2 ^^ 10; //=> 1024

Haskell

Prelude> 2 ^ 10
1024

JavaScript

> 2 ** 10
1024

Julia

julia> 2 ^ 10
1024

Mathematica

In[1]:= 2 ^ 10

Out[1]= 1024

Python

>>> 2 ** 10
1024

Ruby

[1] pry(main)> 2 ** 10
=> 1024

探したけど定義がなさそうだった言語:

オイラーのトーシェント関数

オイラーのトーシェント関数は、以下の形で表すことができます(正確な定義は オイラーのφ関数 - Wikipedia にあります)。

\varphi(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})

この式の括弧内の分母を揃えます。

\varphi(n) = n (\frac{p_1 - 1}{p_1}) (\frac{p_2 - 1}{p_2}) \cdots (\frac{p_k - 1}{p_k})

プログラムで値を得るときは、この式を元に以下のように計算していました。

import std.experimental.all;

int totient(int n) {
    int ret = n;
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            ret = ret / p * (p - 1);
            while (n % p == 0) n /= p;
        }
    }
    if (n != 1) ret = ret / n * (n - 1);
    return ret;
}

void main() {
    writeln(iota(1, 20).map!totient);
    //=> [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18]
}

npca2013年部誌_競技プログラミングと初等整数論入門(PDF) と読むと、 この関数を次のように計算していました。

int totient2(int n) {
    int ret = n;
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            ret -= ret / p; // ここが違う
            while (n % p == 0) n /= p;
        }
    }
    if (n != 1) ret -= ret / n; // ここが違う
    return ret;
}

こちらのほうが計算が単純になっていますね。この計算方法がどこから来るのか考えてみます。

最初の式に戻りますと、

\varphi(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})

この式の最初の n(1 - \frac{1}{p_1}) を掛けると

\varphi(n) = (n - \frac{n}{p_1}) (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})

となります。最初の括弧内の項では、n から \frac{n}{p_1} を引いています。 次に最初の括弧内の項を A と置くと

\varphi(n) = A (1 - \frac{1}{p_2}) \cdots (1 - \frac{1}{p_k})

となり、A を展開すると

\varphi(n) = (A - \frac{A}{p_2}) \cdots (1 - \frac{1}{p_k})

となります。ここで行っているのは、A から \frac{A}{p_2} を引いています。
つまり、これは ret -= ret / p がやっていることなのですね。

参考

D言語: recurrence の練習

import std.experimental.all;

void main() {
    // 初項 1, 公差 2
    auto a = recurrence!((a, n) => a[n-1] + 2)(1);
    writeln(a.take(10));
    //=> [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

    // 初項 3, 公比 2
    auto b = recurrence!((a, n) => a[n-1] * 2)(3);
    writeln(b.take(10));
    //=> [3, 6, 12, 24, 48, 96, 192, 384, 768, 1536]

    // フィボナッチ数列
    auto fibs = recurrence!((a, n) => a[n-2] + a[n-1])(1, 1);
    writeln(fibs.take(10));
    //=> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

    // 三角数
    auto t = recurrence!((a, n) => a[n-1] + n)(0).drop(1);
    writeln(t.take(10));
    //=> [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
}

参考