7
\$\begingroup\$

Introduction

When solving a rubiks cube, one often write down the times like this

11.91, (11.28), (12.32)

This is called a average of 3, while a average of 5 looks like this

13.36, (11.89), 12.31, (16.44), 12.26

Note how the worst and best times have parenthesis around them. When calculating the average of 5 these times are removed. For an average of 3 the worst and best times are NOT removed. Similarly when calculating the standard deviation.

When taking the average of more than 12 cubes things start to get a bit harder. The general rule of thumb is:

When solving fewer than 5 cubes, do not remove any times when calculating avg or std

When evaluating fewer than 12 times, remove the best and worst time when calculating avg or std

When evaluating fewer than 40 times remove the 1/12 worst and 1/12 best times rounded down the nearest integer.

When evaluating more than 40 times remove the 1/20 worst times and the 1/20 best times rounded down to the nearest integer.

For an average of 100 this would mean we would remove the (100/20) = 5 best solves and (100/20) = 5 worst solves. Giving

14.88, 12.28, 13.76, 16.06, 13.82, 13.26, 14.57, 12.56, 15.02, 14.73, 
13.87, 14.59, 15.17, (18.48), 12.09, 12.76, 11.65, 14.14, 12.83, 14.30, 
13.28, 14.02, 12.55, 15.18, 13.65, 12.72, 14.86, 14.08, 15.07, 12.88, 13.78,
13.88, 14.63, 12.72, (10.10), 14.70, 12.82, 13.27, 13.82, 14.74, (11.22), 
13.46, 12.66, 14.06, (10.58), 15.06, (18.27), 13.39, (17.88), (18.67), 
15.38, 15.60, 14.24, 12.64, 15.51, 14.23, 16.71, 14.55, 14.32, 12.33, 11.90, 
13.65, 13.69, 13.90, 13.15, (9.61), 12.91, 13.39, 11.77, 12.64, 15.22, 
14.69, 12.76, 15.10, 11.91, (11.28), 12.32, 14.28, 14.46, 14.66, 14.15, 
15.27, (17.73), 12.70, 14.58, 11.84, 13.25, 13.36, 13.26, 15.72, 14.15, 
12.77, 15.26, 12.87, 12.96, 13.57, 14.50, 14.30, 14.57, 12.69

The challenge

The problem at hand is to take a (large) list of numbers and figure out the best average or std of a subset of these.

input

list, n, avg or std

Write a program that takes in a list of numbers formated exactly as comma seperated numbers 12.91, 13.39, ... or [12.91, 13,39 ... ] You can assume that the list only contains real valued positive numbers less than 2^32.

A number n indicating how many numbers to average or take the std of, if n=0 one should take the average / std of all the numbers.

A string avg or std indicating if one should return the lowest average of n numbers or the lowest standard deviation (std). A negative n or a non integer should throw an error, blank or return false.

Output

The output should be exactly on the form

avg = ...
list of of numbers

or

std = ...
list of of numbers

As shown in the examples. Note that the best and worst times are marked with brackets as given by the rules above. The function should return the n consecutive times with the lowest avg or std At every 12 time, a newline should be inserted.

Test case

I will use the following list of 200 numbers to base my tests on

15.86, 17.02, 24.01, 21.01, 15.93, 14.86, 18.43, 12.52, 18.48, 19.85, 13.01, 14.92, 13.07, 13.44, 13.07, 15.08, 12.70, 13.59, 15.22, 11.88, 13.26, 13.62, 12.85, 16.88, 15.78, 15.94, 14.88, 12.28, 13.76, 16.06, 13.82, 13.26, 14.57, 12.56, 15.02, 14.73, 13.87, 14.59, 15.17, 18.48, 12.09, 12.76, 11.65, 14.14, 12.83, 14.30, 13.28, 14.02, 12.55, 15.18, 13.65, 12.72, 14.86, 14.08, 15.07, 12.88, 13.78, 13.88, 14.63, 12.72, 10.10, 14.70, 12.82, 13.27, 13.82, 14.74, 11.22, 13.46, 12.66, 14.06, 10.58, 15.06, 18.27, 13.39, 17.88, 18.67, 15.38, 15.60, 14.24, 12.64, 15.51, 14.23, 16.71, 14.55, 14.32, 12.33, 11.90, 13.65, 13.69, 13.90, 13.15, 9.61, 12.91, 13.39, 11.77, 12.64, 15.22, 14.69, 12.76, 15.10, 11.91, 11.28, 12.32, 14.28, 14.46, 14.66, 14.15, 15.27, 17.73, 12.70, 14.58, 11.84, 13.25, 13.36, 13.26, 15.72, 14.15, 12.77, 15.26, 12.87, 12.96, 13.57, 14.50, 14.30, 14.57, 12.69, 15.21, 14.45, 14.90, 14.91, 15.66, 15.87, 14.79, 15.69, 17.37, 15.42, 12.11, 14.89, 13.39, 12.62, 13.42, 14.07, 14.85, 13.23, 14.05, 14.43, 13.36, 14.19, 14.16, 14.66, 12.02, 12.56, 12.69, 12.55, 14.36, 15.79, 12.53, 12.51, 12.15, 15.60, 13.42, 12.87, 13.02, 15.66, 13.18, 14.77, 13.57, 13.86, 12.26, 14.48, 14.68, 11.85, 14.82, 13.74, 13.85, 15.05, 14.78, 14.43, 12.72, 14.39, 15.06, 15.28, 12.06, 14.59, 15.49, 11.66, 14.83, 14.09, 11.62, 15.96, 14.77, 14.99, 14.20, 12.35, 17.62, 11.66, 13.46, 15.24, 14.85, 13.48

