y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

オフラインリアルタイムどう書く E06 に参加しました

8/6 (土) に開催された「オフラインリアルタイムどう書く E06」というイベントに参加しました。与えられた問題を解くプログラムを 1 時間の制限時間内で実装し、各自が実装したコードを発表するというイベントです。問題と各参加者の実装へのリンク集は、それぞれ以下にあります。

私は当日は PHP で実装したのですが*1、今回は、改めてこの問題を MATLAB で実装してみました。以下、プログラムの処理の流れを説明します。

function output = Solve(input)
    % 入力文字列の解析
    P = strsplit(input, ',');
    P = cellfun(@ReadMonsters, P, 'UniformOutput', false);
    % 総当たり戦を実行
    [I1, I2] = meshgrid(1:length(P));
    R = arrayfun(@(i1, i2) Fight(P{i1}, P{i2}), I1, I2);
    % 勝利数の降順に整列して出力
    [~, I] = sort(sum(R == 1), 'descend');
    output = sprintf(',%d', I);
    output = output(2:end);
end

function M = ReadMonsters(P)
    M = sscanf(P, '%d%c');
    M = reshape(M, 2, []);
    M(2, :) = arrayfun(@(T) find(T == 'RGB'), M(2, :));
end

function R = Fight(P1, P2)
    P1(3, :) = P1(1, :);
    P2(3, :) = P2(1, :);
    while size(P1, 2) * size(P2, 2) > 0
        M = [P1(:, 1) P2(:, 1)];
        D = 2 .^ ([1 mod(M(2, 1) - M(2, 2) + 1, 3)] * [0 2; 1 -1]);
        N = ceil(M(3, :) ./ D);
        N = min(N) - (M(1, :) > flip(M(1, :))) .* (N >= flip(N));
        H = max(M(3, :) - D .* N, 0);
        P1(3, 1) = H(1);
        P2(3, 1) = H(2);
        P1 = P1(:, P1(3, :) > 0);
        P2 = P2(:, P2(3, :) > 0);
    end
    R = sign(size(P1, 2) - size(P2, 2));
end
MATLAB の配列のインデックス

まず、MATLAB のコードを読み書きする際には、配列のインデックスについて注意が必要です。MATLAB の配列のインデックスは 0 ではなく 1 から始まります。また、二次元配列を行列と見立てる場合には、第一次元のインデックスが行で、第二次元のインデックスが列を表します*2。以下に例を示します。なお magic は魔方陣を作る関数で、A は縦横斜めの合計がすべて 15 になっています。

>> A = magic(3)
A =
     8     1     6
     3     5     7
     4     9     2
>> A(2, 3)
ans =
     7
入力文字列の解析

Solve 関数の最初の部分では、入力文字列を解析して、後続の処理で利用しやすい形のデータ構造に格納します。cellfun 関数はセル配列*3に対する map 操作で、セル配列 P の各要素に ReadMonsters 関数を適用します。

ReadMonsters 関数内の sscanf ではフォーマット文字列に '%d%c' しか指定していませんが、MATLAB の sscanf はフォーマット文字列を繰り返し適用して配列に格納します。以下に例を示します。結果の 82 と 71 は 'R' と 'G' のアスキーコードです*4

>> sscanf('3R2G', '%d%c')
ans =
     3
    82
     2
    71

ReadMonsters 関数では、これを 2 行 n 列の行列に変換*5した後、2 行目の値を 'RGB' から 1, 2, 3 に変換します。ここまでの処理で、たとえば入力データが '9B,3R2G,1R2B3G' のときの P は以下のようになります。

>> P{1}
ans =
     9
     3
>> P{2}
ans =
     3     2
     1     2
>> P{3}
ans =
     1     2     3
     1     3     2
総当り戦の実行

次に、n 人のプレイヤー同士の総当り戦の組み合わせを作ります。meshgrid 関数を使うと以下のデータを生成してくれます。

>> [I1, I2] = meshgrid(1:3)
I1 =
     1     2     3
     1     2     3
     1     2     3
I2 =
     1     1     1
     2     2     2
     3     3     3

この I1 と I2 の各要素をプレイヤーのインデックスとして対戦を行えば全体の結果を得られます。MATLAB の arrayfun 関数は多次元配列にも適用できるので便利です。以下に例を示します。@power はべき乗に相当する関数で、I1 と I2 の互いに対応する要素 i1, i2 に対して power(i1, i2) を実行した結果が戻されます。

>> arrayfun(@power, I1, I2)
ans =
     1     2     3
     1     4     9
     1     8    27

今回のプログラムでは、I1 と I2 の互いに対応する要素 (i1, i2) をインデックスとして、プレイヤー P{i1} と P{i2} に Fight 関数を適用して対戦結果を得ます。なお、実際にはこのうち i1 > i2 の範囲だけ計算すれば十分ですが、今回のコードでは全体を計算しています。triu 関数などを利用して工夫すれば、必要な部分だけを計算する実装もそれほど難しくはありません。

プレイヤー同士の対戦

Fight 関数でプレイヤー P1 と P2 の対戦を行います。P1 が勝った場合に 1, 引き分けの場合に 0, 負けた場合に -1 を戻すようにしました。たとえば '9B' と '3R2G' の対戦であれば、引数の P1, P2 は以下のようになっています。それぞれ 1 行目がモンスターのレベル、2 行目がモンスターのタイプ (RGB を 1, 2, 3 に変換したもの) です。

