Pelo menos h com pelo menos h

42

Entrada

Uma lista de números inteiros não negativos.

Saída

O maior número inteiro não negativo, de hmodo que pelo menos hos números da lista sejam maiores ou iguais a h.

Casos de teste

[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

Regras

Você pode escrever um programa completo ou uma função, e funções anônimas também são permitidas. Isso é código-golfe, então a menor contagem de bytes vence. As brechas padrão não são permitidas.

fundo

O índice h é uma noção usada na academia que visa capturar o impacto e a produtividade de um pesquisador. Segundo a Wikipedia, um pesquisador tem o índice h , se ele publicou h artigos científicos, cada um dos quais foi citado em outros artigos pelo menos h vezes. Portanto, esse desafio é sobre o cálculo do índice h a partir de uma lista de contagens de citações.


Atualizar

Uau, ótimas respostas o tempo todo! Aceitei a mais curta, mas se alguém vier com uma ainda mais curta, atualizarei minha escolha.

Vencedores por idioma

Aqui está uma tabela de vencedores por idioma que também tentarei manter atualizada. Incluí todas as postagens com pontuação não negativa. Corrija-me se cometi um erro aqui.

  • 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 de @ ɐɔıʇǝɥʇ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 de @MickyT
  • Ruby : 41 bytes por @daniero
  • Scala : 62 bytes por @ChadRetz
  • SQL : 83 bytes de @MickyT
  • TI-BASIC : 22 bytes de @Timtech
Zgarb
fonte

Respostas:

7

APL 7

+/⊢≥⍋∘⍒

Pode ser experimentado online em 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
fonte
11

Python, 52

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

Uma solução recursiva. Execute isso no Stackless Python se estiver preocupado com estouros.

A partir de n=0, verifica se pelo menos n+1os números são pelo menos n+1. Nesse caso, aumenta ne inicia novamente. Caso contrário, as saídas n.

A condicional é feita usando o curto-circuito do Python para booleanos. A expressão sum(n<x for x in s)conta o número de valores smaiores do que a nadição do indicador Booleans, que são tratados como 0ou 1.

Para comparação, o equivalente iterativo é 2 caracteres a mais. Requer Python 2.

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

Infelizmente, a entrada precisa ser salva para uma variável antes de ser iterada ou o Python tentará ler a entrada repetidamente.

xnor
fonte
11

Pitão, 13 10 bytes

tf<l-QUTT1

Insira um formulário como [22,33,1,2,4]no STDIN.

Experimente aqui.

Como funciona:

-QUTé todos os números na entrada ( Q) pelo menos tão grandes quanto o número que está sendo verificado T.

<l-QUTTé verdadeiro se o comprimento dessa lista for menor que T.

f<l-QUTT1localiza o primeiro número inteiro que retorna true para a verificação interna, iniciando 1e subindo.

tf<l-QUTT1 decrementa isso em um, fornecendo o maior valor para o qual a condição é falsa, que é o índice h.

A partir de 1 garante que 0seja retornado quando o teste for sempre verdadeiro, como no primeiro caso de teste.

isaacg
fonte
11

Python 2, 49

A entrada deve ser digitada no mesmo formato que os exemplos.

i=0
for z in sorted(input())[::-1]:i+=z>i
print i
feersum
fonte
3
Que algoritmo incrível!
proud haskeller
8

CJam, 15 bytes

Tradução direta da minha solução Perl.

l~{~}${W):W>},,
nutki
fonte
4
l~$W%{W):W>},,- 14 bytes
Otimizador
@ Optimizer Obrigado, eu esperava que houvesse uma maneira curta de reverter uma tabela. Surpreende-me, porém, que não haja acesso à contagem de iterações nos mapas. De qualquer forma, se apenas 1 byte é suficiente, isso não é ruim para meu primeiro código CJam.
nutki
Agora existem algumas soluções de 12 bytes: {$W%ee::<1b}( eefoi adicionado 17-04-2015) e {$W%_,,.>1b}( .foi adicionado 2015-02-21).
Peter Taylor
6

