Posted By

dirkchang on 01/25/11


Tagged


Versions (?)

liarliar version A (using std::set)


 / Published in: C++
 

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

Report this snippet  

You need to login to post a comment.