Siapa yang paling tinggi?

32

N anak-anak, tanpa dua berbagi ukuran persisnya, berbaris dalam urutan tertentu. Masing-masing hanya dapat membandingkan ketinggian dengan tetangga terdekat mereka. Ketika guru berteriak "angkat tangan jika kamu yang tertinggi", mereka melakukannya jika mereka lebih tinggi dari kedua tetangga mereka, dan mereka melakukannya secara bersamaan. Jika hanya satu yang mengangkat tangan, dia menang. Jika lebih dari satu mengangkat tangan, mereka semua tersingkir dari barisan (menjaga urutan anak-anak lainnya) dan mereka mengulangi prosesnya.

Tulis sebuah program, yang mengambil array bilangan bulat yang berbeda (Anda dapat mengasumsikan mereka benar-benar positif) dan menghasilkan pemenang game ini. Ini kode-golf, jadi kode terpendek menang.

Contoh (dengan tahap peralihan ditampilkan):

5 3 9 8 7 → 3 8 7 → 8

1 2 9 4 → 9

9 3 8 7 4 12 5 → 3 7 4 5 → 3 4 → 4


Pemimpin saat ini:

  1. Jelly: 17 byte [oleh Dennis ♦]
  2. MATL: 20 byte [oleh Luis Mendo]
  3. APL: 28 byte [voidhawk]
  4. k: 40 byte [oleh Paul Kerrigan]

Ada juga pertempuran Python terjadi. Masih menunggu lebih banyak bahasa golf muncul.

Saat ini saya menerima jawaban Dennis ♦ - jika ada pemenang baru, saya akan memperbarui pilihan.

orion
sumber
2
terdengar lebih seperti "siapa yang mungkin yang tertinggi, atau mungkin tidak?" - untuk benar-benar menemukan "siapa yang tertinggi" Anda harus menghilangkan orang-orang yang menjaga tangan mereka ke bawah
Alnitak
4
Saya menggambar kesamaan dengan permainan anak-anak, di mana satu orang meneriakkan beberapa frasa tanda tangan setelah permainan dinamai. Lucunya, yang tertinggi paling tidak mungkin menang (dengan selisih sangat besar). Asimtotik, dari N! permutasi, hanya dalam 2 ^ (N-1) kasus ia menang.
orion

Jawaban:

4

Jelly , 17 byte

j@N»3\=x@ḟ@ḢṖ?µ¬¿

Input adalah string integer yang dipisahkan koma.

Cobalah online!

Kredit pergi ke @Xanderhall, @Sherlock, dan @ErikGolfer untuk meletakkan dasar.

Bagaimana itu bekerja

j@N»3\=x@ḟ@ḢṖ?µ¬¿ Main link: Argument: A (integer or list of integers)

               ¬¿ While the logical NOT of A (0 for a positive integer, a non-empty
                  array for a non-empty array) is truthy:
              µ     Execute the chain of links to the left.
  N                   Negative; multiply all integers in A by -1.
j@                    Join -A, separating by A. This prepends and appends a
                      negative to A and appends more integers that will be ignored.
   »3\                Compute the maxima of all overlapping slices of length 3.
      =               Compare the maxima with the elements of A, yielding 1 or 0.
       x@             Repeat the elements of A, 1 or 0 times.
                      This ignores Booleans without a counterpart in A.
            Ṗ?        If the popped result is truthy, i.e., if it has at least two
                      elements:
         ḟ@             Filter/remove those elements from A.
                      Else:
           Ḣ            Head; extract the (only) element of the return value.
Dennis
sumber
10

JavaScript (ES6), 78 76 72 byte

Terima kasih kepada @ edc65 untuk -4 byte

f=a=>a.map((c,i)=>(p>c|c<a[i+1]?q:r).push(p=c),p=q=[],r=[])&&r[1]?f(q):r

Mengambil array bilangan bulat dan menghasilkan array yang hanya berisi pemenang.

