n vertices numbered 1 to n. Its edges are listed in links, where [a, b] means vertices a and b are connected.
A beetle starts at vertex 1. Every second it crawls to a neighbouring vertex it has not visited yet, picking one uniformly at random among all such neighbours. It never goes back to a visited vertex. If there is no unvisited neighbour, the beetle stays where it is forever.
Return the probability that after exactly steps seconds the beetle is at vertex goal. Answers within 10⁻⁵ of the true value are accepted.n=5, links=[[1, 2], [1, 3], [3, 4], [3, 5]], steps=2, goal=5 → 0.25
From vertex 1 the beetle goes to 3 with probability 1/2, then from 3 to 5 with probability 1/2. That gives 1/4.
n=5, links=[[1, 2], [1, 3], [3, 4], [3, 5]], steps=7, goal=2 → 0.5
Once the beetle reaches 2 after the first second it is stuck there, with no unvisited neighbours left. The probability is 1/2.
n=3, links=[[1, 2], [2, 3]], steps=1, goal=2 → 1.0
After one second the beetle is surely at 2, so the answer is 1. With steps equal to 2 it would be 0, since it would have moved on to 3.
n=5, links=[[1, 2], [1, 3], [3, 4], [3, 5]], steps=2, goal=5
0.25
Run checks the first 3 tests in your browser. Submit checks all 67 tests on the server, hidden ones included.