A Graph Problem

Makefile

all:
	g++ new.cc -o sta -pthread
	@#g++ old.cc -o org -pthread
	g++ try.cc -o dev -pthread
clean:
	rm -rf dev org sta
format:
	clang-format -i *.cc

new.cc

#include <algorithm>
#include <assert.h>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iterator>
#include <mutex>
#include <thread>
#include <vector>

#include <fstream>
#include <iomanip>

bool pfx_status;
std::mutex pfx_mtx;
std::vector<bool> *pfx;

const int alen = 64;
int disp_w = 0, N, M;

int amazing_gap[] = {1,   2,   4,   5,   8,   10,  14,  15,  16,  21,  22,
                     25,  26,  28,  33,  34,  35,  36,  38,  40,  42,  46,
                     48,  49,  50,  53,  57,  60,  62,  64,  65,  70,  77,
                     80,  81,  83,  85,  86,  90,  91,  92,  100, 104, 107,
                     108, 116, 119, 124, 127, 132, 133, 137, 141, 144, 145,
                     148, 150, 151, 154, 158, 159, 163, 165};

int amazing[] = {1,    2,    4,    8,    13,   21,   31,   45,   60,   76,
                 97,   119,  144,  170,  198,  231,  265,  300,  336,  374,
                 414,  456,  502,  550,  599,  649,  702,  759,  819,  881,
                 945,  1010, 1080, 1157, 1237, 1318, 1401, 1486, 1572, 1662,
                 1753, 1845, 1945, 2049, 2156, 2264, 2380, 2499, 2623, 2750,
                 2882, 3015, 3152, 3293, 3437, 3582, 3730, 3880, 4031, 4185,
                 4343, 4502, 4665, 4830};

#define FIX_POINT 2
#define str(x) #x

std::ifstream checkpoint;
std::ofstream savepoint;
std::vector<int *> chkpt;

int distance(int idx, int jdx) {
  int val = abs(idx - jdx);
  return std::min(val, N - val);
}

void load_checkpoint(int prefix_len, int m) {
  int v, l;
  char mode;
  checkpoint.open("checkpoint.txt");
  if (checkpoint && checkpoint >> v >> l) {
    if (prefix_len == v && m == l) {
      while (checkpoint >> mode) {
        if (mode == 'r') {
          int *rec = new int[prefix_len];
          for (int i = 0; i < prefix_len; i++) {
            checkpoint >> v;
            rec[i] = v;
          }
          chkpt.push_back(rec);
        } else if (mode == 'a') {
          std::cout << "cached ans: ";
          for (int i = 0; i < l; i++)
            checkpoint >> v, std::cout << v << " ";
          std::cout << std::endl;
        }
      }
      checkpoint.close();
      savepoint.open("checkpoint.txt", std::ofstream::app);
    } else {
      savepoint.open("checkpoint.txt");
      savepoint << prefix_len << " " << m << std::endl;
      savepoint.flush();
    }
  } else {
    savepoint.open("checkpoint.txt");
    if (!checkpoint) {
      savepoint << prefix_len << " " << m << std::endl;
      savepoint.flush();
    }
  }
}

std::mutex chkpt_mtx;
void save_chkpt(char type, int *buffer, int size) {
  chkpt_mtx.lock();
  savepoint << type << ' ';
  for (int i = 0; i < size; i++)
    savepoint << buffer[i] << " ";
  savepoint << std::endl;
  savepoint.flush();
  chkpt_mtx.unlock();
}

bool prefix_in_chkpt(int *buffer) {
  for (auto i = 0ull; i < chkpt.size(); i++) {
    // for(int j = 0; j < prefix_len - FIX_POINT; j++){
    //    printf("%d | %d\n", chkpt[i][j], (buffer + FIX_POINT)[j]);
    //}
    if (std::equal(chkpt[i], chkpt[i] + disp_w, buffer)) {
      // puts("in record");
      return true;
    }
  }
  // puts("not in record");
  return false;
}

std::mutex io_mtx;
bool check(int *buffer, int n, int m) {
#if 0
    //if (m == M) {
        io_mtx.lock();
        printf("check %d: ", m);
        for (int i = 0; i < m; i++)
            printf("%d ", buffer[i]);
        puts("");
        io_mtx.unlock();
    //}
#endif

  char dist[n / 2 + 1];
  memset(dist, 0, n / 2 + 1);

  for (int i = 0; i < m; i++)
    for (int j = i + 1; j < m; j++) {
      // int idx = abs(buffer[i] - buffer[j]);
      // idx = std::min(idx, n - idx);
      int idx = distance(buffer[i], buffer[j]);
      if (dist[idx])
        return false;
      else
        dist[idx] = true;
    }

  if (m == M) {
    io_mtx.lock();
    printf("ans: ");
    for (int i = 0; i < m; i++)
      printf("%d ", buffer[i]);
    puts("");
    io_mtx.unlock();
    save_chkpt('a', buffer, m);
  }

  return true;
}

