42
\$\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
\$\endgroup\$

34 Answers 34

7
\$\begingroup\$

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
\$\endgroup\$
11
\$\begingroup\$

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.

\$\endgroup\$
11
\$\begingroup\$

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.

\$\endgroup\$
11
\$\begingroup\$

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
\$\endgroup\$
  • 3
    \$\begingroup\$ What an amazing algorithm! \$\endgroup\$ – proud haskeller Dec 22 '14 at 23:59
8
\$\begingroup\$

CJam, 15 bytes

Direct translation of my Perl solution.

l~{~}${W):W>},,
\$\endgroup\$
  • 4
    \$\begingroup\$ l~$W%{W):W>},, - 14 bytes \$\endgroup\$ – Optimizer Dec 22 '14 at 14:23
  • \$\begingroup\$ @Optimizer Thanks, I expected there should be a short way of reversing a table. I am surprised though that there is no access to iteration count in maps. Anyway if 1 byte is all you can take that is not bad for my first CJam code. \$\endgroup\$ – nutki Dec 23 '14 at 9:29
  • \$\begingroup\$ There's are some 12-byte solutions now: {$W%ee::<1b} (ee was added 2015-04-17) and {$W%_,,.>1b} (. was added 2015-02-21). \$\endgroup\$ – Peter Taylor Jul 5 '16 at 16:04
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Using #\<: instead of i.@#< saves a character. \$\endgroup\$ – algorithmshark Dec 22 '14 at 18:57
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @MartinBüttner You're right, I can use #>i++. I tested some more cases. (And thanks for all the suggestions!) \$\endgroup\$ – kukac67 Dec 23 '14 at 17:45
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can use COUNT(R) instead of COALESCE(MAX(R),0) for a shorter fix for the NULL problem. \$\endgroup\$ – nutki Dec 23 '14 at 9:26
  • \$\begingroup\$ @nutki of course ... Thank you \$\endgroup\$ – MickyT Dec 23 '14 at 9:46
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Nice! You can even shorten to 29 by directly summing the logical vector: s=sort(i);sum(s>=length(s):1) \$\endgroup\$ – plannapus Dec 25 '14 at 8:54
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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'
\$\endgroup\$
  • 1
    \$\begingroup\$ sort{$b-$a} saves 2 more \$\endgroup\$ – mob Dec 25 '14 at 23:59
3
\$\begingroup\$

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))))
\$\endgroup\$
  • \$\begingroup\$ You can save some chars by using enumerate. \$\endgroup\$ – xnor Dec 23 '14 at 2:52
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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
$ 
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 47 bytes: f=(l,h=0)=>l.map(v=>x+=v>h,x=0)&&x>h?f(l,h+1):h. However, your solution would be 47 bytes too if you just change the h=-1 to h=0. \$\endgroup\$ – vrugtehagel May 9 at 11:22
2
\$\begingroup\$

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;}}
\$\endgroup\$
2
\$\begingroup\$

APL, 12 characters

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

\$\endgroup\$
2
\$\begingroup\$

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;}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

GolfScript, 13 bytes

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

Test this code online.1

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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 ('). 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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\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}
}
\$\endgroup\$
0
\$\begingroup\$

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;
    }
}
\$\endgroup\$
0
\$\begingroup\$

Scala, 62

def h(a:Int*)=Range(a.size,-1,-1).find(b=>a.count(b<=)>=b).get
\$\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.