Au moins h avec au moins h

42

Contribution

Une liste d'entiers non négatifs.

Sortie

Le plus grand entier non négatif htel qu'au moins hl'un des nombres de la liste soit supérieur ou égal à h.

Cas de test

[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

Règles

Vous pouvez écrire un programme complet ou une fonction. Les fonctions anonymes sont également autorisées. C'est le code-golf, donc le plus petit nombre d'octets gagne. Les failles standard sont interdites.

Contexte

L' indice h est une notion utilisée dans le monde universitaire qui vise à capturer l'impact et la productivité d'un chercheur. Selon Wikipedia, un chercheur a l'indice h , s'il a publié h articles scientifiques, chacun d'eux ayant été cité dans d'autres articles au moins h fois. Ce défi consiste donc à calculer l'indice h à partir d'une liste de comptes de citations.


Mise à jour

Wow, bonnes réponses tout autour! J'ai accepté le plus court, mais si quelqu'un d'autre en propose un encore plus court, je modifierai mon choix en conséquence.

Gagnants par langue

Voici un tableau des gagnants par langue que je vais également essayer de tenir à jour. J'ai inclus tous les messages avec un score non négatif. S'il vous plaît, corrigez-moi si j'ai commis une erreur ici.

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

Réponses:

7

APL 7

+/⊢≥⍋∘⍒

Peut être essayé en ligne sur 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
Moris Zucca
la source
11

Python, 52

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

Une solution récursive. Exécutez ceci en Stackless Python si vous craignez des débordements.

À partir de n=0, vérifie si au moins n+1les nombres sont au moins n+1. Si c'est le cas, incrémente net recommence. Sinon, les sorties n.

Le conditionnel est effectué à l'aide du court-circuitage de Booléens de Python. L'expression sum(n<x for x in s)compte le nombre de valeurs ssupérieures à celle najoutée en ajoutant l'indicateur Booleans, qui sont traités comme 0ou 1.

À titre de comparaison, l'équivalent itératif est 2 caractères plus longs. Cela nécessite Python 2.

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

Malheureusement, l'entrée doit être enregistrée pour une variable avant d'être itérée, sinon Python essaiera de lire l'entrée plusieurs fois.

Xnor
la source
11

Pyth, 13 à 10 octets

tf<l-QUTT1

Entrez sous une forme telle que [22,33,1,2,4]sur STDIN.

Essayez ici.

Comment ça marche:

-QUTest l' ensemble des nombres dans l'entrée ( Q) au moins aussi grand que le nombre étant cochée, T.

<l-QUTTest vrai si la longueur de cette liste est inférieure à T.

f<l-QUTT1trouve le premier entier qui retourne vrai pour le contrôle interne, en commençant à 1et en remontant.

tf<l-QUTT1 décrémente cela de un, en donnant la plus grande valeur pour laquelle la condition est fausse, qui est l'indice h.

Commencer à 1 garantit que cette valeur 0est renvoyée lorsque le test est toujours vrai, comme dans le premier cas de test.

isaacg
la source
11

Python 2, 49

Les entrées doivent être saisies dans le même format que les exemples.

i=0
for z in sorted(input())[::-1]:i+=z>i
print i
feersum
la source
3
Quel algorithme incroyable!
fier haskeller
8

CJam, 15 octets

Traduction directe de ma solution Perl.

l~{~}${W):W>},,
nutki
la source
4
l~$W%{W):W>},,- 14 octets
Optimiseur
@Optimizer Merci, je m'attendais à ce qu'il y ait un court moyen d'inverser une table. Je suis surpris cependant qu'il n'y ait pas d'accès au nombre d'itérations dans les cartes. Quoi qu'il en soit, si 1 octet est tout ce que vous pouvez prendre, ce n'est pas mauvais pour mon premier code CJam.
nutki
Il existe actuellement des solutions à 12 octets: {$W%ee::<1b}( eeajouté le 2015-04-17) et {$W%_,,.>1b}( .ajouté le 2015-02-21).
Peter Taylor
6

J ( 13 12)

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

Assez similaire à la solution de randomra. Manifestation:

   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
ıʇǝɥʇuʎs
la source
Utiliser #\<:au lieu de i.@#<enregistre un personnage.
algorithmshark
5