Input 0:

list, 3, avg

Output 0:

avg = 11.84
11.91, (11.28), (12.32)

Input 1:

list, 12, avg

Output 1:

avg = 12.88
(9.61), 12.91, 13.39, 11.77, 12.64, (15.22), 14.69, 12.76, 15.10, 11.91, 11.28, 12.32

Input 2:

list, 12, std

Output 2:

std = 0.44
15.21, 14.45, 14.90, 14.91, 15.66, 15.87, 14.79, 15.69, (17.37), 15.42, (12.11), 14.89

Input 3:

list, 0, std

Output 3:

std = 1.21
15.86, 17.02, (24.01), (21.01), 15.93, 14.86, (18.43), 12.52, (18.48), (19.85), 13.01, 14.92, 
13.07, 13.44, 13.07, 15.08, 12.70, 13.59, 15.22, 11.88, 13.26, 13.62, 12.85, 16.88, 
15.78, 15.94, 14.88, 12.28, 13.76, 16.06, 13.82, 13.26, 14.57, 12.56, 15.02, 14.73, 
13.87, 14.59, 15.17, (18.48), 12.09, 12.76, (11.65), 14.14, 12.83, 14.30, 13.28, 14.02, 
12.55, 15.18, 13.65, 12.72, 14.86, 14.08, 15.07, 12.88, 13.78, 13.88, 14.63, 12.72, 
(10.10), 14.70, 12.82, 13.27, 13.82, 14.74, (11.22), 13.46, 12.66, 14.06, (10.58), 15.06, 
(18.27), 13.39, (17.88), (18.67), 15.38, 15.60, 14.24, 12.64, 15.51, 14.23, 16.71, 14.55, 
14.32, 12.33, 11.90, 13.65, 13.69, 13.90, 13.15, (9.61), 12.91, 13.39, (11.77), 12.64, 
15.22, 14.69, 12.76, 15.10, 11.91, (11.28), 12.32, 14.28, 14.46, 14.66, 14.15, 15.27, 
(17.73), 12.70, 14.58, 11.84, 13.25, 13.36, 13.26, 15.72, 14.15, 12.77, 15.26, 12.87, 
12.96, 13.57, 14.50, 14.30, 14.57, 12.69, 15.21, 14.45, 14.90, 14.91, 15.66, 15.87, 
14.79, 15.69, 17.37, 15.42, 12.11, 14.89, 13.39, 12.62, 13.42, 14.07, 14.85, 13.23, 
14.05, 14.43, 13.36, 14.19, 14.16, 14.66, 12.02, 12.56, 12.69, 12.55, 14.36, 15.79, 
12.53, 12.51, 12.15, 15.60, 13.42, 12.87, 13.02, 15.66, 13.18, 14.77, 13.57, 13.86, 
12.26, 14.48, 14.68, 11.85, 14.82, 13.74, 13.85, 15.05, 14.78, 14.43, 12.72, 14.39, 
15.06, 15.28, 12.06, 14.59, 15.49, (11.66), 14.83, 14.09, (11.62), 15.96, 14.77, 14.99, 
14.20, 12.35, 17.62, (11.66), 13.46, 15.24, 14.85, 13.48

Split the lines at every 12 number.

Input 4:

list, 201, avg

Output 5:

Throw `Error` or `False`. 

Input 6:

list, 1, avg

Output 6:

avg = 9.61
(9.61)

Input 8:

list, 1, std

Output 8:

std = 0
(15.86)

just return the first element of the list.

Scoring

Submissions will be scored in bytes. I recommend this website to keep track of your byte count, though you can use any counter you like. Like always whitespace counts as bytes.

Remove 25% of your byte count if your function has the ability to switch between highest avg and std, and lowest avg and std. Eg input on the form

