fork download
copy 
  1. /**
  2. * Trie - a tree for keeping a set of words, factoring out duplicate prefixes.
  3. * Demo application - find the shortest set of operations for printing a given set of words.
  4. *
  5. * INPUT: a number N, and a list of N words.
  6. * OUTPUT: the length of the shortest sequence of operations, and one such sequence.
  7. * 
  8. * @author Erel Segal  http://t...content-available-to-author-only...s.fm/rentabrain
  9. * @date 2010-10-14
  10. */
  11.  
  12. #include <map>
  13. #include <string>
  14. #include <string.h>
  15. #include <stdlib.h>
  16. #include <iostream>
  17. #include <sstream>
  18. using namespace std;
  19.  
  20.  
  21. class Trie;
  22. typedef Trie* PTrieNode;
  23.  
  24. typedef unsigned long ulong;
  25.  
  26. string randomWord(int length) { // for testing
  27. 	string r="";
  28. 	for (int i=0; i<length; ++i) {
  29. 		char c = 'a'+rand()%26;
  30. 		r+=c;
  31. 	}
  32. 	return r;
  33. }
  34.  
  35. // A Trie for holding words above [a-z]
  36. class Trie {
  37. 	PTrieNode myChildren[26];  // non-capitals only!
  38. 	unsigned int wordCount;  // number of words contained in this node
  39.  
  40. 	// keep a record of the longest word in this Trie.
  41. 	// It should be printed at the end, because we don't care about letters remaining in the printer.
  42. 	int myLongestWordLength;
  43. 	short myLongestWordPrefix;
  44.  
  45. public:
  46.  
  47. 	Trie(): wordCount(0), myLongestWordLength(0), myLongestWordPrefix(0) {
  48. 		fill_n(myChildren, 26, (PTrieNode)NULL);
  49. 	}
  50.  
  51. 	/* recursively add a single word to the node */
  52. 	void add (const char* newWord) {
  53. 		// add the word:
  54. 		char first = newWord[0];
  55. 		if (!first) { // end of word
  56. 			++wordCount; // add 1 to the number of words ending here
  57. 		} else {
  58. 			if ('a'<=first && first <= 'z') {
  59. 				if (!myChildren[first-'a']) {
  60. 					myChildren[first-'a'] = new Trie();
  61. 				}
  62. 				myChildren[first-'a']->add(newWord+1);
  63. 			}
  64.  
  65. 			// keep track of the longest word:
  66. 			int len = strlen(newWord);
  67. 			if (len > myLongestWordLength) {
  68. 				myLongestWordLength = len;
  69. 				myLongestWordPrefix = first-'a';
  70. 			}
  71. 		}
  72. 	}
  73.  
  74.  
  75. 	void addWords(istream& in) {
  76. 		int wordCount;
  77. 		in >> wordCount;
  78. 		string word;
  79. 		for (int i=0; i<wordCount; ++i) {
  80. 			in >> word;
  81. 			add(word.c_str());
  82. 		}
  83. 	}
  84.  
  85. 	void addRandomWords(int wordCount, int wordLength) {
  86. 		for (int i=0; i<wordCount; ++i) {
  87. 			add(randomWord(wordLength).c_str());
  88. 		}
  89. 	}
  90.  
  91.  
  92. 	/* recursively print a minimal set of printer operations needed to print the set of words.
  93. 		[a..z] = add a letter.
  94. 		- = remove a letter.
  95. 		P = print the current word.
  96. 	*/
  97. 	void printOperations (ostream& out, bool topLevel=true) const {
  98. 		for (unsigned int i=0; i<wordCount; ++i) {
  99. 			out << "P";
  100. 		}
  101.  
  102. 		for (int i=0; i<26; ++i) {
  103. 			char c = i+'a';
  104. 			if (i==myLongestWordPrefix) continue; // print it at the end
  105. 			PTrieNode child = myChildren[i];
  106. 			if (child) {
  107. 				out << c;
  108. 				child->printOperations(out, /*topLevel=*/false);
  109. 				out << "-";
  110. 			}
  111. 		}
  112.  
  113. 		if (myLongestWordLength) {
  114. 			out << (char)(myLongestWordPrefix+'a');
  115. 			myChildren[myLongestWordPrefix]->printOperations(out, topLevel);
  116. 			if (!topLevel) out << "-";
  117. 		}
  118. 	}
  119. };
  120.  
  121.  
  122. void test(string input, string expected) {
  123. 	stringstream in(input);
  124. 	Trie t;
  125.  
  126. 	time_t before = time(NULL);
  127. 	t.addWords(in);
  128. 	stringstream operationStream;
  129. 	t.printOperations(operationStream);
  130. 	string a = operationStream.str();
  131.  
  132. 	if (a!=expected) {
  133. 		cerr << "ERROR: operations for '" << input << "' should be " << expected << " but was " << a << endl;
  134. 	} else {
  135. 		time_t after = time(NULL);
  136. 		cout << "calculated cost of " << input.size() << " chars in " << (after-before) << " seconds" << endl;
  137. 	}
  138. }
  139.  
  140. void testRandom(int wordCount, int wordLength) {
  141. 	Trie t;
  142. 	time_t before = time(NULL);
  143. 	t.addRandomWords(wordCount, wordLength);
  144. 	stringstream operationStream;
  145. 	t.printOperations(operationStream);
  146. 	string a = operationStream.str();
  147. 	time_t after = time(NULL);
  148. 	cout << "calculated cost of " << wordLength << "x" << wordCount << " chars in " << (after-before) << " seconds" << endl;
  149. 	if (a.length()<2000)
  150. 		cout << "result=" << a << endl;
  151. }
  152.  
  153. int main() {
  154. 	//test("3 print the poem", "theP---poemP---rintP");
  155. 	//test("3 arint the aoem", "theP---aoemP---rintP");
  156. 	//testRandom(50,20);
  157. 	//return 1;
  158.  
  159. 	Trie t;
  160. 	t.addWords(cin);
  161.  
  162. 	stringstream operationStream;
  163. 	t.printOperations(operationStream);
  164. 	string operations = operationStream.str();
  165.  
  166. 	unsigned long operationsCount = operations.length();
  167. 	cout << operationsCount << endl;
  168. 	for (unsigned long i=0; i<operationsCount; ++i) {
  169. 		cout << operations[i] << endl;
  170. 	}
  171. }
  172.  
  173.  
  174.  
Success #stdin #stdout 0s 2876KB
comments (?)
stdin
copy 
4
print
the
poem
print
stdout
copy 
21
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P
P
https://ideone.com/pC8hz
language:
C++ (gcc 8.3)
created:
13 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!