SHARE
TWEET

Untitled

a guest Jul 10th, 2016 35 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdlib.h>
  2. #include <unistd.h>
  3. #include <sys/wait.h>
  4. #include <stdio.h>
  5.  
  6. // Note that this program brute-forces all possible seed values.
  7. // This may take a fair amount of time - 40 minutes or so in
  8. // average case, for example, seed 2**32/100 is bruted in 48s, or
  9. // seed 500000000 in 9:49.
  10. //
  11. // If you want to have some progress printing (one character every
  12. // 1/256 of work done), please compile with DEBUG symbol defined
  13. // (for example, using -DDEBUG flag during compilation).
  14. //
  15. // As for chances of failure: for a seed other than chosen to pass
  16. // my tests, it would have to produce correct N (1/1000 chance)
  17. // and have first double within 1e-11 (about 2/1e11 chance). Close
  18. // to impossible even when multiplied by amount of seeds.
  19.  
  20. #define MXN 1000
  21.  
  22. #ifdef DEBUG
  23. #define dprintf(...) printf(__VA_ARGS__)
  24. #else
  25. #define dprintf(...)
  26. #endif
  27.  
  28. // This function brute forces the seed. It is able to parallelize well,
  29. // but doing so messes with main process (dunno why, and don't ask - it's
  30. // 3AM now :P). So single thread processing it is then.
  31. void brute(unsigned int id, double x, int N, int all){
  32.     dprintf("Started %d\n", id);
  33.     unsigned int sd=id;
  34.     FILE* f;
  35.     char name[10]="/tmp/0";
  36.     name[5]+=id;
  37.     f=fopen(name, "w");
  38.     do{
  39.         if((sd&0xFFFFFF)==id){
  40.             dprintf("%u",id);
  41.             fflush(stdout);
  42.         }
  43.         srand(sd);
  44.         int myN=(rand()%MXN)+1;
  45.         if(myN!=N){ continue; }
  46.         double rd=(double)rand()/RAND_MAX;
  47.         rd-=x;
  48.         if(rd<0){ rd=-rd; }
  49.         if(rd<1e-11){ // Significantly less than given 15 digits of precision.
  50.             dprintf("\nFound fitting seeed: %u\n", sd);
  51.             fprintf(f, "%u\n", sd);
  52.             fflush(f);
  53.             break;
  54.         }
  55.     }while((sd+=all) != id);
  56.     fclose(f);
  57. }
  58.  
  59. int guess_max(double x, int N, int count) {
  60.     static int done=0;
  61.     static int should;
  62.     if(done){
  63.         dprintf("Called with %d %lf\n", count, x);
  64.         return count==should;
  65.     }
  66.     int nprocesses=1;
  67.     brute(0,x,N,nprocesses);
  68.     unsigned int sd=0;
  69.     for(int i=0;i<nprocesses;i++){
  70.         FILE* f;
  71.         char name[10]="/tmp/0";
  72.         name[5]+=i;
  73.         f=fopen(name, "r");
  74.         while(EOF!=fscanf(f,"%u",&sd));
  75.         fclose(f);
  76.     }
  77.     dprintf("Using seed: %u\n", sd);
  78.     srand(sd);
  79.     int myN=(rand()%MXN)+1;
  80.     double biggest=-1;
  81.     int maxind=-1;
  82.     for(int i=1;i<=myN;i++){
  83.         double rd=(double)rand()/RAND_MAX;
  84.         dprintf("%dth: %lf\n", i, rd);
  85.         if(rd>biggest){
  86.             biggest=rd;
  87.             maxind=i;
  88.         }
  89.     }
  90.     should=maxind;
  91.     done=1;
  92.     dprintf("Should - %d\n", should);
  93.     return maxind==count;
  94. }
RAW Paste Data
Want to get better at C?
Learn to code C in 2017
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top