競技プログラミングのテストケースから読み解くALTAのテスト技法

この記事は

競技プログラミングを始めたばかりの人に伝えたいこと、13日目として書きます。

• どちらかというと、あまりプログラムさわったことないテスターの方向けに、テストのお勉強にもなるので競技プログラミング始めるといいよ！ということを伝えたくて書きます。
• 競プロ始めたばかりの人で、どんな役にたつの？と思っている方にも、「こんな利用方法もあるよ」と参考になるものを目指して書きました。

この記事で書いてあること

AtCoderで公式に公開されているテストケースについて、JSTQB-ALTAシラバスに載っているテスト技法の観点でテストケースを読み解きます。

この記事を書いた背景

この1年AtCoderにどハマりしていて、若干テストの勉強を疎かにしていました。（反省）
2月にJSTQB-ALTAを受けられることになったので、テスト技法について復習したいのがキッカケ。

競技プログラミングとは

• プログラミングや数学が大好きな人たち（偏見かも）が、週末の21時頃からリアルタイムでプログラミングの正確性と速さを競っています。（感覚としてはスポーツです）
• TwitterやDiscordで精進（コンテスト以外の時間に問題を解くこと）も活発です。
• なんぞやについては、AtCoder社長のブログに託します。

テスト技法とは

テスト技法については、JSTQBのALTAシラバス第３章より、ブラックボックステストの技法を抽出し、下記について説明します。

• 同値分割法
• 境界値分析
• ディシジョンテーブル
• 状態遷移テスト

以下もあるのですが力尽きたのとユーザがらみのものものもあってちょっと難しかったのでお許しを。
（AtCoderのユーザーストーリーって言い出したら足が10万本あったり、ようかんの長さが1000000000cmなのが普通の世界線になっちゃいます）

• 原因結果グラフ法
• 組み合わせテスト技法
• ユースケーステスト
• ユーザーストーリーテスト
• ドメイン分析
• 技法の組み合わせ

AtCoderのテストについては公式のDropBoxにあります。

• テストケースは、ファイルに分割されているので、下記のスクリプトを実行して、テキストファイルにまとめてから内容を確認しています。

同値分割法/境界値分析

同値分割法の定義：（シラバスより引用）

同値分割法（EP）は、入力、出力、内部値、および時間関連の値の処理を効率的にテストする場合に必要なテストケースの数を少なくするために使用する。同じ方法で処理される値のセットとして作成される同値クラス（同値分割とも呼ばれる）を作成するために分割を使用する。同値クラスから 1 つの代表値を選択することにより、同じ同値クラス内のすべてのアイテムに対するカバレッジとみなす。

境界値分析の定義：（シラバスより引用）

境界値分析（BVA）は、順序付けられた同値分割の境界上に存在する値をテストするために使用する。BVA には、2 つの値を用いる方法と 3 つの値を用いる方法の 2 つの方法がある。2 つの値を用いる方法では、境界値（境界上）と境界を少し超えた値（最小の増加分）を使用する。たとえば、同値クラスに 1 から 10 の範囲の値が 0.5 刻みで存在する場合、2 つの値を用いる方法の上位の境界値は、10 と 10.5 である。下位の境界値は、1 と 0.5 である。境界は、定義されている同値クラスの最大値と最小値に基づいて定義する。

• 問題：(abc219_a)AtCoder Quiz 2
  • 次の級まであと何点必要かを出力するプログラムを書く問題です。
• テストケース：ABC219-A(DropBox)

境界値は全部のケースありますが、同値分割については70-89の間の境界値ではない値はありませんでした。
rand06が29なのですが、本当は79あたりにしたかったのかなという雰囲気があります。
境界値のテストを同値分割に含める考え方もあるので問題はないのだろうと思います。

このネタをで、同じJSTQB-AL目指す先輩とディスカッションしたところ、『境界値って「39」「40」「41」の３点でやることもあるよね〜』という話題にもなりました。また、ソースコードで「＜」しか使わないようにや、設計書に書いていない数字は使わないように、とルールでしばることでテストケースを減らすような運用もするとのこと。
テストに限らず品質を上げるために何をすればいいかのお話が聞けて勉強になりました。「テスト」は、品質をあげる手段であり、手段はいくらでもあるので、コスト効果を考えて選択するのが大事ですね。

このケースの場合、例えば級が変わる境界を「40」でなく「41」と間違えたとき、「次の級までの点数」を出すので結局「39」「40」のケースでもNGとなるので、3つはいらないのだろうと思いました。ALTAの問題集では、「39」「40」「41」のように境界値の両端をテストしている問題もありました。

私の提出ソースコードはこちら。

ただ、以下のような実装も考えられますね。
このコードのバグは用意されたテストでは見つけられません。（見つけられても偶然）
ブラックボックステストって難しい。

ディシジョンテーブルテスト

定義：（シラバスより引用）

