liarliar version A (using std::set)


/ Published in: C++
Save to your folder(s)



Copy this code and paste it in your HTML
  1. // liarliar.cpp
  2. // 2011/1/2
  3.  
  4. #include <fstream>
  5. #include <string>
  6. #include <iostream>
  7. #include <vector>
  8. #include <set>
  9. #include <list>
  10. #include <iterator>
  11. #include <algorithm>
  12. using namespace std;
  13.  
  14. class Liar {
  15. private:
  16. typedef vector<string> Names;
  17. typedef set<string> Set;
  18.  
  19. class Group {
  20. public:
  21. Set &TheSet() {return the_set;}
  22. Set const &TheSet() const {return the_set;}
  23. Group *const TheOppositeSet() {return the_opposite_set;}
  24. Group const *const TheOppositeSet() const {return the_opposite_set;}
  25. void SetOppositeSet(Group *const p) {the_opposite_set = p;}
  26. private:
  27. Set the_set;
  28. Group * the_opposite_set;
  29. };
  30.  
  31. typedef list<Group> Groups;
  32.  
  33. public:
  34. Liar();
  35.  
  36. int Readin(string const file_name);
  37. int Process();
  38. void Output() const;
  39. private:
  40. int get_a_chunk(ifstream & fin, string & accuser, int & no_liars, Names & liars);
  41. int process_a_chunk(string const & accuser, Names const & liars);
  42.  
  43. private:
  44. Groups _groups;
  45. int _g1, _g2;
  46. };
  47.  
  48. int Liar::process_a_chunk(string const & accuser, Names const & liars) {
  49. Groups::iterator it_g;
  50. Set::iterator it_s;
  51. Names::const_iterator it_n;
  52. for(it_g = _groups.begin(); it_g != _groups.end(); ++it_g) {
  53. if((it_s = it_g->TheSet().find(accuser)) != it_g->TheSet().end()) { // found
  54. it_g->TheSet().insert(accuser);
  55. it_g->TheOppositeSet()->TheSet().insert(liars.begin(), liars.end());
  56. return 0; // end of task
  57. }
  58. else { // let's now try all the names in liars
  59. for(it_n = liars.begin(); it_n != liars.end(); ++it_n) {
  60. if((it_s = it_g->TheSet().find(*it_n)) != it_g->TheSet().end()) { // found
  61. it_g->TheSet().insert(liars.begin(), liars.end());
  62. it_g->TheOppositeSet()->TheSet().insert(accuser);
  63. return 0;
  64. }
  65. }
  66. }
  67. }
  68.  
  69. // not found, we create 2 groups here
  70. Groups::iterator it_g1, it_g2;
  71. it_g1 = _groups.insert(_groups.end(), Group());
  72. it_g2 = _groups.insert(_groups.end(), Group());
  73. it_g1->TheSet().insert(accuser);
  74. it_g1->SetOppositeSet(&*it_g2);
  75. it_g2->TheSet().insert(liars.begin(), liars.end());
  76. it_g2->SetOppositeSet(&*it_g1);
  77. return 0;
  78. }
  79.  
  80. Liar::Liar() {}
  81.  
  82. int Liar::Readin(string const file_name) {
  83. if(!_groups.empty()) _groups.clear();
  84.  
  85. ifstream fin(file_name.c_str());
  86. int no_chunk(0);
  87. fin >> no_chunk;
  88.  
  89. string accuser;
  90. int no_liars(0);
  91. Names * pliars = new Names[no_chunk];
  92. for(int i = 0; i < no_chunk; ++i) {
  93. get_a_chunk(fin, accuser, no_liars, pliars[i]);
  94. process_a_chunk(accuser, pliars[i]);
  95. }
  96. delete [] pliars;
  97.  
  98. /*Groups::const_iterator it_g;
  99. for(it_g = _groups.begin(); it_g != _groups.end(); ++it_g) {
  100. copy(it_g->TheSet().begin(), it_g->TheSet().end(), ostream_iterator<string>(cout, " "));
  101. cout << '\n';
  102. }*/
  103. return 0;
  104. }
  105.  
  106. int Liar::Process() { // we merge all data in this function
  107. _g1 = _g2 = 0;
  108. if(_groups.size() == 2) {
  109. _g1 = _groups.begin()->TheSet().size();
  110. _g2 = _groups.begin()->TheOppositeSet()->TheSet().size();
  111. return 0;
  112. }
  113. Groups::iterator it_g1, it_g2;
  114. vector<bool> merged(_groups.size(), false);
  115. int i1(0), i2(0);
  116. for(it_g1 = _groups.begin(); it_g1 != _groups.end(); ++it_g1) {
  117. for(it_g2 = _groups.begin(); it_g2 != _groups.end(); ++it_g2) {
  118. i2 = 0;
  119. if(it_g1 != it_g2 && it_g1->TheOppositeSet() != &*it_g2 && !merged[i2]) {
  120. // try if we can merge this group into the it_g1 group
  121. if(search(it_g1->TheSet().begin(), it_g1->TheSet().end(), it_g2->TheSet().begin(), it_g2->TheSet().end())!=it_g1->TheSet().end()) { //found
  122. it_g1->TheSet().insert(it_g2->TheSet().begin(), it_g2->TheSet().end());
  123. it_g1->TheOppositeSet()->TheSet().insert(it_g2->TheOppositeSet()->TheSet().begin(), it_g2->TheOppositeSet()->TheSet().end());
  124. merged[i2] = true;
  125. if(!(i2 % 2)) merged[i2 + 1] = true;
  126. else merged[i2 - 1] = true;
  127. }
  128. }
  129. ++i2;
  130. }
  131. ++i1;
  132. }
  133.  
  134. /*Groups::const_iterator it_g;
  135. for(it_g = _groups.begin(); it_g != _groups.end(); ++it_g) {
  136. copy(it_g->TheSet().begin(), it_g->TheSet().end(), ostream_iterator<string>(cout, " "));
  137. cout << '\n';
  138. }*/
  139.  
  140. Groups::const_iterator it_cg = _groups.begin();
  141. for(size_t i = 0; i < _groups.size(); i+=2) {
  142. if(merged[i] != false) {
  143. _g1 = it_cg->TheSet().size();
  144. it_cg++;
  145. _g2 = it_cg->TheSet().size();
  146. break;
  147. }
  148. it_cg++;
  149. it_cg++;
  150. }
  151.  
  152. return 0;
  153. }
  154.  
  155. void Liar::Output() const {
  156. if(_g1 > _g2) cout << _g1 << ' ' << _g2 << '\n';
  157. else cout << _g2 << ' ' << _g1 << '\n';
  158. }
  159.  
  160. int Liar::get_a_chunk(ifstream &fin, string &accuser, int &no_liars, Names &liars) {
  161. fin >> accuser >> no_liars;
  162. string liar;
  163. for(int i = 1; i <= no_liars; ++i) {
  164. fin >> liar;
  165. liars.push_back(liar);
  166. }
  167. return 0;
  168. }
  169.  
  170. int main(int argc, char **argv) {
  171. Liar liar;
  172. liar.Readin(argv[1]);
  173. liar.Process();
  174. liar.Output();
  175. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.