>> P1
P1 =
     9
     3
>> P2
P2 =
     3     2
     1     2

Fight 関数の先頭で、各モンスターの体力をレベルの値で初期化します。P1, P2 の 3 行目を体力としています。このように、MATLAB の配列は動的に大きさを変更できます。

while ループの内側ではモンスター同士の対戦を処理しています。配列 M は P1, P2 それぞれの先頭のモンスターをまとめたもので、3 行 2 列の行列になります。一体目同士の対戦では以下のとおりです。

>> M
M =
     9     3
     3     1
     9     3

今回のプログラムでは、ターンごとの攻撃をシミュレートするのではなく、対戦結果を直接計算する方法で実装しました。while ループ内の以下の 4 行で計算しています。

D = 2 .^ ([1 mod(M(2, 1) - M(2, 2) + 1, 3)] * [0 2; 1 -1]);
N = ceil(M(3, :) ./ D);
N = min(N) - (M(1, :) > flip(M(1, :))) .* (N >= flip(N));
H = max(M(3, :) - D .* N, 0);

D, N, H はいずれも 1 行 2 列の行列で、それぞれ以下を表します。

変数 意味
D 一回の攻撃で受けるダメージ
N 対戦終了までに攻撃を受ける回数
H 対戦終了時の残り体力

D の計算では、まず、お互いのモンスターのタイプによって mod(M(2, 1) - M(2, 2) + 1, 3) が 0, 1, 2 のいずれかの値になります。詳細な計算は省きますが、この値を n とすると、P1 側のモンスターが受けるダメージは 2^n になります。また、このとき P2 側のモンスターが受けるダメージは 2^(2-n) です。そこで、次の行列計算で両者の被ダメージをまとめて求めています。

{\displaystyle
\qquad \texttt{D} = \texttt{2 .^} \; \left(\begin{array}{cc} 1 & n \end{array}\right) \left(\begin{array}{cc} 0 & 2 \\ 1 & -1 \end{array}\right)
}

N については、まず、双方のモンスターの体力が何回目の攻撃で 0 になるかを計算します。これは簡単で、現在の体力を D で割って切り上げた値になります。モンスターのレベルが同じであれば両者は同時に攻撃するので、お互いに min(N) 回の攻撃を受けます。一方、モンスターのレベルが異なるときにはレベルの高い方が先攻なので、レベルの低い方の体力が 0 になるターンにはレベルの高い方は攻撃を受けません。上記のコード断片の 3 行目で、この補正を含めた被攻撃回数を計算しています。両方の項が true であれば (min(N) - 1) 回しか攻撃を受けません。

コード断片 コード断片の意味
M(1, :) > flip(M(1, :)) 自分が相手よりも高レベルなら true (1)
N >= flip(N) 体力が 0 になるターン数が同じか自分の方が大きければ true (1)

それでは、'9B' と '3R2G' のプレイヤー同士の対戦を確認してみます。最初は '9B' と '3R' の対戦で、対戦後の残り体力は次のように求まります。

>> H
H =
     9     0

この結果 '3R' が敗北します。配列 P1, P2 に残り体力を代入した後、体力が 0 のモンスター (列) を除去します。ここでは以下のように、配列に対する論理インデックス参照を利用しています。このように書くと、P2 のうち P2(3, :) > 0 が true になる列のみが抽出されます。

P2 = P2(:, P2(3, :) > 0);

次は '9B' と '2G' の対戦になります。先ほどの対戦で '9B' は攻撃を受けていないので、残り体力は 9 のままです。

>> M
M =
     9     2
     3     2
     9     2

対戦結果は次のようになります。'B' が 'G' に与えるダメージは 1 なので、最初のターンでは反撃を受けて '9B' の体力は 5 になります。次のターンで '2G' の体力が 0 になります。

>> H
H =
     5     0

これで配列 P2 が空になるので P1 側の勝利になり、Fight 関数は 1 を戻します。なお、配列のサイズを計算する size 関数の第二引数は、何次元目の大きさかを指定するものです。二次元配列であれば、1 を指定すると行数、2 を指定すると列数になります。

勝利数の集計

行列 R にすべての対戦結果が求まった後、各プレイヤーの勝利数を集計して降順に整列します。sort 関数は、整列結果と元の配列でのインデックスを返しますが、今回は整列結果は不要なので ~ (チルダ) で受けて捨てています。インデックスがプレイヤーの番号に一致するので*6、そのまま sprintf で文字列にして結果を出力します。

*1:私の当日の実装は http://qiita.com/y-uti/items/b55b317ee2e94c617891 にあります。

*2:MATLAB の配列は column-major order で格納されます。

*3:MATLAB では矩形配列とジャグ配列を区別します。ジャグ配列を扱うためのデータ構造をセル配列と呼びます。また、MATLAB の文字列は char を要素型とする 1 行 n 列の配列であり、「長さのばらばらな文字列の配列」はセル配列として扱う必要があります。

*4:フォーマット文字列に %d があるので全体が double の配列になり、そのため %c にマッチした値も数値に変換されます。

*5:reshape 関数で実行します。第 3 引数を空配列にすることで、列数を自動計算することを表します。

*6:MATLAB の配列のインデックスが 1 から始まるためです。