// from a to b select n stuff to buffer
bool comb(int a, int b, int n, int *buffer) {
  int p = n - 1;
  while (1) {
    if (buffer[p] < b) {
      buffer[p]++;
      if (b - buffer[p] < n - 1 - p) {
        if (p == 0)
          return false;
      } else {
        while (p < n) {
          buffer[p + 1] = buffer[p] + 1;
          p++;
        }
        break;
      }
    }
    if (p > 0)
      p--;
    else
      return false;
  }
  return true;
}

void init_prefix(int dispatch_width, int n, int m) {
  disp_w = dispatch_width, N = n, M = m;
  pfx_status = true;
}

void next_prefix(int *buffer) {
  int size = std::min(alen, M);
  for (int i = 0; i < size; i++)
    buffer[i] = amazing[i];
  do {
    pfx_status = comb(1, N, disp_w, amazing);
  } while (!check(amazing, N, disp_w) && pfx_status);
#if 0
    puts("pass");
    printf("buffer: ");
    for (int i = 0; i < size; i++)
        printf("%d ", buffer[i]);
    puts("");
    printf("amazing: ");
    for (int i = 0; i < size; i++)
        printf("%d ", amazing[i]);
    puts("");
#endif
  // fix two point
  if (amazing[1] > 2)
    pfx_status = false;

  // for (int i = 1; i <= FIX_POINT; i++)
  //  *buffer++ = i;
  // for (auto i = 0ul; i < pfx->size(); ++i) {
  //  if ((*pfx)[i])
  //    *buffer++ = i + (FIX_POINT + 1);
  //}
  // pfx_status = std::next_permutation(pfx->begin(), pfx->end());
}

void run_thread(int id, int n, int m) {
  bool in_chkpt = false;
  int buffer[n];
  while (1) {
    pfx_mtx.lock();
    if (!pfx_status)
      break;
    do {
      next_prefix(buffer);
    } while ((in_chkpt = prefix_in_chkpt(buffer)) && pfx_status);
    if (in_chkpt)
      break;
    pfx_mtx.unlock();

    for (int i = 0; i < m - disp_w; i++)
      buffer[i + disp_w] = buffer[disp_w - 1] + i + 1;

    check(buffer, n, m);

    if (!(m - disp_w)) {
      save_chkpt('r', buffer, disp_w);
      continue;
    }

    while (comb(buffer[disp_w - 1] + 1, n, m - disp_w, buffer + disp_w))
      check(buffer, n, m);

    save_chkpt('r', buffer, disp_w);
  }
  pfx_mtx.unlock();
}

int main(int argc, char *argv[]) {
  if (argc < 2)
    printf("usage: %s m [thread]\n", argv[0]), exit(1);

  int m = atoi(argv[1]);
  int n = m * (m - 1) + 1;

  int prefix_len = (m < 3 ? 1 : ((m + 1) / 2));
  init_prefix(prefix_len, n, m);

  int thread_number = 1;
  if (argc > 2)
    thread_number = atoi(argv[2]);

  fprintf(stderr, "n = %d, m = %d, pfx = %d, thread = %d\n", n, m, prefix_len,
          thread_number);

  load_checkpoint(prefix_len, m);

  if (n < 2)
    return 0;
  std::vector<std::thread *> pool;
  while (thread_number--)
    pool.push_back(new std::thread(run_thread, thread_number, n, m));
  for (auto it = pool.begin(); it != pool.end(); it++)
    (*it)->join();
  return 0;
}

old.cc

#include <algorithm>
#include <assert.h>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iterator>
#include <mutex>
#include <thread>
#include <vector>

#include <fstream>
#include <iomanip>

bool pfx_status;
std::mutex pfx_mtx;
std::vector<bool> *pfx;

