2020-12-06

プログラムはちゃんとテストをしよう②

はじめに

榊統です。
LOCAL学生部アドベントカレンダー6日目の記事としてブログを書きます。
昨日の続きです。テストを書くってどういうこと？というのがわかったつもりになれることを目指します。
次回のアドカレはたかぴろくんです。楽しみにしています。
adventar.org

前回の振り返り

テストを行うことで、その部分が意図通りに動くかどうか、欠陥がないかといったことがわかります。
もちろん、テスト自体に不備があって、実は欠陥があったりすることもありますが。
テストをして正しく動作すると考えられるところは、バグの原因になりにくいためトラブルを解消するのが楽になります。

本日の内容

テストを書く時はどのようなことを考えれば良いかを考えます。
実際にテストを書く場合はフレームワークとか使うのかもしれませんが、今回は本題からずれてしまいそうなので考えません。

本題

テストをする、というのはそこまで難しいことではありません。
要するに多くの(できれば全ての)場合について、その機能が正しく動いているかを確認できれば良いです。
一番わかりやすいのは競技プログラミングではないでしょうか。
atcoder.jp
この問題では、将棋でいう角行のような移動を繰り返すことで到達可能なマス目の数を求めます。
このようなマス目の数を求めてみましょう。

直感的には、おおよそH×W/2個存在していそうだ、と考えられます。
H×Wが奇数の場合はH×W/2+1。
入力例1,2,3について、正しく答えが求まるはずです。
しかし、実はまだ考察が不足していて、これでは正しくない答えが出てしまうようなケースが存在します。
HかWが1である時です。このような時は実は駒は動けず、答えが1となります。

このような特殊な場合のことをコーナーケースと言ったりします。
テストでは、できる限り多くの場合を考え、動作が意図したものであるかを調べることが大事です。
かといって、あり得る入力全てを試そうと思えば、寿命が来るまで確認作業をしても終わらないでしょう。
適切に条件分岐をして、必要な場合だけテストするのが望ましいです。

テストを書く

今回も関数を用います。
以下のような動作をする関数benefitを作ります。

単価と個数が引数として与えられる。
単価か個数のどちらかまたは両方が負の数の場合は-1を返す。
そうでない場合は単価×個数を返す。

#include <iostream>

int benefit(const int &unit_price,const int &quantity){
    if(unit_price<0||quantity<0) return -1;
    return unit_price*quantity;
}

int main(){
    std::cout<<benefit(5,7)<<std::endl;
    return 0;
}

この関数が正しく動いているかを確認するには、どのような個数、単価を与えれば良いでしょうか？

単価が負の整数で、個数が正の整数
単価が正の整数で、個数が負の整数
単価も個数も負の整数
単価も個数も正の整数

この4つはあると良さそうです。
他には、0という整数を入れてみるのも良いですし、オーバーフローするような大きい数字を入れることを考えて、benefit関数をオーバーフローしないように変更したりしても良いでしょう。

この関数が何をするのかかをテストして、動作を確認できれば、仕様としてまとめることができます。
かなり面倒に思えますが、大規模なプログラムを書きあげる時には、バグの原因を見つける速さが全然違います。
正直、1つ1つ丁寧にテストして確認しながらプログラムを書いた方が、結果的には早く完成しがちです。

最後に

テストを書け、とかテストコードを書け、とか言われても、どうすればテストをしたことになるのかがわからないのではないか、と思っています。
私もよくわかっていません。
どういう条件で実行時エラーを起こすのか。
どのようなデータを持っていて、どのように使われているのか。
テストをしようと思えば、中で行われるべき操作についてよく調べなければなりません。
プログラムを調べることで自分の意図とプログラムをすり合わせることになり、足りなかった仕様や考慮できてなかったケースに気付くことができるかもしれません。
コーディングにおいて、想定外が減ることを切に願います。

2020-12-05

プログラムはちゃんとテストをしよう①

