Project Euler 問題22（名前スコア）を解いてみる

Project Euler で紹介されている問題22を解いてみました。入力をどのように扱うかが主題となります。Unix 流の解法も紹介します。

Project Euler 問題22（名前スコア）

解答例

問題が提供しているファイル「p022_names.txt」の内容は、以下のようになっています。

"MARY","PATRICIA","LINDA","BARBARA","ELIZABETH","JENNIFER","MARIA",...

1行のテキストファイルに5163名の名前が含まれています。

以下の操作が必要になります。

1. ダブルクォーテーションやカンマを取り除いて名前だけを得る。
2. 5163個の名前をアルファベット順にソートする。
3. 名前が持つアルファベット順から値を得る。
4. 名前の位置を掛けて、名前のスコアを得る。
5. すべての名前のスコアの合計を求める。

C 標準ライブラリのソート関数は、この用途には少し使いにくいです。ただし、上の操作の 1 と 2 を別のコマンドに任せると、この問題は楽に解決できます。

入力ファイルを使いやすい形に変換する

以下の Unix コマンドを使います。

• cat ー ファイルの内容を表示する。
• tr ー ファイルの文字を置換する、もしくは削除する。
• sort ー ファイルの内容をソートする。

具体的には、次のコマンドによって「sorted_names.txt」を得ることができます。

$ cat p022_names.txt | tr ',' '\n' | tr -d '"' | sort > sorted_names.txt

Unix の操作の一般的な解説になります。「|」は、パイプと呼ばれています。各コマンドの標準出力を、次のコマンドの標準入力につなげることができます。

最初は、ファイルを表示します（cat）。次にカンマを改行コードに置換します（最初の tr）。次にダブルクォーテーションを削除します（2番目の tr）。最後に名前をソートします（sort）。

ソート済ファイルは次のようになります。ファイルには、1行にひとつの名前が格納されています。名前の数だけ5163行のファイルとなります（7行に見えますが中略しています）。

AARON
ABBEY
ABBIE
   ...
ZULA
ZULEMA
ZULMA

プログラムの処理

名前の文字列から値を求める処理を別関数（calc_score）にします。また、スコアの値が32ビット整数を超える可能性があるため、合計は long long int 型の変数に格納します。

最後の処理をする C のプログラムは以下となります。

#include <stdio.h>

char buffer[256];

int calc_score(char string[])
{
	int index = 0;
	int score = 0;

	while (string[index] != 0) {
		score += (string[index] - 'A' + 1);
		++index;
	}

	return score;
}

int main(void)
{
	int line = 0;
	long long int sum = 0;

	while (scanf("%s", buffer) > 0) {
		++line;
		sum += calc_score(buffer) * line;
	}

	printf("Problem022: %lld\n", sum);

	return 0;
}

今回の処理は、プログラム一つで閉じていません。問題を単純な作業に分解して、ひとつひとつは単純なコマンドによって処理しています。これは、Unix のコマンドラインインターフェイス（CLI: command line interface）の重要な考え方です。

この考え方に従ったため、ライブライ機能が比較的弱い C でも問題を解くことができました。

なお、最後の Ｃ プログラムに「sorted_names.txt」を入力としてリダイレクトするには、次のコマンドを実行します。実行ファイル名は、「problem022.exe」としています。

$ ./problem022.exe < sorted_names.txt

以下のコマンドを実行すれば、中間ファイルを作る必要もなくなります。

$ cat p022_names.txt | tr ',' '\n' | tr -d '"' | sort | ./problem022.exe

解答例（すべてプログラムで処理する場合）

C++ を使って、この問題を解いてみます。C++ はライブライの機能が C より豊富なため、Unix コマンドで行っていた処理をプログラムとして楽に表現することができます。

以下は、実装の方針です。

• 名前は、string を要素に持つ vector コンテナに格納する。
• 入力ファイル（p022_names.txt）は標準入力として処理する。
• 入力は1行なので、全体をいったん string として格納する。
• ファイルの中身から名前を切り分けて、vector コンテナに格納する。
• sort する。
• 残りの処理は、C の場合と同じ。

以下は、C++ のプログラムです。

#include <iostream>
#include <vector>
#include <string>
#include <cctype>
#include <algorithm>

using namespace std;

int calc_score(string name)
{
	int index = 0;
	int score = 0;

	while (name[index] != 0) {
		score += (name[index] - 'A' + 1);
		++index;
	}

	return score;
}

int main()
{
	string buffer;
	cin >> buffer; // Read all file.

	vector<string> name;
	string name_buffer;
	bool in_name = false;
	for (int i = 0; i < buffer.size(); ++i) {
		if (isupper(buffer[i])) {
			name_buffer += buffer[i];
			in_name = true;
		} else {
			if (in_name) {
				name.push_back(name_buffer);
				name_buffer.clear();
				in_name = false;
			}
		}
	}

	sort(name.begin(), name.end());

	long long int sum = 0;
	for (int i = 0; i < name.size(); ++i) {
		sum += calc_score(name[i]) * (i + 1);
	}

	cout << "Problem022: " << sum << endl;

    return 0;
}

最後に

Unix の基本的な考え方を用いて、作業を単純な処理に分けて処理をしました。

次に C++ を使って問題を解きました。C++ は C と比較すると、ライブラリの機能が強力なため、プログラムひとつに閉じて処理できました。

一昔前は、Unix の流儀を採用する場合が多かったのですが、コンピュータの処理能力が上がり、そのため、プログラミング言語の表現能力が上がり、全体をひとつに閉じて処理する傾向がでてきたように感じます。

引き続き、Project Euler の問題を紹介していきます。