16

Alice y Bob están jugando un pequeño juego. Primero, dibujan un árbol desde un nodo raíz (indicado por un punto grueso), sin nodos internos, con números en las hojas. Cualquier nodo puede tener cualquier número de hijos.

Comenzamos en la raíz, y la primera en jugar es Alice (A). Debe seleccionar uno de los hijos del nodo actual. Luego es el turno de Bob, y de manera similar selecciona un nodo hijo. Esto continúa hasta que se alcanza un nodo hoja.

Cuando se alcanza un nodo hoja, el juego termina. El objetivo de Alice es terminar en un nodo con el mayor valor posible, y el objetivo de Bob terminar en un nodo con el menor valor posible.

Dado un árbol en forma de matriz anidada, devuelve el valor de la hoja que se alcanzará si tanto Alice como Bob juegan perfectamente.

Ejemplos:

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]

Puede suponer que el nodo raíz nunca es un nodo hoja y apunta al menos a un nodo hoja. Puede suponer que las hojas son números no negativos.

El código más corto en bytes gana.

code-golf game tree-traversal orlp
fuente

¡Reconozco esto!

Connor Bell

2

Jalea , 7 bytes

Nß€¬¡ṂN

Pruébalo en línea! o verificar todos los casos de prueba .

Esto usa el algoritmo de la respuesta de @ xnor . Para fines de comparación, un enfoque más directo que calcula alternativamente mínimos y máximos pesa 8 bytes :

ß€¬¡€Ṃ€Ṁ

Cómo 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.

Dennis
fuente

8

Python 2, 53 bytes

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

La pregunta principal es cómo alternar entre maxy mincada capa. Usando el hecho de que max(l) == -min([-x for x in l]), en cambio, negamos cada segunda capa y recurrimos con -min. Para negar cada segunda capa, pasamos un multiplicador cque alterna +1y -1, cuando alcanzamos una hoja, ajustamos su valor por el multiplicador. Reconocemos estar en una hoja a través de la condición l<[], ya que Python 2 trata los números como menos que las listas.

Es difícil acortar el else/ifternario porque cualquiera de las ramas podría dar un valor de Verdad (distinto de cero) o Falsey (cero).

xnor
fuente

1

JavaScript (ES6), 53 bytes

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

Utiliza un enfoque similar a la respuesta de @ xnor. Si los números no son cero, entonces solo 49 bytes:

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

Neil
fuente

1

Pyth, 21 bytes

M?sIG*GH_hSmgd_HGLgb1

Mi primera respuesta Pyth! Gracias a Dennis por la ayuda :).

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)

Ven
fuente

Hay una sintaxis más corta para ese mapa: mgd_Hpuede ser gR_H. Además, en lugar de definir una función, puede ingresar Qy reemplazar Lgb1con gQ1.

lirtosiast el

1

Mathematica, 13 bytes

-Min[#0/@-#]&

o equivalente

Max[-#0/@-#]&

Esto se evalúa como una función sin nombre que toma el árbol y devuelve el resultado.

Esto también es esencialmente lo mismo que la solución de xnor: en cada nivel intercambiamos el signo de la lista y el resultado y usamos Mintodo el camino hacia abajo. Esto resultó increíblemente deportivo en Mathematica, porque:

Minpuede tomar números individuales o listas o incluso varias listas. Simplemente le da el valor mínimo en todos sus argumentos. Eso significa que funciona tanto en listas como en hojas (donde solo devuelve la hoja).
/@que es la abreviatura de Mapes una función de orden superior muy general en Mathematica. No solo mapea una función sobre listas, puede mapearlas sobre cualquier expresión. Los números son una expresión de este tipo, pero no contienen ningún elemento para mapear. Eso significa que podemos asignar de forma segura cualquier función sobre los números, lo que no afecta el número en absoluto.

Ambas cosas juntas significan que podemos escribir el código sin condicionales, ya que las operaciones Miny Mapno son operacionales en los números, y posteriormente las dos negaciones se cancelan para que la función se convierta en la identidad cuando se le da un número.

Finalmente, gracias a#0 esto es posible escribir funciones recursivas sin nombre en Mathematica, lo que ahorra algunos bytes más.

Martin Ender
fuente

0

Ruby, 46 bytes

Se utilizó el truco de @ xnor minpara alternar entre max y min.

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

Tinta de valor
fuente

0

Julia, 27 25 bytes

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

Esto usa el algoritmo de la respuesta de @ xnor . Pruébalo en línea!