48
\$\begingroup\$

Input

A list of nonnegative integers.

Output

The largest nonnegative integer h such that at least h of the numbers in the list are greater than or equal to h.

Test Cases

[0,0,0,0] -> 0
[12,312,33,12] -> 4
[1,2,3,4,5,6,7] -> 4
[22,33,1,2,4] -> 3
[1000,2,2,2] -> 2
[23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42] -> 20

Rules

You can write either a full program or a function, and anonymous functions are allowed too. This is code-golf, so the fewest byte count wins. Standard loopholes are disallowed.

Background

The h-index is a notion used in academia which aims to capture the impact and productivity of a researcher. According to Wikipedia, a researcher has index h, if he or she has published h scientific articles, each of which has been cited in other articles at least h times. Thus, this challenge is about computing the h-index from a list of citation counts.

Update

Wow, great answers all round! I have accepted the shortest one, but if someone else comes up with an even shorter one, I'll update my choice accordingly.

Winners by language

Here's a table of winners by language that I'll also try to keep up to date. I have included all posts with nonnegative score. Please correct me if I have made a mistake here.

  • APL: 7 bytes by @MorisZucca
  • Bash + coreutils: 29 bytes by @DigitalTrauma
  • C#: 103 bytes by @LegionMammal978
  • C++: 219 bytes by @user9587
  • CJam: 15 bytes by @nutki
  • GolfScript: 13 bytes by @IlmariKaronen
  • Haskell: 40 bytes by @proudhaskeller
  • J: 12 bytes by @ɐɔıʇǝɥʇuʎs
  • Java: 107 bytes by @Ypnypn
  • JavaScript: 48 bytes by @edc65
  • Mathematica: 38 bytes by @kukac67
  • Perl: 32 bytes by @nutki
  • Pyth: 10 bytes by @isaacg
  • Python: 49 bytes by @feersum
  • R: 29 bytes by @MickyT
  • Ruby: 41 bytes by @daniero
  • Scala: 62 bytes by @ChadRetz
  • SQL: 83 bytes by @MickyT
  • TI-BASIC: 22 bytes by @Timtech
Improve this question
\$\endgroup\$

40 Answers 40

Reset to default
1
2
1
\$\begingroup\$

Vyxal s, 5 bytes

s₌Ṙż≥

Try it Online!

A port of the 05AB1E answer. I originally had ẏ'?<∑≤ + -G, which I kinda like more.

Explained

s₌Ṙż≥
s     # sort the input list
 ₌Ṙż  # and push reversed(^) and range(1, len(^) + 1)
    ≥ # vectorise >= over ^ and input
      # -s sums that

ẏ'?<∑≤
ẏ       # The range [0, len(input))
 '      # with only elements where: (call each element N)
  ?<∑   #   the sum of all elements of the input greater than N
     ≤  #   is less than or equal to N
        # (this gets all h with at least h)
        # -G gets the biggest h from the possible h's
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C++, 81 bytes

int h(std::list<int>a,int i=0){int c=0;for(int x:a)c+=i<x;return i<c?h(a,i+1):i;}

Similar solution to most of the other ones.

Assuming that <list> is included.

Non-recursive solution (85 83 bytes):

int h(std::list<int>a){for(int i=0,c;;i++){c=0;for(int x:a)c+=i<x;if(i>=c)return i;}}

It might be possible to put the c initialization outside the function (because that defaults to 0, and you also don't need the int, but it doesn't seem to work on TIO.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Scala, 41 39 bytes

_.sorted.:\(0){(n,h)=>h+(n/(h+1)).sign}

Try it online!

In Scala 2.13, signum was changed to sign, so it's 2 bytes extra in TIO, which still uses Scala 2.10.

Scala, 41 bytes

a=>a.max to(0,-1)find(b=>a.count(b<=)>=b)

Try it online!

This isn't mine, it's just a modified version of Chad Retz's answer, but since they're not active anymore, I decided to put it here instead of commenting on it.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 57 bytes

FirstCase[Range[Length@#,0,-1],h_/;Count[#,k_/;k>=h]>=h]&

This is an anonymous function taking a list and returning an integer, like

FirstCase[Range[Length@#,0,-1],h_/;Count[#,k_/;k>=h]>=h]&@{1,2,3,4,5,6,7}

Use this to check all test cases:

FirstCase[Range[Length@#,0,-1],h_/;Count[#,k_/;k>=h]>=h]& /@ {
  {0, 0, 0, 0},
  {12, 312, 33, 12},
  {1, 2, 3, 4, 5, 6, 7},
  {22, 33, 1, 2, 4},
  {1000, 2, 2, 2},
  {23, 42, 12, 92, 39, 46, 23, 56, 31, 12, 43, 23, 54, 23, 56, 73, 35,
    73, 42, 12, 10, 15, 35, 23, 12, 42}
}
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Scala, 62

def h(a:Int*)=Range(a.size,-1,-1).find(b=>a.count(b<=)>=b).get
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Java, 107

long f(java.util.ArrayList<Long>l){for(int i=0;;){long x=i++;l.removeIf(j->j<x);if(l.size()<x)return x-1;}}

Explanation:

long f(java.util.ArrayList<Long> l) {
    for(int i = 0;;) {
        long x = i;
        i++;
        l.removeIf(j -> j<x);
        if(l.size() < x)
            return x-1;
    }
}
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

x86 machine code, 24 bytes

Hexdump:

53 8b c2 8b d8 52 39 44 91 fc 72 01 4b 4a 75 f6
5a 48 4b 7d ee 5b 40 c3

A function that takes a pointer to the list and its length; outputs the number.

C-compatible declaration:

int __fastcall hindex(int* list, int size);

Source code:

    // eax = h
    // ebx counts down from h to 0; if it gets to 0, we have found h
    // ecx = list
    // edx = array size
    push ebx;
    mov eax, edx;                   // h = size ... down to 0
h_loop:
    mov ebx, eax;                   // init the countdown
    push edx;
array_loop:
    cmp [ecx + edx * 4 - 4], eax;   // check 1 list element
    jb skip;
    dec ebx;
skip:
    dec edx;                        // go to next element
    jnz array_loop;
    pop edx;
    dec eax;                        // go to next h
    dec ebx;                        // compare the countdown to 0
    jge h_loop;                     // if it was 0 or less, stop
    pop ebx;
    inc eax;                        // undo going to next h
    ret;

It uses a peculiar way to compare a register with 0:

    dec ebx;

Here, if ebx was less or equal to 0, it will be negative now, and then we should stop the outer loop (h_loop). Otherwise, continue:

    jge h_loop;

There is a small price (1 byte) to pay for this trick: the loop control variable h (eax) has already been advanced. So this has to be undone after the loop ends:

    inc eax;

However, even with this price, this trick gives the code the proper do-while structure, which saves 2 bytes when compared to a for structure.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Octave, 41 bytes

@(x)sum(cumprod(-sort(-x)>=(1:numel(x))))

This is an anonymous function.

Try it at Ideone.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

MATL, 8 7 bytes

SPGf<~s

Try it online!

Explanation

Direct application of the definition:

SP    % Take input array implicitly. Sort in non-increasing order
Gf    % Push array of indices of nonzero entries of the input. This gives
      % [1 2 ... n] where n is input size
<~    % True for values of the sorted input that are >= those in [1 2 ... n]
s     % Sum. Implicitly display
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Arturo, 43 bytes

$=>[0-1enumerate arrange&=>[2-&]=>[>&<=1+]]

Try it

Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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