【MATLAB】Cody5:Hard なるものにチャレンジしてみた


はじめに

研究室で MATLAB に触れることが多くなったので, MATLABer 内輪で行われているコードゲーム1 である Cody に挑戦してみました。

MATLAB とは

MATLAB は, 直観的な方法での数値の解析に長けているプログラミング言語になります。豊富な組み込み関数, 広範な学術分野の拡張機能が特徴です。

一時期 NASA も使ってるという宣伝文句が使われてましたが, NASA の Open Source を見てもかなりの割合で MATLAB ベースのものがあるので, これは現在についても本当かと。あと, 神経科学の分野でもデファクトだという記事もありました。

MATLAB のドキュメンテーションはコーダーではなく, 一般の科学者向けの説明になっているため, 使う人によっては用語に違和感があるかと思われます。短所を挙げるなら, インタラクティブな機能を前提としてないためか, 描画機能は低速と感じます。(あと, ライセンスが有料。私は大学がライセンスを与えてくれたので使えています。)

Cody とは

MATLABer が内輪でやってるコードゲームです。需要は正直わかりかねますが, 研究員が研究の暇つぶしにやってたりするんですかね。ほぼすべての大問が英語になっており, 題意の関数を書ければ AC という無難なつくりです。

Cody5:Hard の第1問を解いてみる

Cody5:Hard は Cody の 5 周年を記念して作られた問題集になります。MATLABer は理数系が得意な人が集まる印象なので, これまた難しいんでしょうか。

It's Cody's 5th birthday, and you've been tasked with putting the candles on the cake. Your goal is to maximize the distance between the 5 required candles.

Given a rectangular cake with specified length and width, return the highest possible minimum distance between any two candles.

Important notes

You may assume that a candle can be placed directly on the edge of the cake (even though that would be physically challenging!).
Required tolerance: <0.01

要は, 「長方形の2辺の長さが与えられるので, なるべく各点の距離が離れるように 5 つの点を打て」ってことですね。返すのは 2 点の距離の最小値になります。回答は下図を見れば理解できるでしょう。

$\mathrm{mn}$ が短辺, $\mathrm{mx}$ が長辺になります。

以下が回答のコードです。geometry は正直苦手なので, 上の図が書けるまでちょっと時間がかかりました。

birthdaycandles.m
function ans = birthdaycandles(len,wid)
    mx = max(len,wid);
    mn = min(len,wid);
    l1 = mn * sqrt(3);
    l2 = l1 * 4/3;
    if mx <= l1
        hypot(mn,mx)/2
    elseif mx <= l2
        2*sqrt(mn^2 + (mx/2)^2 - mn*(mx/2)*sqrt(3))
    else
        hypot(mn,mx/4)
    end
end

所望の値のふるまい

折角なので, 所望の値がどのようにふるまうか, プロットして確認してみましょう。

birthdayplot1.m
dist = zeros(1000);
parfor i = 1:1000
    for j = 1:1000
        mx = max(i,j);
        mn = min(i,j);
        l1 = mn * sqrt(3);
        l2 = l1 * 4/3;
        if mx <= l1
            dist(i,j) = hypot(mn,mx)/2;
        elseif mx <= l2
            dist(i,j) = 2*sqrt(mn^2 + (mx/2)^2 - mn*(mx/2)*sqrt(3));
        else
            dist(i,j) = hypot(mn,mx/4);
        end
    end
end
imagesc(dist);
hold on
contour(dist,20,'--black');

parfor に関しては Parallel Computing Toolbox をインストールしている場合に, 自動的にタスクを分割し CPU 上で並列ループ計算を実行できます。

結果は下図で, 左上の頂点が座標と共通の長方形を書いたら, 右下の頂点が所望の値に位置するようになってます。

ちょっと情報量が多い気がするので, 長辺を固定してプロットしてみましょう。

birthdayplot2.m
hold off
plot(dist(1000,:))
title('long side = 1000')
xticks(0:200:1000)
xticklabels(0:0.2:1)

結果は下図。

図から, ケーキは $1:\sqrt3$の割合だと一番効率よく 5 本のロウソクが置けるのでは(?)と推測されました(無理やりな結論)。

おわりに

この拙文で、なんとなく Cody のノリが理解いただけたら幸いに思います。MATLAB を普段使っていらしてる方は力試しになるのではないでしょうか。(AtCoder でも使えたらいいなとか思いつつ)

なんだかんだこのアカウントで記事を書くのも初めてなので, 生存報告代わりに更新していこうかな


  1. AtCoder などは競技としてチートなどができぬようしっかり設計されていますが、Cody はそんなにガチではなく、ほぼすべての問題でチートがトップを占めてます。やるなら気にしない姿勢が大事。