Setidaknya h dengan setidaknya h

42

Memasukkan

Daftar bilangan bulat tidak negatif.

Keluaran

Bilangan bulat non-negatif terbesar hsehingga setidaknya hangka dalam daftar lebih besar atau sama dengan h.

Uji Kasus

[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

Aturan

Anda dapat menulis program lengkap atau fungsi, dan fungsi anonim juga diperbolehkan. Ini adalah kode-golf, sehingga jumlah byte terkecil menang. Celah standar tidak diijinkan.

Latar Belakang

The h-index adalah gagasan yang digunakan dalam dunia akademis yang bertujuan untuk menangkap dampak dan produktivitas peneliti. Menurut Wikipedia, seorang peneliti memiliki indeks h , jika ia telah menerbitkan h artikel ilmiah, yang masing-masing telah dikutip dalam artikel lain setidaknya h kali. Dengan demikian, tantangan ini adalah tentang menghitung indeks-h dari daftar jumlah kutipan.


Memperbarui

Wow, jawaban bagus semuanya! Saya telah menerima yang terpendek, tetapi jika orang lain membuat yang lebih pendek, saya akan memperbarui pilihan saya.

Pemenang berdasarkan bahasa

Berikut adalah daftar pemenang berdasarkan bahasa yang akan saya upayakan tetap up to date. Saya telah memasukkan semua posting dengan skor tidak negatif. Harap perbaiki saya jika saya melakukan kesalahan di sini.

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

Jawaban:

7

APL 7

+/⊢≥⍋∘⍒

Dapat dicoba online di 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
sumber
11

Python, 52

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

Solusi rekursif. Jalankan ini dalam Stackless Python jika Anda khawatir tentang meluap.

Mulai dari n=0, periksa apakah setidaknya n+1angka setidaknya n+1. Jika demikian, tambah ndan mulai lagi. Jika tidak, output n.

Persyaratan dilakukan dengan menggunakan hubung singkat Python untuk Boolean. Ekspresi sum(n<x for x in s)menghitung jumlah nilai syang lebih besar daripada ndengan menambahkan indikator Boolean, yang diperlakukan sebagai 0atau 1.

Sebagai perbandingan, setara iteratif lebih lama 2 karakter. Ini membutuhkan Python 2.

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

Sayangnya, input harus disimpan untuk variabel sebelum diulangi atau Python akan mencoba membaca input berulang kali.

Tidak
sumber
11

Pyth, 13 10 byte

tf<l-QUTT1

Masukan dalam bentuk seperti [22,33,1,2,4]pada STDIN.

Coba di sini.

Bagaimana itu bekerja:

-QUTadalah semua angka dalam input ( Q) setidaknya sama besar dengan angka yang sedang diperiksa T,.

<l-QUTTbenar jika panjang daftar itu kurang dari T.

f<l-QUTT1menemukan integer pertama yang mengembalikan true untuk pemeriksaan dalam, mulai dari 1dan naik.

tf<l-QUTT1 menurunkannya dengan satu, memberikan nilai terbesar yang kondisinya salah, yaitu indeks-h.

Mulai dari 1 memastikan bahwa 0dikembalikan ketika tes selalu benar, seperti dalam kasus uji pertama.

isaacg
sumber
11

Python 2, 49

Input harus diketik dalam format yang sama dengan contoh.

i=0
for z in sorted(input())[::-1]:i+=z>i
print i
feersum
sumber
3
Algoritma yang luar biasa!
haskeller bangga
8

CJam, 15 byte

Terjemahan langsung dari solusi Perl saya.

l~{~}${W):W>},,
nutki
sumber
4
l~$W%{W):W>},,- 14 byte
Pengoptimal
@ Pengoptimal Terima kasih, saya berharap seharusnya ada cara singkat untuk membalikkan tabel. Namun saya terkejut bahwa tidak ada akses ke hitungan iterasi di peta. Lagi pula jika hanya 1 byte yang dapat Anda ambil, itu tidak buruk untuk kode CJam pertama saya.
nutki
Ada beberapa solusi 12-byte sekarang: {$W%ee::<1b}( eeditambahkan 2015-04-17) dan {$W%_,,.>1b}( .ditambahkan 2015-02-21).
Peter Taylor
6

J ( 13 12)

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

Cukup mirip dengan solusi randomra. Demonstrasi:

   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
sumber
Menggunakan #\<:alih-alih i.@#<menyimpan karakter.
algorithmshark
5

