ulvis.paste.net - pastebin

Paste Search Dynamic
Recent pastes
n
  1. #include <algorithm>
  2. #include <math.h>
  3. #include <ctime>
  4. #include <chrono>
  5. #include <iostream>
  6. #include <numeric>
  7. #include <utility>
  8. #include <vector>
  9.  
  10. using namespace std;
  11. using time_pt_t = chrono::steady_clock::time_point;
  12.  
  13. bool is_pfct_sqr(int x, int y);
  14. bool min_count(pair<int, int>& p1, pair<int, int>& p2);
  15. void pre_ord_dfs(const vector<vector<int>>& nodes, int root, int N);
  16.  
  17. template<class T>
  18. void print_vector(const vector<T>& v);
  19.  
  20.  
  21. bool is_pfct_sqr(int x, int y) {
  22.   int z = sqrt(x+y);
  23.   return (z * z == x + y);
  24. }
  25.  
  26. bool min_count(pair<int, int>& p1, pair<int, int>& p2) {
  27.   return (p1.second < p2.second);
  28. }
  29.  
  30. void pre_ord_dfs(const vector<vector<int>>& nodes, int root, int N) {
  31.   vector<int> solution;
  32.   vector<int> stack;
  33.   vector<bool> used(N+1, false);
  34.  
  35.   stack.push_back(root);
  36.  
  37.   while (!stack.empty()) {
  38.         print_vector(solution);
  39.         cout << endl;
  40.     int stack_ptr = stack.back();
  41.     if (!used[stack_ptr]) {
  42.       solution.push_back(stack_ptr);
  43.       used[stack_ptr] = true;
  44.     }
  45.  
  46.     for (auto &n: nodes[stack_ptr - 1]) {
  47.         cout << "for " << stack_ptr << ": " << n << endl;
  48.       if (!used[n])
  49.         stack.push_back(n);
  50.     }
  51.  
  52.     if (solution.size() == N)
  53.       break;
  54.  
  55.     if (stack.back() == stack_ptr) {
  56.       vector<int> unwinder;
  57.       while(!stack.empty()) {
  58.         if (!used[stack.back()]) {
  59.           for (auto &n: unwinder) {
  60.             used[n] = false;
  61.             if (n == solution.back())
  62.               solution.pop_back();
  63.           }
  64.           unwinder.clear();
  65.           break;
  66.         }
  67.         unwinder.push_back(stack.back());
  68.         stack.pop_back();
  69.       }
  70.     }
  71.   }
  72.   if (solution.size() == N)
  73.     print_vector(solution);
  74.   else
  75.     cout << "No solution for: " << N << endl;
  76. }
  77.  
  78. template <class T>
  79. void print_vector(const vector<T>& v) {
  80.   for (auto n: v)
  81.     cout << n << " ";
  82.   cout << endl;
  83. }
  84.  
  85. int main() {
  86.  
  87.   vector<size_t> tests = {26};//{8, 15, 23, 24, 25, 26, 27, 28, 29, 30, 64, 128, 256, 500};
  88.   //for (size_t i = 25; i < 100; ++i) tests.push_back(i);
  89.  
  90.   for (auto &N: tests) {
  91.     vector<int> seq(N);
  92.     vector<vector<int> > pairs(N, vector<int>());
  93.     vector<pair<int, int>> search_order;
  94.     std::iota(seq.begin(), seq.end(), 1);
  95.  
  96.     time_pt_t start_time = chrono::steady_clock::now();
  97.  
  98.     for (size_t i = 0; i < (N - 1); i++) {
  99.       for (size_t j = i; j < N; j++) {
  100.         if (is_pfct_sqr(seq[i], seq[j])) {
  101.           if (seq[i] != seq[j]) {
  102.             pairs[i].push_back(seq[j]);
  103.             pairs[j].push_back(seq[i]);
  104.           }
  105.         }
  106.       }
  107.       search_order.emplace_back(seq[i], pairs[i].size());
  108.     }
  109.     sort(search_order.begin(), search_order.end(), min_count);
  110.  
  111.         print_vector(pairs[1]);
  112.     pre_ord_dfs(pairs, 2, N);
  113.     time_pt_t end_time = chrono::steady_clock::now();
  114.  
  115.     chrono::duration<double> et =
  116.         chrono::duration_cast<chrono::duration<double>>(end_time - start_time);
  117.     cout << "Checking: " << N << " took: " << et.count() << " sec" << endl;
  118.     cout << endl;
  119.   }
  120. }
Parsed in 0.023 seconds