N Kinder, von denen keine zwei ihre genaue Größe teilen, sind in einer bestimmten Reihenfolge aufgestellt. Jeder kann nur Höhen mit seinen unmittelbaren Nachbarn vergleichen. Wenn der Lehrer "Hände heben, wenn Sie der Größte sind" ruft, tun sie dies, wenn sie größer sind als beide Nachbarn, und dies gleichzeitig. Wenn nur einer die Hand hebt, gewinnt er. Wenn mehr als eine Person die Hand hebt, werden sie alle aus der Reihe entfernt (unter Beibehaltung der Ordnung der übrigen Kinder) und wiederholen den Vorgang.

Schreiben Sie ein Programm, das eine Reihe von eindeutigen Ganzzahlen verwendet (Sie können davon ausgehen, dass diese eindeutig positiv sind) und den Gewinner dieses Spiels ausgibt. Das ist Code-Golf, also gewinnt der kürzeste Code.

Beispiele (mit gezeigten Zwischenstufen):

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

Aktuelle Führungskräfte:

1. Gelee: 17 Bytes [von Dennis ♦]
2. MATL: 20 Bytes [von Luis Mendo]
3. APL: 28 Bytes [voidhawk]
4. k: 40 Bytes [von Paul Kerrigan]

Es gibt auch eine Schlacht von Pythons. Ich warte immer noch darauf, dass weitere Golfsprachen auftauchen.

Derzeit habe ich die Antwort von Dennis ♦ akzeptiert. Wenn es neue Gewinner gibt, aktualisiere ich die Auswahl.

Gelee , 17 Bytes

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

Die Eingabe ist eine durch Kommas getrennte Folge von Ganzzahlen.

Probieren Sie es online!

Die Credits gehen an @Xanderhall, @Sherlock und @ErikGolfer, um die Grundlagen zu legen.

Wie es funktioniert

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.

JavaScript (ES6), 78 76 72 Bytes

Vielen Dank an @ edc65 für -4 Bytes

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

Nimmt ein Array von ganzen Zahlen auf und gibt ein Array aus, das nur den Gewinner enthält.

Testschnipsel

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

g=a=>a?console.log("Input:",`[${a}]`,"Output:",f(a.map(Number))+""):console.error("Invalid input")

g([5,3,9,8,7])
g([1,2,9,4])
g([9,3,8,7,4,12,5])

<input id=I value="9 1 8 2 7 3 6 4 5"><button onclick="g(I.value.match(/\d+/g))">Run</button>

Hier sind einige andere Versuche mit .filterund Array-Komprimierungen:

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

Oder eine doppelte for-Schleife, furchtbar lang:

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")

Erläuterung

Die Art und Weise, wie dies funktioniert, ist ziemlich einfach: Es erstellt ein Array von relativ großen ( r) und nicht ( q) Elementen und gibt dann zurück, rwenn es nur ein Element enthält. Wenn nicht, läuft es von selbst weiter qund gibt das Ergebnis zurück.

MATL , 20 Bytes

`tTYadZSd0<~&)nq}x2M

Die Eingabe ist ein Spaltenvektor, der ;als Trennzeichen verwendet wird.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Dies ist eine direkte Implementierung des in der Challenge beschriebenen Verfahrens. Eine do... while-Schleife entfernt solange Elemente, bis nur noch eines entfernt wurde. und das ist die Ausgabe.

Die zu entfernenden Elemente werden erkannt, indem Differenzen, Signum und dann wieder Differenzen genommen werden. Diejenigen, die einen negativen Wert ergeben, sind diejenigen, die entfernt werden müssen.

`        % 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)

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

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)

Vielen Dank an @ZacharyT, @orion und @mathmandan, dass sie 5 45 viele Bytes gespart haben !

Haskell, 85 Bytes

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

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

Wie es funktioniert:

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

Eine Variante, auch 85 Bytes:

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

Binden Sie die Liste von b(so) an n und geben Sie das Element zurück, swenn x\\nes sich um eine Singleton-Liste handelt, f nandernfalls.

Mathematica, 107 108 Bytes

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

Erläuterung

