fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <random>
  5. #include <cassert>
  6.  
  7. using namespace std;
  8.  
  9. // Letter-Frequency pair
  10. typedef pair<char, float> pair_lf;
  11.  
  12. void print(const vector<pair_lf> &vec)
  13. {
  14. 	for (const pair_lf item : vec)
  15. 	{
  16. 		cout << item.first << ": " << item.second << endl;
  17. 	}
  18. }
  19.  
  20. enum class EMove
  21. {
  22. 	N,
  23. 	NE,
  24. 	E,
  25. 	SE,
  26. 	S,
  27. 	SW,
  28. 	W,
  29. 	NW,
  30. 	Last,
  31. 	First = N,
  32. };
  33.  
  34. inline EMove operator++( EMove& x ) { return x = (EMove)(std::underlying_type<EMove>::type(x) + 1); }
  35. EMove operator*(EMove c) {return c;} 
  36. EMove begin(EMove r) {return EMove::First;}
  37. EMove end(EMove r)   {return EMove::Last;}
  38.  
  39. int move(const unsigned int &start, const unsigned int &w, const unsigned int &h, const EMove &m)
  40. {
  41. 	switch (m)
  42. 	{
  43. 		case EMove::N:
  44. 			if (start < w)
  45. 			{
  46. 				return -1;
  47. 			} else {
  48. 				return start - w;
  49. 			}
  50. 			break;
  51. 		case EMove::NE:
  52. 			if (start < w || ((start + 1) % w == 0))
  53. 			{
  54. 				return -1;
  55. 			} else {
  56. 				return start - w + 1;
  57. 			}
  58. 			break;
  59. 		case EMove::E:
  60. 			if ((start + 1) % w == 0)
  61. 			{
  62. 				return -1;
  63. 			} else {
  64. 				return start + 1;
  65. 			}
  66. 			break;
  67. 		case EMove::SE:
  68. 			if (((start + w) > (w * h - 1)) || ((start + 1) % w == 0))
  69. 			{
  70. 				return -1;
  71. 			} else {
  72. 				return start + w + 1;
  73. 			}
  74. 			break;
  75. 		case EMove::S:
  76. 			if ((start + w) > (w * h - 1))
  77. 			{
  78. 				return -1;
  79. 			} else {
  80. 				return start + w;
  81. 			}
  82. 			break;
  83. 		case EMove::SW:
  84. 			if ((start + w) > (w * h - 1) || (start % w == 0))
  85. 			{
  86. 				return -1;
  87. 			} else {
  88. 				return start + w - 1;
  89. 			}
  90. 			break;
  91. 		case EMove::W:
  92. 			if (start % w == 0)
  93. 			{
  94. 				return -1;
  95. 			} else {
  96. 				return start - 1;
  97. 			}
  98. 			break;
  99. 		case EMove::NW:
  100. 			if ((start % w == 0) || (start < w))
  101. 			{
  102. 				return -1;
  103. 			} else {
  104. 				return start - w - 1;
  105. 			}
  106. 			break;
  107. 	}
  108. 	assert(false);
  109. 	return -1;
  110. }
  111.  
  112. bool verify_word(const vector<char> &grid, const unsigned int &w, const unsigned int &h, vector<bool> visited, const string &word, int start)
  113. {
  114. 	if (start == -1)
  115. 	{
  116. 		for (int y = 0; y < h; y++)
  117. 		{
  118. 			for (int x = 0; x < w; x++)
  119. 			{
  120. 				const int new_start = y * w + x;
  121. 				bool found = verify_word(grid, w, h, visited, word, new_start);
  122. 				if (found)
  123. 				{
  124. 					return true;
  125. 				}
  126. 			}
  127. 		}
  128. 		return false;
  129. 	}
  130. 	if (visited[start])
  131. 	{
  132. 		return false;
  133. 	}
  134. 	const unsigned int length = word.length();
  135. 	if (grid[start] == word[length - 1])
  136. 	{
  137. 		if (length == 1)
  138. 		{
  139. 			return true;
  140. 		} else {
  141. 			const string new_word = word.substr(0, length - 1);
  142. 			vector<bool> new_visited = visited;
  143. 			new_visited[start] = true;
  144. 			for (EMove m : EMove())
  145. 			{
  146. 				int new_start = move(start, w, h, m);
  147. 				if (new_start == -1)
  148. 				{
  149. 					continue;
  150. 				}
  151. 				bool found = verify_word(grid, w, h, new_visited, new_word, new_start);
  152. 				if (found)
  153. 				{
  154. 					return true;
  155. 				}
  156. 			}
  157. 			return false;
  158. 		}
  159. 	} else {
  160. 		return false;
  161. 	}
  162. }
  163.  
  164. int main()
  165. {
  166. 	vector<pair_lf> letter_freqs;
  167. 	int count;
  168. 	cin >> count;
  169. 	for (int i = 0; i < count; i++)
  170. 	{
  171. 		char letter;
  172. 		float freq;
  173. 		cin >> letter >> freq;
  174. 		letter_freqs.push_back(make_pair(letter, freq / 100.f));
  175. 	}
  176. 	struct {
  177. 		bool operator()(const pair_lf left, const pair_lf right)
  178. 		{
  179. 			return left.second < right.second;
  180. 		}
  181. 	} pairwise_comparator;
  182. 	sort(letter_freqs.begin(), letter_freqs.end(), pairwise_comparator);
  183. 	vector<pair_lf> bucketed_letters;
  184. 	float sum = 0.f;
  185. 	for (const pair_lf &item : letter_freqs)
  186. 	{
  187. 		sum += item.second;
  188. 		bucketed_letters.push_back(make_pair(item.first, sum));
  189. 	}
  190. 	//cout << "sum: " << sum << endl;
  191. 	random_device rd;
  192. 	int seed = rd();
  193. 	seed = -740863471;
  194. 	cout << "seed: " << seed << endl;
  195. 	mt19937 gen(seed);
  196. 	vector<char> sampled_letters;
  197. 	int w, h;
  198. 	cin >> w >> h;
  199. 	const int grid_size = w * h;
  200. 	//print(bucketed_letters);
  201. 	for (int i = 0; i < grid_size; i++)
  202. 	{
  203. 		const float sample = generate_canonical<float, 10>(gen);
  204. 		int bucket = 0;
  205. 		while (sample > bucketed_letters[bucket].second)
  206. 		{
  207. 			bucket++;
  208. 		}
  209. 		assert(bucket < 26);
  210. 		const auto letter = bucketed_letters[bucket].first;
  211. 		sampled_letters.push_back(letter);
  212. 	}
  213. 	for (int y = 0; y < h; y++)
  214. 	{
  215. 		for (int x = 0; x < w; x++)
  216. 		{
  217. 			cout << sampled_letters[y * w + x] << ' ';
  218. 		}
  219. 		cout << endl;
  220. 	}
  221. 	vector<bool> visited(grid_size, false);
  222. 	while (cin)
  223. 	{
  224. 		string word;
  225. 		cin >> word;
  226. 		const int length = word.length();
  227. 		if (length >= 4 && length < grid_size)
  228. 		{
  229. 			bool found = verify_word(sampled_letters, w, h, visited, word, -1);
  230. 			if (found)
  231. 			{
  232. 				cout << "found " << word << endl;
  233. 			}
  234. 		}
  235. 	}
  236. 	return 0;
  237. }
  238.  