#define FIX_POINT 2
#define str(x) #x
void init_prefix(int n, int r) {
#ifdef FIX_POINT
  if (r <= FIX_POINT)
    puts("prefix_len must > " str(FIX_POINT)), exit(1);
  printf("select %d from %d\n", r, n);
  n -= FIX_POINT, r -= FIX_POINT;
  pfx_status = true;
  pfx = new std::vector<bool>(n);
  std::fill(pfx->end() - r, pfx->end(), true);
  printf("select %d from %d\n", r, n);
#else
  pfx_status = true;
  pfx = new std::vector<bool>(n);
  std::fill(pfx->end() - r, pfx->end(), true);
#endif
}

void next_prefix(int *buffer) {
#ifdef FIX_POINT
  for (int i = 1; i <= FIX_POINT; i++)
    *buffer++ = i;
  for (auto i = 0ul; i < pfx->size(); ++i) {
    if ((*pfx)[i])
      *buffer++ = i + (FIX_POINT + 1);
  }
  pfx_status = std::next_permutation(pfx->begin(), pfx->end());
#else
  for (auto i = 0ul; i < pfx->size(); ++i)
    if ((*pfx)[i])
      *buffer++ = i + 1;
  pfx_status = std::next_permutation(pfx->begin(), pfx->end());
#endif
}

// from a to b select n stuff to buffer
bool comb(int a, int b, int n, int *buffer) {
  int p = n - 1;
  while (1) {
    if (buffer[p] < b) {
      buffer[p]++;
      if (b - buffer[p] < n - 1 - p) {
        if (p == 0)
          return false;
      } else {
        while (p < n) {
          buffer[p + 1] = buffer[p] + 1;
          p++;
        }
        break;
      }
    }
    if (p > 0)
      p--;
    else
      return false;
  }
  return true;
}

std::ifstream checkpoint;
std::ofstream savepoint;
std::vector<int *> chkpt;

void load_checkpoint(int &prefix_len, int m) {
  int v, l;
  char mode;
  checkpoint.open("checkpoint.txt");
  if (checkpoint && checkpoint >> v >> l) {
    if (prefix_len == v && m == l) {
      while (checkpoint >> mode) {
        if (mode == 'r') {
          int *rec = new int[prefix_len - FIX_POINT];
          for (int i = 0; i < prefix_len - FIX_POINT; i++) {
            checkpoint >> v;
            rec[i] = v;
          }
          chkpt.push_back(rec);
        } else if (mode == 'a') {
          for (int i = 0; i < l; i++)
            checkpoint >> v;
        }
      }
      checkpoint.close();
      savepoint.open("checkpoint.txt", std::ofstream::app);
    } else {
      savepoint.open("checkpoint.txt");
      savepoint << prefix_len << " " << m << std::endl;
      savepoint.flush();
    }
  } else {
    savepoint.open("checkpoint.txt");
    if (!checkpoint) {
      savepoint << prefix_len << " " << m << std::endl;
      savepoint.flush();
    }
  }
}

std::mutex chkpt_mtx;
void save_chkpt(char type, int *buffer, int size) {
  chkpt_mtx.lock();
  savepoint << type << ' ';
  for (int i = 0; i < size; i++)
    savepoint << buffer[i] << " ";
  savepoint << std::endl;
  savepoint.flush();
  chkpt_mtx.unlock();
}

bool prefix_in_chkpt(int *buffer, int prefix_len) {
  for (auto i = 0ull; i < chkpt.size(); i++) {
    // for(int j = 0; j < prefix_len - FIX_POINT; j++){
    //    printf("%d | %d\n", chkpt[i][j], (buffer + FIX_POINT)[j]);
    //}
    if (std::equal(chkpt[i], chkpt[i] + prefix_len - FIX_POINT,
                   buffer + FIX_POINT)) {
      // puts("in record");
      return true;
    }
  }
  // puts("not in record");
  return false;
}

std::mutex io_mtx;
bool check(int *buffer, int n, int m) {
#if 0
    io_mtx.lock();
    printf("check: ");
    for(int i = 0; i < m; i++)
        printf("%d ", buffer[i]);
    puts("");
    io_mtx.unlock();
#endif

  char dist[n / 2 + 1];
  memset(dist, 0, n / 2 + 1);

  for (int i = 0; i < m; i++)
    for (int j = i + 1; j < m; j++) {
      int idx = abs(buffer[i] - buffer[j]);
      idx = std::min(idx, n - idx);
      if (dist[idx])
        return false;
      else
        dist[idx] = true;
    }

  io_mtx.lock();
  printf("ans: ");
  for (int i = 0; i < m; i++)
    printf("%d ", buffer[i]);
  puts("");
  io_mtx.unlock();
  save_chkpt('a', buffer, m);
  return true;
}