はじめに

みなさんお久しぶりです。
榊統です。
最近は就活とゼミに追われる日々で、あまりツイートもできていません。
さて、今回はLOCAL学生部アドベントカレンダー5日目の記事としてブログを書きます。
明日はこのブログの続きを書きます。
adventar.org

導入

みなさんはプログラムを書く時に、テストを書きなさいと口酸っぱく言われたことはないでしょうか。
そもそもテストって何なのかわからない、必要性が感じられない等と思っていませんか？
厳密なテストをしなくても、テストをしようと思うだけで、そのプログラムをより深く知ることができます。
このブログと明日のブログで、下記2点が何となくわかったつもりになることを目指します。
①テストの重要さ
②テストでは何をすれば良いのか

プログラムの動作について

プログラムに厳密な仕様があるかどうかはその時々だと思います。
大学の課題のために書いたり、自分が便利だと思うツールを書いたり自動化したり......。
どのような場合でも、「このような時にはこう動いて欲しい」というものは決まっているはずです。
ここでは、学生の中間試験と期末試験の点数から、成績(不可、可、良、優、秀)を求めて返り値とする関数を考えます。
使用する言語はC++で、成績評価方法は以下の通りです。

中間試験と期末試験はともに100点満点で、点数は整数値をとる。
中間試験の点数×0.4+期末試験の点数×0.6をAとします。
Aが0以上60未満ならば不可
Aが60以上70未満ならば可
Aが70以上80未満ならば良
Aが80以上90未満ならば優
Aが90以上100以下ならば秀

この条件をそのままソースコードにした関数は、以下のような感じになります。

#include <iostream>

std::string grade_evalution(const int &mid_term_exam_scores,const int &final_exam_scores){
    const double grade=mid_term_exam_scores*0.4+final_exam_scores*0.6;

    if( 0<=grade&&grade<60) return "不可";
    if(60<=grade&&grade<70) return "可";
    if(70<=grade&&grade<80) return "良";
    if(80<=grade&&grade<90) return "優";
    if(90<=grade&&grade<=100) return "秀";
}

int main(){
    std::string grade=grade_evalution(54,73);
    std::cout<<grade<<std::endl;

    return 0;
}

中間試験の点数と期末試験の点数を引数として与えると、その成績を表す文字列が返り値になる関数です。
試しに実行してみれば、可という出力が得られます。
何となく普通に動いていて、これで問題ないように見えますが、非常に危険な欠陥を抱えています。
例えば、grade_evalution関数に与える引数に、0から100以外の値を入れてみましょう。

std::string grade=grade_evalution(120,150);

実行すると、grade_evalutionはどのif文にも当てはまらず、何も返り値を返すことができません。
このような場合は、プログラムが実行時エラーを吐いて突然終了してしまうことがあります。
また、仮にデータの出力ができても、意味不明な文字列が出力され、それが原因で他のプログラムが意図しない動作をしてしまうかもしれません。

ところで、試験の点数は0点から100点までだから、そのようなケースを考える必要はないと思う人もいるでしょう。
以下のような考察から、そのようなケースを考えるべきだとわかります。
この関数が参照するのは成績なので、外部の.csvファイル等からデータを読み込んで使用する、ということはあり得ます。
.csvファイルへの入力時に、点数を打ち間違えてしまうことはないでしょうか？
人の手が関わるところには、絶対大丈夫はあり得ないという意識を持っておくべきです。

これまでの話から、「このような時にはこう動いて欲しい」という気持ちだけで書いたプログラムには、意図せず不具合を発生させる可能性が潜んでいることがわかって頂けるのではないでしょうか。
次は、このプログラムが意図しない挙動をしないための工夫を考えます。
このようなことを考えると、どのようなテストが必要なのかが見えてきます。

意図しない挙動を減らすために

