Wejście

Lista nieujemnych liczb całkowitych.

Wynik

Największa nieujemna liczba całkowita, htaka, że ​​co najmniej hliczby na liście są większe lub równe h.

Przypadki testowe

[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

Zasady

Możesz napisać pełny program lub funkcję, dozwolone są również funkcje anonimowe. To jest golf golfowy, więc wygrywa najmniej bajtów. Standardowe luki są niedozwolone.

tło

H-indeks to pojęcie używane w środowisku akademickim, który ma na celu uchwycenie wpływu i produktywność badacza. Według Wikipedii badacz ma indeks h , jeśli opublikował h artykułów naukowych, z których każdy był cytowany w innych artykułach co najmniej h razy. Tak więc wyzwanie polega na obliczeniu indeksu h na podstawie liczby cytowań.

Aktualizacja

Wow, świetne odpowiedzi dookoła! Zaakceptowałem najkrótszy, ale jeśli ktoś inny wymyśli jeszcze krótszy, odpowiednio zaktualizuję mój wybór.

Zwycięzcy według języka

Oto tabela zwycięzców według języka, którą również postaram się aktualizować. Dołączyłem wszystkie posty z nieujemnym wynikiem. Popraw mnie, jeśli popełniłem tutaj błąd.

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

APL 7

+/⊢≥⍋∘⍒

Można wypróbować online na 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

Python, 52

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

Rozwiązanie rekurencyjne. Uruchom to w Python bez stosu, jeśli martwisz się przepełnieniami.

Począwszy od n=0, sprawdza, czy co najmniej n+1liczby są co najmniej n+1. Jeśli tak, zwiększa ni zaczyna od nowa. Jeśli nie, wyjścia n.

Warunek jest wykonywany przy użyciu zwarcia Pythona dla booleanów. Wyrażenie sum(n<x for x in s)liczy liczbę wartości, sktóre są większe niż nprzez dodanie wskaźnika booleanów, które są traktowane jako 0lub 1.

Dla porównania, iteracyjny ekwiwalent jest dłuższy o 2 znaki. Wymaga Python 2.

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

Niestety dane wejściowe należy zapisać dla zmiennej przed iteracją, w przeciwnym razie Python spróbuje wielokrotnie odczytać dane wejściowe.

Pyth, 13 10 bajtów

tf<l-QUTT1

Wprowadź dane w formie takiej jak [22,33,1,2,4]na STDIN.

Wypróbuj tutaj.

Jak to działa:

-QUTto wszystkie numery na wejściu ( Q) co najmniej tak duża jak liczba istota zaznaczone T.

<l-QUTTjest prawdziwe, jeśli długość tej listy jest mniejsza niż T.

f<l-QUTT1znajduje pierwszą liczbę całkowitą, która zwraca wartość true dla kontroli wewnętrznej, zaczynając od 1i idąc w górę.

tf<l-QUTT1 zmniejsza to o jeden, dając największą wartość, dla której warunek jest fałszywy, czyli indeks h.

Począwszy od 1 zapewnia, że 0jest zwracany, gdy test jest zawsze prawdziwy, na przykład w pierwszym przypadku testowym.

Python 2, 49

Dane wejściowe należy wpisać w tym samym formacie co przykłady.

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

CJam, 15 bajtów

Bezpośrednie tłumaczenie mojego rozwiązania Perla.

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

J ( 13 12)

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

Całkiem podobne do rozwiązania randomry. Demonstracja:

   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

Mathematica, 44 42 40 38 bajtów

Funkcja anonimowa:

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

Uruchom go, przypinając dane wejściowe do końca w następujący sposób:

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

SQL, 81 94 83

Biorąc pod uwagę tabelę (I) wartości (V), następujące zapytanie zwróci h. Testowany w PostgreSQL i działa również w SQL Server. Edycja Powoduje, że zwraca 0 zamiast NULL. Udoskonalono z COUNT, dzięki @nutki

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

Przykład SQLFiddle

Zasadniczo numeruje wiersze według malejącego rodzaju wartości. Następnie zwraca maksymalną liczbę wierszy, gdzie liczba wierszy jest większa niż wartość.

R, 39 35 29

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

Biorąc pod uwagę wektor liczb całkowitych w i i stosując logikę odwrotnego sortowania, zwracamy długość wektora, w którym liczba elementów jest mniejsza niż s. Dzięki @plannapus za miłą wskazówkę.

> 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

CJam, 23 bajty

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

To bierze listę jako tablicę na STDIN, na przykład

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

Sprawdź to tutaj.

Możesz użyć tego do uruchomienia wszystkich przypadków testowych:

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

Wyjaśnienie

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.";

Logika jest nieco wstecz, ale pozwoliła zaoszczędzić kilka bajtów. Zasadniczo, blok przekazany w celu sortowania zwrotów 0dla ważnych kandydatów i 1nie tylko. Tak więc poprawni kandydaci zajmują pierwsze miejsce w posortowanej tablicy. A ponieważ sortowanie jest stabilne i zaczynamy od listy od N do 1, zwróci to największą prawidłową liczbę h.

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

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

Zajmuje wejście oddzielone spacją w STDIN:

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

Python (63)

Zasadniczo bezpośredni port mojego rozwiązania J. Oczywiście o wiele dłużej, jak można sobie wyobrazić.

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

Haskell, 40

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

wyszukuje pierwszą liczbę, która nie pasuje do schematu i zwraca jej poprzednika.

Ruby 44 41

Rekurencyjna, mniej więcej taka sama strategia jak rozwiązanie Python xnor:

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

Ruby 52

Brak rekurencji:

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

„Stabby” funkcje lambda / anonimowe, wymagają Ruby 1.9 lub nowszego. Zadzwoń npf[[22,33,1,2,4]]

Bash + coreutils, 29

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

Dane wejściowe pobrane ze stdin jako lista rozdzielona znakiem nowej linii.

• sort liczby całkowite w porządku malejącym
• nl poprzedza każdą linię numerem linii opartym na 1, oddzielając numer linii i resztę linii cyfrą większą niż >
• Oceniaj arytmetycznie każdą linię za pomocą bc. Liczby całkowite mniejsze niż numer linii dają wynik 0. W przeciwnym razie 1.
• grepzlicza liczbę 0s, tj. liczbę całkowitą większą lub równąh

Przykład

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

JavaScript (ES6) 48

Rozwiązanie rekurencyjne.

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

Przetestuj w konsoli FireFox / FireBug

;[
  [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)))

