I'm currently working on this (code-golf) challenge, and I'm having a hard time of combining the four requirements given an integer-amount n
, and total decimal-sum s
(given the ranges we're supposed to support: 1 <= n <= 10
and 0 <= s <= n
):
- The
n
items should all be random, and uniformly divided - The total sum of all items must be equal to
s
- None of the items may be above 1.0
- The code must run within 1 second for every
n <= 10
, regardless ofs
Based on this Stackoverflow answer I know how to uniformly divide items in a given range. For example, with n=5, s=4.5
, I could create a list of n-1 = 4
items in the range [0, 1.5]
, with an additional leading 0
and trailing 1.5
. Then I can calculate all the differences (so the total sum of all differences will be equal to s=4.5
). Here a possible implementation of that:
int n=5; double s=4.5;
double[] randomValues = new double[n+1];
randomValues[n] = s;
for(int i=1; i<n; i++)
randomValues[i] = Math.random()*s;
java.util.Arrays.sort(randomValues);
System.out.println("Random values:\n"+java.util.Arrays.toString(randomValues)+"\n");
double[] result = new double[n];
for(int i=0; i<n; i++)
result[i] = Math.abs(randomValues[i]-randomValues[i+1]);
System.out.println("Result values:\n"+java.util.Arrays.toString(result)+"\n");
double resultSum = java.util.Arrays.stream(result).sum();
System.out.println("Sum: "+resultSum);
System.out.println("Is the result sum correct? "+(s==resultSum?"yes":"no"));
Example output:
Random values:
[0.0, 1.3019797415889383, 1.9575834386978177, 2.0417721898726313, 4.109698885802333, 4.5]
Result values:
[1.3019797415889383, 0.6556036971088794, 0.08418875117481361, 2.0679266959297014, 0.39030111419766733]
Sum: 4.5
Is the result sum correct? yes
This above complies to three of the four requirements above (1, 2, and 4). However, not to 3.
I could wrap a loop around it, which continues as long as one of the items in the result
-array is still larger than 1:
for(boolean flag=true; flag; ){
... // Same code as above
flag=false;
for(double d:result)
if(d>1)
flag=true;
}
This still works relatively fast for most n
and s
:
Try it online (prints are removed/moved to not overflow the console)
However, the four //
-disabled test cases at the end, with averages of the expected random values nearing the 1
, take way too long (and even time out after 60 seconds on TIO).
So this is where my question is mostly about. How to uniformly divide the values like I did, AND keep in mind the range of [0, 1]
for each values, AND have a good performance? In the linked code-golf challenge at the top I see some working examples in other programming languages, like Python or JavaScript, but porting longer code-golfed challenges from one programming languages to another usually isn't very straight-forward..
Aucun commentaire:
Enregistrer un commentaire