J ( 13 12)

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

Muito semelhante à solução da randomra. Demonstração:

   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
fonte
Usar em #\<:vez de i.@#<salva um personagem.
algorithmshark
5

Mathematica, 44 42 40 38 bytes

Função anônima:

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

Execute-o alinhando a entrada até o final da seguinte maneira:

In: LengthWhile[i=0;SortBy[#,-#&],#>i++&]&@{1,2,3,4,5,6,7}
Out: 4
kukac67
fonte
@ MartinBüttner Você está certo, eu posso usar #>i++. Eu testei mais alguns casos. (E obrigado por todas as sugestões!)
kukac67
4

SQL, 81 94 83

Dada uma tabela (I) de valores (V), a seguinte consulta retornará h. Testado no PostgreSQL e também funcionará no SQL Server. Editar Faça com que ele retorne 0 em vez de NULL. Melhorou com COUNT, obrigado @nutki

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

Exemplo de SQLFiddle

Essencialmente, ele numera as linhas em uma ordem decrescente dos valores. Em seguida, ele retorna o número máximo de linhas em que o número da linha é maior que igual ao valor.

MickyT
fonte
Você pode usar em COUNT(R)vez de COALESCE(MAX(R),0)uma correção mais curta para o problema NULL.
nutki
@nutki é claro ... Obrigado
MickyT
4

R, 39 35 29

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

Dado um vetor de inteiros em ie usando a lógica de uma ordem inversa, retornando o comprimento do vetor em que o número do elemento é menor que s. Obrigado a @plannapus pela boa dica.

> 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
fonte
Agradável! Você pode até encurtar a 29 pela soma diretamente o vetor lógica:s=sort(i);sum(s>=length(s):1)
plannapus
3

CJam, 23 bytes

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

Isso leva a lista como uma matriz em 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]

Teste aqui.

Você pode usar isso para executar todos os casos de teste:

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

Explicação

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

A lógica está um pouco para trás, mas salvou alguns bytes. Basicamente, o bloco passou para classificar retornos 0para candidatos válidos e 1outros. Portanto, os candidatos válidos vêm em primeiro lugar na matriz classificada. E como a classificação é estável, e começamos com uma lista de N até 1, isso retornará o maior h válido.

Martin Ender
fonte
3

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

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

Toma entrada separada por espaço no STDIN:

perl hidx.pl <<<'1 2 3 4 5 6 7'
nutki
fonte
1
sort{$b-$a}economiza mais 2
mob
3

Python (63)

Basicamente, uma porta direta da minha solução J. Obviamente, muito mais tempo, como se pode imaginar.

lambda x:sum(a>b for a,b in zip(sorted(x)[::-1],range(len(x))))
ɐɔıʇǝɥʇuʎs
fonte
Você pode salvar alguns caracteres usando enumerate.
Xnor
3

Haskell, 40

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

isso procura o primeiro número que não se enquadra no esquema e retorna seu antecessor.

orgulhoso haskeller
fonte
39 bytes com until: Experimente online!
Laikoni
3

Ruby 44 41

Estratégia recursiva, mais ou menos a mesma da solução Python do xnor:

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

Ruby 52

Não recursivo:

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

Funções lambda / anônimas "Stabby", requerem Ruby 1.9 ou mais recente. Ligue com, por exemplof[[22,33,1,2,4]]

daniero
fonte
3

Bash + coreutils, 29

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

Entrada retirada do stdin como uma lista separada por nova linha.

  • sort os números inteiros em ordem decrescente
  • nl prefixa cada linha com seu número de linha com base em 1, separando o número da linha e o restante da linha com um número maior que >
  • Avalie aritmeticamente cada linha com bc. Inteiros menores que o número da linha resultam em 0. Caso contrário, 1.
  • grepconta o número de 0s, ou seja, o número de números inteiros maior ou igual ah

Exemplo

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

JavaScript (ES6) 48

Solução recursiva.

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

Teste no console do 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)))

