Al menos h con al menos h

42

Entrada

Una lista de enteros no negativos.

Salida

El número entero no negativo más grande, de hmodo que al menos uno hde los números de la lista sea mayor o igual que h.

Casos de prueba

[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

Reglas

Puede escribir un programa completo o una función, y también se permiten funciones anónimas. Este es el código de golf, por lo que gana la menor cantidad de bytes. Las lagunas estándar no están permitidas.

Fondo

El índice h es una noción utilizada en la academia que tiene como objetivo capturar el impacto y la productividad de un investigador. Según Wikipedia, un investigador tiene el índice h , si él o ella ha publicado h artículos científicos, cada uno de los cuales ha sido citado en otros artículos al menos h veces. Por lo tanto, este desafío se trata de calcular el índice h a partir de una lista de recuentos de citas.


Actualizar

¡Guau, excelentes respuestas en general! He aceptado el más corto, pero si a alguien más se le ocurre uno más corto, actualizaré mi elección en consecuencia.

Ganadores por idioma

Aquí hay una tabla de ganadores por idioma que también intentaré mantener actualizada. He incluido todas las publicaciones con puntaje no negativo. Corríjame si he cometido un error aquí.

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

Respuestas:

7

APL 7

+/⊢≥⍋∘⍒

Se puede probar en línea en 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
fuente
11

Python, 52

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

Una solución recursiva. Ejecute esto en Stackless Python si le preocupan los desbordamientos.

A partir de n=0, comprueba si al menos n+1los números son al menos n+1. Si es así, aumenta ny comienza de nuevo. Si no, salidas n.

El condicional se realiza utilizando el cortocircuito de Python para booleanos. La expresión sum(n<x for x in s)cuenta el número de valores sque son mayores que nal agregar el indicador Booleanos, que se tratan como 0o 1.

A modo de comparación, el equivalente iterativo es 2 caracteres más largo. Requiere Python 2.

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

Desafortunadamente, la entrada debe guardarse para una variable antes de repetirse o, de lo contrario, Python intentará leer la entrada repetidamente.

xnor
fuente
11

Pyth, 13 10 bytes

tf<l-QUTT1

Ingrese en una forma como [22,33,1,2,4]en STDIN.

Pruébalo aquí

Cómo funciona:

-QUTes todos los números en la entrada ( Q) al menos tan grande como el ser número marcada, T.

<l-QUTTes cierto si la longitud de esa lista es menor que T.

f<l-QUTT1encuentra el primer entero que devuelve verdadero para la verificación interna, comenzando en 1y subiendo.

tf<l-QUTT1 disminuye eso por uno, dando el mayor valor para el cual la condición es falsa, que es el índice h.

Comenzar en 1 asegura que 0se devuelve cuando la prueba siempre es verdadera, como en el primer caso de prueba.

isaacg
fuente
11

Pitón 2, 49

La entrada debe escribirse en el mismo formato que los ejemplos.

i=0
for z in sorted(input())[::-1]:i+=z>i
print i
Feersum
fuente
3
¡Qué algoritmo tan asombroso!
orgulloso Haskeller
8

CJam, 15 bytes

Traducción directa de mi solución Perl.

l~{~}${W):W>},,
nutki
fuente
44
l~$W%{W):W>},,- 14 bytes
Optimizador
@Optimizer Gracias, esperaba que hubiera una forma corta de invertir una tabla. Sin embargo, me sorprende que no haya acceso al recuento de iteraciones en los mapas. De todos modos, si 1 byte es todo lo que puedes tomar, eso no está mal para mi primer código CJam.
nutki
Ahora hay algunas soluciones de 12 bytes: {$W%ee::<1b}( eese agregó el 17/04/2015) y {$W%_,,.>1b}( .se agregó el 21/02/2015).
Peter Taylor
6

J ( 13 12)

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

Bastante similar a la solución de randomra. Demostración:

   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
fuente
Usar en #\<:lugar de i.@#<guardar un personaje.
algorithmshark
5

