Алиса и Боб играют в небольшую игру. Сначала они рисуют дерево из корневого узла (обозначенного жирной точкой), без внутренних узлов, с номерами на листьях. Любой узел может иметь любое количество детей.
Мы начинаем с корня, и первым играем Алиса (A). Она должна выбрать одного из детей текущего узла. Затем очередь Боба, и он аналогичным образом выбирает дочерний узел. Это продолжается до тех пор, пока не будет достигнут листовой узел.
Когда достигнут конечный узел, игра заканчивается. Цель Алисы - закончить узел как можно большим значением, а цель Боба - закончить узел как можно меньшим значением.
Если задано дерево в форме вложенного массива, верните значение листа, который будет достигнут, если Алиса и Боб будут играть идеально.
Примеры:
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]
Вы можете предположить, что корневой узел никогда не является листовым узлом и указывает хотя бы на один листовой узел. Вы можете предположить, что листья - неотрицательные числа.
Самый короткий код в байтах побеждает.
Ответы:
Желе , 7 байт
Попробуйте онлайн! или проверьте все контрольные примеры .
Это использует алгоритм из ответа @ xnor . Для сравнения, более простой подход, который поочередно вычисляет минимумы и максимумы, весит 8 байтов :
Как это устроено
источник
Python 2, 53 байта
Основной вопрос состоит в том , чтобы выбрать между
max
иmin
каждый слой. Используя тот факт, чтоmax(l) == -min([-x for x in l])
мы вместо этого отрицаем каждый второй слой и повторяем с-min
. Чтобы свести на нет каждый второй слой, мы передаем множитель,c
который чередуется,+1
и-1
, когда мы достигаем листа, мы корректируем его значение с помощью множителя. Мы понимаем, что находимся на листе через условиеl<[]
, так как Python 2 рассматривает числа как списки.Трудно сократить
else/if
троичный, потому что любая ветвь может дать значение Truthy (ненулевое) или Falsey (ноль).источник
JavaScript (ES6), 53 байта
Использует аналогичный подход к ответу @ xnor. Если числа ненулевые, то только 49 байтов:
источник
Pyth, 21 байт
Мой первый ответ Pyth! Спасибо Деннису за помощь :).
источник
mgd_H
может бытьgR_H
. Кроме того, вместо определения функции вы можете взять ввод с помощьюQ
и заменитьLgb1
наgQ1
.Mathematica, 13 байт
или эквивалентно
Это оценивает безымянную функцию, которая берет дерево и возвращает результат.
Это также по сути то же самое, что и решение xnor: на каждом уровне мы меняем знак списка и результат и используем его
Min
до конца. Это оказалось невероятно гольфом в Mathematica, потому что:Min
может принимать либо отдельные номера или списки или даже несколько списков. Это просто дает вам минимальное значение по всем своим аргументам. Это означает, что он работает как со списками, так и с листьями (где он просто возвращает лист)./@
это сокращение дляMap
очень общей функции высшего порядка в Mathematica. Он не просто отображает функцию по спискам, он может отображать их по любому выражению. Числа являются таким выражением, но они не содержат элементов для отображения. Это означает, что мы можем безопасно сопоставить любую функцию с числами, что никак не влияет на число.Обе эти вещи вместе означают , что мы можем написать код без какого - либо условного, так
Min
иMap
операции нет-OPS по номерам, а впоследствии два отрицаний отменить так , что функция становится тождественной , когда данный номер.Наконец, благодаря
#0
этому в Mathematica можно писать безымянные рекурсивные функции, что экономит еще несколько байтов.источник
Рубин, 46 байт
Использовал трюк @ xnor с
min
для чередования между макс и мин.источник
Юлия,
2725 байтЭто использует алгоритм из ответа @ xnor . Попробуйте онлайн!
источник