list, n, avg / std, high / low

This is , so the lowest score wins!

\$\endgroup\$
  • \$\begingroup\$ Can a function be written? \$\endgroup\$ – LegionMammal978 Dec 5 '15 at 12:15
  • \$\begingroup\$ yeah =) No problem \$\endgroup\$ – N3buchadnezzar Dec 5 '15 at 12:28
  • 1
    \$\begingroup\$ This is an old post, but I have some questions. Why is output 0 not 10.10? (The 3 lowest values in your example list are [9.61, 10.10, 10.58].) Why are multiple values in parentheses in output 3? (The description just says that those are the "smallest" and "largest", but that's not the case.) Finally, why is output 8 zero? The standard deviation of only 1 number is undefined (because it involves division by zero). I think I have a neat solution to this puzzle, but I'm not sure because the details are so vague... \$\endgroup\$ – rturnbull Oct 2 '16 at 16:12
1
\$\begingroup\$

Java 8, 944 903 bytes

import java.util.*;interface M{static void main(String[]a){String f=a[2];int n=new Short(a[1]),i=0,l,j,k;if(n<0)return;List<Float>L=new Stack(),t,r,R=L,u,U=L,S=L,V=L;for(a=a[0].split(","),l=a.length;i<l;)L.add(new Float(a[i++]));n=n<1?l:n;i=0;float m=99,M=m,q,Q,x,y,z;do{for(t=new Stack(),x=y=j=0;j<n;)t.add(L.get(i+j++));for(k=(int)(n<12?0:n<40?1/12d*n:.05*n),j=k=k<1?1:k,u=new ArrayList(t),r=new Stack();j-->0;){r.add(q=Collections.min(t));r.add(Q=Collections.max(t));if(n>4){t.remove(q);t.remove(Q);}}for(float T:t)x+=T;x/=k=n>4?n-2*k:n;if(x<m){m=x;R=r;U=u;}for(float T:t)y+=(z=T-x)*z;y=(float)Math.sqrt(y/k);if(y<M){M=y;S=r;V=u;}}while(++i<=l-n);j=f.charAt(0)-97;System.out.println(f+" = "+f.format(f="%.2f",q=j<1?n<2?Collections.min(L):m:n<2?0:M));i=0;for(Object o:j<1?U:n<2?L.subList(0,1):V)System.out.print(f.format((j<1?R:S).remove(o)?"(%.2f)":f,n<2&j<1?q:o)+(++i<n?", ":"")+(i%12<1?"\n":""));}}

Full program requirement, strict I/O formatting, validating.. sigh.. >.>

Verify all test cases: 3,avg ; 12,avg ; 12,std ; 0,std ; 201,avg ; 1,avg ; 1,std ; -1,either.

Here is the same as function with somewhat flexible I/O and without validating (still 776 739 bytes..):

import java.util.*;(L,n,f)->{int i=0,l=L.size(),j,k;List<Float>t,r,R=new Stack(),u,U=R,S=R,V=R;n=n<1?l:n;i=0;float m=99,M=m,q,Q,x,y,z;do{for(t=new Stack(),x=y=j=0;j<n;)t.add(L.get(i+j++));for(k=(int)(n<12?0:n<40?1/12d*n:.05*n),j=k=k<1?1:k,u=new ArrayList(t),r=new Stack();j-->0;){r.add(q=Collections.min(t));r.add(Q=Collections.max(t));if(n>4){t.remove(q);t.remove(Q);}}for(float T:t)x+=T;x/=k=n>4?n-2*k:n;if(x<m){m=x;R=r;U=u;}for(float T:t)y+=(z=T-x)*z;y=(float)Math.sqrt(y/k);if(y<M){M=y;S=r;V=u;}}while(++i<=l-n);j=f.charAt(0)-97;System.out.println(f+" = "+f.format(f="%.2f",q=j<1?n<2?Collections.min(L):m:n<2?0:M));i=0;for(Object o:j<1?U:n<2?L.subList(0,1):V)System.out.print(f.format((j<1?R:S).remove(o)?"(%.2f)":f,n<2&j<1?q:o)+" ");}

Try it online.

Explanation:

import java.util.*;           // Required import for List, Stack and Collections
interface M{                  //  Class
  static void main(String[]a){//   Mandatory main-method
    String f=a[2];            //    Save the third argument in String `f`
    int n=new Short(a[1]),    //    Save the second argument as integer in `n`
        i=0,l,j,k;            //    Some temp/index integers
    if(n<0)return;            //    If `n` is negative, stop the program
    List<Float>L=new Stack(), //    Input-List
               t,r,R=L,u,U=L,S=L,V=L;
                              //    Some temp Lists
    for(a=a[0].split(","),l=a.length;i<l;)
                              //    Save the amount of items in the list in `l`
                              //    and loop over these items as Strings
      L.add(new Float(a[i++]));
                              //     And add them as floats to the input-List
    n=n<1?l:n;                //    If `n` was 0, make it equal to `l` instead
    i=0;                      //    Reset index `i` to 0
    float m=99,M=m,           //    Lowest `avg` and `std`, both starting at 99
          q,Q,x,y,z;          //    Some temp floats
    do{                       //    Start the do-while
      for(t=new Stack(),      //     Reset List `t`
          x=y=j=0;j<n;)       //     Loop `j` from 0 to `n` (exclusive)
        t.add(L.get(i+j++));  //      And add the items on index `i+j` of List `L` to `t`
      for(k=(int)(n<12?       //     If `n` is smaller than 12
                   1          //      Set `k` to 1
                  :n<40?      //     Else-if `n` is [12; 40)
                   1/12d*n    //      Set `k` to 1/12th of `n`
                  :           //     Else (`n` is 40 or larger)
                   .05*n),    //      Set `k` to 1/20th of `n`
          j=k=k<1?1:k,        //     If `k` is 0 due to rounding, make it 1 instead
          u=new ArrayList(t), //     Copy List `t` to `u`
          r=new Stack();      //     And reset List `r`
          j-->0;){            //     Loop `k` times
        r.add(q=Collections.min(t));
                              //      Add the smallest item in List `t` to `r`
        r.add(Q=Collections.max(t));
                              //      as well as the largest item
        if(n>4){              //      If `n` is 5 or larger:
          t.remove(q);t.remove(Q);}}
                              //       Remove those two items from List `t`
      for(float T:t)          //     Loop over List `t`
        x+=T;                 //      And sum them all into `x`
      x/=k=n>4?               //     If `n` is 5 or larger
          n-2*k               //      Set `k` to `n-2*k` and divide `x` by that
         :                    //     Else:
          n;                  //      Divide `x` by `n`
      if(x<m){                //     If `x` is smaller than the previous smallest avg `m`
        m=x;                  //      Replace `m` with `x` (smallest avg)
        R=r;                  //      Replace `R` with `r` (items between parenthesis)
        U=u;}                 //      And replace `U` with `u` (all `n` items in this avg) 
      for(float T:t)          //     Loop over List `t` again
        y+=(z=T-x)*z;         //      And sum `(T-x)^2` to `y`
      y=(float)Math.sqrt(y/k);//     Also divide `y` by `k`, and take its square-root
                              //     The process above is how you calculate the std
      if(y<M){                //     If `y` is smaller than the previous smallest std `M`
        M=y;                  //      Replace `M` with `y` (smallest std)
        S=r;                  //      Replace `S` with `r` (items between parenthesis)
        V=u;}}                //      And replace `V` with `u` (all `n` items in this std)
    while(++i<=l-n);          //    Continue the do-while as long as `i` is smaller than `l-n`
    j=f.charAt(0)-97;         //    Set `j` to the alphabetic index of the first letter of `f`
    System.out.println(f+" = "//    Print "`f` = "
      +f.format(f="%.2f",     //     Round to two decimals
        q=j<1?                //     If it's an avg:
           n<2?               //      And `n` is 1:
            Collections.min(L)//       Simply take the smallest value in `L`
           :                  //      Else:
            m                 //       Take the calculated lowest avg `m`
          :                   //     Else (it's an std):
           n<2?               //      If `n` is 1:
            0                 //       Use 0
           :                  //      Else:
            M));              //       Take the calculated lowest std `M`
    i=0;                      //    Reset `i` to 0
    for(Object o:j<1?         //    If it's an avg
                  U           //     Loop over List `U`
                 :            //    Else (it's an std instead)
                  n<2?        //     If `n` is 1:
                   L.subList(0,1)
                              //    Only take the first item of List `L`
                  :           //     Else:
                   V)         //    Loop over List `V`
      System.out.print(f.format(
       (j<1?                   //     If it's an avg
         R                     //      Use List `R`
        :                      //     Else (it's an std instead)
         S)                    //      Use List `S`
           .remove(o)?         //     If the current item is in this List
             "(%.2f)"          //      Round to two decimals, and add parenthesis
            :                  //     Else:
             f,                //      Only round to two decimals
       n<2&j<1?                //     If it's an avg, and `n` is 1:
        q                      //      Take the smallest value in `L`
       :                       //     Else:
        o)                     //      Take the current item in this loop
          +(++i<n?", ":"")     //     If it's not the last item, append a comma
          +(i%12<1?"\n":""));}}//     And every 12 items, append a new-line
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.