グリーディその１辞書順比較

Program

貪欲法って、パズル的な閃きが重要なのかな？

うまいやり方だなあ。。

// best cow line
// 辞書順比較で小さくなるようにsourceの前後からtargetに文字追加
// ひっくり返したのと辞書順比較してみると追加すべきものがわかる
// nekohand

#include <cstdio>
#include <cstdlib>
#include <cfloat>
#include <ctime>
#include <deque>
#include <cassert>
#include <queue>
#include <cstring>

using namespace std;

typedef deque<char> Text;
typedef queue<Text> State;

Text g_source;
Text g_target;
Text g_reverse;

const int TEXT_MIN = 3;
const int TEXT_MAX = 10;

float getRandFlt(float min, float max) {
	float length = max-min;

	assert(0.0f<=length);
	assert(FLT_MAX/2.0f>length);

	static bool init = false;
	if (!init) {
		init = true;
		srand(static_cast<unsigned int>(time(0)));
	}

	float r = static_cast<float>(rand())/static_cast<float>(RAND_MAX);
	r = length*r + min;

	return r;
}

int getRandInt(int min, int max) {
	float r_raw = getRandFlt(static_cast<float>(min), static_cast<float>(max));
	int r = static_cast<int>(r_raw);
	return r;
}

char getRandAlphabet(bool capitalize) {
	int num = getRandInt(0, 'z'-'a');
	char c = capitalize ? 'A' : 'a' + num;
	return c;
}

void init(int length, Text &text, bool capitalize) {
	for(int i=0; i<length; ++i) {
		char c = getRandAlphabet(capitalize);
		text.push_back(c);
	}
}

void init() {
	int source_lenght = getRandInt(TEXT_MIN, TEXT_MAX);
	init(source_lenght, g_source, false);

	int target_lenght = getRandInt(TEXT_MIN-1, source_lenght-1);
	init(target_lenght, g_target, false);

	for(int i=source_lenght-1; i>=0; --i) {
		g_reverse.push_back(g_source.at(i));
	}
}

void show(Text &text, char *mes) {
	printf("%s is :", mes);
	for(unsigned int i=0; i<text.size(); ++i)
		printf("%c", text.at(i));
	printf("\n");
}

void show() {
	show(g_source, "source");
	show(g_target, "target");
	show(g_reverse, "reverse");
}

int cmp(Text &t1, Text &t2) {
	int r = 0;
	for(unsigned int i=0; i<t1.size(); ++i) {
		if (i>t2.size()) {
			r = -1;
		}

		char c1 = t1.at(i);
		char c2 = t2.at(i);
		r = strncmp(&c1, &c2, 1);
		if (0!=r) {
			break;
		}
	}

	return r;
}

void update() {
	unsigned int length = g_source.size();
	while(g_target.size()<length) {
		int r = cmp(g_source, g_reverse);
		if (r<=0) {
			g_target.push_back(g_source.front());
			g_source.pop_front();
			g_reverse.pop_back();
		} else {
			g_target.push_back(g_reverse.front());
			g_source.pop_back();
			g_reverse.pop_front();
		}
	}
}

int main() {
	init();
	show();
	update();
	show();
	return 0;
}

むしろ、乱数関数の再開発に時間かかりましたとさ。。