CodeIQ「中学入試から：対称軸の本数を数えよう」解答コード

cn_taisyozikunohonsu.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* メモリを確保し、確保できなかったら終了する */
void *malloc_with_check(size_t size) {
	void *ret = malloc(size);
	if (ret == NULL) {
		fputs("malloc failed!\n", stderr);
		exit(1);
	}
	return ret;
}
/* mallocを直接使おうとした場合にエラーにする */
#define malloc DO_NOT_USE_MALLOC_DIRECTLY

typedef struct idlist_node_t_tag {
	char *id;
	struct idlist_node_t_tag *next;
} idlist_node_t;

typedef struct {
	idlist_node_t *head;
	idlist_node_t *tail;
} idlist_t;

/* IDのリストを作成する */
idlist_t *idlist_create(void) {
	idlist_t *ret = (idlist_t*)malloc_with_check(sizeof(idlist_t));
	ret->head = ret->tail = NULL;
	return ret;
}

/* IDのリストを開放する */
void idlist_free(idlist_t *lst) {
	if (lst != NULL) {
		idlist_node_t *node = lst->head;
		while (node != NULL) {
			idlist_node_t *next_node = node->next;
			free(node->id);
			free(node);
			node = next_node;
		}
		free(lst);
	}
}

/* IDのリストに要素を追加する */
void idlist_add(idlist_t *lst, const char *id) {
	if (lst != NULL) {
		/* ノードの作成 */
		idlist_node_t *node = (idlist_node_t*)malloc_with_check(sizeof(idlist_node_t));
		if (id != NULL) {
			node->id = (char*)malloc_with_check(sizeof(char) * (strlen(id) + 1));
			strcpy(node->id, id);
		} else {
			node->id = NULL;
		}
		node->next = NULL;
		/* ノードの追加 */
		if (lst->tail == NULL) {
			/* 最初のノード */
			lst->head = lst->tail = node;
		} else {
			/* 末尾に追加 */
			lst->tail->next = node;
			lst->tail = node;
		}
	}
}

/* IDのリストを出力し、改行する。要素数を返す */
int idlist_print(const idlist_t *lst) {
	int elem_count = 0;
	if (lst != NULL) {
		idlist_node_t *cur = lst->head;
		while (cur != NULL) {
			elem_count++;
			if (cur->id != NULL) fputs(cur->id, stdout);
			cur = cur->next;
			if (cur != NULL) putchar(',');
		}
		putchar('\n');
	}
	return elem_count;
}

/* 大文字アルファベットを受け取り、それが何番目かを返す */
int alphabet_to_number(char c) {
	static const char *alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int i;
	for (i = 0; alphabets[i] != '\0'; i++) {
		if (alphabets[i] == c) return i;
	}
	return -1;
}

/* 線分のリストをパースし、線分が存在するかのフラグの配列を返す */
char *parse_segments(int num, const char *segments) {
	int row_max = num * 2;
	int array_max = row_max * row_max;
	char *segment_exists = (char*)malloc_with_check(sizeof(char) * array_max);
	int i;
	/* 初期化 */
	for (i = 0; i < array_max; i++) segment_exists[i] = 0;
	/* 線分を登録する */
	if (segments != NULL) {
		for (i = 0; segments[i] != '\0';) {
			/* 線分の位置を調べる */
			int s = alphabet_to_number(segments[i]) * 2;
			int e = alphabet_to_number(segments[i + 1]) * 2;
			/* 線分を登録する */
			if (s < 0 || e < 0) {
				free(segment_exists);
				return NULL;
			}
			segment_exists[s * row_max + e] = 1;
			segment_exists[e * row_max + s] = 1;
			/* 次の線分を見る */
			i += 2;
			if (segments[i] == ',') i++;
		}
	}
	return segment_exists;
}

/* 指定の軸で反転した点を求める */
int get_flipped_point(int num, int axis, int point) {
	int row_max = num * 2;
	int ret;
	/* 軸を0に持ってくる */
	ret = point - axis;
	if (ret < 0) ret += row_max;
	/* ひっくり返す(軸が0なので、0はひっくり返しても0) */
	if (ret > 0) ret = row_max - ret;
	/* 軸を戻す */
	ret += axis;
	if (ret >= row_max) ret -= row_max;
	return ret;
}

/* axisが対称軸かを判定する */
int is_axis_of_symmetry(int num, const char *segment_exists, int axis) {
	int row_max = num * 2;
	int i, j;
	if (segment_exists != NULL) {
		for (i = 0; i < row_max; i++) {
			for (j = 0; j < row_max; j++) {
				/* 存在する線分について */
				if (segment_exists[i * row_max + j]) {
					/* 軸で反転した線分を求める */
					int fi = get_flipped_point(num, axis, i);
					int fj = get_flipped_point(num, axis, j);
					/* そこに線分が無ければダメ */
					if (!segment_exists[fi * row_max + fj]) return 0;
				}
			}
		}
	}
	return 1;
}

/* 問題を解く */
int solve(int num, const char *segments) {
	char *segment_exists;
	int count = 0;
	int i;
	/* 線分の情報を取得する */
	segment_exists = parse_segments(num, segments);
	if (segment_exists == NULL) return -1;
	/* それぞれの軸について、対称軸かを判定する */
	for (i = 0; i < num; i++) {
		if (is_axis_of_symmetry(num, segment_exists, i)) count++;
	}
	free(segment_exists);
	return count;
}

int main(void) {
	char input_buffer[1024];
	idlist_t *answer_list;
	int answer_num;

	/* 答えのリストを作成する */
	answer_list = idlist_create();

	/* 問題を解く */
	while (fgets(input_buffer, sizeof(input_buffer), stdin) != NULL) {
		char id[1024];
		int num;
		char segments[1024];
		int expected_answer;
		int got_answer;
		if (sscanf(input_buffer, "%1023s%d%1023s%d", id, &num, segments, &expected_answer) == 4) {
			got_answer = solve(num, segments);
			if (got_answer != expected_answer) {
				printf("mismatch in %s : expected %d, got %d\n", id, expected_answer, got_answer);
				idlist_add(answer_list, id);
			}
		}
	}

	/* 答えを出力して終了する */
	puts("\nThe answers:");
	answer_num = idlist_print(answer_list);
	printf("\n%d answer(s) found.\n", answer_num);
	idlist_free(answer_list);
	return 0;
}