Mathematica, 44 42 40 38 octets

Fonction anonyme:

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

Exécutez-le en ajoutant l'entrée à la fin, comme suit:

In: LengthWhile[i=0;SortBy[#,-#&],#>i++&]&@{1,2,3,4,5,6,7}
Out: 4
kukac67
la source
@ MartinBüttner Vous avez raison, je peux utiliser #>i++. J'ai testé d'autres cas. (Et merci pour toutes les suggestions!)
kukac67
4

SQL, 81 94 83

Étant donné une table (I) de valeurs (V), la requête suivante renverra h. Testé dans PostgreSQL et fonctionnera également dans SQL Server. Modifier Faites-le retourner 0 plutôt que NULL. Fait mieux avec COUNT, merci @nutki

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

Exemple SQLFiddle

Essentiellement, il numérote les lignes sur un tri décroissant des valeurs. Ensuite, il renvoie le nombre maximal de lignes où le nombre de lignes est supérieur à égal à la valeur.

MickyT
la source
Vous pouvez utiliser COUNT(R)au lieu de COALESCE(MAX(R),0)pour un correctif plus court pour le problème NULL.
nutki
@nutki bien sûr ... Merci
MickyT
4

R, 39 35 29

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

Étant donné un vecteur d'entiers dans i et en utilisant la logique d'un tri inversé, nous renvoyons alors la longueur du vecteur où le nombre d'éléments est inférieur à s. Merci à @plannapus pour le bon conseil.

> 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
MickyT
la source
Agréable! Vous pouvez même raccourcir à 29 en additionnant directement le vecteur logique:s=sort(i);sum(s>=length(s):1)
plannapus
3

CJam, 23 octets

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

Cela prend la liste comme un tableau sur STDIN, comme

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

Testez-le ici.

Vous pouvez l'utiliser pour exécuter tous les cas de test:

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

Explication

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

La logique est un peu en arrière, mais cela a sauvé quelques octets. En gros, le blocage passé pour trier les déclarations 0des candidats valides et 1autres. Les candidats valides arrivent donc en premier dans le tableau trié. Et comme le tri est stable, et que nous commençons par une liste allant de N à 1, le plus grand h valide est renvoyé.

Martin Ender
la source
3

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

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

Prend une entrée séparée par des espaces sur STDIN:

perl hidx.pl <<<'1 2 3 4 5 6 7'
nutki
la source
1
sort{$b-$a}sauve 2 autres
mob
3

Python (63)

Fondamentalement, un port direct de ma solution J. Évidemment, beaucoup plus longtemps, comme on pourrait l'imaginer.

lambda x:sum(a>b for a,b in zip(sorted(x)[::-1],range(len(x))))
ıʇǝɥʇuʎs
la source
Vous pouvez enregistrer des caractères en utilisant enumerate.
xnor
3

Haskell, 40 ans

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

ceci recherche le premier nombre qui ne correspond pas au schéma et renvoie son prédécesseur.

fier haskeller
la source
39 octets avec until: Essayez-le en ligne!
Laikoni
3

Ruby 44 41

Récursive, plus ou moins la même stratégie que la solution Python de xnor:

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

Ruby 52

Non récursif:

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

Fonctions "Stabby" lambda / anonymous, requièrent Ruby 1.9 ou plus récent. Appel avec par exemplef[[22,33,1,2,4]]

Daniero
la source
3

Bash + coreutils, 29

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

Entrée extraite de stdin sous forme de liste séparée par des lignes.

  • sort les entiers par ordre décroissant
  • nl préfixe chaque ligne avec son numéro de ligne basé sur 1, séparant le numéro de ligne et le reste de la ligne avec un nombre supérieur à >
  • Évaluez arithmétiquement chaque ligne avec bc. Les entiers inférieurs à leur numéro de ligne donnent 0. Sinon, 1.
  • grepcompte le nombre de 0s, c'est-à-dire le nombre entier supérieur ou égal àh

Exemple

$ 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
$ 
Trauma numérique
la source
2

JavaScript (ES6) 48

Solution récursive

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

Test dans la console 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)))

Sortie