今回見つけた不具合になり得る要因は、引数が0から100までの値をとらないかもしれない、というものです。
引数がどちらも0以上100以下の整数値ならば、このプログラムは正しく動作します。

    for(int i=0;i<=100;i++){
        for(int j=0;j<=100;j++){
            std::string grade=grade_evalution(i,j);
            std::cout<<grade<<std::endl;
        }
    }

どちらか、もしくは両方の引数が0以上100以下の整数値をとらない時は、"エラー"という文字列でも返してあげましょう。

std::string grade_evalution(const int &mid_term_exam_scores,const int &final_exam_scores){
    if(mid_term_exam_scores<0||mid_term_exam_scores>100||final_exam_scores<0||final_exam_scores>100) return "エラー";
    
    const double grade=mid_term_exam_scores*0.4+final_exam_scores*0.6;

    if( 0<=grade&&grade<60) return "不可";
    if(60<=grade&&grade<70) return "可";
    if(70<=grade&&grade<80) return "良";
    if(80<=grade&&grade<90) return "優";
    if(90<=grade&&grade<=100) return "秀";
}

これで、引数の値が0以上100以下でないような時でも、文字列を返すことができるようになりました。
イメージ的には、プログラムを書いた時に考察不足になったところがよくバグの原因になったりします。
関数であれば、どのような引数の時にどのような返り値を返すのか、詳細な仕様を残しておくことで、この関数を再利用する時、とても楽になるでしょう。

まとめ

自分が意図した通りにプログラムが動いていても、自分が想定していなかったようなケースが存在することもあります。
それが原因でプログラムが意図しない動作をして、その他のプログラムにまで影響を与えて...と、小さな1つのプログラムが原因で、広範囲にバグをまき散らすと、どのプログラムが原因となっているかがわからず、特定にとても時間が掛かったりします。
そのような状況にならないためにも、ある程度のまとまった機能(例えば関数やクラス)が出来たところで、1つ1つ正しく動作するかを確認すべきです。

明日のブログでは、テストを書く、ということがわかったつもりになれるような記事を書きたいと思います。

2019-12-22

所属サークルで競プロ講座(笑)をしたお話

榊です。AtCoderとCodeforcesが水色です。
弊サークルのとある部員が灰色で停滞しているのを見て、茶色へ引き上げたいと思い、講座を開くことにしました。その第1回についてダメだった点について思うところを書いていきます。
書いている途中で、ダメなところばっかり思いついてしまって、ただの反省公開オナニーブログになってしまうことに気付きました。なので、反省はほどほどにして、講座内容の演習問題を作って載せておきました。

反省点:

1.体系としてまとめ上げることが出来ていなかった

つまりは、2時間程度の講座であるにも関わらず、別々なテーマで3種類のお話をしたことが反省点です。極端な例ですが、文字列操作をやった直後にグラフアルゴリスムをやるような、滅茶苦茶な構成になっていました。次回以降はテーマを1つに定めてやります。

2.受講者のレベルに合わせた話が出来なかった

今回は、珍しく(?)１年生の方も来てくれました。しかし、想定が甘かったため、講座内容の全体を通してよくわからないまま終わってしまったのではないかと思います。

反省はこれくらいにして

反省短すぎない？という気はしますが、講座内容の類題を適当に作成しました。
どこかで見たことがある問題だと思います。
見たことがなく、かつ解けないならば、精進をしましょう！

問題1

榊くんは $N$ 種類の敵iに $A_{i}$ 回だけ攻撃されます。
各敵iの攻撃力は $B_{i}$ です。
弱体化券を使うことで、1種類の敵の攻撃力を $X$ だけ下げることが出来ます。
また、1種類の敵に対して複数枚使用することも出来ます。
ただし、0より下げることはできません。
即ち、敵 $i$ に対して弱体化券を●回使うとすると、 $i$ の攻撃力を $max( 0 , B_{i}$ - ●×X)]にすることが出来ます。
さて、弱体化券は $K$ 個あります。敵 $i$ から受けるダメージはmax(0,(榊くんの防御力)-(敵 $i$ の攻撃力)×(敵 $i$ の攻撃回数))です。
榊くんが全ての敵からのダメージを0にするのに必要な、最小の防御力を求めなさい。

