0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@anonymously115

paiza問題集の「区間和」のリファクタリング・入力チェック・テストコードを考えてみた。

0
Posted at

paizaラーニングレベルアップ問題集の区間和をやってみました。

問題

参考

前回は「累積和」の問題を解きましたが、今回は「区間和」の問題を解いていきます（“前回”なんて知らねーよ）。
参考記事のIntArrayクラスに、新たに区間和メソッドinterval_sumを追加します。

IntArray.h
#ifndef INTARRAY_H_
#define INTARRAY_H_

#include <stdbool.h>

typedef struct __IntArray _IntArray;

typedef struct IntArray {
	_IntArray *_intArray;
	bool (*cumulative_sum)(const struct IntArray*, size_t, int*);
+	bool (*interval_sum)(const struct IntArray*, size_t, size_t, int*);
} IntArray;

IntArray* new_IntArray(size_t, const int*);

void free_IntArray(IntArray**);

#endif /* INTARRAY_H_ */
テストコード

早速、テストコードを書いていきます。このテストをパスするように本体のコードを書いていきます。
今回はinterval_sumメソッドのテストのみ記述します。
interval_sumの要件：

  • 入力添字は$0\le l\le r \le N$
    問題文と異なりますが、この範囲の入力を受け付けるように実装しておきます（後々便利かも。Pythonのsum(A[l:r])と同じ答えになります）。
    • 上記条件を満たす$l, r$に対して、$a_{l+1}+a_{l+2}+\dots+a_{r-1}+a_r$を返す（実装では添字がズレるのでA[l]+A[l+1]+...+A[r-2]+A[r-1]）
    • 上記条件を満たさない入力はfalseをreturnする
      例：$l=-1$（size_t型を引数としているので実現不可）、$r=l-1$（$l=r+1$）、$r=N+1$、等
  • $l=r$の時は$0$を返す（今回の問題ではこのような入力は与えられない）
  • $l=0, r=N$の時は、配列要素全ての和を返す

尚、単体テストツールとして、minunit.hを使います。

IntArrayTest.c
#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <errno.h>
#include "minunit.h"
#include "IntArray.h"

int tests_run = 0;

