Evaluate a minimax tree

Question

Alice and Bob are playing a little game. First, they draw a tree from a root node (indicated by a thick dot), with no internal nodes, with numbers at the leaves. Any node may have any number of children.

We start at the root, and first to play is Alice (A). She must select one of the current node's children. Then it's Bob's turn, and he similarly selects a child node. This continues until a leaf node is reached.

When a leaf node is reached, the game is over. It is Alice's goal to end at a node with as large of a value as possible, and Bob's goal to end at a node with as small of a value as possible.

Given a tree in nested array form, return the value of the leaf that will be reached if both Alice and Bob play perfectly.

---

Examples:

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]

You may assume that the root node never is a leaf node and points to at least one leaf node. You may assume that leafs are nonnegative numbers.

---

Shortest code in bytes wins.

Answer 1

Python 2, 53 bytes

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

The main question is how to alternate between max and min each layer. Using the fact that max(l) == -min([-x for x in l]), we instead negate every second layer and recurse with -min. To negate every second layer, we pass down a multiplier c that alternates +1 and -1, and when we reach a leaf, we adjust its value by the multiplier. We recognize being at a leaf via the condition l<[], since Python 2 treats numbers as less than lists.

It's hard to shorten the else/if ternary because either branch could give a Truthy (nonzero) or Falsey (zero) value.

Answer 2

Jelly, 7 bytes

N߀¬¡ṂN

Try it online! or verify all test cases.

This uses the algorithm from @xnor's answer. For comparison purposes, a more straightforward approach that alternately computes minima and maxima weighs 8 bytes:

߀¬¡€Ṃ€Ṁ

How it works

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.

Answer 3

JavaScript (ES6), 53 bytes

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

Uses a similar approach to @xnor's answer. If the numbers are nonzero, then only 49 bytes:

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

Answer 4

Pyth, 21 bytes

M?sIG*GH_hSmgd_HGLgb1

My first Pyth answer! Thanks to Dennis for the help :).

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)

Answer 5

Mathematica, 13 bytes

-Min[#0/@-#]&

or equivalently

Max[-#0/@-#]&

This evaluates to an unnamed function that takes the tree and returns the result.

This is also essentially the same as xnor's solution: at each level we swap the sign of the list and the result and use Min all the way down. This turned out incredibly golfy in Mathematica, because:

• Min can take either individual numbers or lists or even several lists. It just gives you the minimum value across all of its arguments. That means it works both on lists as well as leaves (where it just returns the leaf).
• /@ which is short for Map is a very general higher-order function in Mathematica. It doesn't just map a function over lists, it can map them over any expression whatsoever. Numbers are such an expression, but they don't contain any elements to be mapped over. That means we can safely map any function over numbers, which doesn't affect the number at all.

Both of those things together mean we can write the code without any conditionals, since the Min and Map operations are no-ops on numbers, and subsequently the two negations cancel out so that the function becomes the identity when given a number.

Finally, thanks to #0 it is possible to write unnamed recursive functions in Mathematica, which saves a few more bytes.

Answer 6

Ruby, 46 bytes

Used @xnor's trick with min for alternating between max and min.

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

Answer 7

Julia, 27 25 bytes

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

This uses the algorithm from @xnor's answer. Try it online!