/*
 * german_tank_problem.cpp
 *
 * Alex Sverdlov; alex@theparticle.com
 * g++ -std=c++17 -O3 german_tank_problem.cpp -o german_tank_problem
 *
 * https://en.wikipedia.org/wiki/German_tank_problem
 * 19, 40, 42 and 60 => ?? tanks.
 */

#include <vector>
#include <cstdlib>
#include <cstdio>

int main(){
  
  std::vector<std::vector<int>> cnts(1000);

  printf("german tank problem: 19, 40, 42, 60\n");

  srand(42);
  for(int i=1;i<1000;i++){   // number of possible tanks
    for(int j=0;j<1000;j++){  // number of experiments to run
      int m = 0;              // experiment:
      for(int k=0;k<4;k++){   // pick 4 random tanks
        int r = rand() % i;
        if(r > m) m = r;      // keep track of max tank
      }
      cnts[m].push_back(i);   // record max tank to possible tanks map
    }
  }

  auto obs = cnts[60];   // max tank observed is 60

  printf("median of max tanks: %d\n",obs[ obs.size()/2 ]);
  printf("middle 5-prcnt: %d ... %d\n",
    obs[(int)(obs.size()/2.0-obs.size()*0.25)],
    obs[(int)(obs.size()/2.0+obs.size()*0.25)] 
  );

  return 0;
}

/*

$ ./german_tank_problem 
german tank problem: 19, 40, 42, 60
median of max tanks: 76
middle 5-prcnt: 66 ... 96

*/