Stellen Sie zuerst xund ygleich der Eingabe ein List. Die Schleife geht weiter bis Length@y==1. x~Split~Lessist die Liste von Listen aufeinanderfolgender, zunehmender Elemente, Split[x,#>#2&]ist die Liste von Listen aufeinanderfolgender, abnehmender Elemente. Wenn Sie die MaxListe aller Listen in der ersten Liste nehmen, wird die Liste der Kinder größer als das Kind rechts von Ihnen (zusammen mit dem am weitesten rechts stehenden Kind). Wenn Sie das erste Argument ( #&) aller Listen in letzterer verwenden, wird die Liste der Kinder größer als das Kind links von ihnen (zusammen mit dem am weitesten links stehenden Kind). Der Schnittpunkt dieser beiden wird die Liste der Kinder sein, die ihre Hand erhoben haben. Stellen Sie dies gleich y. x=DeleteCases[x,#|##&@@y]Entfernt xalle Elemente, die mit einem Element von ) übereinstimmen . Sobald die Schleife beendet ist, kehren Sie zurücky (#|##& entsprichtAlternativesy. Wenn die Ausgabe eine Ganzzahl sein muss (anstelle einer Liste, die eine einzelne Ganzzahl enthält), geben Sie zurück#&@@y (+4 Byte) zurück.

Vielen Dank an Martin Ender für das Speichern von 2 Bytes und das Einhalten der Regeln. Offen für Vorschläge.

Perl 6 , 111 Bytes

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

Erweitert:

{  # 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 )

}

Python 2, 100 98 Bytes

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]

Verwendet die Kurzschlussrückleitung wie in Yodles Antwort (von Zachary T)

Mathematica, 101 Bytes

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

Unbenannte rekursive Funktion, die eine Liste von Zahlen als Eingabe verwendet und eine Liste mit einer einzelnen Zahl (dem Gewinner) als Ausgabe zurückgibt.

Der Kern des Algorithmus ist Max/@Partition[#,3,1,{2,2},0] , der das Array von (dem-Maximum-von-mir-und-meinen-Nachbarn) s aus der Eingabeliste berechnet. a=Position[...-#,0]subtrahiert dann die ursprüngliche Liste und gibt zurück, wo die Nullen sind; das sind die handaufziehenden Kinder.

If[Equal@@a, #[[Last@a]], #0@Fold[Drop@##&,#,Reverse@a]]&Verzweigungen, je nachdem, ob alle Elemente von agleich sind oder nicht (in diesem Fall nur, wenn aes sich um einen Singleton handelt); Wenn ja, dann ist dieses Kind der Gewinner und wir geben seine Nummer aus. Wenn nicht, rufen wir diese Funktion in der Liste rekursiv auf, wobei alle Elemente an den Positionen aentfernt sind.

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)

PHP, 131 Bytes

$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];

Nimmt Zahlen aus Befehlszeilenargumenten. Schlägt fehl, wenn der Dateiname mit einer positiven Zahl beginnt.

Nervenzusammenbruch

// 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];

k, 40 Bytes

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

Erläuterung:
$ ist ein if-else.

Die Bedingung ist, ob 1 die Summe von B ist, die als das Minimum von zwei Listen definiert ist, die durch Prüfen erzeugt werden, ob x größer ist als die vorherigen und Nachpositionen (Pipe ist umgekehrt).

Wenn dies zutrifft, geben wir x zurück, wobei B zutrifft.
Ansonsten greifen wir ohne die wahren Positionen zurück.

Scala 129 Bytes

Golf gespielt

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

Ungolfed

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

Wenn Sie die Liste links und rechts mit 0en auffüllen, können Sie sie dann in 3er-Sets gruppieren und die Liste für diejenigen aufteilen, bei denen die Hand oben ist. Die Elemente ganz links und rechts werden außen mit 0 verglichen ist negativ!)

C ++ 14, 182 Bytes

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

Es wurde erfahren, dass der ternäre Operator mit C ++ - Objekten verwendet werden kann. Erfordert die Eingabe ein Direktzugriffs Behälter mit sein push_back, wie vector, dequeundlist .

Erzeugt zwei Behälter tund sdes gleichen Typs und fügt den lokalen höchsten zu tund den Rests . Wenn es nur ein Element gibt, das zurückgegeben wird t, rufen Sie sich ansonsten rekursiv mit aufs .

Ungolfed:

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

R 83 Bytes

Zwei verschiedene Versionen:

Dieser nimmt einen 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}}

Dieser erzeugt eine rekursiv definierte Funktion F:

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

APL (Dyalog Unicode) , 28 Byte ^SBCS

{1=≢⍸s←⍵=3⌈/∊0⍵0:s/⍵⋄∇⍵/⍨~s}

Probieren Sie es online!