Qui est le plus grand?

32

N enfants, sans deux partageant leur taille exacte, sont alignés dans un certain ordre. Chacun ne peut comparer les hauteurs qu'avec ses voisins immédiats. Lorsque l'enseignant crie «lève la main si tu es le plus grand», il le fait s'il est plus grand que ses deux voisins, et il le fait simultanément. Si un seul lève la main, il gagne. Si plus d'un lève la main, ils sont tous éliminés du rang (en préservant l'ordre du reste des enfants) et ils répètent le processus.

Écrivez un programme, qui prend un tableau d'entiers distincts (vous pouvez supposer qu'ils sont strictement positifs) et génère le gagnant de ce jeu. C'est le code-golf, donc le code le plus court l'emporte.

Exemples (avec les étapes intermédiaires illustrées):

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


Dirigeants actuels:

  1. Gelée: 17 octets [par Dennis ♦]
  2. MATL: 20 octets [par Luis Mendo]
  3. APL: 28 octets [voidhawk]
  4. k: 40 octets [par Paul Kerrigan]

Il y a aussi une bataille de Pythons en cours. Toujours en attente de nouvelles langues de golf pour apparaître.

J'ai actuellement accepté la réponse de Dennis ♦ - s'il y a de nouveaux gagnants, je mettrai à jour la sélection.

orion
la source
2
sonne plus comme "qui pourrait être le plus grand, ou non?" - pour trouver réellement « qui est le plus grand » que vous auriez à éliminer ceux qui gardent leurs mains vers le bas
Alnitak
4
J'ai établi une similitude avec les jeux pour enfants, où une personne crie une phrase de signature après laquelle le jeu est nommé. Curieusement, le plus grand est le moins susceptible de gagner (par une énorme marge). Asymptotiquement, sur N! permutations, seulement dans 2 ^ (N-1) cas, il gagne.
orion

Réponses:

4

Gelée , 17 octets

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

L'entrée est une chaîne d'entiers séparés par des virgules.

Essayez-le en ligne!

Les crédits vont à @Xanderhall, @Sherlock et @ErikGolfer pour avoir jeté les bases.

Comment ça marche

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
la source
10

JavaScript (ES6), 78 76 72 octets

Merci à @ edc65 pour -4 octets

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

Prend un tableau d'entiers et génère un tableau contenant uniquement le gagnant.

Extrait de test

Voici quelques autres tentatives d'utilisation des .filtercomprhensions et des tableaux:

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

Ou une double boucle for, horriblement longue:

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

Explication

La façon dont cela fonctionne est assez simple: il construit un tableau de ceux qui sont relativement plus grands ( r) et un tableau de ceux qui ne le sont pas ( q), puis retourne rs'il n'a qu'un seul élément; sinon, il s'exécute qet renvoie le résultat de cela.

ETHproductions
la source
Où est l'extrait de collation?
Kritixi Lithos
@KritixiLithos Ajouté :-)
ETHproductions
"[1,2,5,8,9,12,3,4,10] Sortie: 5" Je pense que cela devrait produire 8, pas 5. D'abord, 12 et 10 sont éliminés, puis 9 et 4, puis 8 victoires .
orion
1
@orion Mon mauvais, l'extrait ne convertissait pas ses arguments en nombres avant de les envoyer dans la fonction. Cela a été corrigé.
ETHproductions
Vous pouvez enregistrer 4 octets sur votre exemple de filtre en commutant qet r. Vous évitez le &&ret l'expression de filtre se révèle également être un octet plus court.
Neil
8

MATL , 20 octets

`tTYadZSd0<~&)nq}x2M

L'entrée est un vecteur de colonne, utilisé ;comme séparateur.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Il s'agit d'une mise en œuvre directe de la procédure décrite dans le challenge. Une boucle do... whilesupprime les éléments jusqu'à ce qu'un seul ait été supprimé; et celui-là est la sortie.

Les éléments à supprimer sont détectés en reprenant les différences, le signal, puis les différences. Celles qui donnent une valeur négative sont celles à supprimer.

`        % 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
la source
4

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

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)

Merci @ZacharyT, @orion et @mathmandan d'avoir économisé 5 45 beaucoup d'octets!

Yodle
la source
2

Haskell, 85 octets

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

Exemple d'utilisation: f [9,3,8,7,4,12,5]-> 4.

Comment ça marche:

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

Une variante, également 85 octets:

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

Liez la liste de b(voir ci-dessus) à n et retournez l'élément sif x\\nest une liste singleton et f nsinon.

nimi
la source
Vous pouvez vous débarrasser de l'importation et économiser 3 octets avec f x|y@(_:z)<-x++[0]=(#)=<<(x\\)$[b|(a,b,c)<-zip3(0:y)y z,b<a||b<c].
Zgarb
@Zgarb: a \\ toujours besoin de l'importation. Btw, tailspeut également être remplacé par ...|a:b:c:_<-scanr(:)[]$0:x++[0],....
nimi
Ohh oui, je ne m'en rendais pas compte.
Zgarb du
2