制約:

$1≦N≦10^{5}$
$0≦K≦10^{12}$
$1≦A_i,B_i,X≦10^{6}$
実行時間制限:2sec

入力:

N K X
A_1 A_2 ... A_N
B_1 B_2 ... B_N

入力例1:

3 0 5
1 2 3
5 4 3

出力例1:

9
K=0なので敵の攻撃力は減らせません。
敵1は5,敵2は8,敵3は9ダメージを与えてこようとしています。
よって、防御力は9あればすべての敵からのダメージを0に出来ます。

入力例2:

4 2 3
4 4 3 1
1 4 2 4

出力例2:

K=2なので、2回だけ弱体化が行えます。
敵1,2,3,4のうち、2と3に対して1回ずつ弱体化を行うと、
敵1は4,敵2は4,敵3は0,敵4は4ダメージを与えてこようとしています。
よって、防御力は4だけ必要で、これが最小です。

入力例3:

4 100 1
1 1 1 1
1 1 1 1

出力例3:

0
全ての敵の攻撃力を0に出来ます。
よって、0が答えです。

問題2

榊くんは年越しを祝って、N個の整数を用意しました。
この整数を、和がXとなるように取り出す方法は何通りあるでしょうか。

制約:

$1≦N≦15$
$-10^9≦A_i,X≦10^9$

入力:

N X
A_1 A_2 ... A_N

入力例1:

4 5
4 2 1 3

出力例1:

$\{A_1,A_3\},\{A_2,A_4\}$
が条件を満たします。よって、答えは2です。

入力例2:

4 5
-1 1 1 4

出力例2:

$\{A_1,A_2,A_3,A_4\},\{A_2,A_4\},\{A_3,A_4\}$
が条件を満たします。よって、答えは3です。

2019-07-13

ICPC2019国内予選参加記チームWEloveSAINO

C問題の良い実装が思いつかずにA,B2完をした榊です。
初めてICPCに出た感想を記します。

ICPC前日

必死こいてライブラリを作る。
模擬国内で4,50分溶けてしまったEOF対策をする。(意味なかったけど!!)
ネットから使用方法が簡単なライブラリをコピペしてくる。(意味なかったけど!!)
念のため幾何用のライブラリをコピペする。(意味なかったけど!!)
大体1問は文字列操作、構文解析があるので文字列用のライブラリを作る。(意味なかったけど!!)

ICPC当日

まず、先輩方にリアルで顔を合わせて(ツイッター上でやりとりはしていた)、「女装してくるのを期待してたのに...」とか、「3完くらいしてね?」とか煽られる。(その先輩のチームは本番楽しそうでした(後日談))

時間になったら問題を見て、A,Bの解法を出す。
(ここまで10分、なおこの時点でのAは嘘解法,BはBFSとi,jのマンハッタン距離の2通りの解法が出ていた)
メンバーの1人は開始から2時間30分くらいずっとCの考察をしていました。
→C,Dを見る、厳しそう。Cは実装出来るか怪しい。
→A,Bとりあえず解いておくか。
→Visual Studioがバグる。
→2,30分後