static char* message(int expected, int actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static char* test_interval_sum(int expected, size_t l, size_t r, size_t n, ...) {
	va_list args;
	va_start(args, n);
	int A[n];
	for (size_t i = 0; i < n; i++) {
		A[i] = va_arg(args, int);
	}
	va_end(args);
	IntArray *intArray = new_IntArray(n, A);
	int actual;
	bool result = intArray->interval_sum(intArray, l, r, &actual);
	free_IntArray(&intArray);
	mu_assert("Error: expected: <true> but was: <false>", result);
	mu_assert(message(expected, actual), actual == expected);
	mu_assert(message(0, errno), errno == 0);
	return 0;
}

static char* test_interval_sum_fail(size_t l, size_t r, size_t n, ...) {
	va_list args;
	va_start(args, n);
	int A[n];
	for (size_t i = 0; i < n; i++) {
		A[i] = va_arg(args, int);
	}
	va_end(args);
	IntArray *intArray = new_IntArray(n, A);
	int sum;
	bool result = intArray->interval_sum(intArray, l, r, &sum);
	free_IntArray(&intArray);
	mu_assert("Error: expected: <false> but was: <true>", !result);
	mu_assert(message(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_interval_sum_0() {return test_interval_sum(0, 0, 0, 0);}
static char* test_interval_sum_1() {return test_interval_sum_fail(0, 1, 0);}
static char* test_interval_sum_2() {return test_interval_sum_fail(1, 0, 1, 0);}
static char* test_interval_sum_3() {return test_interval_sum(0, 0, 0, 1, 100);}
static char* test_interval_sum_4() {return test_interval_sum(100, 0, 1, 1, 100);}
static char* test_interval_sum_5() {return test_interval_sum(0, 1, 1, 1, 100);}

static char* all_tests() {
	mu_run_test(test_interval_sum_0);
	mu_run_test(test_interval_sum_1);
	mu_run_test(test_interval_sum_2);
	mu_run_test(test_interval_sum_3);
	mu_run_test(test_interval_sum_4);
	mu_run_test(test_interval_sum_5);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

読者諸賢においては、様々なテストデータで試していただきたい。

本体実装

上記のテストをパスするように、interval_sumメソッドを実装していきます（上記のテストデータだけだと、他にもパスしてしまうコードも沢山ありそうだが）。
区間和$\sum_{i=l}^r a_i$は、$S_0=0$、$S_j=\sum_{i=1}^j a_i$を用いて

\begin{align}
\sum_{i=l}^r a_i&=a_l+a_{l+1}+\dots+a_{r-1}+a_r\\
&=\left(a_1+a_2+\dots+a_r\right)-\left(a_1+a_2+\dots+a_{l-1}\right)\\
&=S_r-S_{l-1}
\end{align}

と書けるので、interval_sumメソッドの実装は

static bool IntArray_interval_sum(const IntArray *self, size_t l, size_t r, int *sum) {
	errno = 0;
	if (r < l || self->_intArray->n < r) {
		errno = ERANGE;
		return false;
	}
	*sum = self->_intArray->sum[r] - self->_intArray->sum[l];
	return true;
}

となります（添字のズレの詳細は省略）。
これをコンストラクタnew_IntArrayにて

intArray->interval_sum = IntArray_interval_sum;

を追加すれば完成。

入力チェック

入力後半のクエリ部分に$1\le l\le r\le N$を満たす整数$(l,r)$が入ることになるので、前回のコードからその部分を修正します。

input.h
#ifndef INPUT_H_
#define INPUT_H_

#include <stdbool.h>

bool read_size(const char*, size_t*, size_t*);

bool read_element(const char*, int*);

- bool read_query(const char*, size_t, size_t*);
+ bool read_query(const char*, size_t, size_t*, size_t*);

#endif /* INPUT_H_ */

(以下、read_query関数のみ)

input.c
bool read_query(const char *str, size_t n, size_t *l, size_t *r) {
	if (!str) {
		errno = EINVAL;
		return false;
	}
	char s[] = "100000 100000\n";
	if (strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_ulong(strtok(chomp(strncpy(s, str, sizeof(s))), " "), l)) {
		return false;
	} else if (*l < 1 || n < *l) {
		errno = ERANGE;
		return false;
	}
	if (!parse_ulong(strtok(NULL, " "), r)) {
		return false;
	} else if (*r < *l || n < *r) {
		errno = ERANGE;
		return false;
	}
	if (strtok(NULL, " ")) {
		errno = EINVAL;
		return false;
	}
	return true;
}

以下、read_query関数にかかわるテストのみ記述

inputTest.c
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "minunit.h"
#include "input.h"

int tests_run = 0;

static char* message_d(int expected, int actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static char* message_z(size_t expected, size_t actual) {
	static char msg[72];
	snprintf(msg, sizeof(msg), "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* test_read_query(const char *str, size_t n, size_t el, size_t er) {
	size_t l, r;
	mu_assert("Error: expected: <true> but was: <false>", read_query(str, n, &l, &r));
	mu_assert(message_z(el, l), l == el);
	mu_assert(message_z(er, r), r == er);
	return 0;
}

static char* test_read_query_invalid(const char *str, size_t n) {
	size_t l, r;
	mu_assert("Error: expected: <false> but was: <true>", !read_query(str, n, &l, &r));
	mu_assert(message_d(EINVAL, errno), errno = EINVAL);
	return 0;
}

static char* test_read_query_out_of_range(const char *str, size_t n) {
	size_t l, r;
	mu_assert("Error: expected: <false> but was: <true>", !read_query(str, n, &l, &r));
	mu_assert(message_d(ERANGE, errno), errno = ERANGE);
	return 0;
}

static char* test_read_query_0() {return test_read_query_invalid(NULL, 0);}
static char* test_read_query_1() {return test_read_query_invalid("", 0);}
static char* test_read_query_2() {return test_read_query_invalid("1", 1);}
static char* test_read_query_3() {return test_read_query_invalid("1 1 1", 1);}
static char* test_read_query_4() {return test_read_query_out_of_range("0 1", 1);}
static char* test_read_query_5() {return test_read_query_out_of_range("1 2", 1);}
static char* test_read_query_6() {return test_read_query_out_of_range("2 1", 2);}
static char* test_read_query_7() {return test_read_query("1 1", 1, 1, 1);}
static char* test_read_query_8() {return test_read_query("100000 100000", 100000, 100000, 100000);}

static char* all_tests() {
	mu_run_test(test_read_query_0);
	mu_run_test(test_read_query_1);
	mu_run_test(test_read_query_2);
	mu_run_test(test_read_query_3);
	mu_run_test(test_read_query_4);
	mu_run_test(test_read_query_5);
	mu_run_test(test_read_query_6);
	mu_run_test(test_read_query_7);
	mu_run_test(test_read_query_8);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

エントリポイント

main関数の後半部分を、2整数のクエリを受けて区間和を表示するように改修します。

main.c
#include <stdio.h>
#include <errno.h>
#include "IntArray.h"
#ifdef NDEBUG
#include <string.h>
#include "input.h"
#else
#include <time.h>
#endif

int main() {
#ifndef NDEBUG
	clock_t clockt = clock();
#endif
	size_t N, K;
#ifdef NDEBUG
	do {
		char s[] = "100000 100000\n";
		if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
			for (int c = getchar(); (c == '\0' || c == '\n' || c == EOF); c = getchar());
		} else {
			if (read_size(s, &N, &K)) {
				break;
			}
		}
		perror("The number of elements must be an integer between 1 and 100000.\n"
		       "The number of queries must be an integer between 1 and 100000.");
	} while (true);
#else
	N = 100000;
	K = 100000;
#endif
	int A[N];
	for (size_t i = 0; i < N; i++) {
#ifdef NDEBUG
		do {
			char s[] = "-100\n"; 
			if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
				for (int c = getchar(); (c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else {
				if (read_element(s, &A[i])) {
					break;
				}
			}
			perror("The element must be an integer between -100 and 100.");
		} while (true);
#else
		A[i] = ((int) i) % 201 - 100;
#endif
	}
	IntArray *intArray = new_IntArray(N, A);
	while (K--) {
-		size_t Q;
+		size_t l, r;
#ifdef NDEBUG
		do {
-			char s[] = "100000\n"; 
+			char s[] = "100000 100000\n"; 
			if (!strchr(fgets(s, sizeof(s), stdin), '\n')) {
				for (int c = getchar(); (c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else {
-				if (read_query(s, N, &Q)) {
+				if (read_query(s, N, &l, &r)) {
					break;
				}
			}
			fprintf(stderr, "The index must be an integer between 1 and %zu.\n", N);
		} while (true);
#else
-		Q = N - K;
+		l = K + 1;
+		r = N;
#endif
		int sum;
-		if (!intArray->cumulative_sum(intArray, Q, &sum)) {
+		if (!intArray->interval_sum(intArray, --l, r, &sum)) {
			int e = errno;
			perror(NULL);
			return e;
		}
		printf("%d\n", sum);
	}
	free_Intarray(&intArray);
#ifndef NDEBUG
	fprintf(stderr, "%f sec.\n", (float) (clock() - clockt) / CLOCKS_PER_SEC);
#endif
	return 0;
}
テストコード

テストの内容だけ記載します（前後は省略）。あとは前回の記事のtest.cに埋め込んでください。

  • 最低限。1要素のみの配列に対して区間和（も何もないが）を求める
static char* test0() {
	const char *lines[] = { "1 1", "0", "1 1" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(1, n), n == 1);
	mu_assert(message_s("0\n", result[0]), !strcmp(result[0], "0\n"));
	return 0;
}
  • 入出力例1
static char* test1() {
	const char *lines[] = { "4 2", "16", "88", "10", "-65", "2 4", "1 2" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(2, n), n == 2);
	mu_assert(message_s("33\n", result[0]), !strcmp(result[0], "33\n"));
	mu_assert(message_s("104\n", result[1]), !strcmp(result[1], "104\n"));
	return 0;
}
  • 入出力例2
static char* test2() {
	const char *lines[] = { "10 5",
		"82", "-37", "40", "-72", "-24", "-54", "57", "-6", "42", "-24",
		"8 9", "6 9", "2 3", "4 4", "1 5" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(5, n), n == 5);
	mu_assert(message_s("36\n", result[0]), !strcmp(result[0], "36\n"));
	mu_assert(message_s("39\n", result[1]), !strcmp(result[1], "39\n"));
	mu_assert(message_s("3\n", result[2]), !strcmp(result[2], "3\n"));
	mu_assert(message_s("-72\n", result[3]), !strcmp(result[3], "-72\n"));
	mu_assert(message_s("-11\n", result[4]), !strcmp(result[4], "-11\n"));
	return 0;
}
  • 入力エラーを起こしながら実行
static char* test3() {
	const char *lines[] = {
		"100000  100000", "100001 100001", "0 0", "1 1 1", "2 3",
		"101", "-101", "-100", "100",
		"0 0", "1 1 1", "2", "2 1", "1 3", "1 1", "1 2", "2 2"
	};
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(3, n), n == 3);
	mu_assert(message_s("-100\n", result[0]), !strcmp(result[0], "-100\n"));
	mu_assert(message_s("0\n", result[1]), !strcmp(result[1], "0\n"));
	mu_assert(message_s("100\n", result[2]), !strcmp(result[2], "100\n"));
	return 0;
}
  • $N=100000$、$K=100000$の場合（時間測定用）
static char* test4() {
	static char *lines[200001] = { "100000 100000" };
	for (size_t i = 1; i <= 100000; i++) {
		lines[i] = "-100";
	}
	static char chars[100000][16] = {};
	for (size_t i = 0; i < 100000; i++) {
		snprintf(chars[i], sizeof(chars[i]), "%zu 100000", -~i);
		lines[100001 + i] = chars[i];
	}
	size_t n = test(sizeof(lines) / sizeof(lines[0]), (const char**) lines);
	mu_assert(message_u(100000, n), n == 100000);
	for (size_t i = 0; i < 100000; i++) {
		char expected[11];
		snprintf(expected, sizeof(expected), "-%zu00\n", 100000 - i);
		mu_assert(message_s(expected, result[i]), !strcmp(result[i], expected));
	}
	return 0;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?