D言語で分割代入がしたかった

TL;DR

  • テンプレートよくわからない。助けて。

本編

1行で入力を取りたい

競プロでしばしばこんな文面を見ますよね:

入力は以下の形式で与えられる。 X Y Z

X, Y, Zが整数だったとして、これを例えばpythonで受け取りたければ1行でこう書けます:

X, Y, Z = map(int, input().split())

ところがD言語には分割代入の仕組みがないので、通常こう書くしかありません (追記: readfという便利な関数があるのを教えていただきました。これで十分でしたね……。) :

int X, Y, Z;
auto line = readln.chomp.split.to!(int[]);
X = line[0];
Y = line[1];
Z = line[2];

長いのはもちろんのこと、今後一生使わない変数lineがスコープを汚すのも気に食わない感じがします。 そんなわけで、もう少しすっきりさせたいね、と思ったので簡単なmixinを書きました。

import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

// 「read words as T into D」 のつもり
string readAsInto(T, string D)() {
  return
    T.stringof ~ " " ~ D ~ ";"
  ~ "foreach(tup; zip("
    ~ "[" ~ (D.split(",").map!(s => "&" ~ s.strip).join(",")) ~ "],"
    ~ "readln.chomp.split.to!(" ~ T.stringof ~ "[])"
  ~ ")) *tup[0] = tup[1];";
}

これを使うと先の入力はこのように受け取れます:

mixin(readAsInto!(int, "X, Y, Z"));

短くてめでたい。

分割代入したかった

ところで、さっきのmixinは標準入力を受け取る用途に特化しすぎています。 より一般的に分割代入ができるようにmixinを書き直してみたのですがあまりうまくいかず。 多分テンプレート分かってない。 以下は迷走の記録です。

mixin()に放り込む文字列はコンパイル時に確定していて、かつ合法なソースコードでなければなりません。したがって、文字列の生成は関数ではなくテンプレートによって行う必要があります。

ここで必要になるテンプレートは「変数名の列と値の列を受け取って、各変数を宣言し、各値を代入する」ようなソースコードの文字列を生成するものですので、シグネチャは(気持ち的には)多分こんな感じです:

string decomposeInto(InputRange!E r, string D)() {
    // ...
}

当然ですが型変数Eが未定義なので上のコードは非合法です。どうしよう。

1. alias を使う

そういえば library reference でテンプレート引数をaliasにしているのを見かけたことがあります。Language reference 読んでも正直意味がよく分かりませんでしたが、まあ手を動かせば何か分かるかも知れんしと思い、ものは試しで以下のように書きました:

string decomposeInto(alias R, string D)() {
  return 
    (ElementType!(typeof(R))).stringof ~ " " ~ D ~ ";"
  ~ "foreach(tup; zip("
    ~ "[" ~ (D.split(",").map!(s => "&" ~ s.strip).join(",")) ~ "],"
    ~ R.stringof
  ~ ")) *tup[0] = tup[1];";
}

これを次のようにして使います:

void main() {
  auto a = readln.chomp.split.to!(int[]);
  mixin(decomposeInto!(a, "X, Y, Z"));
  X.writeln;
}

> rdmd test.d
1 2 3
1

動くじゃん。

しかし！main()を以下のように書き直すと……

void main() {
  // 変数 a を省略しただけ
  mixin(decomposeInto!(readln.chomp.split.to!(int[]), "X, Y, Z"));
  X.writeln;
}
> rdmd test.d
test.d(9): Error: identifier 'chomp' of 'readln.chomp.split.to!(int[])' is not defined
test.d(10): Error: undefined identifier 'X'

という謎エラーで怒られます。なんで……？

2. 型変数 E を定義する

やっぱりよく分かっていないものを使うとうまくいきません。分かる範囲でどうにかしましょう。

要はEが定義できればよかろうということで次のように書きました:

template decomposeInto(E) {
  string decomposeInto(InputRange!E R, string D)() {
    // ...
  }
}

冗長ですが仕方がないので以下のようにして呼びます:

auto a = readln.chomp.split.to!(int[]);
mixin(decomposeInto!int.decomposeInto!(a, "X, Y, Z"));

すると:

> rdmd test.d
test.d(11): Error: cannot resolve type for decomposeInto!int
test.d(12): Error: undefined identifier 'X'

詳しいことを何も教えてくれないこの謎のエラーは、テンプレート名と関数名を別にすることでなぜか解消します*1。しかし今度は

