This is basically my attempt to the German Tank Problem in which we are given a few serial numbers and expected to return an estimation of the total production count. Such as, if 4 tanks are captured with serial numbers 19, 37, 42 and 60, return the total number of German tanks there.
For a given number of serial numbers it basically works as follows:
- Take a case of 1000 units production and get the given
serials
array's length many random serial numbers. - Sort them in ascending order and map the difference of the serial numbers so
[19, 37, 42, 60]
would result[19, 18, 5, 18]
(differentiation)- Calculate the average of differences
- Divide 1000 by the average diff and get a multiplier
- Repeat the above routine 1000 times and calculate an average multiplier
- Apply the obtained multiplier to the given serial numbers array
As per this example we should expect Germans to have 80 tanks in total or so. Do you think it's a reasonable approach?
function estimateTotalTankCount(serials){
Array.prototype.shuffle = function(){
var i = this.length,
j;
while (i > 1) {
j = ~~(Math.random()*i--);
this[i] = [this[j],this[j]=this[i]][0];
}
return this;
};
var getDiff = m => Array(1000).fill() // make an array of size 1000 and fill with undefined
.map((_,i) => i+1) // fill the array with serial numbers from 1 to 1000
.shuffle() // shuffle the array
.slice(0,m) // get first `m` many serial numbers
.sort((a,b) => a-b) // sort them ascending
.map((e,i,a) => e - (a[i-1] || 0)) // map the difference of serial number with the previous
.reduce((p,c) => p + c/m,0), // calculate the average of differences
multiplier = m => Array(1000).fill() // create 1000 test cases
.map(e => 1000/getDiff(m)) // find multipliers of each tests
.reduce((p,c) => p + c/1000,0); // calculate the average of the multipliers
return serials.sort((a,b) => a - b) // sort them in ascending order
.map((e,i,a) => e - (a[i-1] || 0)) // map the difference of serial number with the previous
.reduce((p,c,i,a) => p + c/a.length,0) // calculate average of serial number differences
*multiplier(serials.length); // get multiplier for serials.length many serials and multiply by avg diff
}
console.log(Math.round(estimateTotalTankCount([19, 37, 42, 60])));
console.log(Math.round(estimateTotalTankCount([117, 232, 122, 173, 167, 12, 168, 204, 4, 229 ])));
I have decided to add the functional code as well. It's a pretty simple algorithm. We are given a sorted [s1, s2, s3, s4, s5]
array and we will get the differential of it [d1, d2, d3, d4, d5]
as follows;
<---d1---><--d2--><-d3-><---d4---><d5><---dn--->
[.........s1......s2....s3........s4..s5........n]
Then we get the mean of the diff array. After that to reach the "n" figure we multiply it with serials.length + 1
.
function estimateTotalProductionCount(serials){
return Math.round(serials.sort((a,b) => a - b) // sort them in ascending order
.map((e,i,a) => e - (a[i-1] || 0)) // map the difference of serial number with the previous
.reduce((p,c,i,a) => p + c/a.length,0) // calculate average of serial number differences
*(serials.length+1)); // the multiplier is serials.length + 1
}
console.log(estimateTotalProductionCount([117, 232, 122, 173, 167, 12, 168, 204, 4, 229 ]));
As you see the functional one gives 255 while the statistical one weighs towards 258.