[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
edc65
la source
47 octets: f=(l,h=0)=>l.map(v=>x+=v>h,x=0)&&x>h?f(l,h+1):h. Cependant, votre solution consisterait également en 47 octets si vous ne modifiiez que h=-1par h=0.
vrugtehagel
2

Java 8, 116 octets.

Classe complète:

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

Une fonction:

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;}}
Le numéro un
la source
2

C ++ 815 219 à partir de (wc -c main.cpp)

Voici le pire code que j'ai jamais écrit! :)

#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;}
utilisateur9587
la source
2

Gelée, 6 octets

NỤỤ<’S

Explication:

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
Ven
la source
1

CJam, 22 octets

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

Prend la liste en entrée:

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

Sortie:

20

Essayez ici

Optimiseur
la source
1

GolfScript, 13 octets

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

Testez ce code en ligne. 1

Prend les entrées sous forme de tableau sur la pile. Utilise le même algorithme que la solution Python de Feersum, effectuant une itération sur les nombres du tableau et en incrémentant un compteur de 0 jusqu'à ce qu'il soit égal ou supérieur à l'élément actuel du tableau.

1) Le serveur GolfScript en ligne semble connaître à nouveau des délais d'attente aléatoires. Si le programme expire pour vous, essayez de le réexécuter.

Ilmari Karonen
la source
1

TI-BASIC, 22 octets

Représentation ASCII:

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

Décharge Hex:

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

Obtient une liste en entrée. À partir de Ans = 0, vérifie si au moins Ans + 1 des nombres sont au moins Ans + 1. Si tel est le cas, incrémente Ans et boucle à nouveau. Sinon, sort Ans.

Timtech
la source
1

JAGL Alpha 1.2 - 14

Ne compte pas car la fonctionnalité de tableau inversé 'C' a été ajoutée après la question, mais je réponds quand même pour le plaisir.

Suppose que le tableau est le premier élément de la pile et place la réponse en haut de la pile.

0SJC{Sd@>+1}/S

Pour imprimer, ajoutez simplement Pà la fin, en ajoutant un octet.

Explication:

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
Globby
la source
1

J, 15 11 caractères

(La solution J la plus courte actuelle.)

   [:+/#\<:\:~

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

Compare les éléments de la <:liste triée \:~avec 1..n + 1 #\et compte les vraies comparaisons +/.

Test de similarité avec une autre solution J sur 100 tests aléatoires:

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

Reng v.3.2, 43 octets

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

Essayez-le ici! Ce code peut être divisé en trois parties: initiale, informatique et finale.

Initiale

1#xk#yaïí'1ø

Ceci stocke 1dans x, la longueur de la pile d’entrée kdans y, et obtient tout input ( aïí) qui est ensuite trié (' ).passe à la ligne suivante, c'est-à-dire la partie suivante.

Informatique

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

Reng n'a pas intégré dans l'inégalité. Ainsi, un algorithme doit être implémenté. L'algorithme le plus court pour lequel j'ai trouvé a < best %:1,%1e; cela ressemble à ceci:

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)

Je suis sûr que ça a éclairci! Permettez-moi d'expliquer plus loin. x % 1, module avec 1, correspond xà (-1,1). Nous savons que (a/b) % 1c'est a/bquand a < b. Ainsi, cette expression est égale à a < b.

Cependant, cela ne fonctionne pas aussi bien à cause de problèmes de module avec zéro. Donc, nous incrémentons chaque membre de la pile et le compteur initialement.

Après avoir obtenu l'inégalité booléenne sur la pile, l' x+ajoute à x, mais la laisse sur la pile pour le moment. y1-décroît yet ?^monte si y == 0et nous passons à la phase finale. Sinon, nous mettonsy-1 dans yet le nouveau xdans x.

Final

             ~n-1$\

Ceci y-1extrait le résidu de la pile, décrémente le résultat, le sort et termine le programme.

Conor O'Brien
la source
0

Mathematica, 57 octets

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

C'est une fonction anonyme prenant une liste et retournant un entier, comme

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

Utilisez ceci pour vérifier tous les cas de test:

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}
}
Martin Ender
la source
0

C #, 103

Fonction anonyme.

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

Dentelé:

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

Scala, 62

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