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

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

CJam, 15 bytes

Direct translation of my Perl solution.

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

Answer 5

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

Japt, 4 bytes

ñÍè>

Try it here

ñÍè>     :Implicit input of array
ñ        :Sort by
 Í       :  Subtracting from 2
  è      :Count the elements that are
   >     :  Greater than their 0-based indices

Answer 11

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 12

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 13

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 14

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 15

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 16

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 17

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 18

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 19

APL, 12 characters

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

Answer 20

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 21

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 22

Haskell, 72 59 bytes

My C++ solution looked pretty verbose, and the recursive nature made me think of Haskell, so here's my attempt:

a!i|i<foldr(\x s->s+fromEnum(i<x))0 a=a!(i+1)|1<2=i
H a=a!0

Explanation:

foldr (\x s -> s + fromEnum(i < x)) 0 a

I'm sure there's a shorter way to do this, because I'm pretty new to haskell, but basically it counts how many elements of a are less than x.

If this is greater than i, we can check i+1, otherwise, return i.

And the H function is so that we don't need to pass in 0 to h. It adds 10 8 bytes, so I'm pretty sure there's a better way.

-13 bytes thanks to ovs

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

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

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 28

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 29

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 30

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