At least h with at least h

Question

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

Answer 1

APL 7

+/⊢≥⍋∘⍒

Can be tried online on tryapl.org

f←+/⊢≥⍋∘⍒
f¨(4⍴0)(12 312 33 12)(⍳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)
0 4 4 3 2 20

Answer 2

Python, 52

f=lambda s,n=0:n<sum(n<x for x in s)and f(s,n+1)or n

A recursive solution. Run this in Stackless Python if you're worried about overflows.

Starting from n=0, checks whether at least n+1 of the numbers are at least n+1. If so, increments n and starts again. If not, outputs n.

The conditional is done using Python's short-circuiting for Booleans. The expression sum(n<x for x in s) counts the number of values in s that are greater than n by adding the indicator Booleans, which are treated as 0 or 1.

For comparison, the iterative equivalent is 2 chars longer. It requires Python 2.

s=input()
n=0
while n<sum(n<x for x in s):n+=1
print n

Unfortunately, the input need to be saved for a variable before being iterated over or else Python will try to read the input repeatedly.

Answer 3

Pyth, 13 10 bytes

tf<l-QUTT1

Input in a form such as [22,33,1,2,4] on STDIN.

Try it here.

How it works:

-QUT is all of the numbers in the input (Q) at least as large as the number being checked, T.

<l-QUTT is true if the the length of that list is less than T.

f<l-QUTT1 finds the first integer which returns true for the inner check, starting at 1 and going up.

tf<l-QUTT1 decrements that by one, giving the largest value for which the condition is false, which is the h-index.

Starting at 1 ensures that 0 is returned when the test is always true, such as in the first test case.

Answer 4

Python 2, 49

Input should be typed in the same format as the examples.

i=0
for z in sorted(input())[::-1]:i+=z>i
print i

Answer 5

CJam, 15 bytes

Direct translation of my Perl solution.

l~{~}${W):W>},,

Answer 6

J (13 12)

