/*
 *   Get the golumb ruler of a specified size from the data files.
 */
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <fstream>
using namespace std ;
const int SMALLSIZE = 40 ; // show work for this size and smaller
void error(const char *s, const char *s2="") {
   cerr << s << s2 << endl ;
   exit(10) ;
}
int main(int argc, char *argv[]) {
   if (argc < 2)
      error("! please provide the number of marks on the command line") ;
   int n = atol(argv[1]) ;
   int which = 0 ;
   if (argc > 2)
      which = atol(argv[2]) ;
   if (n < 5)
      error("! can only recover rulers of size 5 or greater") ;
   string filename ;
   filename = "golomb-all-" ;
   int th = n / 1000 ;
   if (th < 10)
      filename += "0" ;
   filename += to_string(th) ;
   cout << "Scanning file " << filename << " for best solution." << endl ;
   ifstream fin(filename) ;
   if (!fin.is_open())
      error("! could not read file ", filename.c_str()) ;
   long long nn, len, g, mul ;
   string typ ;
   int whichdown = which ;
   while (fin >> nn >> len >> typ >> g >> mul) {
      if (nn == n && whichdown-- == 0)
         break ;
   }
   if (nn != n) {
      if (which && whichdown != which)
         error("! could not find soluton number ", to_string(which).c_str()) ;
      error("! could not find a solution for size ", to_string(n).c_str()) ;
   }
   fin.close() ;
   cout << "Best solution has length " << len << " generated by construction "
        << typ << " with prime power " << g << " and multiplier " << mul
        << "." << endl ;
   filename = "modrules-" + typ + "-" ;
   int th2 = g / 1000 ;
   if (th2 < 10)
      filename += "0" ;
   filename += to_string(th2) ;
   cout << "Scanning file " << filename << " for modular ruler." << endl ;
   ifstream fin2(filename) ;
   if (!fin2.is_open())
      error("! could not read file ", filename.c_str()) ;
   long long v ;
   string token ;
   char ch ;
   vector<long long> modrule ;
   string search = to_string(g) + ":" ;
   int collecting = 0 ;
   while (fin2 >> token) {
      if (token[token.size()-1] == ':') {
         if (collecting)
            break ;
         if (token == search)
            collecting++ ;
      } else {
         if (collecting)
            modrule.push_back(stoll(token)) ;
      }
   }
   fin2.close() ;
   if (modrule.size() == 0)
      error("! failed to find expected modular ruler") ;
   cout << "Modular ruler found; checking it." << endl << flush ;
   long long mod = 0 ;
   long long expected_length = 0 ;
   if (typ == "pp") {
      mod = g * g + g + 1 ;
      expected_length = g + 1 ;
   } else if (typ == "ap") {
      mod = g * g - 1 ;
      expected_length = g ;
   } else if (typ == "rl") {
      mod = g * (g - 1) ;
      expected_length = g - 1 ;
   } else {
      error("! unknown type ", typ.c_str()) ;
   }
   if (modrule.size() != expected_length)
      error("! did not get a modular ruler of the expected length") ;
   long long s = 0 ;
   for (int i=0; i<modrule.size(); i++) {
      long long ns = s + modrule[i] ;
      modrule[i] = s ;
      s = ns ;
   }
   if (s != mod)
      error("! sum of gaps not equal to the modulus") ;
   if (modrule.size() <= SMALLSIZE) {
      cout << "The modular ruler we found is:" << endl ;
      for (int i=0; i<modrule.size(); i++)
         cout << " " << modrule[i] ;
      cout << endl ;
   }
   for (int i=0; i<modrule.size(); i++) {
      if (modrule[i] < 0 || modrule[i] >= mod)
         error("! value out of range in modular ruler.") ;
      if (i > 0 && modrule[i] <= modrule[i-1])
         error("! modular ruler does not appear to be sorted.") ;
   }
   size_t bmsize = (size_t)(10 + mod / 16) ;
   unsigned char *bm = (unsigned char *)calloc(bmsize, 1) ;
   if (bm == 0)
      error("! could not allocate bitmap to check modular ruler") ;
   long long length = modrule.size() ;
   for (int i=0; i<length; i++)
      for (int j=i+1; j<length; j++) {
         long long v = modrule[j] - modrule[i] ;
         if (v + v > mod)
            v = mod - v ;
         if (bm[v >> 3] & (1 << (v & 7)))
            error("! duplicated distance in modular ruler ",
                                                     to_string(v).c_str()) ;
         bm[v>>3] |= (1 << (v & 7)) ;
      }
   cout << "Modular ruler passes the tests.  Generating multiple." << endl ;
   for (int i=0; i<length; i++)
      modrule[i] = modrule[i] * mul % mod ;
   cout << "Sorting the modular ruler." << endl ;
   sort(modrule.begin(), modrule.end()) ;
   if (modrule.size() <= SMALLSIZE) {
      cout << "The multiplied and sorted modular ruler we calculated is:" << endl ;
      for (int i=0; i<modrule.size(); i++)
         cout << " " << modrule[i] ;
      cout << endl ;
   }
   cout << "Scanning for solution of length " << len << " with " << n
        << " marks." << endl ;
   int found = 0 ;
   for (int i=0; i<length; i++) {
      modrule.push_back(modrule[i]+mod) ;
      if (modrule[i+n-1] - modrule[i] == len) {
         for (int j=0; j<n; j++)
            cout << " " << (modrule[i+j]-modrule[i]) ;
         cout << endl ;
         found++ ;
      }
   }
   if (!found)
      error("! failed to find the expected solution.") ;
}