Project Euler 79

オンラインバンクで通常使われるsecurity methodは, パスコードからランダムに選んだ3文字をユーザーに要求するものである.

たとえば, パスコードが531278のとき, 2番目, 3番目, 5番目の文字を要求されるかもしれない. このとき, 期待される答えは: 317 である.

テキストファイルkeylog.txtには, ログインに成功した50回の試行が記録されている.

3つの文字が常に順番通りに要求されるとするとき, ファイルを分析して, 可能なパスコードのなかでもっとも短いものを見つけよ.

C/C++

#include <iostream>
#include <fstream>
#include <set>
#include <deque>
using namespace std;

int main(){
	set<int> nums;

	//ファイル読み込み
	ifstream ifs("dat079.txt");
	int tmp;
	for(int i=0 ; i<50 ; i++){
		ifs >> tmp;
		nums.insert(tmp);
	}

	/*
	nums2dにnumsの値を2桁にして入れる。
	128は12と28と18になる。
	これはそれぞれ 1->2, 2->8, 1->8 という拘束条件を表す。
	*/
	set<int> nums2d;
	set<int>::iterator it = nums.begin();
	int k;
	for(int i=0 ; i<(signed)nums.size() ; i++){
		k = *it;
		//1桁目と2桁目
		nums2d.insert(k/10);
		//2桁目と3桁目
		nums2d.insert(k%100);
		//1桁目と3桁目
		nums2d.insert((k/100)*10+k%10);
		it++;
	}

	// nums2d 表示
	set<int>::iterator itt = nums2d.begin();
	for(int i=0 ; i<(signed)nums2d.size() ; i++){
		cout << *itt << endl;
		itt++;
	}
	cout << endl;


	itt = nums2d.begin();
	int s[10];
	for(int i=0 ; i<10 ; i++){
		s[i] = 0;
	}
	
	//1桁目と2桁目に出てくる登場回数を数えて、
	//一番大きいものから並べる。
	//※数列に2回以上同じ数字が出てくる場合は使えない。
	for(int i=0 ; i<(signed)nums2d.size() ; i++){
		k= *itt;
		s[k%10]--;
		s[k/10]++;
		itt++;
	}

	for(int i=0 ; i<10 ; i++){
		cout << i << " " << s[i] << endl;
	}

	bool flag=true;
	while(flag){
		int max=-999, maxp;
		for(int i=0 ; i<10 ; i++){
			if(max<s[i] && s[i]!=0){
				maxp = i;
				max = s[i];
			}
		}
		cout << maxp;
		s[maxp] = 0;

		flag = false;
		for(int i=0 ; i<10 ; i++){
			if(s[i]!=0) flag = true;
		}
	}
	cout << endl;
}

気づいたら関数何も作ってなかった。だって関数化しても再利用できそうな処理ばっかりなんだもの・・・
それにしても今回のコードは応急処置にもほどがある。もっと大きい場合は全然使えなくなっちゃうので、機会があれば作り直したいところ。