Alice i Bob grają w małą grę. Najpierw rysują drzewo z węzła głównego (oznaczonego grubą kropką), bez wewnętrznych węzłów, z liczbami na liściach. Dowolny węzeł może mieć dowolną liczbę dzieci.

Zaczynamy od zera, a pierwsza gra to Alice (A). Musi wybrać jedno z dzieci bieżącego węzła. Potem jest kolej Boba i on podobnie wybiera węzeł potomny. Trwa to do momentu osiągnięcia węzła liścia.

Po osiągnięciu węzła liścia gra się kończy. Celem Alicji jest zakończenie w węźle o możliwie największej wartości, a celem Boba jest zakończenie w węźle o możliwie małej wartości.

Biorąc pod uwagę drzewo w formie zagnieżdżonej tablicy, zwróć wartość liścia, która zostanie osiągnięta, jeśli zarówno Alice, jak i Bob będą grać doskonale.

Przykłady:

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]

Możesz założyć, że węzeł główny nigdy nie jest węzłem liścia i wskazuje co najmniej jeden węzeł liścia. Możesz założyć, że liście są liczbami nieujemnymi.

Najkrótszy kod w bajtach wygrywa.

Galaretka , 7 bajtów

N߀¬¡ṂN

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Wykorzystuje algorytm z odpowiedzi @ xnor . Dla celów porównawczych prostsze podejście, które na przemian oblicza minima i maksima, waży 8 bajtów :

߀¬¡€Ṃ€Ṁ

Jak to działa

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 bajty

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

Główne pytanie brzmi: jak zmieniać na przemian maximin każda warstwa. Korzystając z faktu max(l) == -min([-x for x in l]), że zamiast tego negujemy każdą drugą warstwę i powtarzamy z -min. Zanegować każdą drugą warstwę, mijamy dół mnożnik cże zastępcy +1i -1, a gdy dojdziemy liść, dostosowujemy swoją wartość przez mnożnik. Rozumiemy, że jesteśmy na liściu poprzez warunek l<[], ponieważ Python 2 traktuje liczby jako mniej niż listy.

Trudno jest skrócić else/if trójskładnikową, ponieważ każda gałąź może dać wartość Prawda (niezerowa) lub Falsey (zero).

JavaScript (ES6), 53 bajty

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

Stosuje podobne podejście do odpowiedzi @ xnor. Jeśli liczby są niezerowe, to tylko 49 bajtów:

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

Pyth, 21 bajtów

M?sIG*GH_hSmgd_HGLgb1

Moja pierwsza odpowiedź na Pythona! Dzięki Dennis za pomoc :).

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 bajtów

-Min[#0/@-#]&

lub równoważnie

Max[-#0/@-#]&

To zwraca wartość do nienazwanej funkcji, która pobiera drzewo i zwraca wynik.

Jest to w zasadzie to samo, co rozwiązanie xnor: na każdym poziomie zamieniamy znak listy i wynik i używamy Mindo końca. W Mathematica okazało się to niesamowicie golfowe, ponieważ:

• Minmoże przyjmować pojedyncze numery lub listy, a nawet kilka list. Po prostu daje ci minimalną wartość we wszystkich swoich argumentach. Oznacza to, że działa zarówno na listach, jak i liściach (gdzie po prostu zwraca liść).
• /@co jest skrótem od Mapbardzo ogólnej funkcji wyższego rzędu w Mathematica. Nie tylko mapuje funkcję na listach, ale może mapować dowolne wyrażenie. Liczby są takim wyrażeniem, ale nie zawierają żadnych elementów do odwzorowania. Oznacza to, że możemy bezpiecznie zamapować dowolną funkcję na liczby, co wcale nie wpływa na liczbę.

Obie te rzeczy razem oznaczają, że możemy napisać kod bez żadnych warunków, ponieważ MiniMap operacje nie działają na liczbach, a następnie dwie negacje anulują się, dzięki czemu funkcja staje się tożsamością po podaniu liczby.

Wreszcie dzięki#0 Mathematica można pisać bezimienne funkcje rekurencyjne, co pozwala zaoszczędzić jeszcze kilka bajtów.

Rubinowy, 46 bajtów

Użyto sztuczki @ xnor z minnaprzemiennie między maks. I min.

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

Julia, 27 25 bajtów

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

Wykorzystuje algorytm z odpowiedzi @ xnor . Wypróbuj online!