→Aを書く。嘘解法。
→正しく実装しなおす。→合ってた。1完。
→Bを書く。実装が弱いので当然マンハッタンで解く。→合ってた。2完。
→Cの実装が重くて(実装が苦手)Dへ逃げようとした。
→貪欲を書く。通らない。それはそう。DPなので。→いっぱい時間溶ける。
→やっぱりC問題やるしかない！！
→まず、結果的にm個の分銅で作れる重さを全て列挙する。
→バグる。
→long long のmapで書いたら3*10^16くらい?の意味わからない値が混じってる…→絶対値がクソでかい値だけ省けばいいんじゃね？？
→なぜか列挙は出来てるっぽい。チームメンバーにバカと天才は紙一重みたいなことを言われつつ、答えの場合分けに入る。
→分銅であり得る値は列挙しているので、その値と一致していない薬品の数を数える。
→全部一致していれば当然0
→何個か残っているケースを考える。
→1個余ってるのは流石に簡単なので、複数余っている場合を考えた。以下多分嘘解法。
→(ここで、薬品と列挙した分銅を事前にソートしておいて、その差をとったvector配列を用意。)
→(vector配列と一致している範囲が存在するかを判定し、あれば差を取って出力。)
→バグらせた。そもそも解法が正しいかもわからない。
→バグ埋小宮になった。死亡。ここでタイムオーバー。

D問題がDPだとサンプルの最後でちゃんと見抜いていても、多分C問題の実装は無限に時間がかかったし、多分嘘なので詰んでいた感がすごいです。

今後の精進について

効率的な実装を身につけ、思いつけるようにする。
ICPCのD問題は大体DPなので、DPの漸化式を出す精進をする。
4完すればアジア予選行けそうなので頑張ります!!

2018-12-23

Cを踏み台にして，C++を覚えた男の妄言．

この記事はMuroran Institute of Technology Advent Calendar 2018 の23日目です．

adventar.org

　皆さん始めまして，所属する大学の1年にAtCoderの布教をしまくってるsakaki素人です．なお，つい最近茶色になったばかりです．(2018/12/23現在)

　さて，タイトルでお察しの通り，Cでプログラミングしている人にC++をオススメする内容です．コーディングが短くなったり楽になったり，便利な機能がたくさん追加されてたりします．そのごく一部を紹介するので，是非C++に浮気しましょう！（競技プログラミングの目線が過分に含まれています．）

AtCoder

　C++の良さを紹介するために，このサイトから良さそうな問題を選び，紹介します．

atcoder.jp

標準入出力

　C言語だとprintfやscanfなどです．

#include<stdio.h>
int main(){

   int a,b,c;

   scanf("%d %d %d",&a,&b,&c);

   printf("%d %d %d",a,b,c);

   return 0;

}

　超初歩的なやつです．a,b,cを読み取ってただ表示するだけ．これをC++で書くとこうなります．

#include <iostream>

int main(){
	int a, b, c;

	std::cin >> a >> b >> c;

	std::cout << a << " " << b << " " << c;

	return 0;
}

　using namespace std;というのを入れてあげると，std::とかいうよくわからないのを使わなくて済みます．（ちゃんと勉強するとstd::の重要さに気付くらしいです．なおsakaki素人はまだわかってない．）

#include <iostream>
using namespace std;
int main(){
	int a, b, c;

	cin >> a >> b >> c;

	cout << a << " " << b << " " << c;

	return 0;
}

　少し短くなりましたねえ…この程度しか短くならないのかと思うかもしれませんが，フォーマット指定子がないというのは非常に楽です． (sakaki素人は%fと%lfの違いがわからず，いつもCEします．)

　さて，個人的にCで書くのがつらいのでここからはC++のソースコードのみとなります．ご容赦ください．また，AtCoderさんお世話になりますm(__)m．

atcoder.jp

これをCで解こうとすると，

アルファベットの数の分(a～z)だけ配列を用意

char型に入れた文字列からaを見つけたらアルファベットa用の配列に+1...をzまで繰り返す

アルファベット用の配列が全て2で割り切れるか調べる

こんな感じでしょうか．正直やってらんないです．コード書きたくないです．

というわけでC++のコードを見てみましょう．

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
using namespace std;      //std::というよくわからないやつを消せる．
 
