<< Poprzedni Następny >>

Wyzwanie

Teraz, kiedy Mikołaj w końcu wymyślił, jak dostać się do swojej obecnej krypty, zdaje sobie sprawę, że elfy jakoś tam się przed nim dostały i ukradły niektóre z jego prezentów! Nie wymyślili jeszcze, jak opuścić kryptę, więc Mikołaj musi spróbować złapać je wszystkie. Święty Mikołaj i elfy mają nieskończoną energię do biegania, ale niestety elfy mają większą nieskończoność energii, więc jeśli kończą biegać w pętli wszędzie, elfy uwolniły się.

Biorąc pod uwagę wykres nwęzłów i ekrawędzi z odległością między dowolnymi dwoma węzłami oraz pozycje elfów i Świętego Mikołaja, określ, ile elfów Święty Mikołaj może złapać, zanim się zmęczy.

Pościg jest turowy. W każdym cyklu elfy najpierw poruszają się jednocześnie (mogą się również przemieszczać między sobą i do tego samego węzła), a następnie Mikołaj się porusza. Jeśli Święty Mikołaj przenosi się na ten sam węzeł co elf, oznacza to, że złapał tego elfa. Każdy elf może przejść z jednego węzła do swojego sąsiada tylko w jednym kroku. To samo dotyczy Świętego Mikołaja na początku, ale dla każdego złapanego elfa Święty Mikołaj może zrobić jeszcze jeden krok. Tak więc, jeśli Święty Mikołaj złapał elfa, może przenieść się z węzła do sąsiada sąsiada. Oznacza to, że może przenieść się do węzła, a następnie wrócić. Ponieważ jednak Święty Mikołaj biega zbyt szybko w tym czasie, nie złapie żadnych elfów, które przejdą w pośrednich krokach (więc jeśli jest na A, A jest podłączony do B, B jest podłączony do C, elf jest na B, a Święty Mikołaj porusza się z A -> B -> C, elf nie został jeszcze złapany). Święty Mikołaj nie musi jednak wykonywać tak wielu kroków jednocześnie; przesuwa się do 1 + (liczba złapanych elfów) w każdej turze.

Zauważ, że wszystkie elfy muszą się poruszać w każdej turze, a jeśli elf ruszy się na węzeł Świętego Mikołaja, zostanie złapany.

Wszystkie istoty (elfy, Święty Mikołaj) będą na początku w różnych węzłach.

Specyfikacje i zasady

Twój program powinien teoretycznie działać na wprowadzanie dowolnego rozmiaru. Dane wejściowe zostaną podane w postaci wykresu, pozycji elfów i pozycji Świętego Mikołaja. Możesz wziąć wykres w dowolnym rozsądnym formacie (lista węzłów + lista krawędzi, lista krawędzi, macierz przylegania, notacja cyklu itp.) I możesz zająć pozycje w dowolnym rozsądnym formacie, który współpracuje z twoim formatem wejściowym wykresu (indeks na liście węzłów itp.). Wyjście powinno być pojedynczą dodatnią liczbą całkowitą wskazującą maksymalną liczbę elfów, którą Święty Mikołaj może złapać.

Przypadki testowe

Są one podane jako listy krawędzi i numerów węzłów dla pozycji.

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.

^{Myślę, że Święty Mikołaj nie może złapać ani elfów, ani wszystkich elfów, więc wyzwaniem może być po prostu „czy złapie elfa” podpowiedź wskazówka}

Zasady

• Obowiązują standardowe luki
• To jest golf-golf wyzwanie, więc wygrywa najkrótsza odpowiedź w bajtach
• Żadne odpowiedzi nie będą akceptowane

Wesołego golfa!

^{Uwaga: Inspirację do tej serii wyzwań czerpałem z Advent Of Code . Nie mam powiązań z tą stroną}

Możesz zobaczyć listę wszystkich wyzwań w serii, patrząc na sekcję „Połączone” pierwszego wyzwania tutaj .

Wolfram Language (Mathematica) , 129 bajtów

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]]&

Wypróbuj online!

Podobne podejście do mojej odpowiedzi na to pytanie .

Funkcja przyjmuje 3 argumenty jako dane wejściowe: listę sąsiedztwa reprezentowaną jako powiązanie ( narzędzie do generowania listy sąsiedztwa z listy krawędzi ), pozycję elfów i pozycję Świętego Mikołaja.

Należy pamiętać, że Clear[f]jest to konieczne, ponieważ przesłanie funkcji musi być wielokrotnego użytku.

Poniższy kod to niepoddany golfowi kod z częściowym wyjaśnieniem. Więcej wyjaśnień później.

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] ]
]&