Saída

[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
fonte
47 bytes: f=(l,h=0)=>l.map(v=>x+=v>h,x=0)&&x>h?f(l,h+1):h. No entanto, sua solução também teria 47 bytes, se você mudar apenas h=-1para h=0.
vrugtehagel
2

Java 8, 116 bytes.

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

Função:

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;}}
O número um
fonte
2

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

Tudo bem, aqui estão alguns dos piores códigos que eu já escrevi! :)

#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;}
user9587
fonte
2

Gelatina, 6 bytes

NỤỤ<’S

Explicação:

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

CJam, 22 bytes

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

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

Saída:

20

Experimente aqui

Optimizer
fonte
1

GolfScript, 13 bytes

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

Teste este código online. 1

Recebe entrada como uma matriz na pilha. Usa o mesmo algoritmo da solução Python do feersum , iterando sobre os números na matriz e incrementando um contador de 0 até que seja igual ou exceda o elemento atual da matriz.

1) O servidor GolfScript on-line parece estar experimentando tempos limite aleatórios novamente. Se o programa atingir o tempo limite, tente executá-lo novamente.

Ilmari Karonen
fonte
1

TI-BASIC, 22 bytes

Representação ASCII:

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

Despejo hexagonal:

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

Obtém uma lista como entrada. A partir de Ans = 0, verifica se pelo menos Ans + 1 dos números são pelo menos Ans + 1. Nesse caso, incrementa Ans e volta novamente. Caso contrário, gera Ans.

Timtech
fonte
1

JAGL Alpha 1.2 - 14

Não conta porque a funcionalidade de matriz reversa 'C' foi adicionada após a pergunta, mas estou respondendo por diversão de qualquer maneira.

Assume que a matriz é o primeiro item da pilha e coloca a resposta no topo da pilha.

0SJC{Sd@>+1}/S

Para imprimir, basta adicionar P no final, adicionando um byte.

Explicação:

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

J, 15 11 caracteres

(Solução J mais curta atual.)

   [:+/#\<:\:~

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

Compara os elementos da <:lista classificada \:~com 1..n + 1 #\e conta comparações verdadeiras +/.

Teste de similaridade com outra solução J em 100 casos de teste aleatórios:

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

Reng v.3.2, 43 bytes

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

Experimente aqui!Esse código pode ser dividido em três partes: inicial, computacional e final.

Inicial

1#xk#yaïí'1ø

Isso armazena 1a x, o comprimento da pilha de entrada kpara y, e recebe todas as entradas ( aïí) que é então classificadas ( '). vai para a próxima linha, ou seja, a próxima parte.

Computacional

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

Reng não tem embutido na desigualdade. Assim, um algoritmo deve ser implementado. O algoritmo mais curto que encontrei a < bé %:1,%1e; isso é assim:

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)

Tenho certeza que esclareceu tudo! Deixe-me explicar mais. x % 1, ou seja, módulo com 1, mapeia xpara (-1,1). Sabemos que (a/b) % 1é a/bquando a < b. Assim, essa expressão é igual a a < b.

No entanto, isso não funciona tão bem devido a problemas com o módulo com zero. Portanto, incrementamos cada membro da pilha e do contador inicialmente.

Depois de colocar a desigualdade booleana na pilha, a x+adiciona a x, mas a deixa no momento. y1-diminui ye ?^sobe se y == 0continuarmos para a fase final. Caso contrário, nós colocamos y-1em yeo novo xem x.

Final

             ~n-1$\

Isso retira o resíduo y-1da pilha, diminui o resultado, gera o resultado e termina o programa.

Conor O'Brien
fonte
1

05AB1E , 5 bytes

{Rā@O

Experimente online! ou como um conjunto de testes

Explicação

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

Mathematica, 57 bytes

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

Esta é uma função anônima que pega uma lista e retorna um número inteiro, como

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

Use isso para verificar todos os casos de teste:

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

C #, 103

Função 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;}}

Recuado:

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

Scala, 62

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