Wynik

[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

Java 8, 116 bajtów.

Pełna klasa:

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

Funkcjonować:

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

APL, 12 znaków

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

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

Dobra, oto najgorszy kod, jaki kiedykolwiek napisałem! :)

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

Galaretka, 6 bajtów

NỤỤ<’S

Wyjaśnienie:

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

CJam, 22 bajty

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

Pobiera listę jako dane wejściowe:

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

Wynik:

20

Wypróbuj tutaj

GolfScript, 13 bajtów

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

Przetestuj ten kod online. ¹

Pobiera dane wejściowe jako tablicę na stosie. Używa tego samego algorytmu, co rozwiązanie Fehonum w języku Python , iterując po liczbach w tablicy i zwiększając licznik od 0, aż zrówna się lub przekroczy bieżący element tablicy.

^{1) Wydaje się, że online serwer GolfScript ponownie doświadcza przypadkowych przekroczeń czasu. Jeśli program przekroczy limit czasu, spróbuj ponownie go uruchomić.}

TI-BASIC, 22 bajty

Reprezentacja ASCII:

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

Zrzut szesnastkowy:

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

Pobiera listę jako dane wejściowe. Począwszy od Ans = 0, sprawdza, czy przynajmniej Ans + 1 z liczb to przynajmniej Ans + 1. Jeśli tak, zwiększa Ans i zapętla ponownie. Jeśli nie, wyświetla odpowiedź Ans.

JAGL Alpha 1.2 - 14

Nie liczy się, ponieważ po pytaniu dodano funkcję odwrotnej tablicy „C”, ale i tak odpowiadam dla zabawy.

Zakłada, że ​​tablica jest pierwszym elementem na stosie i umieszcza odpowiedź na górze stosu.

0SJC{Sd@>+1}/S

Aby wydrukować, po prostu dodaj Pna końcu, dodając bajt.

Wyjaśnienie:

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

J, 15 11 znaków

(Obecne najkrótsze rozwiązanie J.)

   [:+/#\<:\:~

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

Porównuje <:posortowane \:~elementy listy z 1..n + 1 #\i liczy prawdziwe porównania +/.

Testowanie podobieństwa do innych rozwiązań J na 100 losowych przypadkach testowych:

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

Reng v.3.2, 43 bajty

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

Wypróbuj tutaj! Ten kod można podzielić na trzy części: początkową, obliczeniową i końcową.

Inicjał

1#xk#yaïí'1ø

Zapisuje 1na xdługość stosu wejścia kdo yi pobiera wszystkie dane wejściowe ( aïí), które są następnie sortowane ( '). 1øprzechodzi do następnej linii, tj. następnej części.

Obliczeniowe

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

Reng nie ma wbudowanej nierówności. Dlatego należy zaimplementować algorytm. Najkrótszym algorytmem, jaki znalazłem, a < bjest %:1,%1e; wygląda to tak:

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)

Jestem pewien, że to wyjaśniło! Pozwól mi wyjaśnić dalej. x % 1, tj. moduł z 1, odwzorowuje xna (-1,1). Wiemy, że (a/b) % 1właśnie a/bwtedy a < b. Zatem to wyrażenie jest równe a < b.

Nie działa to jednak tak dobrze z powodu problemów z modułem zerowym. Tak więc początkowo zwiększamy każdego członka stosu i licznika.

Po uzyskaniu logicznej nierówności na stosie x+dodaje ją do x, ale chwilowo pozostawia na stosie. y1-zmniejsza się yi ?^idzie w górę iff y == 0i przechodzimy do ostatniej fazy. W przeciwnym razie, kładziemy y-1się yi nowa xw x.

Finał

             ~n-1$\

To usuwa resztki y-1ze stosu, zmniejsza wynik, wysyła je i kończy program.

05AB1E , 5 bajtów

{Rā@O

Wypróbuj online! lub jako pakiet testowy

Wyjaśnienie

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

Mathematica, 57 bajtów

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

Jest to anonimowa funkcja pobierająca listę i zwracająca liczbę całkowitą, na przykład

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

Użyj tego, aby sprawdzić wszystkie przypadki testowe:

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

C #, 103

Funkcja anonimowa.

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

Zębaty:

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

Scala, 62

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