Mathematica, 44 42 40 38 byte

Fungsi anonim:

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

Jalankan dengan menempelkan input ke ujung seperti:

In: LengthWhile[i=0;SortBy[#,-#&],#>i++&]&@{1,2,3,4,5,6,7}
Out: 4
kukac67
sumber
@ MartinBüttner Anda benar, saya bisa menggunakan #>i++. Saya menguji beberapa kasus lagi. (Dan terima kasih atas semua sarannya!)
kukac67
4

SQL, 81 94 83

Diberikan tabel (I) dari nilai (V), kueri berikut akan mengembalikan h. Diuji dalam PostgreSQL dan juga akan berfungsi di SQL Server. Sunting Buatlah kembali 0 bukannya NULL. Menjadi lebih baik dengan COUNT, terima kasih @nutki

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

Contoh SQLFiddle

Pada dasarnya itu nomor baris pada jenis nilai yang menurun. Kemudian ia mengembalikan nomor baris maksimum di mana nomor baris lebih besar dari sama dengan nilai.

MickyT
sumber
Anda dapat menggunakan COUNT(R)alih-alih COALESCE(MAX(R),0)untuk perbaikan yang lebih pendek untuk masalah NULL.
nutki
@nutki tentu saja ... Terima kasih
MickyT
4

R, 39 35 29

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

Diberikan vektor bilangan bulat di i dan menggunakan logika dari jenis terbalik kemudian mengembalikan panjang vektor di mana jumlah elemen kurang dari s. Terima kasih kepada @plannapus untuk tip yang bagus.

> 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
sumber
Bagus! Anda bahkan dapat mempersingkat menjadi 29 dengan langsung menjumlahkan vektor logis:s=sort(i);sum(s>=length(s):1)
plannapus
3

CJam, 23 byte

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

Ini mengambil daftar sebagai array pada STDIN, seperti

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

Uji di sini.

Anda dapat menggunakan ini untuk menjalankan semua test case:

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

Penjelasan

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

Logikanya agak mundur, tetapi menyimpan beberapa byte. Pada dasarnya, blok diberikan untuk mengurutkan pengembalian 0untuk kandidat yang valid dan 1sebaliknya. Jadi kandidat yang valid menjadi yang utama dalam array yang diurutkan. Dan karena pengurutannya stabil, dan kita mulai dengan daftar dari N hingga 1, ini akan mengembalikan jam valid terbesar.

Martin Ender
sumber
3

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

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

Mengambil input yang dipisahkan ruang pada STDIN:

perl hidx.pl <<<'1 2 3 4 5 6 7'
nutki
sumber
1
sort{$b-$a}hemat 2 lagi
mob
3

Python (63)

Pada dasarnya port langsung dari solusi J saya. Jelas, jauh lebih lama, seperti yang mungkin dibayangkan.

lambda x:sum(a>b for a,b in zip(sorted(x)[::-1],range(len(x))))
ɐɔıʇǝɥʇu
sumber
Anda dapat menyimpan beberapa karakter dengan menggunakan enumerate.
xnor
3

Haskell, 40

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

ini mencari nomor pertama yang tidak sesuai dengan skema dan mengembalikan pendahulunya.

haskeller bangga
sumber
39 byte dengan until: Cobalah online!
Laikoni
3

Ruby 44 41

Strategi rekursif, kurang lebih sama dengan solusi Python xnor:

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

Ruby 52

Non-rekursif:

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

Fungsi lambda / anonim "Stabby", membutuhkan Ruby 1.9 atau lebih baru. Panggil dengan misf[[22,33,1,2,4]]

daniero
sumber
3

Bash + coreutils, 29

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

Masukan diambil dari stdin sebagai daftar yang dipisahkan oleh baris baru.

  • sort bilangan bulat dalam urutan menurun
  • nl awalan setiap baris dengan nomor baris berbasis 1, memisahkan nomor baris dan sisa baris dengan yang lebih besar dari >
  • Secara aritmatis mengevaluasi setiap baris dengan bc. Bilangan bulat kurang dari jumlah barisnya menghasilkan 0. Jika tidak 1.
  • grepmenghitung jumlah 0s, yaitu jumlah bilangan bulat lebih besar dari atau sama denganh

Contoh

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

JavaScript (ES6) 48

Solusi rekursif.

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

Tes di konsol 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)))

Keluaran

