14
\$\begingroup\$

(a paradox, a paradox, a most ingenious paradox)

This is the first part of a multipart series inspired by different R functions.

The Task

Given a dataset \$D\$ of positive integers, I need you to compute the 5 number summary of \$D\$. However, I'm working on large datasets, so I need your code to be as small as possible, allowing me to store it on my computer.

The five number summary consists of:

  • Minimum value
  • First quartile (Q1)
  • Median / Second quartile (Q2)
  • Third quartile (Q3)
  • Maximum value

There are several different ways of defining the quartiles, but we will use the one implemented by R:

Definitions:

  • Minimum and maximum: the smallest and largest values, respectively.
  • Median: the middle value if \$D\$ has an odd number of entries, and the arithmetic mean of the two middle-most values if \$D\$ has an even number of entries. Note that this means the median may be a non-integer value. We have had to Compute the Median before.
  • First and Third Quartiles: Divide the data into two halves, including the central element in each half if \$D\$ has an odd number of entries, and find the median value of each half. The median of the lower half is the First Quartile, and the median of the upper half is the Third Quartile.

Examples:

\$D=[1,2,3,4,5]\$. The median is then \$3\$, and the lower half is \$[1,2,3]\$, yielding a first quartile of \$2\$, and the upper half is \$[3,4,5]\$, yielding a third quartile of \$4\$.

\$D=[1,3,3,4,5,6,7,10]\$. The median is \$4.5\$, and the lower half is \$[1,3,3,4]\$, yielding a first quartile of \$3\$, and the upper half is \$[5,6,7,10]\$, yielding a third quartile of \$6.5\$.

Additional rules:

  • Input is as an array or your language's nearest equivalent.
  • You may assume the array is sorted in either ascending or descending order (but please specify which).
  • You may return/print the results in any consistent order, and in whichever flexible format you like, but please denote the order and format in your answer.
  • Built-in functions equivalent to fivenum are allowed, but please also implement your own solution.
  • You may not assume each of the five numbers will be an integer.
  • Explanations are encouraged.
  • This is , so shortest answer in each language wins!

Randomly generated test cases

1 1 1 1 1 2 2 2 2 2 3 3 4 4 4 4 4 5 5 5 -> 1 1.5 2.5 4 5 
1 2 2 2 4 4 5 5 6 7 7 8 9 9 9 9 9 10 10 10 -> 1 4 7 9 10 
2 2 2 6 8 10 15 16 21 22 23 24 26 33 35 38 38 45 46 47 48 -> 2 10 23 38 48 
1 2 9 -> 1 1.5 2 5.5 9 
1 2 3 3 3 4 9 -> 1 2.5 3 3.5 9
1 1 2 5 7 7 8 8 15 16 18 24 24 26 26 27 27 28 28 28 29 29 39 39 40 45 46 48 48 48 48 49 50 52 60 63 72 73 79 85 86 87 88 90 91 93 94 95 95 97 100 -> 1 25 45 76 100
2 2 4 4 6 8 10 11 13 14 14 15 17 21 23 24 26 27 27 28 28 30 31 33 33 34 36 36 38 38 39 40 41 42 42 43 45 45 47 47 47 47 47 48 48 48 50 51 53 53 55 56 56 56 57 57 58 62 62 63 64 64 65 65 66 67 67 67 68 69 69 71 71 71 74 79 80 81 81 81 82 82 83 83 86 86 86 87 89 94 94 94 95 95 97 98 99 100 100 100 -> 2 33.5 54 76.5 100
1 3 3 4 -> 1 2 3 3.5 4
1 3 3 3 4 -> 1 3 3 3 4
|improve this question
\$\endgroup\$
6
\$\begingroup\$

R, 7 bytes

fivenum

Try it online!

Obvious cheeky answer. ;-)

Interestingly, fivenum(x) is not equivalent to summary(x) even when x is numeric, as the quantiles are computed differently: fivenum averages at discontinuities, whereas summary interpolates. You can force summary to behave like fivenum with the option quantile.type, but this is still longer than

R, 51 bytes

function(x)quantile(x,(0:4)/4,t=2+5*!sum(!!x)%%4-3)

Try it online!

which computes the quantiles of order 0 (min), 0.25 (Q1), 0.5 (median), 0.75 (Q3) and 1 (max). The t=2 specifies how quantiles are defined: there are 9 possible types, and the challenge definition corresponds to type 2 in most cases, and to type 7 when \$n\equiv 3\pmod 4\$. Honestly, this choice of a definition of quantiles is a bit weird.

Note that the source code of the fivenum built-in is very different (and much longer).

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ The only thing I can find is that quantile returns a named vector, while fivenum is unnamed. Maybe that's a problem downstream of where fivenum is used? \$\endgroup\$ – JAD Jul 10 '19 at 9:48
  • \$\begingroup\$ @JAD Enclosing the code in unname() would solve that. Maybe there are historical reasons? \$\endgroup\$ – Robin Ryder Jul 10 '19 at 12:40
  • 1
    \$\begingroup\$ Your function differs from fivenum for inputs of length 3 mod 4, including two of the test cases. \$\endgroup\$ – Nitrodon Jul 10 '19 at 15:18
  • \$\begingroup\$ @Nitrodon Argh! Thanks for noticing! It should be OK now. \$\endgroup\$ – Robin Ryder Jul 11 '19 at 6:10