デシジョンテーブルは、条件の組み合わせ間の相互作用をテストするために使用する。デシジョンテーブルは、条件に関連するすべての組み合わせのテストを確認し、すべての可能な組み合わせがテスト対象のソフトウェアにより処理されることを検証する明確な方法を提供する。デシジョンテーブルテストのゴールは、条件、関係、および制約のすべての組み合わせを確実にテストすることである

• 問題：【abc204_a】Rock-paper-scissors
  • サーバル、アライグマ、フェネックでジャンケンをして、あいこになった。2体の出した手が入力として渡され、もう一体の出した手を当てる。
  • 例）「グー、チョキ」なら「パー」、「パー、パー」なら「パー」※実際には数字で表されています。
• テスト：ABC204-A(DropBox)

GIHOZを使います

このテーブルの通りの9ケースが用意されています。

ちなみにディジョンテーブルテストだとこれだけ分岐がありますが、実際にこんなたくさんの分岐を書くわけではなく、私のコードはこんな感じです。

分岐は1個しかないので、ホワイトボックステストのブランチカバレッジで考えると2ケースです。ただその前に考察でこの式でいけるよな、、、というような検討を頭の中でかなりぐるぐるします。
A問題の回答時間目安は2~3分なので、公式で用意されているレベルのテストを想像する時間はなく、なるべく数学的な解釈で問題を簡略化してシンプルな実装、シンプルなホワイトボックステストで動作確認をします。

状態遷移テスト

定義：（シラバスより引用）

状態遷移テストは、ソフトウェアが、有効または無効な遷移を介して、定義された状態の開始および終了を実行できるかどうかをテストするために使用する。イベントの発生により、ソフトウェアはある状態から別の状態に遷移し、アクションを実行する。テストとして選択したい遷移パスを促す条件（ガード条件または遷移ガードとも呼ばれる）を考慮してイベントを特定する。たとえば、ログインイベントの場合、有効なユーザ名およびパスワードの組み合わせを使用したものと、無効なパスワードを使用したものとは異なる遷移結果となる。

• 問題：【abc139_a】Tenki
  • 3日間の予測された天気と、3日間の実際の天気を比較して、天気予報の当たり日数を答えます。
• テストケース：ABC139-A(DropBox)

ちょっと強引に当たった回数を状態と見て作ってみました。

• 

実際のテストケースを見ると、以下のケースは全て用意されているので、上記の遷移は全て通るケースとなっています。
（あっ、これディシジョンテーブルの2の3乗通り抜き出しているしていることになるなあ、、、）

• あたり、あたり、あたり　(sample_02)
• はずれ、あたり、あたり (testcase_8)
• あたり、はずれ、あたり←ないけど、他のケースで遷移はカバーできる
• あたり、あたり、はずれ(sample_01)
• はずれ、はずれ、あたり(testcase_9)
• はずれ、あたり、はずれ(testcase_2)
• あたり、はずれ、はずれ(testcase_9)
• はずれ、はずれ、はずれ(sample_03)

これにプラスして、SなのかRなのかCなのか、というところのバリエーションを振っているのと、
「CRS」「SCR」のような、3回ハズレだけどインデックスがずれちゃうと当たるようなケースも入っていました。
なるほどこういう間違えやすいところを用意しておくのも大事です。勉強になります。

まとめ

JSTQBのALTAの範囲の技法の一部を、ABCのA問題で説明しました。
一般的な業務ではそれほど難しいアルゴリズムが必要になることはないと思うので、テストを考える上ではA~B問題あたりが練習になると思っています。
ほとんどの人が自分が触ったことがある言語で解けると思いますので、テスト専門の方々も試していただくと、プログラマが何を考えてコーディングをしているのか？等の新しい視座を得られるかもと思っています。

テストの観点でいうともう一つ。
競技プログラミングでは、「サンプルの自動テスト実行」をほとんどの参加者がしているのかなと思っています。
私もこちらの記事を参考に、VScodeで「Command+Shift+B」でサンプルの自動テストを一括実行する環境を用意しています。
Google先生に「atcoder vscode (言語)」あたりで聞いてみると自分の得意な言語について環境構築をしてくれた先人の記事がヒットすると思います。

最後に

テストに限らず、プロジェクトの品質保証って、どこまでテストするか？どこの確認が優先度が高いか、持てる時間とのバトルだと思います。

i個のテストがあり、テストT_iにかかる工数はt_iです。 \\
それぞれのテストがバグを検出する確率と\\
対象機能の重要度から算出したテストの重要度はw_iである。 \\
プロジェクトの品質保証にかけられる工数をD人日（8時間稼働）としたとき、 \\
テストの重要度の合計値を最大にするにはどのテストを選択すれば良いか？

というような問題は、ナップサック問題と呼ばれ、動的計画法で解くことができます。
重みをちゃんと定義できるのかというとそれはそれで難しいですが、、、、

よいテストライフ、AtCoderライフを！！