Cuplikan tes

Berikut adalah beberapa upaya lain, menggunakan .filterdan mengatur susunan:

f=a=>(q=a.filter((c,i)=>p>(p=c)|c<a[i+1]||0*r.push(c),p=r=[]))&&r[1]?f(q):r
f=a=>(r=a.filter((c,i)=>p<(p=c)&c>~~a[i+1]||0*r.push(c),p=q=[]))[1]?f(q):r
f=a=>[for(c of(i=p=q=[],r=[],a))(p>c|c<a[++i]?q:r).push(p=c)]&&r[1]?f(q):r
f=a=>(q=[for(c of(i=p=r=[],a))if(p>(p=c)|c<a[++i]||0*r.push(c))c])&&r[1]?f(q):r

Atau double-loop, sangat panjang:

a=>eval("for(r=[,1];r[1]&&(p=i=q=[],r=[]);a=q)for(c of a)(p>c|c<a[++i]?q:r).push(p=c));r")

Penjelasan

Cara kerjanya cukup sederhana: ia membangun array dari mereka yang relatif lebih tinggi ( r) dan array yang tidak ( q), lalu kembali rjika hanya memiliki satu item; jika tidak, itu berjalan sendiri qdan mengembalikan hasil itu.

Produksi ETH
sumber
Di mana potongan camilannya?
Kritixi Lithos
@KritixiLithos Ditambahkan :-)
ETHproduksi
"[1,2,5,8,9,12,3,4,10] Output: 5" Saya pikir ini akan menghasilkan 8, bukan 5. Pertama, 12 dan 10 dihilangkan, kemudian 9 dan 4, kemudian 8 menang .
orion
1
@atau Buruknya, cuplikan tidak mengubah argumennya menjadi angka sebelum mengirimnya ke fungsi. Ini sudah diperbaiki.
ETHproduksi
Anda dapat menyimpan 4 byte pada contoh filter Anda dengan beralih qdan r. Anda menghindari &&rdan ekspresi filter ternyata menjadi byte lebih pendek juga.
Neil
8

MATL , 20 byte

`tTYadZSd0<~&)nq}x2M

Input adalah vektor kolom, menggunakan ;sebagai pemisah.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

Ini adalah implementasi langsung dari prosedur yang dijelaskan dalam tantangan. A do... whileloop terus menghapus elemen sampai hanya satu yang dihapus; dan itu adalah output.

Elemen-elemen yang akan dihapus terdeteksi dengan mengambil perbedaan, signum, lalu perbedaan lagi. Yang memberi nilai negatif adalah yang harus dihapus.

`        % Do...while
  t      %   Duplicate. Takes input (implicit) the first time
  TYa    %   Append and prepend a zero
  d      %   Consecutive differences
  ZS     %   Signum
  d      %   Consecutive differences
  0<~    %   Logical mask of non-negative values: these should be kept
  &)     %   Split array into two: those that should kept, then those removed
  nq     %   Size minus 1. This is used as loop condition. The loop will exit
         %   if this is 0, that is, if only one element was removed
}        % Finally (i.e. execute at the end of the loop)
  x      %   Delete array of remaining elements
  2M     %   Push last element that was removed
         % End (implicit)
         % Display (implicit)
Luis Mendo
sumber
4

Python3, 265 260 248 243 203 121 117 112 111 byte

def T(I):
 b=[0];q=[];J=b+I+b
 for i,x in enumerate(I):[q,b][J[i]<x>J[i+2]]+=x,
 return len(b)<3and b[1]or T(q)

Terima kasih @ ZacharyT, @orion, dan @mathmandan telah menghemat 5 45 banyak byte!

Yodle
sumber
2

Haskell, 85 byte