[:+/i.@#<\:~

Pretty similar to randomra's solution. Demonstration:

   f=:[:+/i.@:#<\:~
   f 0,0,0,0
0
   f 12,312,33,12
4
   f 1,2,3,4,5,6,7
4
   f 22,33,1,2,4
3
   f 1000,2,2,2
2
   f 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

Answer 7

Mathematica, 44 42 40 38 bytes

Anonymous function:

LengthWhile[i=0;SortBy[#,-#&],#>i++&]&

Run it by tacking the input on to the end like so:

In: LengthWhile[i=0;SortBy[#,-#&],#>i++&]&@{1,2,3,4,5,6,7}
Out: 4

Answer 8

SQL, 81 94 83

Given a table (I) of values (V), the following query will return h. Tested in PostgreSQL and will also work in SQL Server. Edit Make it return 0 rather than NULL. Made better with a COUNT, thanks @nutki

SELECT COUNT(R)FROM(SELECT ROW_NUMBER()OVER(ORDER BY V DESC)R,V FROM I)A WHERE R<=V

SQLFiddle example

Essentially it numbers the rows on a descending sort of the values. Then it returns the maximum row number where the row number is greater than equal to the value.

Answer 9

R, 39 35 29

s=sort(i);sum(s>=length(s):1)

Given a vector of integers in i and using the logic of a reverse sort then returning the length of the vector where element number is less than s. Thanks to @plannapus for the nice tip.

> i=c(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)
> s=sort(i);length(s[s>=length(s):1])
[1] 20
> i=c(0,0,0,0)
> s=sort(i);length(s[s>=length(s):1])
[1] 0

Answer 10

CJam, 23 bytes

l~:I,),W%{_If>:!:+>}$0=

This takes the list as an array on STDIN, like

[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]

Test it here.

You can use this to run all test cases:

[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]]
{:I,),W%{_If>:!:+>}$0=N}/

Explanation

l~:I,),W%{_If>:!:+>}$0=
l~:I                    "Read input, evaluate, store in I.";
    ,                   "Get length of input N.";
     ),W%               "Create range from 0 to N, reverse.";
         {         }$   "Sort stably.";
          _I            "Duplicate candidate h, push input list.";
            f>          "Map each number to 1 if it's less or 0 otherwise.";
              :!        "Invert all results.";
                :+      "Sum them up.";
                  >     "Check if the sum is less than the candidate h.";
                     0= "Pick the first element.";

The logic is a bit backwards, but it saved a couple of bytes. Basically, the block passed to sort returns 0 for valid candidates and 1 otherwise. So the valid candidates come first in the sorted array. And because the sort is stable, and we begin with a list from N down to 1, this will return the largest valid h.

Answer 11

Perl 5: 32 (30 + 2 for -pa)

#!perl -pa
$_=grep$_>$i++,sort{$b<=>$a}@F

Takes space separated input on STDIN:

perl hidx.pl <<<'1 2 3 4 5 6 7'

Answer 12

Python (63)

Basically a direct port of my J solution. Obviously, a lot longer, as one might imagine.

lambda x:sum(a>b for a,b in zip(sorted(x)[::-1],range(len(x))))

Answer 13

Haskell, 40

f s=[x-1|x<-[1..],x>sum[1|r<-s,r>=x]]!!0

this searches for the first number to not fit the scheme and returns it's predecessor.

Answer 14

Ruby 44 41

Recursive, more or less same strategy as xnor's Python solution:

f=->a,n=0{a.count{|x|x>n}<n+1?n:f[a,n+1]}

Ruby 52

Non-recursive:

f=->a{a.size.downto(0).find{|x|a.count{|y|y>=x}>=x}}

"Stabby" lambda/anonymous functions, require Ruby 1.9 or newer. Call with e.g. f[[22,33,1,2,4]]

Answer 15

Bash + coreutils, 29

sort -nr|nl -s\>|bc|grep -c 0

Input taken from stdin as a newline-separated list.

• sort the integers in descending order
• nl prefixes each line with its 1-based line number, separating the line number and rest of the line with a greater-than >
• Arithmetically evaluate each line with bc. Integers less than their line number result in 0. Otherwise 1.
• grep counts the number of 0s, i.e. the number of integers greater than or equal to h

Example

$ for i in {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}; do echo $i; done | ./atleasth.sh
20
$ for i in {1,2,3,4,5,6,7}; do echo $i; done | ./atleasth.sh
4
$ 

Answer 16

JavaScript (ES6) 48

Recursive solution.

F=(l,h=-1)=>l.filter(v=>v>h).length>h?F(l,h+1):h

Test in FireFox/FireBug console

;[
  [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]
 ].forEach(l=>console.log(l,F(l)))

Output

[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

Answer 17

Java 8, 116 bytes.

Full class:

import java.util.*;
import java.util.stream.*;

class H{

    public static void main(String[]a){
        System.out.println(new H().f(Stream.of(a[0].split(",")).mapToInt(Integer::parseInt).toArray()));
    }

    int i;

    int f(int[]n){
        Arrays.sort(n);
        i=n.length;
        Arrays.stream(n).forEach(a->i-=a<i?1:0);
        return i;
    }
}

Function:

import java.util.*;int i;int f(int[]n){Arrays.sort(n);i=n.length;Arrays.stream(n).forEach(a->i-=a<i?1:0);return i;}}

Answer 18

APL, 12 characters

(+/⊢≥⍒)⊂∘⍒⌷⊢

Answer 19

C++ 815 219 from (wc -c main.cpp)

Alright here's some of the worst code I've ever written! :)

#include <iostream>
#include <list>
using namespace std;int main(int c,char** v){list<int>n(--c);int h=c;for(int&m:n)m=atoi(*(v+(h--)));n.sort();for(auto r=n.rbegin();r!=n.rend()&&*r++>++h;);cout<<(h==c?h:--h)<<endl;}

Answer 20

Jelly, 6 bytes

NỤỤ<’S

Explanation:

