Alice et Bob jouent à un petit jeu. Tout d'abord, ils dessinent un arbre à partir d'un nœud racine (indiqué par un point épais), sans nœuds internes, avec des nombres aux feuilles. Tout nœud peut avoir n'importe quel nombre d'enfants.

Nous commençons à la racine, et le premier à jouer est Alice (A). Elle doit sélectionner l'un des enfants du nœud actuel. Ensuite, c'est au tour de Bob, et il sélectionne également un nœud enfant. Cela continue jusqu'à ce qu'un nœud feuille soit atteint.

Lorsqu'un nœud feuille est atteint, la partie est terminée. C'est le but d'Alice de se terminer sur un nœud avec une valeur aussi grande que possible, et le but de Bob de se terminer sur un nœud avec une valeur aussi petite que possible.

Étant donné un arbre sous forme de tableau imbriqué, retournez la valeur de la feuille qui sera atteinte si Alice et Bob jouent parfaitement.

Exemples:

18: [[67, [[100, [[67, 47], [86], 21, 16], [[46, [14], 35, 85], [71, [18, 63, 69], 99, 22], 3]]], [[18, 32, 42, 80]], [[36, 70], [86, 53, 46, 59], [[41], 86, 35]]], 3]
60: [[[84, 35], [44, 60]], [[24, 98], [16, 21]]]
58: [[53, 77], [58, [82, 41]], 52]
59: [[93, [100, 53], 58, 79], [63, 94, 59], [9, [55, 48]], [40, 10, 32]]
56: [[20, 10, [[[89, 22, 77, 10], 55], [24, 28, 30, 63]]], [[49, 31]], 17, 56]
0: [0]

Vous pouvez supposer que le nœud racine n'est jamais un nœud feuille et pointe vers au moins un nœud feuille. Vous pouvez supposer que les feuilles sont des nombres non négatifs.

Le code le plus court en octets gagne.

Gelée , 7 octets

N߀¬¡ṂN

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

Cela utilise l'algorithme de la réponse de @ xnor . À des fins de comparaison, une approche plus simple qui calcule alternativement les minima et les maxima pèse 8 octets :

߀¬¡€Ṃ€Ṁ

Comment ça fonctionne

N߀¬¡ṂN  Main link. Argument: x (array or integer)

N        Negate. For an array, this negates all integers in it.
   ¬     Logical NOT. For an array, this applies to all integers in it.
    ¡    Apply the second link to the left once if ¬ returned an array or 1, or not
         at all if it returned 0.
 ߀      Recursively call the main link on all elements at depth 1 of -x.
         If -x == 0, € will cast 0 to range before mapping ß over it. 
         Since the range of 0 is [], mapping ß over it simply yields [].
     Ṃ   Minimum.
         For an integer, Ṃ simply returns the integer. For [], Ṃ returns 0.
      N  Negate the minimum.

Python 2, 53 octets

f=lambda l,c=1:c*l if l<[]else-min(f(x,-c)for x in l)

La principale question est de savoir comment alterner entre maxet minchaque couche. En utilisant le fait que max(l) == -min([-x for x in l]), nous annulons à la place une couche sur deux et recursons avec -min. Pour annuler chaque deuxième couche, nous transmettons un multiplicateur cqui alterne +1et -1, lorsque nous atteignons une feuille, nous ajustons sa valeur par le multiplicateur. Nous reconnaissons être à une feuille via la condition l<[], car Python 2 traite les nombres comme moins que les listes.

Il est difficile de raccourcir le else/ifternaire car l'une ou l'autre branche peut donner une valeur Truthy (non nulle) ou Falsey (zéro).

JavaScript (ES6), 53 octets

f=(a,s=1)=>a.map?s*Math.max(...a.map(b=>s*f(b,-s))):a

Utilise une approche similaire à la réponse de @ xnor. Si les nombres sont différents de zéro, alors seulement 49 octets:

f=(a,s=1)=>+a||s*Math.max(...a.map(b=>s*f(b,-s)))

Pyth, 21 octets

M?sIG*GH_hSmgd_HGLgb1

Ma première réponse Pyth! Merci à Dennis pour l'aide :).

M                      # define a binary function (G, H)
 ?sIG                  # if G (first argument) is the same with s applied
                       # (check if it's an integer, so, a leaf node)
     *GH               # in such a case, calculate G*H
        _              # negation
         hS            # take the first element of the sorted list (that's the min)
           mgd_HG      # map over G, applying ourself (g) recursively,
                       # with the current lambda's value (d)
                       # and the negation of H
                 Lgb1  # Define a unary function to call our previous
                       # one with the correct base argument (1)

Mathematica, 13 octets

-Min[#0/@-#]&

ou équivalent

Max[-#0/@-#]&

Cela se traduit par une fonction sans nom qui prend l'arborescence et renvoie le résultat.

C'est aussi essentiellement la même que la solution de xnor: à chaque niveau, nous échangeons le signe de la liste et le résultat et utilisons Mintout le long. Cela s'est avéré incroyablement golfique dans Mathematica, car:

• Minpeut prendre des numéros ou des listes individuels ou même plusieurs listes. Il vous donne juste la valeur minimale pour tous ses arguments. Cela signifie qu'il fonctionne aussi bien sur les listes que sur les feuilles (où il renvoie simplement la feuille).
• /@qui est l'abréviation de Mapest une fonction d'ordre général très générale dans Mathematica. Il ne fait pas que mapper une fonction sur des listes, il peut les mapper sur n'importe quelle expression. Les nombres sont une telle expression, mais ils ne contiennent aucun élément à mapper. Cela signifie que nous pouvons mapper en toute sécurité n'importe quelle fonction sur des nombres, ce qui n'affecte pas du tout le nombre.

Ensemble, ces deux choses signifient que nous pouvons écrire le code sans condition, car les opérations Minet Mapsont des opérations sur les nombres, et par la suite les deux négations s'annulent de sorte que la fonction devient l'identité lorsqu'elle reçoit un nombre.

Enfin, grâce à#0 il est possible d'écrire des fonctions récursives sans nom dans Mathematica, ce qui économise encore quelques octets.

Rubis, 46 octets

Utiliser l'astuce @ xnor avec minpour alterner entre max et min.

f=->n,a=1{n==[*n]?-n.map{|c|f[c,-a]}.min: a*n}

Julia, 27 25 octets

!a=0==0a?a:-minimum(!,-a)

Cela utilise l'algorithme de la réponse de @ xnor . Essayez-le en ligne!