import Data.List
f x=(#)=<<(x\\)$[b|a:b:c:_<-tails$0:x++[0],b<a||b<c]
[s]#_=s
_#i=f i

Contoh penggunaan: f [9,3,8,7,4,12,5]-> 4.

Bagaimana itu bekerja:

f x =                            -- main function with parameter x
         [b|                  ]  -- make a list of all b
            a:b:c:_              -- where b is the second element of all lists with
                                 -- at least 3 elements
             <- tails $ 0:x++[0] -- drawn from the tails of x with a 0 pre- and
                                 -- appended (tails [1,2,3] -> [1,2,3],[2,3],[3],[])
               ,b<a||b<c         -- and b is not greater than its neighbors
   (#)=<<(x\\)                   -- feed the list difference of x and that list
                                 -- and the list itself to the function #

[s]#_s                           -- if the list difference is a singleton list,
                                 -- return the element
_#i=f i                          -- else start over with the list of b's

Varian, juga 85 byte:

import Data.List
f x|n<-[b|a:b:c:_<-tails$0:x++[0],b<a||b<c]=last$f n:[s|[s]<-[x\\n]]

Bind daftar b(lihat di atas) ke n dan mengembalikan elemen sjika x\\ndaftar tunggal dan f nsebaliknya.

nimi
sumber
Anda dapat menyingkirkan impor dan menyimpan 3 byte dengan f x|y@(_:z)<-x++[0]=(#)=<<(x\\)$[b|(a,b,c)<-zip3(0:y)y z,b<a||b<c].
Zgarb
@Zgarb: \\ masih perlu impor. Btw, tailsbisa juga diganti dengan ...|a:b:c:_<-scanr(:)[]$0:x++[0],....
nimi
Ohh benar, aku tidak menyadarinya.
Zgarb
2

Mathematica, 107 108 byte

(For[x=y=#,Length@y>1,x=DeleteCases[x,#|##&@@y],y=Intersection[Max@@@x~Split~Less,#&@@@Split[x,#>#2&]]];y)&

Penjelasan

Pertama, setel xdan ysama dengan input List. Lingkaran berlanjut sampai Length@y==1. x~Split~Lessadalah daftar daftar elemen yang berurutan dan terus bertambah, Split[x,#>#2&]adalah daftar daftar elemen yang berurutan dan menurun. Mengambil Maxdari semua daftar di yang pertama memberikan daftar anak-anak yang lebih tinggi daripada anak di sebelah kanan mereka (bersama dengan anak yang paling kanan). Mengambil argumen pertama ( #&) dari semua daftar di yang terakhir memberikan daftar anak-anak lebih tinggi daripada anak di sebelah kiri mereka (bersama dengan anak paling kiri). Persimpangan kedua ini akan menjadi daftar anak-anak yang mengangkat tangan. Tetapkan ini sama dengan y. x=DeleteCases[x,#|##&@@y]menghapus dari xelemen apa pun yang cocok dengan elemen y( #|##&setara denganAlternatives). Setelah loop berakhir, kembali y. Jika output harus berupa bilangan bulat (bukan daftar yang berisi bilangan bulat tunggal), kembalikan #&@@y(+4 byte).

Terima kasih kepada Martin Ender karena telah menghemat 2 byte dan membuat saya mematuhi aturan. Terbuka untuk saran.

ngenisis
sumber
Saya tidak berpikir !Lessberfungsi seperti yang Anda harapkan, karena ini sebenarnya tidak mengevaluasi ke fungsi. Anda mungkin perlu menggunakan Greater(atau #>#2&) di sana. Anda dapat menggunakan x~Split~Lessuntuk yang pertama Splitdan >untuk Lengthkondisi.
Martin Ender
1
Adapun harus mengevaluasi Clear@yantara panggilan fungsi, saya khawatir itu tidak valid . Anda harus mengatur ulang sendiri, lingkup lebih baik, atau mengubahnya menjadi program lengkap dengan Inputdan Print.
Martin Ender
1

Perl 6 , 111 byte

{(@_,{(($/=(0,|@$_,0).rotor(3=>-2).classify({+so .[1]>.[0,2].all})){1}>1??$/{0}!!$/{1})».[1]}...*==1)[*-1][0]}

Diperluas:

{  # bare block lambda with implicit parameter list 「@_」

  (                                    # generate a sequence
    @_,                                # starting with the input

    {   # code block used to get the next value in the sequence
        # which has implicit parameter 「$_」

        (
          (


            $/ =   # store in 「$/」 for later use

            ( 0, |@$_, 0 )             # the input with 0s before and after
            .rotor( 3 => -2 )          # take 3 at a time, back up 2, repeat
            .classify({
              +                        # Numify the following:
              so                       # simplify the following Junction
              .[1] > .[ 0, 2 ].all     # is the middle larger than its neighbors
            })



          ){1}                         # look at the values where it is true
          > 1                          # is there more than 1?

        ??                             # if so
          $/{ 0 }                      # look at the false ones instead

        !!                             # otherwise
          $/{ 1 }                      # look at the true ones

      )».[1]                           # undo the transformation from 「.rotor」
    }

    ...                                # keep doing that until

    * == 1                             # there is only one value
  )\
  [ * - 1 ]                            # the last value of the sequence
  [ 0 ]                                # make it a singular value ( not a list )

}
Brad Gilbert b2gills
sumber
1

Python 2, 100 98 byte

def f(A):
 t=[0];l=[];a=b=0
 for c in A+[0]:[l,t][a<b>c]+=[b];a,b=b,c
 return t[-2]and f(l)or t[1]

Menggunakan pengembalian hubungan arus pendek seperti pada jawaban Yodle (oleh Zachary T)

TFeld
sumber
Anda dapat mengambil 3 byte lebih banyak dengan: menggunakan +=b,alih-alih +=[b](kredit ke mathmandan), menggunakan t=[0]untuk digunakan tuntuk menambah A, dan kemudian, karena kita sekarang mulai dengan 0 in t, memeriksa t[-2]<1lebih pendek dari len(t)<2, dan menggunakan t[1]sebagai hasil dalam kasus itu.
orion
Baris terakhir menjadi return t[-2]and f(l)or t[1].
orion
0

Mathematica, 101 byte

If[Equal@@(a=Position[Max/@Partition[#,3,1,{2,2},0]-#,0]),#[[Last@a]],#0@Fold[Drop@##&,#,Reverse@a]]&

Fungsi rekursif tanpa nama mengambil daftar angka sebagai input, dan mengembalikan daftar dengan nomor tunggal (pemenang) sebagai output.

Inti dari algoritma ini adalah Max/@Partition[#,3,1,{2,2},0], yang menghitung array (the-max-of-me-and-my-neighbor) dari daftar input. a=Position[...-#,0]kemudian kurangi daftar asli dan kembalilah ke tempat 0s berada; ini adalah anak-anak yang mengangkat tangan.

If[Equal@@a, #[[Last@a]], #0@Fold[Drop@##&,#,Reverse@a]]&cabang tergantung pada apakah semua elemen asama atau tidak (dalam hal ini, mereka akan hanya jika atunggal); jika demikian, maka anak ini adalah pemenangnya dan kami menampilkan nomornya; jika tidak, maka kami secara rekursif memanggil fungsi ini pada daftar dengan semua elemen pada posisi adihapus.

Greg Martin
sumber
0

Python 2, 99 Bytes

def f(l):k=[x[0]for x in zip(l,[0]+l,l[1:]+[0])if(max(x),)>x];return(len(k)+2>len(l))*max(l)or f(k)
Lulhum
sumber
0

PHP, 131 byte

$r=$a=$argv;for(;$r[1];$a=array_values(array_diff($a,$r))){$r=[];foreach($a as$i=>$x)if($x>$a[$i-1]&$x>$a[$i+1])$r[]=$x;}echo$r[0];

Mengambil angka dari argumen baris perintah. Gagal jika nama file dimulai dengan angka positif.

kerusakan

// import (and init $r[1])
$r=$a=$argv;
// while more than 1 raised hand, remove them from data
for(;$r[1];$a=array_values(array_diff($a,$r)))
{
    // reset hands
    $r=[];
    // raise hands
    foreach($a as$i=>$x)
        if($x>$a[$i-1]&$x>$a[$i+1])$r[]=$x;
}
// output
echo$r[0];
Titus
sumber
0

k, 40 byte

{$[1=+/B:(|>':|x)&>':x;x@&B;.z.s x@&~B]}

Penjelasan:
$ adalah if-else.

Syaratnya adalah apakah 1 adalah jumlah B, yang didefinisikan sebagai minimum dari dua daftar yang dihasilkan dengan memeriksa apakah x lebih besar dari posisi sebelum dan sesudah (Pipa terbalik).

Jika ini benar, kami mengembalikan x di mana B benar.
Kalau tidak, kita akan muncul kembali tanpa posisi yang sebenarnya.

Paul Kerrigan
sumber
0

Scala 129 byte

Golf

def x(a:List[Int]):Int={val (y,n)=(0+:a:+0).sliding(3).toList.partition(l=>l.max==l(1));if(y.length>1)x(n.map(_(1)))else y(0)(1)}

Tidak disatukan

def whoIsTallest(a: List[Int]): Int = {
  val (handUp, handDown) = (0 +: a :+ 0).sliding(3).toList.partition {
    case x :: y :: z :: Nil => y > x && y > z
  }
  if (handUp.length > 1)
    whoIsTallest(handDown.map(_(1)))
  else
    handUp.head(1)
}

Dengan mengisi daftar kiri dan kanan dengan 0's, maka dapat mengelompokkan dalam set 3 dan mempartisi daftar untuk mereka yang tangannya naik, elemen kiri dan kanan paling banyak dibandingkan dengan 0 di luar sehingga mendapatkan nomor yang benar (dengan asumsi tinggi badan tidak sama negatif!)

sprague44
sumber
0

C ++ 14, 182 byte

#define P .push_back(c[i]);
int f(auto c){decltype(c)t,s;int i=0;(c[0]>c[1]?t:s)P for(;++i<c.size()-1;)(c[i-1]<c[i]&&c[i]>c[i+1]?t:s)P(c[i-1]<c[i]?t:s)P return t.size()<2?t[0]:f(s);}

Belajar bahwa operator ternary dapat digunakan dengan objek C ++. Membutuhkan input untuk menjadi wadah akses acak dengan push_back, suka vector, dequedan list.

Membuat dua kontainer tdan sdari jenis yang sama dan menambahkan lokal tertinggi tdan sisanya s. Jika hanya ada 1 elemen sebagai timbalannya, panggilan rekursif dengan dirinya sendiri s.

Tidak Disatukan:

int f(auto c){
  decltype(c)t,s;
  int i=0;
  (c[0]>c[1] ? t : s).push_back(c[i]);
  for(;++i<c.size()-1;)
    (c[i-1]<c[i]&&c[i]>c[i+1] ? t : s).push_back(c[i]);
  (c[i-1]<c[i] ? t : s).push_back(c[i]);
  return t.size()<2 ? t[0] : f(s);
}
Karl Napf
sumber
0

R, 83 byte

Dua versi berbeda:

Yang ini mengambil vektor N:

while(T){Z=diff(sign(diff(c(0,N,0))))<0;if(sum(Z)>1)N=N[!Z]else{print(N[Z]);break}}

Yang ini menciptakan fungsi F yang didefinisikan secara rekursif:

F=function(N){Z=diff(sign(diff(c(0,N,0))))<0;if(sum(Z)>1)F(N[!Z])else return(N[Z])}
skan
sumber