Alice dan Bob sedang memainkan permainan kecil. Pertama, mereka menggambar pohon dari simpul akar (ditunjukkan oleh titik tebal), tanpa simpul internal, dengan angka di daun. Setiap simpul mungkin memiliki jumlah anak yang banyak.
Kami mulai di root, dan yang pertama bermain adalah Alice (A). Dia harus memilih salah satu dari anak-anak simpul saat ini. Kemudian giliran Bob, dan ia juga memilih simpul anak. Ini berlanjut sampai simpul daun tercapai.
Saat simpul daun tercapai, permainan berakhir. Adalah tujuan Alice untuk mengakhiri pada simpul dengan nilai sebesar mungkin, dan tujuan Bob mengakhiri pada simpul dengan nilai sekecil mungkin.
Diberikan pohon dalam bentuk array bersarang, kembalikan nilai daun yang akan dicapai jika Alice dan Bob bermain dengan sempurna.
Contoh:
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]
Anda dapat mengasumsikan bahwa simpul akar tidak pernah merupakan simpul daun dan menunjuk setidaknya satu simpul daun. Anda dapat berasumsi bahwa daun adalah angka yang bukan negatif.
Kode terpendek dalam byte menang.
Jawaban:
Jelly , 7 byte
Cobalah online! atau verifikasi semua kasus uji .
Ini menggunakan algoritma dari jawaban @ xnor . Untuk tujuan perbandingan, pendekatan yang lebih langsung yang menghitung minima dan maxima secara bergantian berbobot 8 byte :
Bagaimana itu bekerja
sumber
Python 2, 53 byte
Pertanyaan utamanya adalah bagaimana cara mengganti antara
max
danmin
setiap lapisan. Menggunakan fakta bahwamax(l) == -min([-x for x in l])
, kami malah meniadakan setiap lapisan kedua dan berulang dengan-min
. Untuk meniadakan setiap lapisan kedua, kami meneruskan penggandac
yang berganti+1
dan-1
, dan ketika kami mencapai daun, kami menyesuaikan nilainya dengan pengganda. Kami menyadari bahwa Anda berada di daun melalui kondisil<[]
, karena Python 2 memperlakukan angka sebagai kurang dari daftar.Sulit untuk mempersingkat
else/if
terner karena salah satu cabang bisa memberikan nilai Truthy (bukan nol) atau Falsey (nol).sumber
JavaScript (ES6), 53 byte
Menggunakan pendekatan yang mirip dengan jawaban @ xnor. Jika angkanya bukan nol, maka hanya 49 byte:
sumber
Pyth, 21 byte
Jawaban Pyth pertamaku! Terima kasih kepada Dennis untuk bantuannya :).
sumber
mgd_H
bisagR_H
. Selain itu, alih-alih mendefinisikan fungsi, Anda dapat mengambil inputQ
dan menggantinyaLgb1
dengangQ1
.Mathematica, 13 byte
atau setara
Ini mengevaluasi ke fungsi tanpa nama yang mengambil pohon dan mengembalikan hasilnya.
Ini pada dasarnya juga sama dengan solusi xnor: pada setiap level kita menukar tanda daftar dan hasilnya dan menggunakan
Min
semua jalan ke bawah. Ini ternyata sangat menarik di Mathematica, karena:Min
dapat mengambil nomor atau daftar individual atau bahkan beberapa daftar. Itu hanya memberi Anda nilai minimum di semua argumennya. Itu berarti ia berfungsi baik pada daftar maupun daun (di mana ia hanya mengembalikan daun)./@
yang merupakan kependekanMap
adalah fungsi tingkat tinggi yang sangat umum di Mathematica. Itu tidak hanya memetakan fungsi di atas daftar, itu bisa memetakannya di atas ekspresi apa pun. Angka adalah ungkapan seperti itu, tetapi angka tidak mengandung elemen apa pun untuk dipetakan. Itu berarti kita dapat memetakan fungsi apa pun dengan aman pada angka, yang sama sekali tidak memengaruhi angka.Kedua hal tersebut bersama-sama berarti kita dapat menulis kode tanpa syarat, karena operasi
Min
danMap
tidak boleh pada angka, dan kemudian dua negasi membatalkan sehingga fungsi menjadi identitas ketika diberi nomor.Akhirnya, berkat
#0
dimungkinkan untuk menulis fungsi rekursif tanpa nama di Mathematica, yang menghemat beberapa byte lagi.sumber
Ruby, 46 byte
Trik @xnor digunakan dengan
min
untuk berganti-ganti antara maks dan min.sumber
Julia,
2725 byteIni menggunakan algoritma dari jawaban @ xnor . Cobalah online!
sumber