[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
sumber
47 byte: f=(l,h=0)=>l.map(v=>x+=v>h,x=0)&&x>h?f(l,h+1):h. Namun, solusi Anda akan menjadi 47 byte juga jika Anda hanya mengubah h=-1ke h=0.
vrugtehagel
2

Java 8, 116 byte.

Kelas penuh:

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

Fungsi:

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;}}
TheNumberOne
sumber
2

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

Baiklah inilah beberapa kode terburuk yang pernah saya tulis! :)

#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
sumber
2

Jelly, 6 byte

NỤỤ<’S

Penjelasan:

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
Yang Mulia
sumber
1

CJam, 22 byte

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

Mengambil daftar sebagai 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]

Keluaran:

20

Coba di sini

Pengoptimal
sumber
1

GolfScript, 13 byte

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

Uji kode ini secara online. 1

Mengambil input sebagai array pada stack. Menggunakan algoritma yang sama dengan solusi Python feersum , iterasi angka-angka dalam array dan menambah penghitung dari 0 sampai sama dengan atau melebihi elemen array saat ini.

1) Server GolfScript online tampaknya mengalami timeout acak lagi. Jika program Anda habis waktu, coba jalankan kembali.

Ilmari Karonen
sumber
1

TI-BASIC, 22 byte

Representasi ASCII:

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

Mendapat daftar sebagai input. Mulai dari Ans = 0, periksa apakah setidaknya Ans + 1 dari jumlah setidaknya Ans + 1. Jika demikian, tambahkan Ans dan lil lagi. Jika tidak, output Ans.

Timtech
sumber
1

JAGL Alpha 1.2 - 14

Tidak dihitung karena fungsionalitas array terbalik 'C' ditambahkan setelah pertanyaan, tetapi tetap saja menjawab untuk bersenang-senang.

Diasumsikan bahwa array adalah item pertama pada stack, dan menempatkan jawabannya di bagian atas stack.

0SJC{Sd@>+1}/S

Untuk mencetak, cukup tambahkan Pdi bagian akhir, tambahkan satu byte.

Penjelasan:

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

J, 15 11 karakter

(Solusi J terpendek saat ini.)

   [:+/#\<:\:~

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

Membandingkan elemen <:daftar yang diurutkan \:~dengan 1..n + 1 #\dan menghitung perbandingan yang sebenarnya +/.

Menguji kesamaan dengan solusi J lainnya pada 100 kasus uji acak:

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

Reng v.3.2, 43 byte

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

Coba di sini! Kode ini dapat dibagi menjadi tiga bagian: awal, komputasi, dan final.

Awal

1#xk#yaïí'1ø

Ini toko 1untuk x, panjang tumpukan masukan kuntuk y, dan mendapatkan semua input ( aïí) yang kemudian diurutkan ( '). pergi ke baris berikutnya, yaitu bagian selanjutnya.

Komputasi

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

Reng tidak memiliki bawaan untuk ketidaksetaraan. Jadi, suatu algoritma harus diimplementasikan. Algoritma terpendek yang saya temukan a < badalah %:1,%1e; ini terlihat seperti ini:

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)

Saya yakin itu sudah beres! Biarkan saya jelaskan lebih lanjut. x % 1, yaitu modulus dengan 1, memetakan xke (-1,1). Kita tahu bahwa (a/b) % 1adalah a/bketika a < b. Jadi, ungkapan ini sama dengan a < b.

Namun, ini tidak berfungsi dengan baik karena masalah dengan modulus dengan nol. Jadi, kami menambah setiap anggota tumpukan dan penghitung pada awalnya.

Setelah kita mendapatkan ketimpangan Boolean di stack, x+menambahkannya ke x, tetapi meninggalkannya di stack untuk saat ini. y1-penurunan y, dan ?^naik iff y == 0dan kami melanjutkan ke tahap akhir. Jika tidak, kita menempatkan y-1ke dalam ydan baru xke dalam x.

Terakhir

             ~n-1$\

Ini akan memunculkan sisa y-1dari tumpukan, mengurangi hasilnya, mengeluarkannya, dan mengakhiri program.

Conor O'Brien
sumber
1

05AB1E , 5 byte

{Rā@O

Cobalah online! atau sebagai Test Suite

Penjelasan

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

Mathematica, 57 byte

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

Ini adalah fungsi anonim yang mengambil daftar dan mengembalikan bilangan bulat, seperti

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

Gunakan ini untuk memeriksa semua kasus uji:

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

C #, 103

Fungsi anonim.

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

Bertakuk:

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

Scala, 62

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