<< Sebelumnya Berikutnya >>

Tantangan

Sekarang setelah Santa akhirnya menemukan cara untuk masuk ke brankasnya sekarang, ia menyadari bahwa entah bagaimana para elf masuk ke sana sebelum dia dan mencuri beberapa hadiahnya! Mereka belum menemukan cara untuk meninggalkan lemari besi, jadi Santa harus mencoba dan menangkap mereka semua. Sinterklas dan para elf sama-sama memiliki energi tak terbatas untuk berputar, tetapi sayangnya para elf memiliki energi tanpa batas yang lebih tinggi, jadi jika mereka akhirnya berjalan dalam loop di mana-mana, para elf itu telah bebas.

Diberi grafik nnode dane ujung dengan jalan yang ada di antara dua node, dan posisi elf dan Santa, tentukan berapa banyak elf yang bisa ditangkap Santa sebelum dia lelah.

Pengejaran berbasis giliran. Setiap siklus, pertama elf semua bergerak secara bersamaan (mereka dapat bergerak melalui satu sama lain dan ke simpul yang sama juga), dan kemudian Santa akan bergerak. Jika Santa bergerak ke simpul yang sama dengan peri, maka dia telah menangkap peri itu. Setiap peri hanya dapat bergerak dari satu simpul ke tetangganya dalam satu langkah. Hal yang sama berlaku untuk Santa pada awalnya, tetapi untuk setiap peri yang ia tangkap, Santa dapat mengambil satu langkah ekstra. Jadi, jika Santa telah menangkap elf, maka ia dapat berpindah dari satu simpul ke tetangga tetangganya. Ini berarti dia bisa pindah ke sebuah node dan kemudian kembali. Namun, karena Santa berjalan terlalu cepat selama periode waktu ini, dia tidak akan menangkap elf yang lewat di langkah perantara (jadi jika dia berada di A, A terhubung ke B, B terhubung ke C, ada elf di B, dan Santa bergerak dari A -> B -> C, peri belum ditangkap). Namun, Santa tidak harus memindahkan banyak langkah sekaligus; dia bergerak hingga 1+ (jumlah elf yang ditangkap) setiap belokan.

Perhatikan bahwa semua elf harus bergerak setiap belokan, dan jika elf pindah ke simpul Santa, mereka tertangkap.

Semua entitas (elf, Santa) akan berada pada node yang berbeda di awal.

Spesifikasi dan Aturan

Program Anda secara teoritis harus bekerja untuk input dengan ukuran berapa pun. Input akan diberikan sebagai grafik, posisi elf, dan posisi Santa. Anda dapat mengambil grafik dalam format wajar apa pun (daftar node + daftar tepi, daftar tepi, matriks kedekatan, notasi siklus, dll), dan Anda dapat mengambil posisi dalam format wajar apa pun yang berfungsi dengan format input grafik Anda (indeks dalam daftar node, dll). Output harus berupa bilangan bulat positif tunggal yang menunjukkan jumlah maksimum elf yang dapat ditangkap oleh Santa.

Uji Kasus

Ini diberikan sebagai daftar angka tepi dan simpul untuk posisi.

Input -> Output
[(0, 1), (1, 2)], [0, 2], 1 -> 2 # Easy win for Santa, the elves get themselves caught :P
[(0, 1), (1, 2), (2, 3), (3, 0)], [0, 1], 2 -> 2 # The elf opposite of Santa cannot escape but the other one can always just run away each turn, until Santa catches the first elf. Then he can easily just catch the rest.
[(0, 1), (1, 2), (2, 3), (3, 0)], [1], 0 -> 0 # Santa will never catch up
[(0, 1), (1, 2), (2, 3), (3, 0), (1, 4), (4, 5), ..., (10, 11), (11, 3)], [2, 6], 0 -> 2 # The first elf moves to either 1 or 3 and then gets caught. Then, Santa can use his 2-step move to catch up to the second elf no matter what.

^{Saya pikir Santa bisa menangkap baik tidak ada elf atau semua elf, jadi tantangan ini mungkin hanya menjadi "bisa ia menangkap peri" petunjuk petunjuk}

Aturan

• Celah Standar Berlaku
• Ini adalah tantangan kode-golf , jadi jawaban tersingkat dalam byte menang
• Tidak ada jawaban yang akan diterima

Selamat Golf!

^{Catatan: Saya mendapat inspirasi untuk seri tantangan ini dari Advent Of Code . Saya tidak memiliki afiliasi dengan situs ini}

Anda dapat melihat daftar semua tantangan dalam seri ini dengan melihat bagian 'Tertaut' dari tantangan pertama di sini .

Bahasa Wolfram (Mathematica) , 129 byte

Block[{a=#},Clear@f;s_~f~e_:=If[s==e,1,s~f~e=0;s~f~e=Min[(hMax[#~f~h&/@a@s,Boole[h==s]])/@a@e]];Tr[Max[(e#3~f~e)/@#2]^#2]]&

Cobalah online!

Pendekatan serupa dengan jawaban saya untuk pertanyaan ini .

Fungsi mengambil 3 argumen sebagai input: daftar adjacency direpresentasikan sebagai asosiasi ( alat untuk menghasilkan daftar adjacency dari daftar tepi) ), posisi elf dan posisi santa.

Catatan yang Clear[f]diperlukan, karena pengiriman fungsi harus dapat digunakan kembali.

Kode di bawah ini adalah kode yang tidak dipisahkan dengan penjelasan parsial. Penjelasan lebih lanjut nanti.

reverseBoole = # != 0 &

(* Or@@{a, b} === reverseBoole[booleOr[Boole[{a, b}]]] *)
booleOr = Max

booleAnd = Min

(* Boole@f[s, e] = Santa can catch Elf ? *)

mainfunc = Block[{adjlist = #},
  Clear[f];
  f[s_, e_] := If[ s == e, f[s, e] = 1,
    f[s, e] = Boole[False];
    f[s, e] = booleAnd[
      (e1  booleOr[
        ( s1  f[s1, e1] ) /@ adjlist[s],
        Boole[e1 == s]
      ]) /@ adjlist[e]
    ]
  ];
  If [ 0 == booleOr[ ( e  f[#3, e] ) /@ #2 ] , 0, Length[#2] ]
]&