Mathematica, 44 42 40 38 bytes

Función anónima:

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

Ejecútelo agregando la entrada al final de la siguiente manera:

In: LengthWhile[i=0;SortBy[#,-#&],#>i++&]&@{1,2,3,4,5,6,7}
Out: 4
kukac67
fuente
@ MartinBüttner Tienes razón, puedo usar #>i++. Probé algunos casos más. (¡Y gracias por todas las sugerencias!)
kukac67
4

SQL, 81 94 83

Dada una tabla (I) de valores (V), la siguiente consulta devolverá h. Probado en PostgreSQL y también funcionará en SQL Server. Editar Haga que devuelva 0 en lugar de NULL. Mejoró con un COUNT, gracias @nutki

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

Ejemplo de SQLFiddle

Esencialmente numera las filas en un tipo descendente de los valores. Luego devuelve el número máximo de fila donde el número de fila es mayor que igual al valor.

MickyT
fuente
Puede usar en COUNT(R)lugar de COALESCE(MAX(R),0)una solución más corta para el problema NULL.
nutki
@nutki, por supuesto ... Gracias
MickyT
4

R, 39 35 29

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

Dado un vector de enteros en i y usando la lógica de una ordenación inversa, devuelve la longitud del vector donde el número de elemento es menor que s. Gracias a @plannapus por el buen consejo.

> 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
fuente
¡Agradable! Incluso puede acortar a 29 sumando directamente el vector lógico:s=sort(i);sum(s>=length(s):1)
plannapus
3

CJam, 23 bytes

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

Esto toma la lista como una matriz en STDIN, como

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

Pruébalo aquí.

Puede usar esto para ejecutar todos los casos de prueba:

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

Explicación

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 lógica es un poco al revés, pero ahorró un par de bytes. Básicamente, el bloque pasado para ordenar retornos 0para candidatos válidos y de 1otra manera. Por lo tanto, los candidatos válidos son los primeros en la matriz ordenada. Y debido a que el ordenamiento es estable, y comenzamos con una lista desde N hasta 1, esto devolverá la h válida más grande.

Martin Ender
fuente
3

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

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

Toma entrada separada por espacios en STDIN:

perl hidx.pl <<<'1 2 3 4 5 6 7'
nutki
fuente
1
sort{$b-$a}ahorra 2 más
mafia
3

Pitón (63)

Básicamente un puerto directo de mi solución J. Obviamente, mucho más tiempo, como uno podría imaginar.

lambda x:sum(a>b for a,b in zip(sorted(x)[::-1],range(len(x))))
ɐɔıʇǝɥʇuʎs
fuente
Puede guardar algunos caracteres utilizando enumerate.
xnor
3

Haskell, 40

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

esto busca el primer número que no se ajusta al esquema y devuelve su predecesor.

orgulloso Haskeller
fuente
39 bytes con until: ¡ Pruébelo en línea!
Laikoni
3

Rubí 44 41

Recursiva, más o menos la misma estrategia que la solución Python de xnor:

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

Rubí 52

No recursivo:

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

Las funciones lambda / anónimas "Stabby" requieren Ruby 1.9 o posterior. Llamar con egf[[22,33,1,2,4]]

daniero
fuente
3

Bash + coreutils, 29

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

Entrada tomada de stdin como una lista separada por nueva línea.

  • sort los enteros en orden descendente
  • nl prefija cada línea con su número de línea basado en 1, separando el número de línea y el resto de la línea con un valor mayor que >
  • Evalúe aritméticamente cada línea con bc. Los enteros menores que su número de línea dan como resultado 0. De lo contrario, 1.
  • grepcuenta el número de 0s, es decir, el número de enteros mayor o igual queh

Ejemplo

$ 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 digital
fuente
2

JavaScript (ES6) 48

Solución recursiva.

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

Prueba en la consola 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)))

Salida