>rdmd test.d
test.d(11): Error: variable a cannot be read at compile time
test.d(11):        while looking for match for hoge!(a, "X, Y, Z")
test.d(12): Error: undefined identifier 'X'

と怒られます。いや確かに考えてみればそれはそう。でもじゃあなんでaliasなテンプレート引数は実行時に渡しても怒られないんだ……？というかaliasって何？

D言語くんと対話できない

別にどうしても分割代入を書きたくて苦しんでいるわけではなく、吐かれたエラーを理解できないところで苦しんでいます。D言語くんと真に仲良くなれる日は訪れるのでしょうか。

おわりに

こんな本質から外れたことばっかやってるから水色になれないんだぞ。

*1:本当になんで？

On Error Resume Next (解決編)

大抵は自分が間違えている

前回の記事でエラーを解決せずに全部投げてオチをつけてしまいましたが、片がついたのでメモを残します。

clear を呼べない問題

Point[] 型の変数 buf に対して buf.clear を呼ぶと cannot deduce で以下の通り怒られた問題について:

Error: template `object.clear` cannot deduce function from argument types `!()(Point[])`
candidates are:
  `object.clear(T : Value[Key], Value, Key)(T aa)`
  `object.clear(T : Value[Key], Value, Key)(T* aa)`

ただのエラーメッセージ読め案件だったので恥ずかしいんですが、上記を読むとどうもobjectモジュールのclearテンプレートを展開しようとして失敗していますね。 僕が呼びたいのは Point[] 型の clear メソッドなんですけど……？ UFCS って obj.method(a, b, ...) に合うシグネチャのメソッドが見つからなかったときに初めて method(obj, a, b, ...) を探しに行くんじゃなかったんです？

しかし愚かなのは僕の方でした。 そうです、D言語の動的配列に clear メソッドは存在しないのです。 clear が存在するのは Appender オブジェクトか std.container モジュールに収められているコンテナオブジェクトだけです。 当然動的配列にもあるもんだと思っていた……。

というわけで、この問題の解決法は buf.clear を以下の通り修正することです:

// 再代入する
buf = [];

// length プロパティは set 可能なのでこれでもよい
buf.length = 0;

cannot deduce とか言われると推論のための情報が足りないのかと思ってしまうけど、そもそも呼ぶ対象を間違えているケースがあるのだと知りました。なるほどなあ。

SList!Point を使うと RE する問題

bufの型を SList!Point にすると buf.clear でもコンパイルが通ります。 通りますし、手元(DMD v2.083.0)でも動きますが、ジャッジサーバ(DMD v2.070.1)では全ケース RE になります。

こればっかりはソースをいくら睨んでも解決しないと思ったので、ジャッジサーバの環境を手元に入れました。 仮想環境組むの面倒だったんで、手元の環境一度アンインストールして古い実行環境を再インストールするとかいうよわよわムーブを見せつけてしまった。

余談ですが、アンインストーラを走らせたらD言語環境関連のあれこれがしっかりディスクから取り除かれるのに、なぜかD/dmd2/html/d/images/compiler-dmd.pngだけが残ったんですよ。 それがコイツなんですけど:

f:id:penpenpng:20190611191433p:plain

D言語くんは死んでなんかいない……今も君のディスクの中にいるよ……*1。

閑話休題。とあるコードが手元(DMD v2.083.0)では走るのにジャッジサーバ(DMD v2.070.1)では実行時に落ちるという話でした。 その問題のコードの抜粋がこちら:

SList!Point buf;

// 中略

buf.insert(Point(x, y));

こちらをジャッジサーバ環境で走らせると、なるほど確かに実行時エラーを吐きますね:

core.exception.AssertError@std\container\slist.d(57): Assertion failure

すると気になるのは std\container\slist.d(57) です。ちょっと覗いてみます:

struct SList(T)
{

    // ……中略……

    private Node * _root;

    private void initialize() @trusted nothrow pure
    {
        if (_root) return;
        _root = cast (Node*) new NodeWithoutPayload();
    }

    private ref inout(Node*) _first() @property @safe nothrow pure inout
    {
        assert(_root);        // 57行目
        return _root._next;
    }

    // ……中略……

}

_root が null なので怒られたらしいですね。 これ、もしや SList が初期化されてないだけでは？

というわけで解決策は buf 変数を宣言時に初期化しておくことです:

auto buf = make!(SList!Point);

めでたしめでたし*2。

おわりに