void run_thread(int id, int pfxl, int n, int m) {
  bool in_chkpt = false;
  int buffer[n];
  while (1) {
    pfx_mtx.lock();
    if (!pfx_status)
      break;
    do {
      next_prefix(buffer);
    } while ((in_chkpt = prefix_in_chkpt(buffer, pfxl)) && pfx_status);
    if (in_chkpt)
      break;
    pfx_mtx.unlock();

    for (int i = 0; i < m - pfxl; i++)
      buffer[i + pfxl] = buffer[pfxl - 1] + i + 1;

    if (buffer[2] == 3)
      continue;

    check(buffer, n, m);

    if (!(m - pfxl)) {
      save_chkpt('r', buffer + FIX_POINT, pfxl - FIX_POINT);
      continue;
    }

    while (comb(buffer[pfxl - 1] + 1, n, m - pfxl, buffer + pfxl))
      check(buffer, n, m);

    save_chkpt('r', buffer + FIX_POINT, pfxl - FIX_POINT);
  }
  pfx_mtx.unlock();
}

int main(int argc, char *argv[]) {
  if (argc < 2)
    printf("usage: %s m [thread]\n", argv[0]), exit(1);

  int m = atoi(argv[1]);
  int n = m * (m - 1) + 1;

  int prefix_len = 3;
  int postfix_len = m - prefix_len;
  init_prefix(n - postfix_len, prefix_len);

  int thread_number = 1;
  if (argc > 2)
    thread_number = atoi(argv[2]);

  load_checkpoint(prefix_len, m);

  fprintf(stderr, "n = %d, m = %d, thread = %d\n", n, m, thread_number);

  std::vector<std::thread *> pool;
  while (thread_number--)
    pool.push_back(
        new std::thread(run_thread, thread_number, prefix_len, n, m));
  for (auto it = pool.begin(); it != pool.end(); it++)
    (*it)->join();
  return 0;
}

try.cc

#include <algorithm>
#include <assert.h>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iterator>
#include <mutex>
#include <set>
#include <thread>
#include <vector>

#include <fstream>
#include <iomanip>

bool pfx_status;
std::mutex pfx_mtx;
std::vector<bool> *pfx;

const int alen = 64;
int disp_w = 0, N, M;

int amazing_gap[] = {1,   2,   4,   5,   8,   10,  14,  15,  16,  21,  22,
                     25,  26,  28,  33,  34,  35,  36,  38,  40,  42,  46,
                     48,  49,  50,  53,  57,  60,  62,  64,  65,  70,  77,
                     80,  81,  83,  85,  86,  90,  91,  92,  100, 104, 107,
                     108, 116, 119, 124, 127, 132, 133, 137, 141, 144, 145,
                     148, 150, 151, 154, 158, 159, 163, 165};

int amazing[] = {1,    2,    4,    8,    13,   21,   31,   45,   60,   76,
                 97,   119,  144,  170,  198,  231,  265,  300,  336,  374,
                 414,  456,  502,  550,  599,  649,  702,  759,  819,  881,
                 945,  1010, 1080, 1157, 1237, 1318, 1401, 1486, 1572, 1662,
                 1753, 1845, 1945, 2049, 2156, 2264, 2380, 2499, 2623, 2750,
                 2882, 3015, 3152, 3293, 3437, 3582, 3730, 3880, 4031, 4185,
                 4343, 4502, 4665, 4830};

std::ifstream checkpoint;
std::ofstream savepoint;
std::vector<int *> chkpt;

int distance(int idx, int jdx) {
  int val = abs(idx - jdx);
  return std::min(val, N - val);
}

void load_checkpoint(int prefix_len, int m) {
  int v, l;
  char mode;
  checkpoint.open("checkpoint.txt");
  if (checkpoint && checkpoint >> v >> l) {
    if (prefix_len == v && m == l) {
      while (checkpoint >> mode) {
        if (mode == 'r') {
          int *rec = new int[prefix_len];
          for (int i = 0; i < prefix_len; i++) {
            checkpoint >> v;
            rec[i] = v;
          }
          chkpt.push_back(rec);
        } else if (mode == 'a') {
          std::cout << "cached ans: ";
          for (int i = 0; i < l; i++)
            checkpoint >> v, std::cout << v << " ";
          std::cout << std::endl;
        }
      }
      checkpoint.close();
      savepoint.open("checkpoint.txt", std::ofstream::app);
    } else {
      savepoint.open("checkpoint.txt");
      savepoint << prefix_len << " " << m << std::endl;
      savepoint.flush();
    }
  } else {
    savepoint.open("checkpoint.txt");
    if (!checkpoint) {
      savepoint << prefix_len << " " << m << std::endl;
      savepoint.flush();
    }
  }
}