[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
fuente
47 bytes: f=(l,h=0)=>l.map(v=>x+=v>h,x=0)&&x>h?f(l,h+1):h. Sin embargo, su solución también sería de 47 bytes si solo cambia el h=-1a h=0.
vrugtehagel
2

Java 8, 116 bytes.

Clase completa:

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

Función:

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;}}
El numero uno
fuente
2

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

Muy bien, ¡aquí está uno de los peores códigos que he escrito! :)

#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;}
usuario9587
fuente
2

Jalea, 6 bytes

NỤỤ<’S

Explicación:

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

CJam, 22 bytes

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

Toma la lista como entrada:

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

Salida:

20

Pruébalo aquí

Optimizador
fuente
1

GolfScript, 13 bytes

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

Prueba este código en línea. 1

Toma la entrada como una matriz en la pila. Utiliza el mismo algoritmo que la solución Python de feersum , iterando sobre los números en la matriz e incrementando un contador desde 0 hasta que iguala o excede el elemento actual de la matriz.

1) El servidor de GolfScript en línea parece estar experimentando tiempos de espera aleatorios nuevamente. Si el programa se agota, intente volver a ejecutarlo.

Ilmari Karonen
fuente
1

TI-BASIC, 22 bytes

Representación ASCII:

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

Volcado hexadecimal:

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

Obtiene una lista como entrada. A partir de Ans = 0, verifica si al menos Ans + 1 de los números son al menos Ans + 1. Si es así, incrementa Ans y repite nuevamente. Si no, genera la respuesta

Timtech
fuente
1

JAGL Alpha 1.2 - 14

No cuenta porque la funcionalidad de matriz inversa 'C' se agregó después de la pregunta, pero de todos modos estoy respondiendo por diversión.

Asume que la matriz es el primer elemento de la pila y coloca la respuesta en la parte superior de la pila.

0SJC{Sd@>+1}/S

Para imprimir, solo agregue P al final, agregando un byte.

Explicación:

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

J, 15 11 caracteres

(La solución J más corta actual).

   [:+/#\<:\:~

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

Compara elementos de <:lista ordenados \:~con 1..n + 1 #\y cuenta comparaciones verdaderas +/.

Prueba de similitud con otra solución J en 100 casos de prueba aleatorios:

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

Reng v.3.2, 43 bytes

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

Pruébalo aquí! Este código se puede dividir en tres partes: inicial, computacional y final.

Inicial

1#xk#yaïí'1ø

Este tiendas 1a x, la longitud de la pila de entrada ka y, y obtiene toda la entrada ( aïí) que se clasifica entonces ( ').va a la siguiente línea, es decir, la siguiente parte.

Computacional

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

Reng no tiene incorporado la desigualdad. Por lo tanto, se debe implementar un algoritmo. El algoritmo más corto que encontré para a < bes %:1,%1e; esto se ve así:

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)

Estoy seguro de que eso lo aclaró! Déjame explicarte más. x % 1, es decir, módulo con 1, se asigna xa (-1,1). Sabemos que (a/b) % 1es a/bcuando a < b. Por lo tanto, esta expresión es igual a a < b.

Sin embargo, esto no funciona tan bien debido a problemas con el módulo con cero. Entonces, incrementamos cada miembro de la pila y el contador inicialmente.

Después de obtener la desigualdad booleana en la pila, la x+agrega a x, pero la deja en la pila por el momento. y1-decrementos y, y ?^sube iff y == 0y procedemos a la fase final. De lo contrario, ponemos y-1dentro yy lo nuevo xdentro x.

Final

             ~n-1$\

Esto extrae el residuo y-1de la pila, disminuye el resultado, lo genera y finaliza el programa.

Conor O'Brien
fuente
1

05AB1E , 5 bytes

{Rā@O

Pruébalo en línea! o como un conjunto de pruebas

Explicación

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

Mathematica, 57 bytes

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

Esta es una función anónima que toma una lista y devuelve un entero, como

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

Use esto para verificar todos los casos de prueba:

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

C #, 103

Función anónima.

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

Sangrado:

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

Scala, 62

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