ちょっとだけD言語くんと仲良くなれる兆しが見えたかもしれない。 それはそれとして、どうせ競プロのためにしか使わないなら手元のコンパイラのバージョンをジャッジサーバのものと揃えておくのが無難っぽいですね。

*1:正直怖かった。

*2:RE は解消されたがそもそも計算量がアレで TLE になったというオチがつく。

On Error Resume Next

あたまがはてな

お久しぶりです。大体2ヶ月ぶりになりますね。まあTwitterには毎日いるんですが。

本当はもっと早く何か書きたかったんですが、就活のために棚上げにしていたありとあらゆるタスク*1に囲われ袋叩きにされる生活がここのところ続いていてそれどころではなかったという事情があります。

ということで、2ヶ月ほど遅れての報告になりますが、内定をいただきました。 聡明な皆さんは今日の日付と2ヶ月前の投稿頻度を見比べて何かに気づいたりもしたでしょうが、そこはそれ: この "はてなぶろぐ" って奴を吸うとな……頭がスゥーーー…っとして現実のことなんてみんな忘れちまえるんだ……お前さんもどうだい？

ニシキヘビは足が遅い

今日の記事はほとんど技術ポエムみたいなもんなのでTLDRもないし、見出しにも情報がないです。あしからず。

最近まわりで競プロ始める人が多いんですよ。 就活控えた情報畑の人とかはまあなんか分かるんですけど、今までプログラミングのプの字も見せなかった人までなぜだかこぞってatcoderで遊んでいます。 なんで？まわりの人が偏ってるから？

それで感化されてというか、先日のabc129に参加しました。 久しぶりの参加、そして元よりよわよわ緑マンとは言え、過去最低級のパフォーマンスを叩き出して少しカチンと来た*2ので、暇をみて修行しようと心に決めました。暇くれ。

ところで本題はここからです。 先日のコンテストには python で参加したのですけど、あの言語遅っそいですね。知ってたけど。 D問題結局 TLE*3 で通せなかったので慣れない C で書き直して時間食いました。本当に悔やまれる。

あー、どっかに LL みたいにさらっと書けるコンパイラ言語いないかな～～～。

もしや今こそD言語くんと再び対話するときなのではないか……？

以前僕はD言語ニワカ勢としてちょびっと記事を書いたりしましたが、あれからめっきり触らなくなってしまったのでもはや何も覚えてません。 いや、文法は好きなんだけどいかんせん用事がなくって……。

いい機会なので先日の問題をD言語で解き直してみようかなと思ったわけです。

D言語くんは言うことを聞かない

既に python で書いたコードばかりなので、写すだけだし楽勝やろと思ってたんですよ。

A - Airplane

3点 A, B, C と各点間の距離が与えられたとき、すべての点を回る最小距離を求める問題。 言うまでもないことですが、AB, BC, CA の3つの距離のうち短い2つの和が答えになります。

コードは1行でさらっと書けます:

import std.algorithm;
import std.conv;
import std.stdio;
import std.string;

void main() {
  readln.chomp.split.to!(int[]).sort[0..2].sum.writeln;
}

ところが提出すると CE *4 が出ている。Warning: use std.algorithm.sort instead of .sort propertyだそうだ。なんでや手元じゃ動いたやろが*5。

どうやら原因はこの辺にあるらしい。 手元の環境(DMD v2.083.0)では既に存在しないものの、配列には .sort プロパティというのがかつて存在して、これがジャッジサーバの環境(DMD v2.070.1)ではまだ存在するが deprecated なので警告が出たという話である模様。 でもさっきのページ見る限り deprecated になったの 2.072 からっぽいんですけど……？おかしいな。

これを回避するには、ちゃんと std.algorithm の sort() を呼んだんだぞということを教えてあげればよい。つまり:

// .sort の後の () を省略しない
readln.chomp.split.to!(int[]).sort()[0..2].sum.writeln;

これでちゃんと AC *6 になりました。

B - Balance

長さ N の数列が与えられたとき、その数列を適当な位置で2分して、前半の和と後半の和の差の絶対値を最小化する問題。N が高々 100 なので全探索一択です。

1行とまでは言わないけどさらっと書けるでしょ。こんな感じでどうですか:

// import文は省略

void main() {
  auto n = readln.chomp.to!int;
  auto w = readln.chomp.split.to!(int[]);

  int ans = int.max;
  iota(1, n).each!(t => {ans = ans.min(abs(w[0..t].sum - w[t..$].sum));});
  ans.writeln;
}

