projecteuler/PE098.cpp at master · kart/projecteuler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cassert>
#include <hash_set>

using namespace std;

map<string, vector<string> > anagrams;
map<long long, vector<long long> > int_anagrams;
hash_set<string> squares;
hash_set<char> used;

#define MAX			999999999

string convert2string(long long N)
{
	stringstream ss;
	ss << N;
	return ss.str();
}

string string_signature(string word)
{
	vector<char>	v;
	string			s = "";

	for (int i = 0; i < word.length(); i++)
		v.push_back(word[i]);
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
		s += v[i];
	return s;
}

bool replace_all(string &s1, string &s2, char c1, char c2)
{
	assert(s1.length() == s2.length());
	for (int i = 0; i < s1.length(); i++)
	{
		if (s1[i] == c1)
			s1[i] = c2;
		if (s2[i] == c1)
			s2[i] = c2;
	}
	return true;
}

string		square_anagram(string s1, string s2)
{
	int			len = s1.length(), i;
	string		ret;

	for (i = 0; i < len; i++)
		if ((s1[i] >= 'A' && s1[i] <= 'Z'))
			break;
	if (i == len)
	{
		if (squares.find(s1) != squares.end() && squares.find(s2) != squares.end())
		{
			if (s1 > s2)
				return s1;
			return s2;
		}
		return "";
	}
	for (char c = '9'; c >= (i == 0 ? '1' : '0'); c--)
	{
		char save = s1[i];
		if (used.find(c) != used.end())
			continue;
		replace_all(s1, s2, s1[i], c);
		used.insert(c);
		if ((ret = square_anagram(s1, s2)) != "")
			return ret;
		used.erase(c);
		replace_all(s1, s2, c, save);
	}
	return "";
}

int PE098()
{
	ifstream	fs;
	string		line;
	int			count = 0;

	fs.open("C:\\Users\\Karthik\\words2.txt", ifstream::in);
	getline(fs, line);
	istringstream ss(line);

	while (ss)
	{
		string		word, sig;
		if (!getline(ss, word, ','))
			break;
		sig = string_signature(word);
		if (anagrams.find(sig) != anagrams.end())
			anagrams[sig].push_back(word);
		else
		{
			vector<string> v(1, word);
			anagrams[sig] = v;
		}
	}
	for (long long i = 1; i * i <= MAX; i++)
		squares.insert(convert2string(i * i));
	for (map<string, vector<string> >::iterator it = anagrams.begin(); it != anagrams.end(); it++)
	{
		vector<string>		v = (*it).second;
		string				ret;

		if (v.size() == 2 && v[0].length() >= 4)
		{
			used.clear();
			if ("" != (ret = square_anagram(v[0], v[1])))
				cout << v[0] << "; " << v[1] << " == > " << ret << endl;
		}
	}
	fs.close();
	return 0;
}