Success #stdin #stdout 0s 3288KB
comments (?)
stdin
copy 
26
a 	8.167
b 	1.492
c 	2.782
d 	4.253
e 	12.702
f 	2.228
g 	2.015
h 	6.094
i 	6.966
j 	0.153
k 	0.772
l 	4.025
m 	2.406
n 	6.749
o 	7.507
p 	1.929
q 	0.095
r 	5.987
s 	6.327
t 	9.056
u 	2.758
v 	0.978
w 	2.361
x 	0.150
y 	1.974
z 	0.074
4 4
acid
acrid
actor
afdc
agra
arcs
arid
cara
carat
cars
crag
crags
craw
dario
dict
dior
dirac
dirt
fact
factoid
factor
fdic
fica
firs
fora
fort
gars
grad
grid
grit
iowa
iras
radio
rags
ragwort
rift
riot
rotc
sacra
sara
sari
scad
scar
scrag
tags
tara
taro
tarot
tars
tics
tort
trio
trot
trow
twit
wags
wars
wart
wort
writ
stdout
copy 
seed: -740863471
f a s v 
d c r g 
t i w a 
f o r t 
found acid
found acrid
found actor
found afdc
found agra
found arcs
found arid
found cara
found carat
found cars
found crag
found crags
found craw
found dario
found dict
found dior
found dirac
found dirt
found fact
found factoid
found factor
found fdic
found fica
found firs
found fora
found fort
found gars
found grad
found grid
found grit
found iowa
found iras
found radio
found rags
found ragwort
found rift
found riot
found rotc
found sacra
found sara
found sari
found scad
found scar
found scrag
found tags
found tara
found taro
found tarot
found tars
found tics
found tort
found trio
found trot
found trow
found twit
found wags
found wars
found wart
found wort
found writ
https://ideone.com/0MI2wh
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!