Guest User

Untitled

a guest
Oct 15th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.12 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <sstream>
  4. #include <regex>
  5. #include <unordered_map>
  6. #include <unordered_set>
  7. #include <set>
  8. #include <map>
  9.  
  10. using namespace std;
  11.  
  12. /**
  13. * Tuple representing the circuit element where
  14. * 0 - kind of the element (T, D, R, C or E)
  15. * 1 - number of the element (1-999999999)
  16. * 2 - type of the element
  17. * 3 - numbers of connected nodes of the element
  18. */
  19. using element_data = tuple<char, int, string, vector<int>>;
  20.  
  21. /**
  22. * A map from the kind of the element to the set of numbers of existing elements
  23. */
  24. using existing_numbers_map = unordered_map<char, unordered_set<int>>;
  25.  
  26. /**
  27. * A map from type of the element to connected node numbers of that element
  28. */
  29. using elements_map = unordered_map<string, set<int>>;
  30.  
  31. /**
  32. * @param line - A valid string containing the state of the element
  33. * @return tuple represented in the string
  34. */
  35. static element_data parse_line(const string &line) {
  36. vector<string> tokens;
  37. istringstream is(line);
  38. string word;
  39. // Split the string into words ignoring any whitespace in between
  40. while (is >> word)
  41. tokens.push_back(word);
  42.  
  43. int number = stoi(tokens[0].substr(1, string::npos));
  44. vector<int> nums(tokens.size() - 2);
  45. // Populate the vector of connection nodes
  46. for (int i = 2; i < tokens.size(); ++i)
  47. nums[i - 2] = stoi(tokens[i]);
  48.  
  49.  
  50. return make_tuple(tokens[0][0], number, tokens[1], nums);
  51. }
  52.  
  53. /**
  54. * @param data - the element
  55. * @param numbers - kind of element to set of numbers map
  56. * @return true iff the element is a valid component in the circuit
  57. */
  58. static bool validate_element_data(const element_data &data,
  59. existing_numbers_map &numbers) {
  60. char kind;
  61. int number;
  62. const vector<int> &nodes = get<3>(data);
  63. tie(kind, number, ignore, ignore) = data;
  64. // Fail the validation if there are other element with the same kind connected to the same node
  65. if (numbers[kind].count(number) != 0)
  66. return false;
  67. // Get rid of duplicate integers
  68. set<int> unique_nodes(nodes.begin(), nodes.end());
  69. if (unique_nodes.size() == 1)
  70. return false;
  71. // Transistors have to be connected to 3 nodes, whereas all other kinds of elements 2
  72. return (kind == 'T' && nodes.size() == 3) || (kind != 'T' && nodes.size() == 2);
  73. }
  74.  
  75.  
  76. /**
  77. * Add a new element to the circuit
  78. * @param data - the element
  79. * @param numbers - kind of element to set of numbers map
  80. * @param nodes_connections - map representing connections of nodes
  81. * @param elements_by_kind - representation of the circuit grouped by kind
  82. */
  83. static void add_new_element(const element_data &data, existing_numbers_map &numbers, map<int, int> &nodes_connections,
  84. unordered_map<char, elements_map> &elements_by_kind) {
  85. char kind = get<0>(data);
  86. int number = get<1>(data);
  87. const string &type = get<2>(data);
  88. const vector<int> &nodes = get<3>(data);
  89. numbers[kind].insert(number);
  90. set<int> unique_nodes(nodes.begin(), nodes.end());
  91. // Update the number of nodes connected
  92. for (int node : unique_nodes) {
  93. if (nodes_connections.count(node) == 0)
  94. nodes_connections[node] = 1;
  95. else
  96. ++nodes_connections[node];
  97. }
  98. elements_map &elements = elements_by_kind[kind];
  99. // Init as empty set if not found
  100. if (elements.count(type) == 0)
  101. elements[type] = set<int>();
  102. elements[type].insert(number);
  103. }
  104.  
  105. static void print_results(unordered_map<char, elements_map> &elements_by_kind) {
  106. // Iterate over all kinds
  107. for (char c : {'T', 'D', 'R', 'C', 'E'}) {
  108. elements_map &elements = elements_by_kind[c];
  109. vector<pair<string, set<int>>> vec;
  110. copy(elements.begin(), elements.end(), back_inserter(vec));
  111. // Sort the vector by element type string
  112. sort(vec.begin(), vec.end(), [](const pair<string, set<int>> &p1, const pair<string, set<int>> &p2) {
  113. return *(p1.second.begin()) < *(p2.second.begin());
  114. });
  115. // Print the results
  116. for (auto &p : vec) {
  117. auto it = p.second.begin();
  118. cout << c << *it;
  119. ++it;
  120. while (it != p.second.end()) {
  121. cout << ", " << c << *it;
  122. ++it;
  123. }
  124. cout << ": " << p.first << endl;
  125. }
  126. }
  127. }
  128.  
  129.  
  130. /**
  131. *
  132. * @param nodes_connections
  133. */
  134. static void print_nodes_warning(const map<int, int> &nodes_connections) {
  135. bool first = true;
  136. for (const auto &kv : nodes_connections) {
  137. if (kv.second < 2) {
  138. if (first) {
  139. cerr << "Warning, unconnected node(s): " << kv.first;
  140. first = false;
  141. } else {
  142. cerr << ", " << kv.first;
  143. }
  144. }
  145. }
  146. cerr << endl;
  147. }
  148.  
  149. /**
  150. * Driver function to read the input, collect the circuit elements and print the results
  151. */
  152. static void run() {
  153.  
  154. const char *regex_str =
  155. "\\s*[T|R|D|C|E]{1}[1-9]{1}[0-9]{0,8}" // Match the kind of the element followed by the number
  156. "\\s*[A-Z|0-9]{1}[a-z|A-Z|0-9|\\,|\\-|\\/]{0,}" // Math the type of the element
  157. "(\\s*(([1-9]{1}[0-9]{0,8})|0)){2,3}\\s*)"; // Match from 2 to 3 connected node numbers
  158.  
  159. const regex re(regex_str);
  160.  
  161. // A mapping from node N to the number of elements that connect to the node N
  162. map<int, int> nodes_connections({{0, 0}});
  163.  
  164. // A mapping from the kind of the element K to the set of numbers of elements that are of kind K
  165. existing_numbers_map element_numbers({
  166. {'T', unordered_set<int>()},
  167. {'R', unordered_set<int>()},
  168. {'D', unordered_set<int>()},
  169. {'C', unordered_set<int>()},
  170. {'E', unordered_set<int>()}
  171. });
  172.  
  173. // A map representing element_map instances grouped by their kind
  174. unordered_map<char, elements_map> elements_by_kind({
  175. {'T', elements_map()},
  176. {'R', elements_map()},
  177. {'D', elements_map()},
  178. {'C', elements_map()},
  179. {'E', elements_map()}
  180. });
  181. int line_number = 0;
  182. string line;
  183. while (getline(cin, line)) {
  184. ++line_number;
  185. if (!line.empty()) {
  186. bool is_valid = regex_match(line, re);
  187. if (is_valid) {
  188. const element_data data = parse_line(line);
  189. is_valid = validate_element_data(data, element_numbers);
  190. if (is_valid)
  191. add_new_element(data, element_numbers, nodes_connections, elements_by_kind);
  192.  
  193. }
  194. if (!is_valid)
  195. cerr << "Error in line " << line_number << ": " << line << endl;
  196. }
  197. }
  198. print_results(elements_by_kind);
  199. print_nodes_warning(nodes_connections);
  200. }
  201.  
  202. int main() {
  203. run();
  204. return 0;
  205. }
Add Comment
Please, Sign In to add comment