Kto jest najwyższy?

32

N dzieci, z których nie ma dwóch identycznych rozmiarów, są ustawione w jednej kolejności. Każdy może porównać wysokość tylko z najbliższymi sąsiadami. Kiedy nauczyciel krzyczy „podnieś ręce, jeśli jesteś najwyższy”, robi to, jeśli są oni wyżsi niż obaj sąsiedzi, i robią to jednocześnie. Jeśli tylko ktoś podniesie rękę, wygrywa. Jeśli więcej niż jeden podniesie ręce, wszyscy zostaną wyeliminowani z rzędu (zachowując kolejność reszty dzieci) i powtórzą ten proces.

Napisz program, który pobiera tablicę różnych liczb całkowitych (możesz założyć, że są one ściśle dodatnie) i wypisuje zwycięzcę tej gry. To jest golf golfowy, więc wygrywa najkrótszy kod.

Przykłady (z pokazanymi etapami pośrednimi):

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


Obecni liderzy:

  1. Galaretka: 17 bajtów [autor Dennis ♦]
  2. MATL: 20 bajtów [autor: Luis Mendo]
  3. APL: 28 bajtów [voidhawk]
  4. k: 40 bajtów [autor: Paul Kerrigan]

Trwa także bitwa Pytonów. Wciąż czekam na pojawienie się większej liczby języków golfowych.

Obecnie zaakceptowałem odpowiedź Dennisa ♦ - jeśli są nowi zwycięzcy, zaktualizuję wybór.

orion
źródło
2
brzmi bardziej jak „kto może być najwyższy, a może nie?” - aby faktycznie znaleźć „kto jest najwyższy”, musisz wyeliminować tych, którzy trzymają ręce w dół
Alnitak
4
Zwróciłem uwagę na gry dla dzieci, w których jedna osoba krzyczy jakąś charakterystyczną frazę, od której pochodzi nazwa gry. Co zabawne, najwyższe prawdopodobieństwo wygranej jest najmniejsze (z ogromnym marginesem). Asymptotycznie z N! permutacje, tylko w 2 ^ (N-1) przypadkach wygrywa.
orion

Odpowiedzi:

4

Galaretka , 17 bajtów

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

Dane wejściowe to ciąg liczb całkowitych oddzielonych przecinkami.

Wypróbuj online!

Podziękowania dla @Xanderhall, @Sherlock i @ErikGolfer za położenie fundamentów.

Jak to działa

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
źródło
10

JavaScript (ES6), 78 76 72 bajtów

Dzięki @ edc65 za -4 bajty

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

Pobiera tablicę liczb całkowitych i wysyła tablicę zawierającą tylko zwycięzcę.

Testowy fragment kodu

Oto kilka innych prób, wykorzystujących .filteri zestawień tablicowych:

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

Lub podwójnie zapętlona, ​​strasznie długa:

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

Wyjaśnienie

Sposób, w jaki to działa, jest dość prosty: buduje tablicę tych, którzy są stosunkowo wyżsi ( r) i tablicę tych, którzy nie są ( q), a następnie zwraca, rjeśli ma tylko jeden element; jeśli nie, uruchamia się qi zwraca wynik.

ETHprodukcje
źródło
Gdzie jest fragment przekąski?
Kritixi Lithos
@KritixiLithos Dodano :-)
ETHprodukcje
„[1,2,5,8,9,9,3,3,4,10] Wyjście: 5” Myślę, że powinno to dać wynik 8, a nie 5. Najpierw wyeliminowano 12 i 10, a następnie 9 i 4, a następnie 8 wygrywa .
orion
1
@orion Mój zły, fragment nie konwertuje swoich argumentów na liczby przed wysłaniem ich do funkcji. Zostało to naprawione.
ETHprodukcje
Możesz zapisać 4 bajty na przykładzie filtra, przełączając qi r. Unikniesz tego, &&ra wyrażenie filtrujące również okazuje się krótszym bajtem.
Neil
8

MATL , 20 bajtów

`tTYadZSd0<~&)nq}x2M

Dane wejściowe to wektor kolumny za pomocą ; jako separator.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Jest to bezpośrednie wdrożenie procedury opisanej w wyzwaniu. A do...while pętla utrzymuje usuwanie elementów, dopóki tylko jeden został usunięty; i to jest wyjście.

Elementy do usunięcia są wykrywane poprzez pobranie różnic, podpisanie, a następnie różnic. Te, które dają wartość ujemną, należy usunąć.

`        % 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
źródło
4

Python3, 265 260 248 243 203 121 117 112 111 bajtów

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)

Dziękuję @ZacharyT, @orion i @mathmandan za uratowanie 5 45 dużo bajtów!

Jodła
źródło
2

Haskell, 85 bajtów

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

Przykład użycia: f [9,3,8,7,4,12,5]->4 .

Jak to działa:

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

Wariant, również 85 bajtów:

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

Powiąż listę b(patrz wyżej) z n i zwróć element, sjeśli x\\njest listą singletonów i w f nprzeciwnym razie.

