Advent Challenge 2: The Present Vault Raid!

Question

<< Prev Next >>

Challenge

Now that Santa has finally figured out how to get into his present vault, he realises that somehow the elves got in there before him and stole some of his presents! They haven't figured out how to leave the vault yet though, so Santa has to try and catch them all. Santa and the elves both have infinite energy to run around but unfortunately the elves have a higher infinity of energy, so if they end up running in loops everywhere, the elves have gotten free.

Given a graph of n nodes and e edges with a walk existing between any two nodes, and the positions of the elves and Santa, determine how many elves Santa can catch before he gets tired.

The chase is turn-based. Each cycle, the elves first all move simultaneously (they can move through each other and onto the same node as well), and then Santa will move. If Santa moves onto the same node as an elf, then he has caught that elf. Each elf may only move from one node to its neighbour in one step. The same goes for Santa in the beginning, but for every elf he has caught, Santa can take one extra step. So, if Santa has caught an elf, then he can move from a node to its neighbour's neighbour. This means he could move to a node and then back. However, since Santa is running too quickly during this time period, he will not catch any elves that passes in the intermediate steps (so if he is on A, A is connected to B, B is connected to C, there is an elf on B, and Santa moves from A -> B -> C, the elf has not yet been caught). However, Santa doesn't have to move that many steps at once; he moves up to 1 + (number of elves caught) each turn.

Note that all of the elves must move each turn, and if an elf moves onto Santa's node, they get caught.

All entities (elves, Santa) will be on distinct nodes in the beginning.

Specifications and Rules

Your program should theoretically work for input of any size. The input will be given as a graph, the positions of the elves, and the position of Santa. You may take the graph in any reasonable format (list of nodes + list of edges, list of edges, adjacency matrix, cycle notation, etc), and you may take the positions in any reasonable format that works with your graph input format (index in the list of nodes, etc). The output should be a single positive integer indicating the maximum number of elves that Santa can catch.

Test Cases

These are given as lists of edges and node numbers for 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.

^{I think Santa can catch either no elves or all the elves, so this challenge might just be "can he catch an elf" hint hint}

Rules

• Standard Loopholes Apply
• This is a code-golf challenge, so the shortest answer in bytes wins
• No answers will be accepted

Happy Golfing!

^{Note: I drew inspiration for this challenge series from Advent Of Code. I have no affiliation with this site}

You can see a list of all challenges in the series by looking at the 'Linked' section of the first challenge here.

Answer 1

Wolfram Language (Mathematica), 129 bytes

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

Try it online!

Similar approach to my answer to this question.

The function takes 3 arguments as input: adjacency list represented as an association (tool to generate adjacency list from edge list), elves position and santa position.

Note that Clear[f] is necessary, because function submissions must be reusable.

The code below is ungolfed code with partial explanation. More explanation later.

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

---

Answer 2

Python3, 691 bytes

R=range
def T(g,s):
 q=[[s]]
 while q:A=q.pop(0);yield(l:={b for i in A for a,b in g if a==i});q+=[l]
def f(g,e,s):
 q,a,D,v=[(e,0,s,0)],[(e,s)],{},[]
 while q:
  E,c,S,B=q.pop(0);v+=[B]
  if c<len(E):
   if E[c]==-1:q+=[(E,c+1,s,B)];continue
   J=1
   for i in next(T(g,E[c])):
    O=[*E];J=0
    if i!=S:
     O[c]=i
     if(O,S)not in a:J=0;q+=[(O,c+1,S,B)]
    else:O[c]=-1;q+=[(O,c+1,S,B+1)]
   if J:q+=[(O,c+1,S,B)]
  else:
   t,L=T(g,S),0
   for i in R(max(sum(k==-1for k in E)+1,1)):
    for I in R(L,i+1):M=next(t)
    L=i+1
    for I in M:
     O=[*E];x=B
     for y in R(len(E)):G=O[y]==I;O[y]=[O[y],-1][G];x+=G;v+=[x]
     if(O,I)not in a:q+=[(O,0,I,x)];a+=[(O,I)]
 return max(v)

Try it online!

Also, a 808 byte solution that uses caching for faster execution: try it online