5
\$\begingroup\$

MATL, 18 bytes

tno?t.5Xqh]5:q4/Xq

Output order is increasing, as in the test cases.

Try it online! Or verify all test cases.

Explanation

MATL, like MATLAB, computes quantiles using linear interpolation if needed (just as specified in the challenge for the median). To achieve the required behaviour for the first and third quartiles, it suffices to repeat the median if the length of the input is odd. Then the results are just the 0, .25, .5, .75 and 1 quantiles.

t       % Implicit input: numeric row array. Duplicate
no      % Length, parity
?       % If not zero (that is, if input length is odd)
  .5    %   Push .5
  Xq    %   .5-quantile: median. For even length it behaves as required
  h     %   Concatenate horizontally
]       % End
5:q     % Push [0 1 2 3 4]
4/      % Divide by 4, element-wise: gives [0 .25 .5 .75 1]
Xq      % [0 .25 .5 .75 1]-quantiles. Implicit display
|improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 13 bytes

œs2a\;WÆṁ;Ḣ;Ṫ

Try it online!

Order: [Q1, Q3, Q2/med, min, max].

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3.8 (pre-release), 66 bytes

lambda l:[(l[~-i//4]+l[-~i//4])/2for i in[1,n:=len(l),~n-n,~n,-3]]

Try it online!

Input and output are in ascending order.

|improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 3.8, 97 bytes

lambda l:[l[0],l[-1]]+[(i[x(i)//2]+i[~x(i)//2])/2for i in(l[:~((x:=len)(l)//2-1)],l,l[x(l)//2:])]

This assumes that the input list is sorted in ascending order. f is the function to return the 5-number summary.

The 5-number summary is in the order: \$\{min, max, Q1, Q2,Q3\}\$

I took off a few bytes by taking some hints from FlipTack's answer to Compute the Median.

Try it online!

How does it work?

lambda l:
    [l[0],l[-1]] # The minimum and maximum, because l is assumed to be sorted in ascending order
    +[(i[x(i)//2]+i[~x(i)//2])/2 # This line computes the median...
    for i in(l[:~((x:=len)(l)//2-1)],l,l[x(l)//2:])] # ...for each of these lists (the first half, the overall list, and the second half)
    # The (x:=len) is an assignment expression from Python 3.8.
    # It assigns the len function to the variable x but also returns len.
    # Therefore, x can be used as len to save a byte (yes, just one byte)
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ it's fine to use a function that computes the median; that submission would no longer by Python (3?), but "Python + statistics package" or similar. \$\endgroup\$ – Giuseppe Jul 10 '19 at 1:10
1
\$\begingroup\$

Charcoal, 33 bytes

≔⊖ＬθηＩＥ⟦⁰⊘÷η²⊘η⁻η⊘÷η²η⟧⊘⁺§θ⌊ι§θ⌈ι

Try it online! Link is to verbose version of code. Outputs in ascending or descending order depending on whether the input is in ascending or descending order. Explanation:

≔⊖Ｌθη

Get the index of the last element.

ＩＥ

Map over the elements of the following array and cast the result to string for implicit print on separate lines.

⟦⁰⊘÷η²⊘η⁻η⊘÷η²η⟧

Calculate the positions of the quartile elements, where an extra 0.5 denotes that the value is the average of two adjacent elements.

⊘⁺§θ⌊ι§θ⌈ι

Calculate the quartile at each position by taking the average of the values at the floor and ceiling of the position.

|improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby 2.7-preview1, 59 bytes

A direct ripoff port of xnor's Python answer.

->a{[1,n=a.size,~n-n,~n,-3].map{(a[~-@1/4]+a[-~@1/4])/2.0}}

Try it online! (one byte longer since TiO is using Ruby 2.5 and doesn't have numbered block parameters e.g. @1).

|improve this answer
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 123 121 119 bytes

-2 thanks to ceilingcat.

Assumes a list sorted in ascending order.

Outputs in order: min, Q1, Q2, Q3, max.

#define M(K,x)(K[~-x/2]+K[x/2])/2.,
f(L,n,m)int*L;{m=n-n/2;printf("%d %f %f %f %d",*L,M(L,m)M(L,n)M((L+n/2),m)L[n-1]);}

Try it online!

|improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 18 bytes

2F2äнIR})€ÅmIWsà‚«

Output-order is: [Q1, Q3, Q2, min, max].

Try it online or verify all test cases. (I've added a sort { for the test suite, so the test cases are easier to verify in the order [min, Q1, Q2, Q3, max].)

Explanation:

2F                 # Loop 2 times:
  2ä               #  Split the list at the top of the stack into two halves
                   #  (which is the (implicit) input-list in the first iteration)
    н              #  Only leave the first halve
     IR            #  Push the input in reverse
       })          # After the loop: wrap all three lists into a list
         €         # For each of the lists:
          Åm       #  Get the middle/median depending on the parity of the size of the list
            I      # Then push the input-list again
             W     # Get the minimum (without popping)
              s    # Swap to get the input-list again
               à   # Get the maximum (by popping the list)
                ‚  # Pair the min-max together to a pair
                 « # And merge both lists together
                   # (after which the result is output implicitly)
|improve this answer
\$\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.