std::mutex chkpt_mtx;
void save_chkpt(char type, int *buffer, int size) {
  chkpt_mtx.lock();
  savepoint << type << ' ';
  for (int i = 0; i < size; i++)
    savepoint << buffer[i] << " ";
  savepoint << std::endl;
  savepoint.flush();
  chkpt_mtx.unlock();
}

bool prefix_in_chkpt(int *buffer) {
  for (auto i = 0ull; i < chkpt.size(); i++) {
    if (std::equal(chkpt[i], chkpt[i] + disp_w, buffer)) {
      return true;
    }
  }
  return false;
}

std::mutex io_mtx;
bool check(int *buffer, int n, int m) {
  char dist[n / 2 + 1];
  memset(dist, 0, n / 2 + 1);

  for (int i = 0; i < m; i++)
    for (int j = i + 1; j < m; j++) {
      int idx = distance(buffer[i], buffer[j]);
      if (dist[idx])
        return false;
      else
        dist[idx] = true;
    }

  if (m == M) {
    io_mtx.lock();
    printf("ans: ");
    for (int i = 0; i < m; i++)
      printf("%d ", buffer[i]);
    puts("");
    io_mtx.unlock();
    save_chkpt('a', buffer, m);
  }
  return true;
}

// from a to b select n stuff to buffer
bool comb(int a, int b, int n, int *buffer) {
  int p = n - 1;
  while (1) {
    if (buffer[p] < b) {
      buffer[p]++;
      if (b - buffer[p] < n - 1 - p) {
        if (p == 0)
          return false;
      } else {
        while (p < n) {
          buffer[p + 1] = buffer[p] + 1;
          p++;
        }
        break;
      }
    }
    if (p > 0)
      p--;
    else
      return false;
  }
  return true;
}

void init_prefix(int dispatch_width, int n, int m) {
  disp_w = dispatch_width, N = n, M = m;
  pfx_status = true;
}

void next_prefix(int *buffer) {
  int size = std::min(alen, M);
  for (int i = 0; i < size; i++)
    buffer[i] = amazing[i];
  do {
    pfx_status = comb(1, N, disp_w, amazing);
  } while (!check(amazing, N, disp_w) && pfx_status);
  // fix two point
  if (amazing[1] > 2)
    pfx_status = false;
}

void opt_stuff(int *buffer) {
  std::set<int> gaps;
  for (int i = 1; i <= N / 2; i++)
    gaps.insert(i);
  int *bptr = buffer + disp_w;
  for (auto i = gaps.begin(); i != gaps.end() && bptr < bptr + M; i++, bptr++) {
    *bptr = *(bptr - 1) + *i;
  }
}

void run_thread(int id, int n, int m) {
  bool in_chkpt = false;
  int buffer[n];
  while (1) {
    pfx_mtx.lock();
    if (!pfx_status)
      break;
    do {
      next_prefix(buffer);
    } while ((in_chkpt = prefix_in_chkpt(buffer)) && pfx_status);
    if (in_chkpt)
      break;
    pfx_mtx.unlock();

    // opt here
    opt_stuff(buffer);

    check(buffer, n, m);

    if (!(m - disp_w)) {
      save_chkpt('r', buffer, disp_w);
      continue;
    }

    while (comb(buffer[disp_w - 1] + 1, n, m - disp_w, buffer + disp_w))
      check(buffer, n, m);

    save_chkpt('r', buffer, disp_w);
  }
  pfx_mtx.unlock();
}

int main(int argc, char *argv[]) {
  if (argc < 2)
    printf("usage: %s m [thread]\n", argv[0]), exit(1);

  int m = atoi(argv[1]);
  int n = m * (m - 1) + 1;

  int prefix_len = (m < 3 ? 1 : ((m + 1) / 2));
  init_prefix(prefix_len, n, m);

  int thread_number = 1;
  if (argc > 2)
    thread_number = atoi(argv[2]);

  fprintf(stderr, "n = %d, m = %d, pfx = %d, thread = %d\n", n, m, prefix_len,
          thread_number);

  load_checkpoint(prefix_len, m);

  if (n < 2)
    return 0;
  std::vector<std::thread *> pool;
  while (thread_number--)
    pool.push_back(new std::thread(run_thread, thread_number, n, m));
  for (auto it = pool.begin(); it != pool.end(); it++)
    (*it)->join();
  return 0;
}