<< Précédent Suivant >>

Défi

Maintenant que le Père Noël a enfin compris comment entrer dans son coffre-fort actuel, il se rend compte que les elfes sont entrés avant lui et ont volé certains de ses cadeaux! Ils n'ont pas encore compris comment quitter le coffre-fort, donc le Père Noël doit essayer de tous les attraper. Le Père Noël et les elfes ont tous deux une énergie infinie pour courir, mais malheureusement les elfes ont une infinité d'énergie plus élevée, donc s'ils finissent par courir en boucles partout, les elfes se sont libérés.

Étant donné un graphique des nnœuds et des ebords avec une marche existant entre deux nœuds et les positions des elfes et du Père Noël, déterminez combien d'elfes le Père Noël peut attraper avant qu'il ne se fatigue.

La poursuite est au tour par tour. À chaque cycle, les elfes se déplacent d'abord simultanément (ils peuvent se déplacer entre eux et sur le même nœud également), puis le Père Noël se déplacera. Si le Père Noël se déplace sur le même nœud qu'un elfe, alors il a attrapé cet elfe. Chaque elfe ne peut se déplacer que d'un nœud à son voisin en une seule étape. Il en va de même pour le Père Noël au début, mais pour chaque elfe qu'il a attrapé, le Père Noël peut faire un pas supplémentaire. Donc, si le Père Noël a attrapé un elfe, alors il peut passer d'un nœud au voisin de son voisin. Cela signifie qu'il pourrait se déplacer vers un nœud, puis revenir. Cependant, puisque le Père Noël court trop vite pendant cette période, il n'attrapera aucun elfe qui passe dans les étapes intermédiaires (donc s'il est sur A, A est connecté à B, B est connecté à C, il y a un elfe sur B, et le Père Noël se déplace de A -> B -> C, l'elfe n'a pas encore été attrapé). Cependant, le Père Noël n'a pas à déplacer autant d'étapes à la fois; il se déplace jusqu'à 1 + (nombre d'elfes capturés) à chaque tour.

Notez que tous les elfes doivent se déplacer à chaque tour, et si un elfe se déplace sur le nœud du Père Noël, ils se font prendre.

Toutes les entités (elfes, Père Noël) seront sur des nœuds distincts au début.

Spécifications et règles

Votre programme devrait théoriquement fonctionner pour une entrée de n'importe quelle taille. L'entrée sera donnée sous forme de graphique, les positions des elfes et la position du Père Noël. Vous pouvez prendre le graphique dans n'importe quel format raisonnable (liste de nœuds + liste d'arêtes, liste d'arêtes, matrice d'adjacence, notation de cycle, etc.), et vous pouvez prendre les positions dans n'importe quel format raisonnable qui fonctionne avec votre format d'entrée de graphique (index dans la liste des nœuds, etc.). La sortie doit être un seul entier positif indiquant le nombre maximum d'elfes que le Père Noël peut attraper.

Cas de test

Ceux-ci sont donnés sous forme de listes d'arêtes et de numéros de nœuds pour les positions.

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.

^{Je pense que le Père Noël peut attraper soit pas les elfes ou tous les elfes, donc ce défi pourrait bien être « peut - il attraper un elfe » hint hint}

Règles

• Les échappatoires standard s'appliquent
• Ceci est un défi de code-golf , donc la réponse la plus courte en octets gagne
• Aucune réponse ne sera acceptée

Bon golf!

^{Remarque: je me suis inspiré de cette série de défis d' Advent Of Code . Je n'ai aucune affiliation avec ce site}

Vous pouvez voir une liste de tous les défis de la série en consultant la section 'Linked' du premier défi ici .

Wolfram Language (Mathematica) , 129 octets

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

Essayez-le en ligne!

Approche similaire à ma réponse à cette question .

La fonction prend 3 arguments en entrée: la liste de contiguïté représentée comme une association ( outil pour générer la liste de contiguïté à partir de la liste de bord ), la position des elfes et la position du père Noël.

Notez que cela Clear[f]est nécessaire, car les soumissions de fonctions doivent être réutilisables.

Le code ci-dessous est un code non golfé avec une explication partielle. Plus d'explications plus tard.

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