Project Euler で紹介されている問題17を解いてみました。数学的な要素はなく、プログラミングの問題です。ある程度の長さがあるプログラムなので、段階的に作りこむ様子を紹介します。
Project Euler 問題17（数字の文字数）
1 から 5 までの数字を書くと、one、two、three、four、five となり、3 + 3 + 5 + 4 + 4 = 19 文字が使われている。
1 から 1000 までの数字をすべて書くと何文字使われるか求めよ。
注：スペースやハイフンは数えないでください。例えば、342（three hundred and forty-two）は、23文字を含みます。115（one hundred and fifteen）は、20文字を含みます。数字を書きだすときに「and」を使うのは、イギリスの用法です。
解答例（第一段階）
この問題は、純粋にプログラミングの問題です。
以下のように解いていきます。
- 1 から 1000 までの単語を出力するプログラムを書く。
- このプログラムの出力する英字をカウントする。
このように2段階に分けるのは、いきなり文字数を出力しても、それが不正解になったときに、どこが間違ったか分からないためです。まず数字を単語として出力して、その内容を確認して先に進めたほうが良いと考えました。
第一段階の1 19までの単語を出力する
最初に、法則性が弱い19までの単語を出力しましょう。C言語で実装しました。
#include <stdio.h>
char *word_under19[20] = {
"zero", "one", "two", "three", "four"
, "five", "six", "seven", "eight", "nine"
, "ten", "eleven", "twelve", "thirteen", "fourteen"
, "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
char * num2word(int number)
{
return word_under19[number];
}
int main(void)
{
int i;
for (i = 1; i <= 19; ++i) {
printf("%s\n", num2word(i));
}
return 0;
}関数 num2word は、数字を引数に与えると、その単語の文字列へのポインタを渡します。この段階では、1から19の単語を返すだけです。いままでの Project Euler の問題で使っていなかったポインタを使っています。文法的な難易度が上がりましたので、分かりにくいかたは、プログラムを段階的に作りこむ様子を読み取っていただければと思います。
出力を確認して、1から19の単語がでていることを確認しました。
第一段階の2 99までの単語を出力する
99までの単語を3つの場合に分けて考えます。
- 19までの数字（第一段階の1と同じ）
- 20以上で、10で割り切れる数字（twenty, thirty, …, ninety）
- それ以外（XX-YY の形の単語になる。例 forty-two）
99以下を処理する関数 num2word_under99 を関数 num2word と分けて実装することにします。
関数 num2word_under99 は、外部で定義した変数 buffer_under99 に文字列を出力して、それを返すようにしました。新しい単語の配列 *word_10n も用意して、10の桁の単語を定義しました。num2word は、num2word_under99 が返したポインタを返すだけにしています。
コード差分のみ、以下に示します。
char buffer_under99[50];
char *word_10n[10] = {
"zero", "ten", "twenty", "thirty", "forty"
, "fifty", "sixty", "seventy", "eighty", "ninety"};
char * num2word_under99(int number)
{
if (number <= 19) {
sprintf(buffer_under99, "%s", word_under19[number]);
} else if (number % 10 == 0) {
sprintf(buffer_under99, "%s", word_10n[number / 10]);
} else {
sprintf(buffer_under99, "%s-%s", word_10n[number / 10], word_under19[number % 10]);
}
return buffer_under99;
}
char * num2word(int number)
{
return num2word_under99(number);
}出力を確認して、1から99の単語がでていることを確認しました。
第一段階の3 1000までの単語を出力する
1000までの単語は次のように場合分けできます。
- 99までの数字（第一段階の2と同じ）
- 1000（これは例外なので先に処理します。one thousand と出力します。）
- 100以上で、100で割り切れる数字（one hundred, two hundred, …, nine hundred）
- それ以外（XXX hundred and YY-ZZ）
もともと99以下を処理する関数を分けていましたので、関数 num2word の実装に集中できるようになっています。少し長いですが、すべてのコードを示します。第一段階の2からのコード差分の背景色を変更しました。
#include <stdio.h>
char buffer_under99[50];
char buffer[100];
char *word_under19[20] = {
"zero", "one", "two", "three", "four"
, "five", "six", "seven", "eight", "nine"
, "ten", "eleven", "twelve", "thirteen", "fourteen"
, "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
char *word_10n[10] = {
"zero", "ten", "twenty", "thirty", "forty"
, "fifty", "sixty", "seventy", "eighty", "ninety"};
char * num2word_under99(int number)
{
if (number <= 19) {
sprintf(buffer_under99, "%s", word_under19[number]);
} else if (number % 10 == 0) {
sprintf(buffer_under99, "%s", word_10n[number / 10]);
} else {
sprintf(buffer_under99, "%s-%s", word_10n[number / 10], word_under19[number % 10]);
}
return buffer_under99;
}
char * num2word(int number)
{
if (number <= 99) {
sprintf(buffer, "%s", num2word_under99(number));
} else if (number == 1000) {
sprintf(buffer, "one thousand");
} else if (number % 100 == 0) {
sprintf(buffer, "%s hundred", word_under19[number / 100]);
} else {
sprintf(buffer, "%s hundred and %s"
, word_under19[number / 100], num2word_under99(number % 100));
}
return buffer;
}
int main(void)
{
int i;
for (i = 1; i <= 1000; ++i) {
printf("%s\n", num2word(i));
}
return 0;
}長い出力でしたが、1から1000までの単語が正しく出力できていることを確認しました。
解答例（第二段階）
ここまでくれば、この問題の大部分は解決できました。あとは、単語を出力するのではなく英字を数えて、その合計を表示するだけです。
文字数をカウントする関数 count_alphabet を作って、main の中で、文字数の合計を求めて、解答として出力しました。これが最終版です。第一段階の3からのコード差分の背景色を変更しました。
#include <stdio.h>
char buffer_under99[50];
char buffer[100];
char *word_under19[20] = {
"zero", "one", "two", "three", "four"
, "five", "six", "seven", "eight", "nine"
, "ten", "eleven", "twelve", "thirteen", "fourteen"
, "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
char *word_10n[10] = {
"zero", "ten", "twenty", "thirty", "forty"
, "fifty", "sixty", "seventy", "eighty", "ninety"};
char * num2word_under99(int number)
{
if (number <= 19) {
sprintf(buffer_under99, "%s", word_under19[number]);
} else if (number % 10 == 0) {
sprintf(buffer_under99, "%s", word_10n[number / 10]);
} else {
sprintf(buffer_under99, "%s-%s", word_10n[number / 10], word_under19[number % 10]);
}
return buffer_under99;
}
char * num2word(int number)
{
if (number <= 99) {
sprintf(buffer, "%s", num2word_under99(number));
} else if (number == 1000) {
sprintf(buffer, "one thousand");
} else if (number % 100 == 0) {
sprintf(buffer, "%s hundred", word_under19[number / 100]);
} else {
sprintf(buffer, "%s hundred and %s"
, word_under19[number / 100], num2word_under99(number % 100));
}
return buffer;
}
int count_alphabet(char buffer[])
{
int index = 0;
int count = 0;
while (buffer[index] != 0) {
if (('a' <= buffer[index])&&(buffer[index] <= 'z')) {
++count;
}
++index;
}
return count;
}
int main(void)
{
int i;
int sum = 0;
for (i = 1; i <= 1000; ++i) {
sum += count_alphabet(num2word(i));
}
printf("Problem017: %d\n", sum);
return 0;
}Project Euler は、解答のみを入力します。サイトの反応も、正しいか、間違っているか、しか出力されません。段階的にプログラミングをした成果で、一度で正解となりました。
最後に
今回は、純粋にプログラミングの問題でした。非常に才能がある人だと、正解を出力するプログラムを一発で書きあげることができるかもしれません。
一方、今回のように差分を明確にして、段階的に作りこむ場合、多少時間がかかるかもしれませんが、着実に正解に近づいていきます。途中で、どこかで間違いが発生しても、このやり方だといろいろな対応ができます。
70行程度のプログラムでしたが、参考になれば幸いです。
引き続き、Project Euler の問題を紹介していきます。
