Alice e Bob estão jogando um joguinho. Primeiro, eles desenham uma árvore a partir de um nó raiz (indicado por um ponto grosso), sem nós internos, com números nas folhas. Qualquer nó pode ter qualquer número de filhos.

Começamos pela raiz e o primeiro a tocar é Alice (A). Ela deve selecionar um dos filhos do nó atual. Então é a vez de Bob, e ele também seleciona um nó filho. Isso continua até que um nó folha seja alcançado.

Quando um nó folha é atingido, o jogo termina. O objetivo de Alice é terminar em um nó com o maior valor possível e o objetivo de Bob em terminar em um nó com o menor valor possível.

Dada uma árvore em forma de matriz aninhada, retorne o valor da folha que será atingida se Alice e Bob jogarem perfeitamente.

Exemplos:

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]

Você pode assumir que o nó raiz nunca é um nó folha e aponta para pelo menos um nó folha. Você pode assumir que as folhas são números não negativos.

O código mais curto em bytes vence.

Geléia , 7 bytes

N߀¬¡ṂN

Experimente online! ou verifique todos os casos de teste .

Isso usa o algoritmo da resposta do @ xnor . Para fins de comparação, uma abordagem mais direta que calcula alternativamente mínimos e máximos pesa 8 bytes :

߀¬¡€Ṃ€Ṁ

Como funciona

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 bytes

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

A questão principal é como alternar entre maxe mincada camada. Usando o fato de que max(l) == -min([-x for x in l]), em vez disso, negamos cada segunda camada e recorremos a -min. Para negar cada segunda camada, passamos um multiplicador cque se alterna +1e -1, quando atingimos uma folha, ajustamos seu valor pelo multiplicador. Reconhecemos estar em uma folha através da condiçãol<[] , já que o Python 2 trata os números como menos do que as listas.

É difícil encurtar o else/ifternário, porque qualquer ramo poderia dar um valor Truthy (diferente de zero) ou Falsey (zero).

JavaScript (ES6), 53 bytes

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

Usa uma abordagem semelhante à resposta do @ xnor. Se os números forem diferentes de zero, apenas 49 bytes:

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

Pitão, 21 bytes

M?sIG*GH_hSmgd_HGLgb1

Minha primeira resposta Pyth! Obrigado a Dennis pela ajuda :).

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 bytes

-Min[#0/@-#]&

ou equivalente

Max[-#0/@-#]&

Isso avalia uma função sem nome que pega a árvore e retorna o resultado.

Isso também é essencialmente o mesmo que a solução do xnor: em cada nível, trocamos o sinal da lista e o resultado e usamos Min todo o caminho. Isso resultou incrivelmente divertido no Mathematica, porque:

• Minpode pegar números ou listas individuais ou até várias listas. Apenas fornece o valor mínimo em todos os seus argumentos. Isso significa que ele funciona tanto em listas quanto em folhas (onde apenas retorna a folha).
• /@que é a abreviação de Mapé uma função de ordem superior muito geral no Mathematica. Ele não apenas mapeia uma função sobre as listas, mas também pode mapeá-las sobre qualquer expressão. Os números são uma expressão dessas, mas eles não contêm nenhum elemento a ser mapeado. Isso significa que podemos mapear com segurança qualquer função sobre números, o que não afeta o número.

Juntas, essas duas coisas significam que podemos escrever o código sem condicionais, já que o MineMap operações não são ops nos números e, subsequentemente, as duas negações são canceladas, de modo que a função se torna identidade quando recebe um número.

Finalmente, graças a#0 que é possível escrever funções recursivas não identificadas no Mathematica, o que economiza mais alguns bytes.

Ruby, 46 bytes

Utilizado o truque do @ xnor com minpara alternar entre max e min.

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

Julia, 27 25 bytes

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

Isso usa o algoritmo da resposta do @ xnor . Experimente online!