nimi
źródło
Możesz pozbyć się importu i zapisać 3 bajty za pomocą f x|y@(_:z)<-x++[0]=(#)=<<(x\\)$[b|(a,b,c)<-zip3(0:y)y z,b<a||b<c].
Zgarb,
@Zgarb: \\ nadal wymaga importu. Btw, tailsmoże również zostać zastąpione ...|a:b:c:_<-scanr(:)[]$0:x++[0],....
nimi
No tak, nie zdawałem sobie z tego sprawy.
Zgarb,
2

Mathematica, 107 108 bajtów

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

Wyjaśnienie

First, set x and y equal to the input List. The loop continues until Length@y==1. x~Split~Less is the list of lists of consecutive, increasing elements, Split[x,#>#2&] is the list of lists of consecutive, decreasing elements. Taking the Max of all of the lists in the former gives the list of children taller than the child to their right (along with the right-most child). Taking the first argument (#&) of all of the lists in the latter gives the list of children taller than the child to their left (along with the left-most child). The intersection of these two will be the list of children who raised their hand. Set this equal to y. x=DeleteCases[x,#|##&@@y] removes from x any elements matching an element of y (#|##& is equivalent to Alternatives). Once the loop terminates, return y. If the output must be an integer (rather than a list containing a single integer), return #&@@y (+4 bytes).

Thanks to Martin Ender for saving 2 bytes and making me comply with the rules. Open to suggestions.

ngenisis
źródło
I don't think !Less works as you expect, since this doesn't actually evaluate to a function. You'll probably need to use Greater (or #>#2&) there. You can use x~Split~Less for the first Split though and > for the Length condition.
Martin Ender
1
As for having to evaluate Clear@y between function calls, I'm afraid that's not valid. You'll either have to reset it yourself, scope it better, or turn this into a full program with Input and Print.
Martin Ender
1

Perl 6, 111 bytes

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

Expanded:

{  # 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
źródło
1

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]

Uses the short-circuiting return as in Yodle's answer (by Zachary T)

TFeld
źródło
You can take 3 more bytes off by: using +=b, instead of +=[b] (credit to mathmandan), using t=[0] to use t to add to A, and then, since we now start with 0 in t, checking t[-2]<1 is shorter than len(t)<2, and use t[1] as the result in that case.
orion
The last line becoming return t[-2]and f(l)or t[1].
orion
0

Mathematica, 101 bytes

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

Unnamed recursive function taking a list of numbers as input, and returning a list with a single number (the winner) as output.

The core of the algorithm is Max/@Partition[#,3,1,{2,2},0], which computes the array of (the-max-of-me-and-my-neighbors)s from the input list. a=Position[...-#,0] then subtracts the original list and returns where the 0s are; these are the hand-raising children.

If[Equal@@a, #[[Last@a]], #0@Fold[Drop@##&,#,Reverse@a]]& branches depending on whether all the elements of a are equal or not (in this case, they will be only if a is a singleton); if so, then this child is the winner and we output her number; if not, then we recursively call this function on the list with all elements at positions in a removed.

Greg Martin
źródło
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
źródło
0

PHP, 131 bajtów

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

Pobiera liczby z argumentów wiersza poleceń. Nie powiedzie się, jeśli nazwa pliku zaczyna się od liczby dodatniej.

awaria

// 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];
Tytus
źródło
0

k, 40 bajtów

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

Objaśnienie:
$ jest if-else.

Warunkiem jest to, czy 1 jest sumą B, która jest zdefiniowana jako minimum dwóch list wygenerowanych przez sprawdzenie, czy x jest większy od poprzedniego i po pozycji (Rura jest odwrotna).

Jeśli to prawda, zwracamy x, gdzie B jest prawdziwe.
W przeciwnym razie powracamy bez prawdziwych pozycji.

Paul Kerrigan
źródło
0

Skala 129 bajtów

Grał w golfa

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

Bez golfa

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

Wypełniając listę lewą i prawą cyfrą 0, możesz następnie pogrupować w zestawy 3 i podzielić listę na te, w których ręka jest uniesiona, większość elementów lewej i prawej porównuje się z 0 na zewnątrz, więc uzyskaj poprawną liczbę (zakładając wysokość nobodys jest ujemny!)

sprague44
źródło
0

C ++ 14, 182 bajty

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

Nauczyłem się, że operator trójskładnikowy może być używany z obiektami C ++. Wymaga wkładu być losowy dostęp z pojemnika push_back, jak vector, dequeilist .

Tworzy dwa pojemniki ti stego samego typu i dołącza do lokalnego najwyższy ti resztęs . Jeśli w tzamian jest tylko jeden element, w przeciwnym razie wywołuje się sam zs .

Nie golfowany:

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
źródło
0

R, 83 bajty

Dwie różne wersje:

Ten przyjmuje wektor N:

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

Ten tworzy funkcję F zdefiniowaną rekurencyjnie:

F=function(N){Z=diff(sign(diff(c(0,N,0))))<0;if(sum(Z)>1)F(N[!Z])else return(N[Z])}
skan
źródło