はい、WA *7です。

今度は何だとブチ切れながら調べていると、このラムダ式が良くないらしい:

t => {ans = ans.min(abs(w[0..t].sum - w[t..$].sum));}

C# を書くときのノリで調べもせずに適当に書いたのですが、どうやらこの書き方だと「tを引数に取ってsum(w[0..t])-sum(w[t..$])の絶対値がansより小さければansを上書きする」という意味にはならないようです。 なぜならば D言語の { /* ... */ } は デリゲートリテラル だからで、したがって先のコードは「tを引数に取って『sum(w[0..t])-sum(w[t..$])の絶対値がansより小さければansを上書きする』ような関数(正確にはデリゲート)を返す」という意味になります。そりゃ何も起こらんわ。

したがって以下のように修正する必要があります:

// {} を外す
t => ans = ans.min(abs(w[0..t].sum - w[t..$].sum))

// あるいはラムダ式をやめて直接デリゲートリテラルを置く
(t) {ans = ans.min(abs(w[0..t].sum - w[t..$].sum));}

これで AC です。

C - Typical Stairs

1段または2段ずつ階段を登れるとして、指定されたM個の段を踏まないように N段 の階段を登りきる方法は何通りあるかを求める問題。N = 1 から順番に部分問題を解いていけばいいだけ。

「指定された段」を愚直に配列で管理すると O(NM) となって TLE になる*8ので、HashSet などを使って適切に管理する必要があります。 D言語に HashSet はありませんが、代わりに赤黒木があるのでこちらを使います。

// import文は省略

void main() {
  const MOD = 1000000007;

  auto nm = readln.chomp.split.to!(int[]);
  auto n = nm[0];
  auto m = nm[1];
  
  auto a = make!(RedBlackTree!int)(stdin.byLine.map!(to!int));

  int[int] dp = [
    0: 1,
    1: 1 in a ? 0 : 1,
  ];

  foreach (k; 2..(n + 1))
    dp[k] = k in a ? 0 : (dp[k - 1] + dp[k - 2]) % MOD;
  
  dp[n].writeln;
}

珍しくつつがなく AC が出ました。

D - Lamp

壁または床で構成されたチェス盤の適当な位置に1つルークを置くとき、ルークの移動可能範囲を最大化する問題。盤が広いので雑に実装すると TLE する。

各マスに「そこから左右に何マス動けるか」「そこから上下に何マス動けるか」の情報を持たせればよいので、「連続する床の枚数を数えながら盤を歩き、壁にあたったら折り返して各床に数字を書き込む」といった真似をすればよいことになります*9。コードは長いわりに中身がないので省略。

あまり綺麗な方法ではないですがちょっと横着して、連続する床の座標をPoint[] buf(Pointはユーザ定義の構造体)に記録し、壁に当たる度にbufに格納された各床に数字を書きに行くといった処理を書きました*10。 当然、数字を書いた後はまたbufを空にしなければならないので、buf.clearを実行しますが:

Error: template `object.clear` cannot deduce function from argument types `!()(Point[])`
candidates are:
  `object.clear(T : Value[Key], Value, Key)(T aa)`
  `object.clear(T : Value[Key], Value, Key)(T* aa)`

なんで……？

ちなみにbufの型をSList!Pointにするとbuf.clearでもコンパイルが通ります。 通りますし、手元でも動きますが、ジャッジサーバでは全ケース RE *11*12になります。

どうして…………？

はーーーーーー知らん！！！今日はもうおしまい！！！

おわりに

D言語くん基本的に好きだけどこういう謎エラーたくさん吐くとこきらい。人と仲良くして。

(追記) 解決編です: On Error Resume Next (解決編)

*1:主に研究活動。

*2:逆ギレ。

*3:Time Limit Exceeded。プログラムの実行が制限時間内に終わらなかったことを意味する。

*4:Compilation Error。出直せの意。

*5:というかただの警告ならつべこべ言わずに動いてくれ。

*6:Accepted。正解したという意味。

*7:Wrong Answer。出直せの意。

*8:「指定された段」が昇順で与えられることを利用するならばこの限りでない。

*9:もっと賢い方針もあった。

*10:実際には連続する床すべての座標を記録する必要はなく、連続する床のうち最初の床の位置だけでよいのですが、こっちの方がコードが短くて済みそうだったので。

*11:Runtime Error。出直せの意。

*12:CE だとエラーログ教えてくれるけど RE の場合は教えてくれないので原因もよくわからない。