N           Negate (so that repeated elements won't mess up the second grade down)
 Ụ          Grade down
  Ụ         Twice.
   <’       Predicate, check for each element if the new one (after grading) is lower than original array (minus 1 on each element)
     S      Sum

Answer 21

05AB1E, 5 bytes

{Rā@O

Try it online! or as a Test Suite

Explanation

{R      # sort descending
  ā@    # check each element if it's greater than or equal to its 1-based index
    O   # sum

Answer 22

J, 15 11 chars

(Current shortest J solution.)

   [:+/#\<:\:~

   ([:+/#\<:\:~) 1 2 3 4 5 6 7
4

Compares <: sorted list \:~ elements with 1..n+1 #\ and counts true comparisons +/.

Testing similarity against other J solution on 100 random test cases:

   */ (([:+/#\<:\:~) = ([:+/i.@#<\:~))"1 ?100 100$100
1

Answer 23

CJam, 22 bytes

q~:Q,),{Q{1$>},,>!},W=

Takes the list as input:

[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]

Output:

20

Try it here

Answer 24

JAGL Alpha 1.2 - 14

Doesn't count because the 'C' reverse array functionality was added after the question, but am answering for fun anyway.

Assumes that the array is the first item on the stack, and puts the answer at the top of the stack.

0SJC{Sd@>+1}/S

To print, just add P at the end, adding a byte.

Explanation:

0               Push the number 0 (the counter)
 SJC            Swap to array, sort and reverse
    {Sd@>+1}/   For each item in the array, add 1 to counter if counter is less than item
             S  Swap counter to top of stack

Answer 25

GolfScript, 13 bytes

$-1%0\{1$>+}/

Test this code online.¹

Takes input as an array on the stack. Uses the same algorithm as feersum's Python solution, iterating over the numbers in the array and incrementing a counter from 0 until it equals or exceeds the current element of the array.

^{1) The online GolfScript server seems to be experiencing random timeouts again. If the program times out for you, try re-running it.}

Answer 26

TI-BASIC, 22 bytes

ASCII representation:

Input L1:1:While Ans≤sum(Ans≥L1:Ans+1:End:Ans

Hex dump:

DC 5D 00 3E 31 3E D1 72 6D B6 72 6C 5D 00 3E 72 70 31 3E D4 3E 72

Gets a list as input. Starting from Ans=0, checks whether at least Ans+1 of the numbers are at least Ans+1. If so, increments Ans and loops again. If not, outputs Ans.

Answer 27

Reng v.3.2, 43 bytes

1#xk#yaïí'1ø ~n-1$\
1+)x(%:1,%1ex+y1-?^#y#x

Try it here! This code can be split into three parts: initial, computational, and final.

Initial

1#xk#yaïí'1ø

This stores 1 to x, the length of the input stack k to y, and gets all input (aïí) which is then sorted ('). 1ø goes to the next line, i.e., the next part.

Computational

1+)x(%:1,%1ex+y1-?^#y#x

Reng has no built-in for inequality. Thus, an algorithm must be implemented. The shortest algorithm I found for a < b is %:1,%1e; this looks like this:

Command | Stack
  ---   | a, b
   %    | a/b
   :    | a/b, a/b
   1    | a/b, a/b, 1
   ,    | a/b, (a/b)%1
   e    | (a/b) == ((a/b)%1)

I'm sure that cleared it up! Let me explain further. x % 1, i.e modulus with 1, maps x to (-1,1). We know that (a/b) % 1 is a/b when a < b. Thus, this expression is equal to a < b.

However, this doesn't work quite as well because of problems with modulus with zero. So, we increment every member of the stack and the counter initially.

After we get the inequality Boolean on the stack, x+ adds it to x, but leaves it on the stack for the moment. y1- decrements y, and ?^ goes up iff y == 0 and we proceed to the final phase. Otherwise, we put y-1 into y and the new x into x.

Final

             ~n-1$\

This pops the residual y-1 from the stack, decrements the result, outputs it, and ends the program.

Answer 28

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}
}

Answer 29

C#, 103

Anonymous function.

a=>{try{return a.OrderBy(b=>-b).Select((b,c)=>new{b,c}).First(b=>b.b<b.c+1).c;}catch{return a.Length;}}

Indented:

a =>
{
    try
    {
        return a.OrderBy(b => -b).Select((b, c) => new { b, c }).First(b => b.b < b.c + 1);
    }
    catch
    {
        return a.Length;
    }
}

Answer 30

Scala, 62

def h(a:Int*)=Range(a.size,-1,-1).find(b=>a.count(b<=)>=b).get

Answer 31

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;
    }
}

Answer 32

MATL, 8 7 bytes (non-competing)

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

Answer 33

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.

Answer 34

Octave, 41 bytes

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

This is an anonymous function.

Try it at Ideone.