4問目

回文数はどちらから読んでも同じ数字になる. 2つの2桁の数の積となる最大の回文数は 9009 = 91 × 99 だ.
では, 2つの3桁の数の積となる最大の回文数を求めよ.

http://projecteuler.net/index.php?section=problems&id=4

今回のは回文数が題材で, その生成や判定が面倒だった. やっぱり C は数値計算とかメモリの配置を意識したようなプログラムに向いてる反面, 人間にとって分かりやすい意味を扱うのが苦手な印象を受けた. 「〜桁目の数字」を求める digitAt 関数を作りながらそう思った.

問題に正解すると他の人のコードも読め, 色々参考になる. 自分のコードはある程度再利用性や可読性を考えて書いているので, どうしても長くなってしまうが, それを考慮しても PerlHaskell などはもっと短く書けるみたいだ. C は文字列操作が苦手だからねぇ(^-^;

そしていつもの通り, 安直バージョンの solveVer00 関数と, 無駄な処理をできるだけしないように考慮した solveVer01 関数を書いてみたが, 見た目には速度は全く変わらず一瞬で終わった. brute force(力付く, ごり押し)でやってもこれだけ速いなんて, やっぱり現代は富豪的プログラミングの時代だなぁ, としみじみ思う.

/* Problem004.c */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <ctype.h>
#include <math.h>
#include "palindrome.h"

#define LENGTH_OF_PALIND 6
#define LENGTH_OF_FACTOR 3
#define MAX_3_FIGURES_NUM 999
#define MIN_3_FIGURES_NUM 100
#define MAX_6_FIGURES_NUM 999999
#define MIN_6_FIGURES_NUM 100000

int parseArg(int, char**);
void solveVer00();
void solveVer01();

int version;

int main(int argc, char **argv) {
	if (parseArg(argc, argv) == EXIT_FAILURE) {
		return EXIT_FAILURE;
	}
	switch (version) {
	case 0:
		solveVer00();
		break;
	case 1:
		solveVer01();
		break;
	default:
		break;
	}
	return EXIT_SUCCESS;
}

int parseArg(int argc, char **argv) {
	int optChar;

	// default values
	version = 0;

	while ((optChar = getopt(argc, argv, "v:")) != -1) {
		switch (optChar) {
		case 'v':
			version = atoi(optarg);
			break;
		case '?':
			if (optopt == 'c') {
				fprintf(stderr, "Option -%c requires an argument.\n", optopt);
			} else if (isprint(optopt)) {
				fprintf(stderr, "Unknown option `-%c'.\n", optopt);
			} else {
				fprintf(stderr, "Unknown option character `\\x%x'.\n", optopt);
			}
			return EXIT_FAILURE;
		default:
			abort();
		}
	}
	return EXIT_SUCCESS;
}

void solveVer00() {
	int number;
	int factor;
	int cofactor;

	for (number = MAX_6_FIGURES_NUM; number > MIN_6_FIGURES_NUM; number--) {
		if (isPalindrome(number)) {
			for (factor = MAX_3_FIGURES_NUM; factor >= MIN_3_FIGURES_NUM; factor--) {
				if ((number % factor) == 0) {
					cofactor = number / factor;
					if (cofactor <= MAX_3_FIGURES_NUM) {
						goto success;
					}
				}
			}
		}
	}
	fprintf(stdout, "Cannot find solution.\n");
	return;
success:
	fprintf(stdout, "Solution: %d = %d * %d.\n", number, factor, cofactor);
}

void solveVer01() {
	int number;
	int factor;
	int cofactor;
	int palindrome;

	for (number = MAX_3_FIGURES_NUM; number >= MIN_3_FIGURES_NUM; number--) {
		palindrome = getPalindrome(number, LENGTH_OF_PALIND);
		for (factor = number + 1; factor <= MAX_3_FIGURES_NUM; factor++) {
			if ((palindrome % factor) == 0) {
				cofactor = palindrome / factor;
				goto success;
			}
		}
	}
	fprintf(stdout, "Cannot find solution.\n");
	return;
success:
	fprintf(stdout, "Solution: %d = %d * %d.\n", palindrome, factor, cofactor);
}
/* palindrome.h */
#ifndef __PALINDROME_H__
#define __PALINDROME_H__

#include <math.h>

#define RADIX 10

int getPalindrome(int, int);
int isPalindrome(int);

#endif
#include "palindrome.h"

int digitAt(double, int);

/*
 * Return the palindrome.
 * - halfLeft = 123, lengthOfPalind = 0 -> 0
 * - halfLeft = 123, lengthOfPalind = 1 -> 1
 * - halfLeft = 123, lengthOfPalind = 2 -> 11
 * - halfLeft = 123, lengthOfPalind = 3 -> 121
 * - halfLeft = 123, lengthOfPalind = 4 -> 1221
 * - halfLeft = 123, lengthOfPalind = 5 -> 12321
 * - halfLeft = 123, lengthOfPalind = 6 -> 123321
 * - halfLeft = 123, lengthOfPalind = 7 -> 1230321
 */
int getPalindrome(int halfLeft, int lengthOfPalind) {
	int halfLength;
	int lengthOfHalfLeft;
	int result;
	int i, j;
	int digit;

	halfLength = lengthOfPalind / 2;
	lengthOfHalfLeft = (int) (log(halfLeft) / log(RADIX)) + 1;

	for (i = lengthOfPalind - 1, j = 0, result = 0; i > j; i--, j++) {
		digit = digitAt(halfLeft, --lengthOfHalfLeft);
		result += digit * (pow(RADIX, i) + pow(RADIX, j));
	}
	if (i == j) {
		digit = digitAt(halfLeft, --lengthOfHalfLeft);
		result += digit * pow(RADIX, i);
	}
	return result;
}

/*
 * number = 123456, place = 0 -> 6
 * number = 123456, place = 1 -> 5
 * number = 123456, place = 2 -> 4
 * number = 123456, place = 3 -> 3
 * number = 123456, place = 4 -> 2
 * number = 123456, place = 5 -> 1
 * number = 123456, place = 6 -> 0
 */
int digitAt(double number, int place) {
	number /= pow(RADIX, place);
	return (int) number % RADIX;
}

int isPalindrome(int number) {
	int lengthOfNumber;
	int i, j;

	lengthOfNumber = (int) log(number) / log(RADIX) + 1;
	for (i = lengthOfNumber - 1, j = 0; i > j; i--, j++) {
		if (digitAt(number, i) != digitAt(number, j)) {
			return 0;
		}
	}
	return 1;
}