int main(void) {
	string w; cin >> w;       //string型，char型の上位互換だと思ってる．
	map<char, int> mp;       
	int i;
	for (i = 0; i < w.size(); i++) {
		mp[w[i]] += 1;       
	}
 
	for (pair<char, int> x : mp) {
		if (x.second % 2 != 0) {
			cout << "No" << endl; return 0;
		}
	}
 
	cout << "Yes" << endl;
	return 0;
}

　string？map？pair？なんか見知らぬ謎な型名が出てきましたね．でもこれ，便利なんです．

string型．
　char型だとchar a[5]みたいにして要素数を宣言しないといけませんでしたが，要素数が要らなくなりました！おかげで最後に\0（NULL文字）が入ることとかを考えずに済みます．
map．
　何言ってんだこれって感じですよね．
pair．
　これも何言ってるんだって感じですね．言葉の意味的に2つを何かするのかな？って感じですが．

　string型のwを宣言し，wの要素1つ1つをmap型のmpに入れて，値をインクリメントする．値が2で割り切れなかったらNo．割り切れたらYes．このコードは，mapとpairと拡張for文の使い方がわからないと解読できません．これについては書こうとするともう1つブログを書く必要がありますね（宿題発生）．多分今度書きます．

　さて，mapを覚えたsakaki素人君は，調子に乗って次の問題をmapでやろうとしました．しかし，All Clearにはなりませんでした．

beta.atcoder.jp

ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
 
int main(void) {
	int n, l; cin >> n >> l;
	int i;
	map<string, int> mp;
	string s;
 
	for (i = 0; i < n; i++) {
		cin >> s;
		mp[s] = 0;
	}
 
	for (pair<string,int> x:mp) {
		cout << x.first;
	}
	return 0;
}

　sakaki素人君は重大な勘違いをしていたのです．彼はこう考えました．
　map＜string，int＞を宣言し，string型を入れると，mapの内部ではstringの部分がソートされるので，それを出力すれば良いだろう，と．
　しかし，map＜string，＞の左側は同じ値が入らないということを理解できていなかったのです．以下のソースコードを試せばなんとなく察しがつくと思います．

#include <iostream>
#include <string>
#include<map>

using namespace std;

int main(){
	string s;
	int a;
	map<string, int> mp;
	int i; 
	for (i = 0; i < 5;i++) {//5つの要素を入れるぞ!!
		cin >> s;
		cin >> a;
		mp[s] = a;
	}

	cout << endl;

	for (pair<string, int> x : mp) {
		cout << x.first << " " << x.second << endl;
	}

	return 0;
}

入力
sakaki 5
sakaki 4
Sakaki 3
SAKAKI 2
Sakaki 1

出力
SAKAKI 2
Sakaki 1
sakaki 4

　この問題ではmapは使えませんでした．string型をソートしましょう．これもC++には素晴らしい機能がついてます．

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
 
int main(void) {
	int n, l; cin >> n >> l;
	int i;
	string s[n];
 
	for (i = 0; i < n; i++) {
		cin >> s[i];
	}
 
	sort(s, s + n);
 
	for (i = 0; i < n; i++) {
		cout << s[i];
	}
	return 0;
}

　sortという名の通り，ソートするための関数である．始まりと終わりを指定するだけで勝手にソートしてくれる．（しかも普通にソートのコード書くより早い．）Cだとstrcmpとか使って比較するんでしょうか．とにかく便利です．

まとめ的な何か

　Cにはない様々な便利機能が，C++にはあります．うまく使いこなすには精進が必要ですが，一度使えるようになると面白いようにコードが書けるようになります．(なぜがC++を勉強し始めたらCがわかってきた不思議．)今回出てきたpairやmapなどはまたの機会に書くので，そちらではちゃんとお話しします．
　今回はC++への浮気を推奨するために書いたので，使われた関数の説明などは一切なかったのですが，ソースコードはCで書こうとするよりすっきりしているのではないでしょうか．

最後に

　AtCoderやろうぜ！！！！！！！！！！