Mathematica, 107 108 octets

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

Explication

Tout d'abord, réglez xet yégal à l'entrée List. La boucle continue jusqu'au Length@y==1. x~Split~Lessest la liste des listes d'éléments consécutifs croissants, Split[x,#>#2&]est la liste des listes d'éléments consécutifs décroissants. La prise Maxde toutes les listes de la première donne la liste des enfants plus grands que l'enfant à leur droite (avec l'enfant le plus à droite). La prise du premier argument ( #&) de toutes les listes de cette dernière donne la liste des enfants plus grands que l'enfant à gauche (avec l'enfant le plus à gauche). L'intersection de ces deux sera la liste des enfants qui ont levé la main. Définissez cette valeur sur y. x=DeleteCases[x,#|##&@@y]supprime de xtout élément correspondant à un élément de y( #|##&équivaut àAlternatives). Une fois la boucle terminée, revenez y. Si la sortie doit être un entier (plutôt qu'une liste contenant un seul entier), retournez #&@@y(+4 octets).

Merci à Martin Ender d'avoir sauvé 2 octets et de m'avoir fait respecter les règles. Ouvert aux suggestions.

ngenisis
la source
Je ne pense pas que cela !Lessfonctionne comme prévu, car cela n'évalue pas réellement une fonction. Vous devrez probablement utiliser Greater(ou #>#2&) là-bas. Vous pouvez utiliser x~Split~Lesspour le premier Splitbien et >pour la Lengthcondition.
Martin Ender
1
Quant à devoir évaluer Clear@yentre les appels de fonction, je crains que ce ne soit pas valide . Vous devrez soit le réinitialiser vous-même, l'étendre mieux, ou le transformer en un programme complet avec Inputet Print.
Martin Ender
1

Perl 6 , 111 octets

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

Étendu:

{  # 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
la source
1

Python 2, 100 98 octets

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]

Utilise le retour de court-circuit comme dans la réponse de Yodle (par Zachary T)

TFeld
la source
Vous pouvez retirer 3 octets supplémentaires en: utilisant +=b,au lieu de +=[b](crédit à mathmandan), en utilisant t=[0]à utiliser tpour ajouter à A, puis, puisque nous commençons maintenant avec 0 dans t, la vérification t[-2]<1est plus courte que len(t)<2, et utilisez t[1]comme résultat dans ce cas.
orion
La dernière ligne devient return t[-2]and f(l)or t[1].
orion
0

Mathematica, 101 octets

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

Fonction récursive sans nom prenant une liste de nombres en entrée et renvoyant une liste avec un seul numéro (le gagnant) en sortie.

Le cœur de l'algorithme est Max/@Partition[#,3,1,{2,2},0], qui calcule le tableau des (les-max-de-moi-et-mes-voisins) à partir de la liste d'entrée. a=Position[...-#,0]soustrait ensuite la liste d'origine et retourne où les 0 sont; ce sont les enfants qui élèvent la main.

If[Equal@@a, #[[Last@a]], #0@Fold[Drop@##&,#,Reverse@a]]&branches selon que tous les éléments de asont égaux ou non (dans ce cas, ils ne le seront que si aest un singleton); si c'est le cas, alors cet enfant est le gagnant et nous sortons son numéro; sinon, nous appelons récursivement cette fonction sur la liste avec tous les éléments aux positions asupprimés.

Greg Martin
la source
0

Python 2, 99 octets

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
la source
0

PHP, 131 octets

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

Prend des nombres à partir des arguments de ligne de commande. Échoue si le nom de fichier commence par un nombre positif.

panne

// 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
la source
0

k, 40 octets

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

Explication:
$ est un if-else.

La condition est de savoir si 1 est la somme de B, qui est définie comme le minimum de deux listes générées en vérifiant si x est supérieur aux positions antérieure et postérieure (Pipe est inversé).

Si cela est vrai, nous renvoyons x où B est vrai.
Sinon, nous récurons sans les vraies positions.

Paul Kerrigan
la source
0

Scala 129 octets

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

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

En remplissant la liste de gauche et de droite avec des 0, vous pouvez ensuite regrouper en ensembles de 3 et partitionner la liste pour ceux où la main est levée, la plupart des éléments gauche et droit se comparent à 0 à l'extérieur, donc obtenez le nombre correct (en supposant la hauteur de nobodys est négatif!)

sprague44
la source
0

C ++ 14, 182 octets

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

Appris que l'opérateur ternaire peut être utilisé avec des objets C ++. Nécessite l'entrée à un récipient d'accès aléatoire avec push_back, comme vector, dequeet list.

Crée deux conteneurs tet sdu même type et ajoute le plus haut local au tet le reste à s. S'il n'y a qu'un seul élément en tretour celui-là, sinon récursif appelez-vous avec s.

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);
}
Karl Napf
la source
0

R, 83 octets

Deux versions différentes:

Celui-ci prend un vecteur N:

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

Celui-ci crée une fonction F définie récursivement:

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