Evaluate a minimax tree
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.
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.